[Boost-Users] Re: [BGL] Permutation of a graph

From: Paolo Fosser (pfosser_at_[hidden])
Date: 2002-12-13 05:43:10

Chris Russell wrote:

> "Paolo Fosser" <pfosser_at_[hidden]> wrote in message
> news:3DEDBD05.46E3F692_at_dsi.unive.it...
> > Hi all,
> >    I'm using BGL in some graph matching algorithms. Now I have to
> > shuffle a bit one of the graphs I'm comparing. I think it all ends up in
> > considering the nodes in a different order when cycling on them. (BTW am
> > I right?). So my question: is there an elegant way to do this in BGL?
> > The only solution that comes into my mind is to build up a map from the
> > range of vertex descriptors to a permutation of them.
> >

> 
> Paolo, would you please provide a little more information.
> 
> For starters, are you comparing graphs to determine differences in topology,
> attached edge/vertex properties, or both? Can we assume both BGL graphs are
> based on adjacency_list and store their edges/vertices in the same type of
> STL containers? Also, can we assume identical property map semantics?
> 

Hi Chris,
   thank you for your interest. My problem isn't related to the fact I
use BGL _also_ for implementing some (one) of the algorithms I have.
It's more related to the generation of the data I feed the algorithms
with. However, as you asked, here's brief summary of how the algorithms
work. The first uses nodes attributes to seed the initial match and than
it does comparisons of subunits (neighbourhoods) based above all on
topological informations. For technicians, it is founded on Bayes'
theory and it's the one implemented using BGL. The second is a nonlinear
optimization algorithm which basically relaxes an assignment problem.
The last employs a pivoting technique. Only the first one makes use of
attributes.

Forgive me if I was not clear in my first msg. As I mentioned graph
matching, maybe my problem appeared more complicated than it really is.
Don't bother with what use I make of the graphs. I simply need to
permute one. This can affect some algorithms because their success could
heavily rely on the order with which they take nodes into consideration.
Consider the following example.
If you apply permutation 1->3, 2->4, 3->1, 4->2 to

1-4         1-4
|\  you get  \|
2-3         2-3

Clearly they're isomorphic, but think of it in a larger scale. If an
algorithm considers vertices in the order suggested by the indeces, it
could come to different conclusions in the two cases.

Best,
Paolo

P.S. Sorry if the language is not right, I'm Italian :)

--
Do you want to live forever?  Alex Chiu has invented a device which will
give you physical immortality.  Click here!
http://www.alexchiu.com/affiliates/clickthru.cgi?id=pfosser