ROSE  0.9.9.168
Classes | Public Member Functions | List of all members
Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP > Class Template Reference

Description

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
class Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >

Common subgraph isomorphism solver.

Finds subgraphs of two given graphs where the subgraphs are isomorphic to one another.

The solver assumes that any vertex in the first graph can be isomorphic to any vertex of the second graph unless the user provides his own equivalence predicate. The default predicate, CsiEquivalence, allows any vertex to be isomorphic to any other vertex (the solver additionally requires that the two subgraphs of any solution have the same number of edges). Providing an equivalence predicate can substantially reduce the search space, as can limiting the minimum size of solutions.

Each time a solution is found, the SolutionProcessor is invoked. Users will typically provide their own solution processor since the default processor, CsiShowSolution, only prints the solutions to standard output. The solution processor is only called for complete solutions when the end of a search path is reached; it is not called for intermediate solutions. The processor can return a code that indicates how the algorithm should proceed. See CsiShowSolution for more information.

To use this class, instantiate an instance and specify the two graphs to be compared (they can both be the same graph if desired), the solution handler callback, and the vertex equivalence predicate. Then, if necessary, make adjustements to the callback and/or predicate. Finally, invoke the run method. The graphs must not be modified between the time this solver is created and the run method returns.

The following functions are convenient wrappers around this class: findCommonIsomorphicSubgraphs, findFirstCommonIsomorphicSubgraph, findIsomorphicSubgraphs, findMaximumCommonIsomorphicSubgraphs.

Definition at line 407 of file GraphAlgorithm.h.

#include <GraphAlgorithm.h>

Public Member Functions

 CommonSubgraphIsomorphism (const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor=SolutionProcessor(), EquivalenceP equivalenceP=EquivalenceP())
 Construct a solver. More...
 
void run ()
 Perform the common subgraph isomorphism analysis. More...
 
void reset ()
 Releases memory used by the analysis. More...
 
size_t minimumSolutionSize () const
 Property: minimum allowed solution size. More...
 
void minimumSolutionSize (size_t n)
 Property: minimum allowed solution size. More...
 
size_t maximumSolutionSize () const
 Property: maximum allowed solution size. More...
 
void maximumSolutionSize (size_t n)
 Property: maximum allowed solution size. More...
 
bool monotonicallyIncreasing () const
 Property: monotonically increasing solution size. More...
 
void monotonicallyIncreasing (bool b)
 Property: monotonically increasing solution size. More...
 
SolutionProcessor & solutionProcessor ()
 Property: reference to the solution callback. More...
 
const SolutionProcessor & solutionProcessor () const
 Property: reference to the solution callback. More...
 
EquivalenceP & equivalencePredicate ()
 Property: reference to the vertex equivalence predicate. More...
 
const EquivalenceP & equivalencePredicate () const
 Property: reference to the vertex equivalence predicate. More...
 
bool findingCommonSubgraphs () const
 Property: find common subgraphs. More...
 
void findingCommonSubgraphs (bool b)
 Property: find common subgraphs. More...
 

Constructor & Destructor Documentation

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::CommonSubgraphIsomorphism ( const Graph g1,
const Graph g2,
SolutionProcessor  solutionProcessor = SolutionProcessor(),
EquivalenceP  equivalenceP = EquivalenceP() 
)
inline

Construct a solver.

Constructs a solver that will find subgraphs of g1 and g2 that are isomorpic to one another. The graphs must not be modified between the call to this constructor and the return of its run method.

The solution processor and equivalence predicate are copied into this solver. If the size of these objects is an issue, then they can be created with default constructors when the solver is created, and then modified afterward by obtaining a reference to the copies that are part of the solver.

