All Known Implementing Classes:

IsomorphismTesterAbstract, IsomorphismTesterVf2
```
public interface IsomorphismTester
```
Tester that check whether two graphs are isomorphic.
Given two graphs, an isomorphism is a mapping function that maps the first graph vertices to the second graph vertices, while preserving the structure of the graph. There are few variants of the problem:
- Full: Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a full isomorphism is a bijective function \(m: V_1 \rightarrow V_2\) such that \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. Note that full isomorphism can only exists between graphs with the same number of vertices and edges, as the vertex mapping is bijective.
- Induced subgraph: Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), an induced subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is an induced sub graph of g2 that is isomorphic to g1. Note that induced subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\). Full isomorphism between two graphs can be seen as a special case of induced subgraph isomorphism where the the number of vertices and edges is the same.
- Subgraph: Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that if \((u, v) \in E_1\) than \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is a sub graph of g2 that is isomorphic to g1. Note that subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\), and edges of \(G_2\) that are not mapped to any edge of \(G_1\) (even if they are connecting mapped vertices of \(G_2\)).
All the methods in this interface accept two graphs g1 and g2 and check for a sub graph isomorphism between them, where g1 is the smaller graph, and g2 is the bigger graph. The methods accept a boolean flag that indicates whether to search for a sub graph isomorphism or an induced sub graph isomorphism. To check for a full isomorphism, use induced sub graph isomorphism and make sure that the number of vertices of g1 and g2 are the same.
The full isomorphism problem which asks whether two graphs are isomorphic is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known subsets: P and NP-complete. The sub graph isomorphism variants are NP-complete.
Use newInstance() to get a default implementation of this interface.
Author:

Barak Ugav

See Also:

IsomorphismMapping, Wikipedia

Method Summary

All Methods Static Methods Instance Methods Abstract Methods Default Methods
Modifier and Type	Method	Description
`default <V1,E1,V2,E2> Optional<IsomorphismMapping<V1,E1,V2,E2>>`	`isomorphicMapping(Graph<V1,E1> g1, Graph<V2,E2> g2)`	Get an induced sub graph isomorphism mapping between two graphs if one exists.
`default <V1,E1,V2,E2> Optional<IsomorphismMapping<V1,E1,V2,E2>>`	`isomorphicMapping(Graph<V1,E1> g1, Graph<V2,E2> g2, boolean induced)`	Get a sub graph isomorphism mapping between two graphs if one exists, optionally induced.
`default <V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>>`	`isomorphicMappingsIter(Graph<V1,E1> g1, Graph<V2,E2> g2)`	Get an iterator over all the induced sub graph isomorphism mappings between two graphs.
`default <V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>>`	`isomorphicMappingsIter(Graph<V1,E1> g1, Graph<V2,E2> g2, boolean induced)`	Get an iterator over all the sub graph isomorphism mappings between two graphs, optionally induced.
`<V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>>`	`isomorphicMappingsIter(Graph<V1,E1> g1, Graph<V2,E2> g2, boolean induced, BiPredicate<? super V1,? super V2> vertexMatcher, BiPredicate<? super E1,? super E2> edgeMatcher)`	Get an iterator over all the sub graph isomorphism mappings between two graphs, optionally induced, with vertex and/or edge matchers.
`static IsomorphismTester`	`newInstance()`	Create a new isomorphism tester.

- Method Detail
  - isomorphicMapping
```
default <V1,E1,V2,E2> Optional<IsomorphismMapping<V1,E1,V2,E2>> isomorphicMapping(Graph<V1,E1> g1,
                                                                                                                      Graph<V2,E2> g2)
```
    Get an induced sub graph isomorphism mapping between two graphs if one exists.
    Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), an induced subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is an induced sub graph of g2 that is isomorphic to g1. Note that induced subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\). In such case the inverse of the returned mapping may not map all vertices and edges of g2, see IsomorphismMapping.
    If g1 and g2 have the same number of vertices, then searching for an induced sub graph isomorphism is equivalent to searching for a full isomorphism. In full isomorphism, the mapping is bijective, and all vertices and edges of g2 are mapped to vertices and edges of g1.
    To find a sub graph isomorphism, use isomorphicMapping(Graph, Graph, boolean) with the induced flag set to false.
    Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered.
    If both g1 and g2 are instances of IntGraph, the optional return value will be an instance of IsomorphismIMapping.
    
    Type Parameters:
    
    V1 - the type of vertices of the first graph
    
    E1 - the type of edges of the first graph
    
    V2 - the type of vertices of the second graph
    
    E2 - the type of edges of the second graph
    
    Parameters:
    
    g1 - the first graph
    
    g2 - the second graph
    
    Returns:
    
    an induced sub graph isomorphism mapping between the two graphs if one exists, Optional.empty() otherwise. The returned mapping maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().
    
    Throws:
    
    IllegalArgumentException - if g1 is directed and g2 is undirected, or vice versa
  - isomorphicMapping
