...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate <class Graph1, class Graph2, class P, class T, class R> bool isomorphism(const Graph1& g1, const Graph2& g2, const bgl_named_params<P,T,R>& params =all defaults)// non-named parameter versiontemplate <typename Graph1, typename Graph2, typename IsoMap, typename VertexInvariant1, typename VertexInvariant2, typename V1Map, typename V2Map> bool isomorphism(const Graph1& g1, const Graph2& g2, IsoMap f, VertexInvariant1 invariant2, VertexInvariant2 invariant2, std::size_t max_invariant, VertexIndex1Map i1_map, VertexIndex2Map i2_map)

An ** isomorphism** is a 1-to-1 mapping of the vertices in
one graph to the vertices of another graph such that adjacency is
preserved. Another words, given graphs

This function returns `true` if there exists an isomorphism
between graph 1 and graph 2 and `false` otherwise. Also, if a
isomorphism map named parameter is provided then an isomorphism is
recorded in the map.

The current implementation is based on descriptions of a backtracking algorithm in [46,48]. The file isomorphism-impl.pdf contains a "literate" description of the implementation. The algorithm used is simple but slow. A more efficient (and much more complex) algorithm is described in [47]. When (and if) a version of this algorithm is ported to the BGL interface it should replace the current algorithm.

A directed or undirected graph. The graph type must model of Vertex List Graph and Edge List Graph.IN:

A directed or undirected graph. The graph type must model Bidirectional Graph and Vertex List Graph.

The mapping from vertices in graph 1 to vertices in graph 2. This must be a Read/Write Property Map.IN:

Default:aniterator_property_mapconstructed from astd::vectorof graph 2's vertex descriptor type and the vertex index map for graph 1.

Python: Must be avertex_vertex_mapfor the first graph.

A mappingIN:ifrom vertices to integers such that if there is some isomorphism that mapsvontov'theni(v) == i(v'). TheVertexInvarianttype must be a BinaryFunction where the first argument is a vertex descriptor, the second argument is a graph, and the result type is an integer. The vertex invariant must work with the types for graph 1.

Default:degree_vertex_invariant

Python: Unsupported parameter.

A mappingIN:ifrom vertices to integers such that if there is some isomorphism that mapsvontov'theni(v) == i(v'). TheVertexInvarianttype must be a BinaryFunction where the first argument is a vertex descriptor, the second argument is a graph, and the result type is an integer. The vertex invariant must work with the types for both graph 2.

Default:degree_vertex_invariant

Python: Unsupported parameter.

An upper bound on the possible values returned from either vertex_invariant1 or vertex_invariant2.IN:

Default:vertex_invariant2.max(). The defaultvertex_invariant2parameter, an instance ofdegree_vertex_invariant, defines this function to returnnum_vertices(g2) * (num_vertices(g2)+1).

Python: Unsupported parameter.

This maps each vertex to an integer in the rangeIN:[0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The typeVertexIndex1Mapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of graph 1 needs to be usable as the key type of the map.

Default:get(vertex_index, g1)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python: Unsupported parameter.

This maps each vertex to an integer in the range[0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The typeVertexIndex2Mapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of graph 2 needs to be usable as the key type of the map.

Default:get(vertex_index, g2)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python: Unsupported parameter.

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |