|
ROSE
0.11.145.0
|
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 443 of file GraphAlgorithm.h.
#include <util/Sawyer/GraphAlgorithm.h>
Public Member Functions | |
| CommonSubgraphIsomorphism (const GraphA &g1, const GraphB &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... | |
|
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 608 of file GraphAlgorithm.h.
|
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 641 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph().
|
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 642 of file GraphAlgorithm.h.
|
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 659 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph().
|
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 660 of file GraphAlgorithm.h.
|
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 671 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().
|
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 672 of file GraphAlgorithm.h.
|
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 681 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph(), and Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().
|
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 682 of file GraphAlgorithm.h.
|
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 694 of file GraphAlgorithm.h.
|
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 695 of file GraphAlgorithm.h.
|
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 708 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findIsomorphicSubgraphs().
|
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 709 of file GraphAlgorithm.h.
|
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 727 of file GraphAlgorithm.h.
Referenced by Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs(), Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph(), Sawyer::Container::Algorithm::findIsomorphicSubgraphs(), and Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs().
|
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 737 of file GraphAlgorithm.h.
References Sawyer::Container::DenseIntegerSet< T >::insertAll().
Referenced by Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run().
1.8.10