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 java.lang.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 Classes Modifier and Type Class Description private static class
ColorRefinementIsomorphismInspector.DistinctGraphObject<T,V,E>
Representation of a graph vertex in the disjoint union
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph1
The input graphsprivate Graph<V,E>
graph2
The input graphsprivate boolean
isColoringDiscrete
contains whether the two graphs produce a discrete coloring.private boolean
isForest
contains whether the two graphs are forests.private java.lang.Boolean
isIsomorphic
contains whether the graphs are isomorphic or not.private IsomorphicGraphMapping<V,E>
isomorphicGraphMapping
The isomorphism that is calculated by this color refinement isomorphism inspectorprivate boolean
isomorphismTestExecuted
contains whether the isomorphism test is executed to ensure that every operation is defined all the time
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private 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>>
getDisjointGraphUnion(Graph<V,E> graph1, Graph<V,E> graph2)
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)
java.util.Iterator<GraphMapping<V,E>>
getMappings()
Get an iterator over all calculated (isomorphic) mappings between two graphs.(package private) boolean
isColoringDiscrete()
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
isomorphismExists()
Check if an isomorphism exists.private void
sortColorClasses(java.util.List<java.util.Set<V>> colorClasses, VertexColoringAlgorithm.Coloring<V> coloring)
Sorts a list of color classes by the size and the color (integer representation of the color) andprivate 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
-
-
-
Field Detail
-
isomorphicGraphMapping
private IsomorphicGraphMapping<V,E> isomorphicGraphMapping
The isomorphism that is calculated by this color refinement isomorphism inspector
-
isIsomorphic
private java.lang.Boolean 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 isColoringDiscrete
contains whether the two graphs produce a discrete coloring. Then, we can decide whether the graphs are isomorphic.
-
isForest
private boolean isForest
contains whether the two graphs are forests. Forests can be identified to be isomorphic or not.
-
isomorphismTestExecuted
private boolean isomorphismTestExecuted
contains whether the isomorphism test is executed to ensure that every operation is defined all the time
-
-
Constructor Detail
-
ColorRefinementIsomorphismInspector
public ColorRefinementIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2)
Constructor for a isomorphism inspector based on color refinement. It checks whethergraph1
andgraph2
are isomorphic.- Parameters:
graph1
- the first graphgraph2
- the second graph
-
-
Method Detail
-
getMappings
public java.util.Iterator<GraphMapping<V,E>> 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,E>> coloring) throws IsomorphismUndecidableException
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(java.util.List<java.util.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,E>,ColorRefinementIsomorphismInspector.DistinctGraphObject<E,V,E>> getDisjointGraphUnion(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
-
-