org.jgrapht.experimental.isomorphism

Class AdaptiveIsomorphismInspectorFactory

java.lang.Object

org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory

public class AdaptiveIsomorphismInspectorFactory
extends Object

This class serves as a factory for GraphIsomorphismInspector concrete implementations. It can be used in two ways:

1. You can can let this class to determine what is the most efficient algorithm for your graph.
2. You can specify the type of your graph (planar / tree / other) and save this class the graph-checking time.

Note that the concrete implementations are package-private and should not be created directly. If you are the maintainer of the package, you can add new implementation classes, and add them to the "check-list". The current algorithms do not support graphs with multiple edges (Multigraph / Pseudograph)

Since:

Jul 17, 2005

Author:

Assaf

See Also:

GraphIsomorphismInspector

Field Summary

Fields

Modifier and Type	Field and Description
static int	GRAPH_TYPE_ARBITRARY
static int	GRAPH_TYPE_MULTIGRAPH
static int	GRAPH_TYPE_PLANAR
static int	GRAPH_TYPE_TREE

Constructor Summary

Constructors

Constructor and Description
AdaptiveIsomorphismInspectorFactory()

Method Summary

Modifier and Type	Method and Description
protected static void	assertUnsupportedGraphTypes(Graph g) Checks if one of the graphs is from unsupported graph type and throws IllegalArgumentException if it is.
protected static int	checkGraphsType(Graph graph1, Graph graph2)
protected static <V,E> GraphIsomorphismInspector	createAppropriateConcreteInspector(int graphType, Graph<V,E> graph1, Graph<V,E> graph2, EquivalenceComparator<V,Graph<V,E>> vertexChecker, EquivalenceComparator<E,Graph<V,E>> edgeChecker) Checks the graph type, and accordingly decides which type of concrete inspector class to create.
static <V,E> GraphIsomorphismInspector	createIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2) Creates a new inspector, letting this class determine what is the most efficient algorithm and using default equivalence comparators.
static <V,E> GraphIsomorphismInspector	createIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, EquivalenceComparator<V,Graph<V,E>> vertexChecker, EquivalenceComparator<E,Graph<V,E>> edgeChecker) Creates a new inspector, letting this class determine what is the most efficient algorithm.
static <V,E> GraphIsomorphismInspector	createIsomorphismInspectorByType(int type, Graph<V,E> graph1, Graph<V,E> graph2) Creates a new inspector for a particular graph type (planar / tree / other) using default equivalence comparators.
static <V,E> GraphIsomorphismInspector	createIsomorphismInspectorByType(int type, Graph<V,E> graph1, Graph<V,E> graph2, EquivalenceComparator<V,Graph<V,E>> vertexChecker, EquivalenceComparator<E,Graph<V,E>> edgeChecker) Creates a new inspector for a particular graph type (planar / tree / other).
protected static <V,E> GraphIsomorphismInspector	createTopologicalExhaustiveInspector(Graph<V,E> graph1, Graph<V,E> graph2, EquivalenceComparator<V,Graph<V,E>> vertexChecker, EquivalenceComparator<E,Graph<V,E>> edgeChecker)

Methods inherited from class java.lang.Object

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

Field Detail

GRAPH_TYPE_ARBITRARY

public static final int GRAPH_TYPE_ARBITRARY

See Also:

Constant Field Values

GRAPH_TYPE_PLANAR

public static final int GRAPH_TYPE_PLANAR

See Also:

Constant Field Values

GRAPH_TYPE_TREE

public static final int GRAPH_TYPE_TREE

See Also:

Constant Field Values

GRAPH_TYPE_MULTIGRAPH

public static final int GRAPH_TYPE_MULTIGRAPH

See Also:

Constant Field Values

Constructor Detail

AdaptiveIsomorphismInspectorFactory

public AdaptiveIsomorphismInspectorFactory()

Method Detail

createIsomorphismInspector

public static <V,E> GraphIsomorphismInspector createIsomorphismInspector(Graph<V,E> graph1,
                                                                         Graph<V,E> graph2,
                                                                         EquivalenceComparator<V,Graph<V,E>> vertexChecker,
                                                                         EquivalenceComparator<E,Graph<V,E>> edgeChecker)

Creates a new inspector, letting this class determine what is the most efficient algorithm.

Parameters:

graph1 -

graph2 -

vertexChecker - may be null

edgeChecker - may be null

createIsomorphismInspector

public static <V,E> GraphIsomorphismInspector createIsomorphismInspector(Graph<V,E> graph1,
                                                                         Graph<V,E> graph2)

Creates a new inspector, letting this class determine what is the most efficient algorithm and using default equivalence comparators.

same as calling createIsomorphismInspector(graph1,graph2,null,null);

Parameters:

graph1 -

graph2 -

createIsomorphismInspectorByType

public static <V,E> GraphIsomorphismInspector createIsomorphismInspectorByType(int type,
                                                                               Graph<V,E> graph1,
                                                                               Graph<V,E> graph2,
                                                                               EquivalenceComparator<V,Graph<V,E>> vertexChecker,
                                                                               EquivalenceComparator<E,Graph<V,E>> edgeChecker)

Creates a new inspector for a particular graph type (planar / tree / other).

Parameters:

type - - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX

graph1 -

graph2 -

vertexChecker - - can be null

edgeChecker - - can be null

createIsomorphismInspectorByType

public static <V,E> GraphIsomorphismInspector createIsomorphismInspectorByType(int type,
                                                                               Graph<V,E> graph1,
                                                                               Graph<V,E> graph2)

Creates a new inspector for a particular graph type (planar / tree / other) using default equivalence comparators.

same as calling createAppropriateConcreteInspector(graph1,graph2,null,null);

Parameters:

type - - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX

graph1 -

graph2 -

createAppropriateConcreteInspector

protected static <V,E> GraphIsomorphismInspector createAppropriateConcreteInspector(int graphType,
                                                                                    Graph<V,E> graph1,
                                                                                    Graph<V,E> graph2,
                                                                                    EquivalenceComparator<V,Graph<V,E>> vertexChecker,
                                                                                    EquivalenceComparator<E,Graph<V,E>> edgeChecker)

Checks the graph type, and accordingly decides which type of concrete inspector class to create. This implementation creates an exhaustive inspector without further tests, because no other implementations are available yet.

Parameters:

graph1 -

graph2 -

vertexChecker -

edgeChecker -

assertUnsupportedGraphTypes

protected static void assertUnsupportedGraphTypes(Graph g)
                                           throws IllegalArgumentException

Checks if one of the graphs is from unsupported graph type and throws IllegalArgumentException if it is. The current unsupported types are graphs with multiple-edges.

Parameters:

g -

Throws:

IllegalArgumentException

checkGraphsType

protected static int checkGraphsType(Graph graph1,
                                     Graph graph2)

createTopologicalExhaustiveInspector

protected static <V,E> GraphIsomorphismInspector createTopologicalExhaustiveInspector(Graph<V,E> graph1,
                                                                                      Graph<V,E> graph2,
                                                                                      EquivalenceComparator<V,Graph<V,E>> vertexChecker,
                                                                                      EquivalenceComparator<E,Graph<V,E>> edgeChecker)

Returns:

ExhaustiveInspector, where the equivalence comparator is chained with a topological comparator. This implementation uses: vertex degree size comparator