```
default <V1,E1,V2,E2> Optional<IsomorphismMapping<V1,E1,V2,E2>> isomorphicMapping(Graph<V1,E1> g1,
                                                                                                                      Graph<V2,E2> g2,
                                                                                                                      boolean induced)
```
    Get a sub graph isomorphism mapping between two graphs if one exists, optionally induced.
    Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that if \((u, v) \in E_1\) than \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. An induced subgraph isomorphism is same as above, but the mapping also satisfies \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is a sub graph of g2 that is isomorphic to g1. Note that subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\), and if non-induced sub graph isomorphism is searched, also edges of \(G_2\) that are not mapped to any edge of \(G_1\) (even if they are connecting mapped vertices of \(G_2\)). In such case the inverse of the returned mapping may not map all vertices and edges of g2, see IsomorphismMapping.
    Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered.
    If both g1 and g2 are instances of IntGraph, the optional return value will be an instance of IsomorphismIMapping.
    
    Type Parameters:
    
    V1 - the type of vertices of the first graph
    
    E1 - the type of edges of the first graph
    
    V2 - the type of vertices of the second graph
    
    E2 - the type of edges of the second graph
    
    Parameters:
    
    g1 - the first graph. If sub graph isomorphism is searched, g1 is the smaller graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    g2 - the second graph. If sub graph isomorphism is searched, g2 is the bigger graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    induced - whether to search for an induced sub graph isomorphism or a sub graph isomorphism. See the interface documentation for more details
    
    Returns:
    
    a (optionally induced) sub graph isomorphism mapping between the two graphs if one exists, Optional.empty() otherwise. The returned mapping maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().
    
    Throws:
    
    IllegalArgumentException - if g1 is directed and g2 is undirected, or vice versa
  - isomorphicMappingsIter
```
default <V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>> isomorphicMappingsIter(Graph<V1,E1> g1,
                                                                                                                           Graph<V2,E2> g2)
```
    Get an iterator over all the induced sub graph isomorphism mappings between two graphs.
    Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), an induced subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is an induced sub graph of g2 that is isomorphic to g1. Note that induced subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\). In such case the inverse of the returned mappings may not map all vertices and edges of g2, see IsomorphismMapping.
    If g1 and g2 have the same number of vertices, then searching for an induced sub graph isomorphism is equivalent to searching for a full isomorphism. In full isomorphism, the mapping is bijective, and all vertices and edges of g2 are mapped to vertices and edges of g1.
    To get an iterator over all sub graph isomorphisms, use isomorphicMappingsIter(Graph, Graph, boolean) with the induced flag set to false.
    Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered.
    If both g1 and g2 are instances of IntGraph, the returned iterator will iterate over objects of IsomorphismIMapping.
    
    Type Parameters:
    
    V1 - the type of vertices of the first graph
    
    E1 - the type of edges of the first graph
    
    V2 - the type of vertices of the second graph
    
    E2 - the type of edges of the second graph
    
    Parameters:
    
    g1 - the first graph
    
    g2 - the second graph
    
    Returns:
    
    an iterator over all the induced sub graph isomorphism mappings between the two graphs. The returned mappings maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().
    
    Throws:
    
    IllegalArgumentException - if g1 is directed and g2 is undirected, or vice versa
  - isomorphicMappingsIter
