BGL isomorphism edge invariants

[Evan Driscoll <driscoll@…>]

Can you add a feature that would allow the user to specify edge invariants in a similar way to how it is presently possible to specify vertex invariants? (I.e. an isomorphism is only considered if some functor says that two edges are somehow equivalent.)

The motivation for this is I'd like to test isomorphism between finite automata from another library, for testing purposes. I'm considering converting the transition graph to a BGL graph and using the isomorphism function, but I'm not sure that's possible as I can't require that corresponding edges are labeled with the same symbol.

(In the meantime I think I may know where to slip it into the code, so I may make my own copy of invariant.hpp and make that change. If I can get it to seemingly work, I'll report back with the patch.)

Alternately, it may be possible with something I'm missing; I'm a newbie to the BGL. But I don't know where it'd show up.

[slithy]

Any update on this feature? I would like to use this as well.

[driscoll@…]

I never implemented it; the code was pretty complex (despite being reasonably well-documented) and I didn't have a good enough reason to do it.

If you're not wed to the BGL already and specifying edge "colors" is enough (as opposed to the yes/no predicate I proposed), there are alternatives such as the igraph library <​http://igraph.sourceforge.net/> that support isomorphism checking with edge constraints. (That's a C library and I've only used it a tiny bit, but it looks reasonably clean.)

[driscoll@…]

I never implemented it; the code was pretty complex (despite being reasonably well-documented) and I didn't have a good enough reason to do it.

If you're not wed to the BGL already and specifying edge "colors" is enough (as opposed to the yes/no predicate I proposed), there are alternatives such as the igraph library <​http://igraph.sourceforge.net/> that support isomorphism checking with edge constraints. (That's a C library and I've only used it a tiny bit, but it looks reasonably clean.)