Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism
Class ColorRefinementIsomorphismInspector<V,E>
java.lang.Object
org.jgrapht.alg.isomorphism.ColorRefinementIsomorphismInspector<V,E>
- Type Parameters:
V
- the type of the verticesE
- the type of the edges
- All Implemented Interfaces:
IsomorphismInspector<V,
E>
public class ColorRefinementIsomorphismInspector<V,E>
extends Object
implements IsomorphismInspector<V,E>
Implementation of the color refinement algorithm isomorphism test using its feature of detecting
isomorphism between two graphs
as described in C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the
complexity of canonical colour refinement. Theory of Computing
Systems,doi:10.1007/s00224-016-9686-0, 2016 (color refinement) The complexity of this algorithm
is O(|V| + |E| log |V|).
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Representation of a graph vertex in the disjoint union -
Field Summary
FieldsModifier and TypeFieldDescriptionThe input graphsThe input graphsprivate boolean
contains whether the two graphs produce a discrete coloring.private boolean
contains whether the two graphs are forests.private Boolean
contains whether the graphs are isomorphic or not.private IsomorphicGraphMapping
<V, E> The isomorphism that is calculated by this color refinement isomorphism inspectorprivate boolean
contains whether the isomorphism test is executed to ensure that every operation is defined all the time -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
calculateGraphMapping
(VertexColoringAlgorithm.Coloring<V> coloring1, VertexColoringAlgorithm.Coloring<V> coloring2) calculates the graph isomorphism as GraphMapping and assigns it to attributeisomorphicGraphMapping
private boolean
coarseColoringAreEqual
(VertexColoringAlgorithm.Coloring<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, E>> coloring) Checks whether two coarse colorings are equal.private Graph
<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, E>, ColorRefinementIsomorphismInspector.DistinctGraphObject<E, V, E>> Calculates and returns a disjoint graph union ofgraph1
andgraph2
private Graph
<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, E>, ColorRefinementIsomorphismInspector.DistinctGraphObject<E, V, E>> getDistinctObjectGraph
(Graph<V, E> graph) Get an iterator over all calculated (isomorphic) mappings between two graphs.(package private) boolean
Returns whether the coarse colorings of the two given graphs are discrete.(package private) boolean
isForest()
Returns whether the two given graphs are forests.boolean
Check if an isomorphism exists.private void
sortColorClasses
(List<Set<V>> colorClasses, VertexColoringAlgorithm.Coloring<V> coloring) Sorts a list of color classes by the size and the color (integer representation of the color) andsplitColoring
(VertexColoringAlgorithm.Coloring<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, E>> coloring) Splits up the coloring of the union graph into the two colorings of the original graphs
-
Field Details
-
graph1
The input graphs -
graph2
The input graphs -
isomorphicGraphMapping
The isomorphism that is calculated by this color refinement isomorphism inspector -
isIsomorphic
contains whether the graphs are isomorphic or not. If we cannot decide whether they are isomorphic the value will be not present. -
isColoringDiscrete
private boolean isColoringDiscretecontains whether the two graphs produce a discrete coloring. Then, we can decide whether the graphs are isomorphic. -
isForest
private boolean isForestcontains whether the two graphs are forests. Forests can be identified to be isomorphic or not. -
isomorphismTestExecuted
private boolean isomorphismTestExecutedcontains whether the isomorphism test is executed to ensure that every operation is defined all the time
-
-
Constructor Details
-
ColorRefinementIsomorphismInspector
Constructor for a isomorphism inspector based on color refinement. It checks whethergraph1
andgraph2
are isomorphic.- Parameters:
graph1
- the first graphgraph2
- the second graph
-
-
Method Details
-
getMappings
Get an iterator over all calculated (isomorphic) mappings between two graphs.- Specified by:
getMappings
in interfaceIsomorphismInspector<V,
E> - Returns:
- an iterator over all calculated (isomorphic) mappings between two graphs
- Throws:
IsomorphismUndecidableException
- if the isomorphism test was not executed and the inspector cannot decide whether the graphs are isomorphic
-
isomorphismExists
public boolean isomorphismExists()Check if an isomorphism exists.- Specified by:
isomorphismExists
in interfaceIsomorphismInspector<V,
E> - Returns:
- true if there is an isomorphism, false if there is no isomorphism
- Throws:
IsomorphismUndecidableException
- if the inspector cannot decide whether the graphs are isomorphic
-
isColoringDiscrete
boolean isColoringDiscrete()Returns whether the coarse colorings of the two given graphs are discrete. This method is undefined if the colorings are not the same or graph1 == graph2.- Returns:
- if both colorings are discrete.
- Throws:
IsomorphismUndecidableException
- if the isomorphism test was not executed and the inspector cannot decide whether the graphs are isomorphic
-
isForest
boolean isForest()Returns whether the two given graphs are forests. This method is undefined if an isomorphism exists and the coloring is discrete, or graph1 == graph2.- Returns:
- if both graphs are forests.
- Throws:
IsomorphismUndecidableException
- if the isomorphism test was not executed and the inspector cannot decide whether the graphs are isomorphic
-
coarseColoringAreEqual
private boolean coarseColoringAreEqual(VertexColoringAlgorithm.Coloring<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, throws IsomorphismUndecidableExceptionE>> coloring) Checks whether two coarse colorings are equal. Furthermore, it setsisColoringDiscrete
to true iff the colorings are discrete.- Parameters:
coloring
- the coarse coloring of the union graph- Returns:
- if the given coarse colorings are equal
- Throws:
IsomorphismUndecidableException
-
splitColoring
private Pair<VertexColoringAlgorithm.Coloring<V>,VertexColoringAlgorithm.Coloring<V>> splitColoring(VertexColoringAlgorithm.Coloring<ColorRefinementIsomorphismInspector.DistinctGraphObject<V, V, E>> coloring) Splits up the coloring of the union graph into the two colorings of the original graphs- Parameters:
coloring
- the coloring to split up- Returns:
- the two colorings of the original graphs
-
sortColorClasses
private void sortColorClasses(List<Set<V>> colorClasses, VertexColoringAlgorithm.Coloring<V> coloring) Sorts a list of color classes by the size and the color (integer representation of the color) and- Parameters:
colorClasses
- the list of the color classescoloring
- the coloring
-
calculateGraphMapping
private void calculateGraphMapping(VertexColoringAlgorithm.Coloring<V> coloring1, VertexColoringAlgorithm.Coloring<V> coloring2) calculates the graph isomorphism as GraphMapping and assigns it to attributeisomorphicGraphMapping
- Parameters:
coloring1
- the discrete vertex coloring of graph1coloring2
- the discrete vertex coloring of graph2
-
getDisjointGraphUnion
private Graph<ColorRefinementIsomorphismInspector.DistinctGraphObject<V,V, getDisjointGraphUnionE>, ColorRefinementIsomorphismInspector.DistinctGraphObject<E, V, E>> (Graph<V, E> graph1, Graph<V, E> graph2) Calculates and returns a disjoint graph union ofgraph1
andgraph2
- Parameters:
graph1
- the first graph of the disjoint uniongraph2
- the second graph of the disjoint union- Returns:
- the disjoint union of the two graphs
-
getDistinctObjectGraph
-