org.jgrapht.experimental.isomorphism
Class AdaptiveIsomorphismInspectorFactory

java.lang.Object
  extended by 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:

  • You can can let this class to determine what is the most efficient algorithm for your graph.
  • 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
    static int GRAPH_TYPE_ARBITRARY
               
    static int GRAPH_TYPE_MULTIGRAPH
               
    static int GRAPH_TYPE_PLANAR
               
    static int GRAPH_TYPE_TREE
               
     
    Constructor Summary
    AdaptiveIsomorphismInspectorFactory()
               
     
    Method Summary
    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


  • Copyright © 2013. All rights reserved.