The default solution processor, CsiShowSolution, prints the solutions to standard output. The default vertex equivalence predicate, CsiEquivalence, allows any vertex in graph g1 to be isomorphic to any vertex in graph g2. The solver additionally constrains the two sugraphs of any solution to have the same number of edges (that's the essence of subgraph isomorphism and cannot be overridden by the vertex isomorphism predicate).

Definition at line 571 of file GraphAlgorithm.h.

Member Function Documentation

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
size_t Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::minimumSolutionSize ( ) const
inline

Property: minimum allowed solution size.

Determines the minimum size of solutions for which the solution processor callback is invoked. This minimum can be changed at any time before or during the analysis and is useful when looking for the largest isomorphic subgraphs. Not only does this property control when the solution processor is invoked, but it's also used to limit the search space–specifying a large minimum size causes the analysis to run faster.

Decreasing the minimum solution size during a run will not cause solutions that were smaller than its previous value to be found if those solutions have already been skipped or pruned from the search space.

The default minimum is one, which means that the trivial solution of two empty subgraphs is not reported to the callback.

See also, maximumSolutionSize.

Definition at line 604 of file GraphAlgorithm.h.

Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::minimumSolutionSize ( size_t  n)
inline

Property: minimum allowed solution size.

Determines the minimum size of solutions for which the solution processor callback is invoked. This minimum can be changed at any time before or during the analysis and is useful when looking for the largest isomorphic subgraphs. Not only does this property control when the solution processor is invoked, but it's also used to limit the search space–specifying a large minimum size causes the analysis to run faster.

Decreasing the minimum solution size during a run will not cause solutions that were smaller than its previous value to be found if those solutions have already been skipped or pruned from the search space.

The default minimum is one, which means that the trivial solution of two empty subgraphs is not reported to the callback.

See also, maximumSolutionSize.

Definition at line 605 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
size_t Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::maximumSolutionSize ( ) const
inline

Property: maximum allowed solution size.

Determines the maximum size of solutions for which the solution processor callback is invoked. The maximum can be changed any time before or during the analysis. Once a maximum solution is found along some search path, the remainder of the search path is discarded.

Increasing the maximum solution size during a run will not cause solutions that were larger than its previous value to be found if those solutions have already been skipped.

The default maximum is larger than both graphs, which means all solutions will be found.

See also, minimumSolutionSize.

Definition at line 622 of file GraphAlgorithm.h.

Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::maximumSolutionSize ( size_t  n)
inline

Property: maximum allowed solution size.

Determines the maximum size of solutions for which the solution processor callback is invoked. The maximum can be changed any time before or during the analysis. Once a maximum solution is found along some search path, the remainder of the search path is discarded.

Increasing the maximum solution size during a run will not cause solutions that were larger than its previous value to be found if those solutions have already been skipped.

The default maximum is larger than both graphs, which means all solutions will be found.

See also, minimumSolutionSize.

Definition at line 623 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
bool Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::monotonicallyIncreasing ( ) const
inline

Property: monotonically increasing solution size.

If true, then each solution reported to the solution processor will be at least as large as the previous solution. Setting this property will result in more efficient behavior than culling solutions in the solution processor because in the former situation the solver can eliminate branches of the search space. This property is useful when searching for the largest isomorphic subgraph.

Definition at line 634 of file GraphAlgorithm.h.

Referenced by Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::monotonicallyIncreasing ( bool  b)
inline

Property: monotonically increasing solution size.

If true, then each solution reported to the solution processor will be at least as large as the previous solution. Setting this property will result in more efficient behavior than culling solutions in the solution processor because in the former situation the solver can eliminate branches of the search space. This property is useful when searching for the largest isomorphic subgraph.

Definition at line 635 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
SolutionProcessor& Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::solutionProcessor ( )
inline

Property: reference to the solution callback.

Returns a reference to the callback that will process each solution. The callback can be changed at any time between construction of this analysis and the return from its run method.

Definition at line 644 of file GraphAlgorithm.h.

Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph(), and Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
const SolutionProcessor& Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::solutionProcessor ( ) const
inline

Property: reference to the solution callback.

Returns a reference to the callback that will process each solution. The callback can be changed at any time between construction of this analysis and the return from its run method.

Definition at line 645 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
EquivalenceP& Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::equivalencePredicate ( )
inline

Property: reference to the vertex equivalence predicate.

Returns a reference to the predicate that determines whether a vertex from one graph can be isomorphic to a vertex of the other graph. Solutions will only contain pairs of vertices for which the predicate returns true.

Changing the predicate during the run method may or may not have the desired effect. This is because the return value from the predicate (at least it's mu method) is computed up front and cached.

Definition at line 657 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
const EquivalenceP& Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::equivalencePredicate ( ) const
inline

Property: reference to the vertex equivalence predicate.

Returns a reference to the predicate that determines whether a vertex from one graph can be isomorphic to a vertex of the other graph. Solutions will only contain pairs of vertices for which the predicate returns true.

Changing the predicate during the run method may or may not have the desired effect. This is because the return value from the predicate (at least it's mu method) is computed up front and cached.

Definition at line 658 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
bool Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs ( ) const
inline

Property: find common subgraphs.

This property controls whether the solver finds subgraphs of both specified graphs, or requires that the entire first graph is a subgraph of the second. When true (the default) the solver finds solutions to the "common subgraph isomorphism" problem; when false it finds solutions to the "subgraph isomorphism" problem.

When this property is false the minimumSolutionSize is ignored; all solutions will be equal in size to the number of vertices in the first graph.

Definition at line 671 of file GraphAlgorithm.h.

Referenced by Sawyer::Container::Algorithm::findIsomorphicSubgraphs().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs ( bool  b)
inline

Property: find common subgraphs.

This property controls whether the solver finds subgraphs of both specified graphs, or requires that the entire first graph is a subgraph of the second. When true (the default) the solver finds solutions to the "common subgraph isomorphism" problem; when false it finds solutions to the "subgraph isomorphism" problem.

When this property is false the minimumSolutionSize is ignored; all solutions will be equal in size to the number of vertices in the first graph.

Definition at line 672 of file GraphAlgorithm.h.

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run ( )
inline

Perform the common subgraph isomorphism analysis.

Runs the common subgraph isomorphism analysis from beginning to end, invoking the constructor-supplied solution processor for each solution that's found to be large enough (see minimumSolutionSize). The solutions are not detected in any particular order.

The graphs provided to the analysis constructor on which this analysis runs must not be modified between when the analysis is created and this method returns. Actually, it is permissible to modify the contents of the graphs, just not their connectivity. I.e., changing the values stored at vertices and edges is fine, but inserting or erasing vertices or edges is not.

The run method may be called multiple times and will always start from the beginning. If the solution processor determines that the analysis is not required to complete then it may throw an exception. The reset method can be called afterward to delete memory used by the analysis (memory usage is not large to begin with), although this is not necessary since the destructor does not leak memory.

Definition at line 690 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::reset().

Referenced by Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs(), Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph(), Sawyer::Container::Algorithm::findIsomorphicSubgraphs(), and Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().

template<class Graph, class SolutionProcessor = CsiShowSolution<Graph>, class EquivalenceP = CsiEquivalence<Graph>>
void Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::reset ( )
inline

Releases memory used by the analysis.

Releases memory that's used by the analysis, returning the analysis to its just-constructed state. This method is called implicitly at the beginning of each run.

Definition at line 700 of file GraphAlgorithm.h.

References Sawyer::Container::DenseIntegerSet< T >::insertAll().

Referenced by Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run().


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