Package com.jgalgo.alg.isomorphism

Class IsomorphismTesterAbstract

java.lang.Object

com.jgalgo.alg.isomorphism.IsomorphismTesterAbstract

All Implemented Interfaces:

IsomorphismTester

Direct Known Subclasses:

IsomorphismTesterVf2

public abstract class IsomorphismTesterAbstract
extends Object
implements IsomorphismTester

Abstract class for computing isomorphism mapping between two graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
IsomorphismTesterAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.jgalgo.alg.isomorphism.IsomorphismTester

isomorphicMapping, isomorphicMapping, isomorphicMappingsIter, isomorphicMappingsIter

Constructor Details

IsomorphismTesterAbstract

public IsomorphismTesterAbstract()

Default constructor.

Method Details

isomorphicMappingsIter

public <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)

Description copied from interface: IsomorphismTester

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.

Specified by:

isomorphicMappingsIter in interface IsomorphismTester

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().