C++ Boost graph library: Isomorphism with edge property

Question

The boost graph library has an isomorphism function with a very minimal example:

https://www.boost.org/doc/libs/1_68_0/libs/graph/example/isomorphism.cpp

I need to find isomorphism between two graphs with a very minimal extension, that each line has two properties, that can be indicated with integer values. I guess this is equivalent to a weight.

I cannot for the life of me understand the role of property maps or how to incorporate those. Could someone point me to a relevant example so I can see how this works?

Answer 1

Boost.Graph uses "property maps" to associate data with different graph elements (i.e. vertices, edges, or the graph as a whole). A property map is simply a container that can associate the graph's internal descriptor types to some other data. A few examples can be found here and here.

I assume you've already seen the docs for the isomorphism function. So in your case each of your graphs will have one property map for edge weights, and then you have the option to provide more property maps when calling the isomorphism function to control the behavior and/or get extra data out. However, I don't see any way to provide a predicate for verifying that the edge weights match; you may have to handle that yourself (e.g. first run the function to check for "pure" isomorphism, then walk edges of one graph and use the output isomorphism_map to find corresponding edges in the second graph and check equality)

Answer 2

As far as I can tell that algorithm doesn't allow you to specify edge equivalence criteria. Perhaps you can apply vf2_sub_graph_iso, though, which takes an optional EdgeEquivalencePredicate