next up previous contents index
Next: Graph Morphism Algorithm Functionality Up: Graph Algorithms Previous: Graph Drawing Algorithms (   Contents   Index

Graph Morphism Algorithms ( graph_morphism )


An instance alg of the parameterized data type graph_morphism< graph_t, impl > is an algorithm object that supports finding graph isomorphisms, subgraph isomorphisms, graph monomorphisms and graph automorphisms. The first parameter type parametrizes the input graphs' types. It defaults to graph. The second parameter type determines the actual algorithm implementation to use. There are two implementations available so far which work differently well for certain types of graphs. More details can be found in the report Graph Isomorphism Implementation for LEDA by Johannes Singler. It is available from our homepage. You can also contact our support team to get it: resp.

#include < LEDA/graph/graph_morphism.h >


Allowed implementations parameters are vf2<graph_t> and conauto<graph_t, ord_t>.


#include <LEDA/graph/graph_morphism.h>

// declare the input graphs.
graph g1, g2;

// In order to use node compatibility, declare associated node maps for the 
// attributes and a corresponding node compatibility function 
// (exemplary, see above for the definition of identity_compatibility).

node_map<int> nm1(g1), nm2(g2);
identity_compatibility<int> ic(nm1, nm2);

// do something useful to build up the graphs and the attributes

// instantiate the algorithm object
graph_morphism<graph, conauto<graph> > alg;

// declare the node and edge mapping arrays
node_array<node> node_mapping(g2);
edge_array<edge> edge_mapping(g2);

// prepare a graph morphism data structure for the first graph.
graph_morphism_algorithm<>::prep_graph pg1 = alg.prepare_graph(g1, ic);

// find the graph isomorphism.
bool isomorphic = alg.find_iso(pg1, g2, &node_mapping, &edge_mapping, ic);

// delete the prepared graph data structure again.

Please see demo/graph_iso/gw_isomorphism.cpp for an interactive demo program.

Christian Uhrig 2017-04-07