adaptiveisomorphisminspectorfactory.java

使用Java开发的图论算法的包

/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2007, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -----------------
 * AdaptiveIsomorphismInspectorFactory.java
 * -----------------
 * (C) Copyright 2005-2007, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: AdaptiveIsomorphismInspectorFactory.java 485 2006-06-26 09:12:14Z
 * perfecthash $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.isomorphism;

import org.jgrapht.*;
import org.jgrapht.experimental.equivalence.*;
import org.jgrapht.graph.*;


/**
 * This class serves as a factory for GraphIsomorphismInspector concrete
 * implementations. It can be used in two ways:
 * <li>You can can let this class to determine what is the most efficient
 * algorithm for your graph.
 * <li>You can specify the type of your graph (planar / tree / other) and save
 * this class the graph-checking time.
 *
 * <p>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)
 *
 * @author Assaf
 * @see GraphIsomorphismInspector
 * @since Jul 17, 2005
 */
public class AdaptiveIsomorphismInspectorFactory
{
    //~ Static fields/initializers ---------------------------------------------

    public static final int GRAPH_TYPE_ARBITRARY = 0;
    public static final int GRAPH_TYPE_PLANAR = 1;
    public static final int GRAPH_TYPE_TREE = 2;
    public static final int GRAPH_TYPE_MULTIGRAPH = 3;

    //~ Methods ----------------------------------------------------------------

    /**
     * Creates a new inspector, letting this class determine what is the most
     * efficient algorithm.
     *
     * @param graph1
     * @param graph2
     * @param vertexChecker may be null
     * @param edgeChecker may be null
     */
    public static <V, E> GraphIsomorphismInspector createIsomorphismInspector(
        Graph<V, E> graph1,
        Graph<V, E> graph2,
        EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
        EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
    {
        int graphType = checkGraphsType(graph1, graph2);
        return createAppropriateConcreteInspector(
            graphType,
            graph1,
            graph2,
            vertexChecker,
            edgeChecker);
    }

    /**
     * Creates a new inspector, letting this class determine what is the most
     * efficient algorithm and using default equivalence comparators.
     *
     * <p>same as calling createIsomorphismInspector(graph1,graph2,null,null);
     *
     * @param graph1
     * @param graph2
     */
    public static <V, E> GraphIsomorphismInspector createIsomorphismInspector(
        Graph<V, E> graph1,
        Graph<V, E> graph2)
    {
        return createIsomorphismInspector(graph1, graph2, null, null);
    }

    /**
     * Creates a new inspector for a particular graph type (planar / tree /
     * other).
     *
     * @param type - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX
     * @param graph1
     * @param graph2
     * @param vertexChecker - can be null
     * @param edgeChecker - can be null
     */
    public static <V, E> GraphIsomorphismInspector
    createIsomorphismInspectorByType(
        int type,
        Graph<V, E> graph1,
        Graph<V, E> graph2,
        EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
        EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
    {
        return createAppropriateConcreteInspector(
            type,
            graph1,
            graph2,
            vertexChecker,
            edgeChecker);
    }

    /**
     * Creates a new inspector for a particular graph type (planar / tree /
     * other) using default equivalence comparators.
     *
     * <p>same as calling
     * createAppropriateConcreteInspector(graph1,graph2,null,null);
     *
     * @param type - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX
     * @param graph1
     * @param graph2
     */
    public static <V, E> GraphIsomorphismInspector
    createIsomorphismInspectorByType(
        int type,
        Graph<V, E> graph1,
        Graph<V, E> graph2)
    {
        return createAppropriateConcreteInspector(
            type,
            graph1,
            graph2,
            null,
            null);
    }

    /**
     * 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.
     *
     * @param graph1
     * @param graph2
     * @param vertexChecker
     * @param edgeChecker
     */
    protected static <V, E> GraphIsomorphismInspector
    createAppropriateConcreteInspector(
        int graphType,
        Graph<V, E> graph1,
        Graph<V, E> graph2,
        EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
        EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
    {
        assertUnsupportedGraphTypes(graph1);
        assertUnsupportedGraphTypes(graph2);
        GraphIsomorphismInspector currentInspector = null;

        switch (graphType) {
        case GRAPH_TYPE_PLANAR:
        case GRAPH_TYPE_TREE:
        case GRAPH_TYPE_ARBITRARY:
            currentInspector =
                createTopologicalExhaustiveInspector(
                    graph1,
                    graph2,
                    vertexChecker,
                    edgeChecker);
            break;

        default:

            throw new IllegalArgumentException(
                "The type was not one of the supported types.");
        }
        return currentInspector;
    }

    /**
     * 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.
     *
     * @param graph1
     * @param graph2
     *
     * @throws IllegalArgumentException
     */
    protected static void assertUnsupportedGraphTypes(Graph g)
        throws IllegalArgumentException
    {
        if ((g instanceof Multigraph)
            || (g instanceof DirectedMultigraph)
            || (g instanceof Pseudograph))
        {
            throw new IllegalArgumentException(
                "graph type not supported for the graph" + g);
        }
    }

    protected static int checkGraphsType(Graph graph1, Graph graph2)
    {
        return GRAPH_TYPE_ARBITRARY;
    }

    /**
     * @return ExhaustiveInspector, where the equivalence comparator is chained
     * with a topological comparator. This implementation uses:
     * <li>vertex degree size comparator
     */
    @SuppressWarnings("unchecked")
    protected static <V, E> GraphIsomorphismInspector
    createTopologicalExhaustiveInspector(
        Graph<V, E> graph1,
        Graph<V, E> graph2,
        EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
        EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
    {
        VertexDegreeEquivalenceComparator<V, E> degreeComparator =
            new VertexDegreeEquivalenceComparator<V, E>();
        EquivalenceComparatorChain<V, Graph<V, E>> vertexChainedChecker =
            new EquivalenceComparatorChainBase<V, Graph<V, E>>(
                degreeComparator);
        vertexChainedChecker.appendComparator(vertexChecker);

        GraphIsomorphismInspector inspector =

            // FIXME hb060208 I don't understand how to generify this, yet
            new EquivalenceIsomorphismInspector(
                graph1,
                graph2,
                vertexChainedChecker,
                edgeChecker);
        return inspector;
    }
}

// End AdaptiveIsomorphismInspectorFactory.java