Boost logo

Boost :

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-18 02:55:00


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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk