[Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
Hi all, First of all, I new to the mailing list, so please excuse me for any beginner's mistakes I may make :) I am also new to the Boost Graph Library. I am having some trouble implementing the Boost Graph Library isomorphism algorithm under MSVC++ 2008 Express Edition. Since I am using MSVC++, I cannot use the named parameter method, as specified in the docs. I am not entirely sure, but I think my problem is the vertex invariants that I pass to the algorithm. I am using Boost 1.43. My graph and relevant typedefs look like this: typedef adjacency_list<listS, listS, undirectedS, VertexProperty, EdgeProperty, no_property, listS> UndirectedGraph; typedef graph_traits<UndirectedGraph>::vertex_descriptor VertexDescriptor; I am using bundled properties: struct VertexProperty { string id; int index; }; struct EdgeProperty { string id; int weight; }; Here's my code that tries to call the isomorphism algorithm: bool BoostGraph::Compare(BoostGraph& comparableGraph) { vector<VertexDescriptor> f(GetNoVertices()); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap1 = get(&VertexProperty::index, uGraph); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap2 = get(&VertexProperty::index, comparableGraph.GetGraph()); return isomorphism(uGraph, comparableGraph.GetGraph(), isomorphism_map(make_iterator_property_map(f.begin(), indexMap1, f[0])), ???, ???, vertex_invariant2.max(), indexMap1, indexMap2); } The two '???' are where I need to pass the vertex degree invariants, but I do not know how to construct them. I hope I have supplied sufficient information for you. Thanks in advance!
On Thu, 30 Dec 2010, Alexander Bock wrote:
Hi all,
First of all, I new to the mailing list, so please excuse me for any beginner's mistakes I may make :) I am also new to the Boost Graph Library.
I am having some trouble implementing the Boost Graph Library isomorphism algorithm under MSVC++ 2008 Express Edition. Since I am using MSVC++, I cannot use the named parameter method, as specified in the docs. I am not entirely sure, but I think my problem is the vertex invariants that I pass to the algorithm. I am using Boost 1.43.
Please try the named parameter version -- the comment about VC++ is probably about version 6, and you are using a much newer (and more compliant) version. Otherwise, the actual default used in the implementation appears to be difficult to construct. You might be able to pass "boost::constant_property_map<VertexDescriptor, int>(0)" as both of the invariant arguments (and 1 as vertex_max_invariant), but I'm not sure and haven't tried it. -- Jeremiah Willcock
Thank you for your suggestion, that should make it a whole lot simpler. When I try to compile the following though, I get an error stating that Boost cannot find a certain property. I am not sure which property it is, but I think it might be something to do with the fact that I'm using bundled properties. I see the vertex_index_t property, but I since I am using bundled properties (with my own index property), maybe I need to tell Boost to use that instead, like I do in the index property maps? vector<VertexDescriptor> f(GetNoVertices()); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap1 = get(&VertexProperty::index, uGraph); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap2 = get(&VertexProperty::index, comaparableGraph.GetGraph()); isomorphism(uGraph, comparableGraph.GetGraph(), isomorphism_map(make_iterator_property_map(f.begin(), indexMap1, f[0]))); Here's the error messages I get (1 error, 13 warnings): 1>Compiling... 1>BoostGraph.cpp 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(34) : warning C4018: '<' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(294) : warning C4018: '<' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(359) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(426) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(472) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(473) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(511) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(512) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(547) : warning C4018: '>' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(565) : warning C4101: 'foundpos' : unreferenced local variable 1>c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\property_map\property_map.hpp(444) : error C2664: 'boost::detail::error_property_not_found::error_property_not_found(const boost::detail::error_property_not_found &)' : cannot convert parameter 1 from 'size_t' to 'const boost::detail::error_property_not_found &' 1> Reason: cannot convert from 'size_t' to 'const boost::detail::error_property_not_found' 1> No constructor could take the source type, or constructor overload resolution was ambiguous 1> c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\property_map\property_map.hpp(440) : while compiling class template member function 'boost::safe_iterator_property_map<RandomAccessIterator,IndexMap,T,R>::safe_iterator_property_map(RandomAccessIterator,size_t,const IndexMap &)' 1> with 1> [ 1> RandomAccessIterator=std::_Vector_iterator<VertexDescriptor ,std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::listS,boost::listS,boost::undirectedS,boost::property<boost::vertex_bundle_t,VertexProperty>,boost::property<boost::edge_bundle_t,EdgeProperty>,boost::no_property,boost::listS>::config::vertex_ptr >>, 1> IndexMap=boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,const boost::detail::error_property_not_found &,boost::vertex_index_t>, 1> T=vertex2_t, 1> R=vertex2_t & 1> ] 1> c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\graph\isomorphism.hpp(412) : see reference to class template instantiation 'boost::safe_iterator_property_map<RandomAccessIterator,IndexMap,T,R>' being compiled 1> with 1> [ 1> RandomAccessIterator=std::_Vector_iterator<VertexDescriptor ,std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::listS,boost::listS,boost::undirectedS,boost::property<boost::vertex_bundle_t,VertexProperty>,boost::property<boost::edge_bundle_t,EdgeProperty>,boost::no_property,boost::listS>::config::vertex_ptr >>, 1> IndexMap=boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,const boost::detail::error_property_not_found &,boost::vertex_index_t>, 1> T=vertex2_t, 1> R=vertex2_t & 1> ] 1> c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\boostgraph.cpp(328) : see reference to function template instantiation 'bool boost::isomorphism<UndirectedGraph,UndirectedGraph,boost::iterator_property_map<RandomAccessIterator,IndexMap,T,R>,boost::vertex_isomorphism_t,boost::no_property>(const Graph1 &,const Graph2 &,const boost::bgl_named_params<boost::iterator_property_map<RandomAccessIterator,IndexMap,T,R>,Tag,Base> &)' being compiled 1> with 1> [ 1> RandomAccessIterator=std::_Vector_iterator<VertexDescriptor ,std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::listS,boost::listS,boost::undirectedS,boost::property<boost::vertex_bundle_t,VertexProperty>,boost::property<boost::edge_bundle_t,EdgeProperty>,boost::no_property,boost::listS>::config::vertex_ptr >>, 1> IndexMap=boost::bundle_property_map<UndirectedGraph,void *,VertexProperty,int>, 1> T=void *, 1> R=void *&, 1> Graph1=UndirectedGraph, 1> Graph2=UndirectedGraph, 1> Tag=boost::vertex_isomorphism_t, 1> Base=boost::no_property 1> ] 1>CommandParser.cpp 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\commandparser.cpp(53) : warning C4018: '<' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\commandparser.cpp(81) : warning C4018: '<' : signed/unsigned mismatch 1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\rna program\rna program\commandparser.cpp(264) : warning C4018: '<' : signed/unsigned mismatch 1>Generating Code...
Date: Fri, 31 Dec 2010 13:00:25 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Thu, 30 Dec 2010, Alexander Bock wrote:
Hi all,
First of all, I new to the mailing list, so please excuse me for any beginner's mistakes I may make :) I am also new to the Boost Graph Library.
I am having some trouble implementing the Boost Graph Library isomorphism algorithm under MSVC++ 2008 Express Edition. Since I am using MSVC++, I cannot use the named parameter method, as specified in the docs. I am not entirely sure, but I think my problem is the vertex invariants that I pass to the algorithm. I am using Boost 1.43.
Please try the named parameter version -- the comment about VC++ is probably about version 6, and you are using a much newer (and more compliant) version. Otherwise, the actual default used in the implementation appears to be difficult to construct. You might be able to pass "boost::constant_property_map<VertexDescriptor, int>(0)" as both of the invariant arguments (and 1 as vertex_max_invariant), but I'm not sure and haven't tried it.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Mon, 3 Jan 2011, Alexander Bock wrote:
Thank you for your suggestion, that should make it a whole lot simpler. When I try to compile the following though, I get an error stating that Boost cannot find a certain property. I am not sure which property it is, but I think it might be something to do with the fact that I'm using bundled properties. I see the vertex_index_t property, but I since I am using bundled properties (with my own index property), maybe I need to tell Boost to use that instead, like I do in the index property maps?
Yes, you would need to specify your own index map as a separate argument to the algorithm in the case you are describing. It looks like the error message is saying that as well, so please try it and see if you still get errors. Once you have done that, any temporary property maps that are built based on the vertex_index map should also use yours. -- Jeremiah Willcock
Isn't that what I'm already doing by passing the following two to the algorithm?: property_map<UndirectedGraph, int VertexProperty::*>::type indexMap1 = get(&VertexProperty::index, uGraph); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap2 = get(&VertexProperty::index, comaparableGraph.GetGraph()); Or maybe I am misunderstanding what you are saying?
Date: Mon, 3 Jan 2011 10:41:35 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Mon, 3 Jan 2011, Alexander Bock wrote:
Thank you for your suggestion, that should make it a whole lot simpler. When I try to compile the following though, I get an error stating that Boost cannot find a certain property. I am not sure which property it is, but I think it might be something to do with the fact that I'm using bundled properties. I see the vertex_index_t property, but I since I am using bundled properties (with my own index property), maybe I need to tell Boost to use that instead, like I do in the index property maps?
Yes, you would need to specify your own index map as a separate argument to the algorithm in the case you are describing. It looks like the error message is saying that as well, so please try it and see if you still get errors. Once you have done that, any temporary property maps that are built based on the vertex_index map should also use yours.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Mon, 3 Jan 2011, Alexander Bock wrote:
Isn't that what I'm already doing by passing the following two to the algorithm?:
property_map<UndirectedGraph, int VertexProperty::*>::type indexMap1 = get(&VertexProperty::index, uGraph); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap2 = get(&VertexProperty::index, comaparableGraph.GetGraph());
Or maybe I am misunderstanding what you are saying?
In named-parameter mode, you are omitting the vertex_invariant* arguments, and so you need to provide vertex_index1_map and vertex_index2_map arguments (using the index maps you show here). -- Jeremiah Willcock
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though. Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong. Here's the full error message: Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0) The error occurs on line 163 in the STL vector header.
Date: Wed, 5 Jan 2011 13:39:12 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Mon, 3 Jan 2011, Alexander Bock wrote:
Isn't that what I'm already doing by passing the following two to the algorithm?:
property_map<UndirectedGraph, int VertexProperty::*>::type indexMap1 = get(&VertexProperty::index, uGraph); property_map<UndirectedGraph, int VertexProperty::*>::type indexMap2 = get(&VertexProperty::index, comaparableGraph.GetGraph());
Or maybe I am misunderstanding what you are saying?
In named-parameter mode, you are omitting the vertex_invariant* arguments, and so you need to provide vertex_index1_map and vertex_index2_map arguments (using the index maps you show here).
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, 9 Jan 2011, Alexander Bock wrote:
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though.
Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong.
Here's the full error message:
Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0)
The error occurs on line 163 in the STL vector header.
Do you have a simple, complete example that I could try? Does your STL implementation have a debugging mode that turns on bounds checking, or do you have a tool similar to Valgrind? -- Jeremiah Willcock
The attached project should compile, and crash at the same location. Note that it was compiled in MSVC++ 2008 Express Edition with Boost 1.43 It looks like my STL implementation uses _SCL_SECURE_VALIDATE_RANGE(*range checking goes here*) to check bounds. I do not have Valgrind or a tool similar to it. I just used the debugging mode in MSVC++. The BoostGraph::Compare(BoostGraph& comparableGraph) implements the isomorphism algorithm. I'm using Boost for a bioinformatics project. The ViennaFile::dotBracket strings are identical and thus generate the same graph.
Date: Mon, 10 Jan 2011 10:44:21 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Sun, 9 Jan 2011, Alexander Bock wrote:
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though.
Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong.
Here's the full error message:
Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0)
The error occurs on line 163 in the STL vector header.
Do you have a simple, complete example that I could try? Does your STL implementation have a debugging mode that turns on bounds checking, or do you have a tool similar to Valgrind?
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Sorry for the repeated mails I am sending you. The file size was to big and got rejected by the mailing list. This attachment should go through however.
Date: Mon, 10 Jan 2011 10:44:21 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Sun, 9 Jan 2011, Alexander Bock wrote:
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though.
Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong.
Here's the full error message:
Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0)
The error occurs on line 163 in the STL vector header.
Do you have a simple, complete example that I could try? Does your STL implementation have a debugging mode that turns on bounds checking, or do you have a tool similar to Valgrind?
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, 16 Jan 2011, Alexander Bock wrote:
Date: Mon, 10 Jan 2011 10:44:21 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Sun, 9 Jan 2011, Alexander Bock wrote:
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though.
Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong.
Here's the full error message:
Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0)
The error occurs on line 163 in the STL vector header.
Do you have a simple, complete example that I could try? Does your STL implementation have a debugging mode that turns on bounds checking, or do you have a tool similar to Valgrind?
Are you initializing the index bundled property in your graphs? You are passing it in as the vertex_invariant* arguments to isomorphism(), and that algorithm requires that the invariant maps both be initialized. Valgrind reports a use of an uninitialized value, which is likely from one of the invariant maps. Also, what are you passing in as max_invariant? It appears that you are leaving it as the default, which appears to only work if your invariant is the vertex degree. -- Jeremiah Willcock
No, it seems I have overlooked that sadly, even though I know they are not initialized automatically. I threw together a somewhat unelegant function to initialize the bundled properties: void BoostGraph::InitializeBundledProperties() { VertexIterator vertexIter; VertexIterator vertexIterEnd; int count = 0; for(tie(vertexIter, vertexIterEnd) = vertices(uGraph); vertexIter != vertexIterEnd; ++vertexIter) { uGraph[(*vertexIter)].index = count; ++count; } } Calling this after I have finished loading the graphs with BoostGraph::LoadVienna(...) seems to do the trick. The test files I created return the correct results (Isomorphic for identical graphs, not isomorphic for graphs with different layouts). The default max_invariant works too. I hope you can confirm this as well. Put the call to BoostGraph::InitializeBundledProperties() inside BoostGraph::LoadVienna(...) just before the member function returns true. Then change the dotBracket strings of the two vienna files to either identical or different and you should see what I see.
Date: Mon, 17 Jan 2011 14:12:49 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Sun, 16 Jan 2011, Alexander Bock wrote:
Date: Mon, 10 Jan 2011 10:44:21 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Sun, 9 Jan 2011, Alexander Bock wrote:
Ok. I don't see the appropriate function in the header. I see one that looks like one on line 387 in isomorphism.hpp though.
Through trial and error, I managed to get the code to compile by changing the container for vertices from listS to vecS. I ran some tests and sometimes it works, but on strange occasions the program crashes with what looks like an index out of range message...I tracked down the crash to line 205 of isomorphism.hpp in the function bool match(edge_iter iter, int dfs_num_k). I have no idea if this is an actual bug (I doubt it though) or what I'm doing wrong.
Here's the full error message:
Expression: ("_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast && _Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst", 0)
The error occurs on line 163 in the STL vector header.
Do you have a simple, complete example that I could try? Does your STL implementation have a debugging mode that turns on bounds checking, or do you have a tool similar to Valgrind?
Are you initializing the index bundled property in your graphs? You are passing it in as the vertex_invariant* arguments to isomorphism(), and that algorithm requires that the invariant maps both be initialized. Valgrind reports a use of an uninitialized value, which is likely from one of the invariant maps. Also, what are you passing in as max_invariant? It appears that you are leaving it as the default, which appears to only work if your invariant is the vertex degree.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Mon, 17 Jan 2011, Alexander Bock wrote:
No, it seems I have overlooked that sadly, even though I know they are not initialized automatically. I threw together a somewhat unelegant function to initialize the bundled properties:
void BoostGraph::InitializeBundledProperties() { VertexIterator vertexIter; VertexIterator vertexIterEnd; int count = 0;
for(tie(vertexIter, vertexIterEnd) = vertices(uGraph); vertexIter != vertexIterEnd; ++vertexIter) { uGraph[(*vertexIter)].index = count; ++count; } }
Calling this after I have finished loading the graphs with BoostGraph::LoadVienna(...) seems to do the trick. The test files I created return the correct results (Isomorphic for identical graphs, not isomorphic for graphs with different layouts). The default max_invariant works too.
Will this work if the graphs have isomorphic vertices in a different order? Why not just leave off the invariant maps altogether and let BGL create them for you? -- Jeremiah Willcock
Passing two vienna files whose dotBracket looks like these: viennaFile1.dotBracket = ".(.(..)).." viennaFile2.dotBracket = "..((..).)." (the inverse of viennaFile1) These two yield the same graph (I checked manually), but with different id's attached to them. The algorithm returns true. Calling the algorithm without the invariants seems to work as well: isomorphism(uGraph, comparableGraph.GetGraph()); I also commented out the call to InitializeBundledProperties() and it does not affect the algorithm, so I guess everything works now?
Date: Mon, 17 Jan 2011 16:39:41 -0500 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
On Mon, 17 Jan 2011, Alexander Bock wrote:
No, it seems I have overlooked that sadly, even though I know they are not initialized automatically. I threw together a somewhat unelegant function to initialize the bundled properties:
void BoostGraph::InitializeBundledProperties() { VertexIterator vertexIter; VertexIterator vertexIterEnd; int count = 0;
for(tie(vertexIter, vertexIterEnd) = vertices(uGraph); vertexIter != vertexIterEnd; ++vertexIter) { uGraph[(*vertexIter)].index = count; ++count; } }
Calling this after I have finished loading the graphs with BoostGraph::LoadVienna(...) seems to do the trick. The test files I created return the correct results (Isomorphic for identical graphs, not isomorphic for graphs with different layouts). The default max_invariant works too.
Will this work if the graphs have isomorphic vertices in a different order? Why not just leave off the invariant maps altogether and let BGL create them for you?
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (2)
-
Alexander Bock -
Jeremiah Willcock