Sawyer::Container::Algorithm::CsiEquivalence< GraphA, GraphB > Class Template Reference

Description

template<class GraphA, class GraphB>
class Sawyer::Container::Algorithm::CsiEquivalence< GraphA, GraphB >

Vertex equivalence for common subgraph isomorphism.

Determines when a pair of vertices, one from each of two graphs, can be considered isomorphic. This class serves as both a model for those wishing to write their own formulation of equivalence, and as the default implementation when none is provided by the user.

Definition at line 326 of file GraphAlgorithm.h.

#include <util/Sawyer/GraphAlgorithm.h>

Public Member Functions
bool	mu (const GraphA &g1, const typename GraphA::ConstVertexIterator &v1, const GraphB &g2, const typename GraphB::ConstVertexIterator &v2) const
	Isomorphism of two vertices. More...
bool	nu (const GraphA &g1, typename GraphA::ConstVertexIterator i1, typename GraphA::ConstVertexIterator i2, const std::vector< typename GraphA::ConstEdgeIterator > &edges1, const GraphB &g2, typename GraphB::ConstVertexIterator j1, typename GraphB::ConstVertexIterator j2, const std::vector< typename GraphB::ConstEdgeIterator > &edges2) const
	Isomorphism of vertices based on incident edges. More...
void	progress (size_t)
	Called at each step during the algorithm. More...

Member Function Documentation

template<class GraphA , class GraphB >

bool Sawyer::Container::Algorithm::CsiEquivalence< GraphA, GraphB >::mu ( const GraphA &  g1, const typename GraphA::ConstVertexIterator &  v1, const GraphB &  g2, const typename GraphB::ConstVertexIterator &  v2  ) const

inline

Isomorphism of two vertices.

Given a pair of vertices, one from each of two graphs, return true if the vertices could be an isomorphic pair in common subgraph isomorphism algorithms. This default implementation always returns true.

Definition at line 332 of file GraphAlgorithm.h.

template<class GraphA , class GraphB >

bool Sawyer::Container::Algorithm::CsiEquivalence< GraphA, GraphB >::nu ( const GraphA &  g1, typename GraphA::ConstVertexIterator  i1, typename GraphA::ConstVertexIterator  i2, const std::vector< typename GraphA::ConstEdgeIterator > &  edges1, const GraphB &  g2, typename GraphB::ConstVertexIterator  j1, typename GraphB::ConstVertexIterator  j2, const std::vector< typename GraphB::ConstEdgeIterator > &  edges2  ) const

inline

Isomorphism of vertices based on incident edges.

Given two pairs of vertices, (i1, i2) and (j1, j2), one from each of two graphs g1 and g2, and given the two sets of edges that connect the vertices of each pair (in both directions), determine whether vertices i2 and j2 are isomorphic. The pair (i1, j1) is already part of a common subgraph isomorphism solution. Vertices i2 and j2 are already known to satisfy the mu predicate and have the appropriate number of edges for inclusion into the solution.

This default implementation always returns true.

Definition at line 350 of file GraphAlgorithm.h.

template<class GraphA , class GraphB >

void Sawyer::Container::Algorithm::CsiEquivalence< GraphA, GraphB >::progress ( size_t  )

inline

Called at each step during the algorithm.

This method is called each time the algorithm tests a potential solution. It can be used to report progress or terminate the search after some number of iterations. The argument is the number of vertices in the potential solution.

Definition at line 370 of file GraphAlgorithm.h.

---

The documentation for this class was generated from the following file:

• GraphAlgorithm.h