Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm

Subject: Re: [boost] [Boost Graph Library] Having trouble constructing necessary parameters for the isomorphism algorithm
From: Alexander Bock (sky_ax_at_[hidden])
Date: 2011-01-17 16:26:51

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_at_[hidden]
> To: boost_at_[hidden]
> 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_at_[hidden]
> >> To: boost_at_[hidden]
> >> 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