Graph Morphism Algorithms ( graph_morphism )

**Definition**

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:
`support@algorithmic-solutions.com` resp. `support@quappa.com`.

#include < LEDA/graph/graph_morphism.h >

**Implementation**

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

**Example**

#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. alg.delete_prepared_graph(pg1);

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

root 2008-01-09