Re: [BGL] Permutation of a graph

Hi Paolo, sorry I didn't understand your original post. I'm now quite sure what you're doing is over my head. Thank you for the great description of your algorithms - fascinating. - Chris ----- Original Message ----- From: "Paolo Fosser" Newsgroups: gmane.comp.lib.boost.user Sent: Friday, December 13, 2002 5:43 AM Subject: Re: [BGL] Permutation of a graph Chris Russell wrote:

"Paolo Fosser" wrote in message news:3DEDBD05.46E3F692@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 Info: http://www.boost.org Wiki: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl Unsubscribe: mailto:boost-users-unsubscribe@yahoogroups.com Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/