```
default <V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>> isomorphicMappingsIter(Graph<V1,E1> g1,
                                                                                                                           Graph<V2,E2> g2,
                                                                                                                           boolean induced)
```
    Get an iterator over all the sub graph isomorphism mappings between two graphs, optionally induced.
    Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that if \((u, v) \in E_1\) than \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. An induced subgraph isomorphism is same as above, but the mapping also satisfies \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is a sub graph of g2 that is isomorphic to g1. Note that subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\), and if non-induced sub graph isomorphism is searched, also edges of \(G_2\) that are not mapped to any edge of \(G_1\) (even if they are connecting mapped vertices of \(G_2\)). In such case the inverse of the returned mappings may not map all vertices and edges of g2, see IsomorphismMapping.
    Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered.
    If both g1 and g2 are instances of IntGraph, the returned iterator will iterate over objects of IsomorphismIMapping.
    
    Type Parameters:
    
    V1 - the type of vertices of the first graph
    
    E1 - the type of edges of the first graph
    
    V2 - the type of vertices of the second graph
    
    E2 - the type of edges of the second graph
    
    Parameters:
    
    g1 - the first graph. If sub graph isomorphism is searched, g1 is the smaller graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    g2 - the second graph. If sub graph isomorphism is searched, g2 is the bigger graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    induced - whether to search for an induced sub graph isomorphism or a sub graph isomorphism. See the interface documentation for more details
    
    Returns:
    
    an iterator over all the (optionally induced) sub graph isomorphism mappings between the two graphs. The returned mappings maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().
    
    Throws:
    
    IllegalArgumentException - if g1 is directed and g2 is undirected, or vice versa
  - isomorphicMappingsIter
```
<V1,E1,V2,E2> Iterator<IsomorphismMapping<V1,E1,V2,E2>> isomorphicMappingsIter(Graph<V1,E1> g1,
                                                                                                                   Graph<V2,E2> g2,
                                                                                                                   boolean induced,
                                                                                                                   BiPredicate<? super V1,? super V2> vertexMatcher,
                                                                                                                   BiPredicate<? super E1,? super E2> edgeMatcher)
```
    Get an iterator over all the sub graph isomorphism mappings between two graphs, optionally induced, with vertex and/or edge matchers.
    Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that if \((u, v) \in E_1\) than \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. An induced subgraph isomorphism is same as above, but the mapping also satisfies \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is a sub graph of g2 that is isomorphic to g1. Note that subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\), and if non-induced sub graph isomorphism is searched, also edges of \(G_2\) that are not mapped to any edge of \(G_1\) (even if they are connecting mapped vertices of \(G_2\)). In such case the inverse of the returned mappings may not map all vertices and edges of g2, see IsomorphismMapping.
    In addition to the structure of the graphs, this method also takes two predicates that filter pairs of vertices and edges, one from each graph, that are not allowed to be mapped to each other. For a given pair \(v_1,v_2\) where \(v_1 \in V_1\) and \(v_2 \in V_2\), if the vertex matcher returns false, then the pair is not considered for mapping. The edge matchers is used similarly. If a matcher is null, all pairs of vertices or edges are allowed. The matchers allow to compare other properties of the vertices/edge besides their structure, such as weights.
    Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered, along with the matchers, if provided.
    If both g1 and g2 are instances of IntGraph, the returned iterator will iterate over objects of IsomorphismIMapping.
    
    Type Parameters:
    
    V1 - the type of vertices of the first graph
    
    E1 - the type of edges of the first graph
    
    V2 - the type of vertices of the second graph
    
    E2 - the type of edges of the second graph
    
    Parameters:
    
    g1 - the first graph. If sub graph isomorphism is searched, g1 is the smaller graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    g2 - the second graph. If sub graph isomorphism is searched, g2 is the bigger graph, namely the method search for a mapping from g1 to a sub graph of g2
    
    induced - whether to search for an induced sub graph isomorphism or a sub graph isomorphism. See the interface documentation for more details
    
    vertexMatcher - a predicate that filters pairs of vertices, one from each graph, that are not allowed to be mapped to each other. For a given pair \(v_1,v_2\) where \(v_1 \in V_1\) and \(v_2 \in V_2\), if the matcher returns false, then the pair is not considered for mapping. If null, all pairs of vertices are allowed.
    
    edgeMatcher - a predicate that filters pairs of edges, one from each graph, that are not allowed to be mapped to each other. For a given pair \(e_1,e_2\) where \(e_1 \in E_1\) and \(e_2 \in E_2\), if the matcher returns false, then the pair is not considered for mapping. If null, all pairs of edges are allowed.
    
    Returns:
    
    an iterator over all the (optionally induced) sub graph isomorphism mappings between the two graphs. The returned mappings maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().
    
    Throws:
    
    IllegalArgumentException - if g1 is directed and g2 is undirected, or vice versa
  - newInstance
```
static IsomorphismTester newInstance()
```
    Create a new isomorphism tester.
    This is the recommended way to instantiate a new IsomorphismTester object.
    
    Returns:
    
    a default implementation of IsomorphismTester

Interface IsomorphismTester

Method Summary

Method Detail

isomorphicMapping

isomorphicMapping

isomorphicMappingsIter

isomorphicMappingsIter

isomorphicMappingsIter

newInstance