abstractexhaustiveisomorphisminspector.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.
 */
/* -----------------
 * AbstractExhaustiveIsomorphismInspector.java
 * -----------------
 * (C) Copyright 2005-2007, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: AbstractExhaustiveIsomorphismInspector.java 485 2006-06-26 09:12:14Z
 * perfecthash $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.isomorphism;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.experimental.equivalence.*;
import org.jgrapht.experimental.permutation.*;
import org.jgrapht.util.*;


/**
 * Abstract base for isomorphism inspectors which exhaustively test the possible
 * mappings between graphs. The current algorithms do not support graphs with
 * multiple edges (Multigraph / Pseudograph). For the maintainer: The reason is
 * the use of GraphOrdering which currently does not support all graph types.
 *
 * @author Assaf Lehr
 * @since May 20, 2005 ver5.3
 */
abstract class AbstractExhaustiveIsomorphismInspector<V, E>
    implements GraphIsomorphismInspector<IsomorphismRelation>
{
    //~ Static fields/initializers ---------------------------------------------

    public static EquivalenceComparator<Object, Object>
        edgeDefaultIsomorphismComparator =
            new UniformEquivalenceComparator<Object, Object>();
    public static EquivalenceComparator<Object, Object>
        vertexDefaultIsomorphismComparator =
            new UniformEquivalenceComparator<Object, Object>();

    //~ Instance fields --------------------------------------------------------

    protected EquivalenceComparator<? super E, ? super Graph<V, ? super E>>
        edgeComparator;
    protected EquivalenceComparator<? super V, ? super Graph<? super V, E>>
        vertexComparator;

    protected Graph<V, E> graph1;
    protected Graph<V, E> graph2;

    private PrefetchIterator<IsomorphismRelation> nextSupplier;

    // kept as member, to ease computations
    private GraphOrdering lableGraph1;
    private LinkedHashSet<V> graph1VertexSet;
    private LinkedHashSet<E> graph2EdgeSet;
    private CollectionPermutationIter<V> vertexPermuteIter;
    private Set<V> currVertexPermutation; // filled every iteration, used in the

    //~ Constructors -----------------------------------------------------------

    // result relation.

    /**
     * @param graph1
     * @param graph2
     * @param vertexChecker eq. group checker for vertexes. If null,
     * UniformEquivalenceComparator will be used as default (always return true)
     * @param edgeChecker eq. group checker for edges. If null,
     * UniformEquivalenceComparator will be used as default (always return true)
     */
    public AbstractExhaustiveIsomorphismInspector(
        Graph<V, E> graph1,
        Graph<V, E> graph2,

        // XXX hb 060128: FOllowing parameter may need Graph<? super V,? super
        // E>
        EquivalenceComparator<? super V, ? super Graph<? super V, ? super E>> vertexChecker,
        EquivalenceComparator<? super E, ? super Graph<? super V, ? super E>> edgeChecker)
    {
        this.graph1 = graph1;
        this.graph2 = graph2;

        if (vertexChecker != null) {
            this.vertexComparator = vertexChecker;
        } else {
            this.vertexComparator = vertexDefaultIsomorphismComparator;
        }

        // Unlike vertexes, edges have better performance, when not tested for
        // Equivalence, so if the user did not supply one, use null
        // instead of edgeDefaultIsomorphismComparator.

        if (edgeChecker != null) {
            this.edgeComparator = edgeChecker;
        }

        init();
    }

    /**
     * Constructor which uses the default comparators.
     *
     * @param graph1
     * @param graph2
     *
     * @see #AbstractExhaustiveIsomorphismInspector(Graph,Graph,EquivalenceComparator,EquivalenceComparator)
     */
    public AbstractExhaustiveIsomorphismInspector(
        Graph<V, E> graph1,
        Graph<V, E> graph2)
    {
        this(
            graph1,
            graph2,
            edgeDefaultIsomorphismComparator,
            vertexDefaultIsomorphismComparator);
    }

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

    /**
     * Inits needed data-structures , among them:
     * <li>LabelsGraph which is a created in the image of graph1
     * <li>vertexPermuteIter which is created after the vertexes were divided to
     * equivalence groups. This saves order-of-magnitude in performance, because
     * the number of possible permutations dramatically decreases.
     *
     * <p>for example: if the eq.group are even/odd - only two groups. A graph
     * with consist of 10 nodes of which 5 are even , 5 are odd , will need to
     * test 5!*5! (14,400) instead of 10! (3,628,800).
     *
     * <p>besides the EquivalenceComparator`s supplied by the user, we also use
     * predefined topological comparators.
     */
    private void init()
    {
        this.nextSupplier =
            new PrefetchIterator<IsomorphismRelation>(
                // XXX hb 280106: I don't understand this warning, yet :-)
                new NextFunctor());

        this.graph1VertexSet = new LinkedHashSet<V>(this.graph1.vertexSet());

        // vertexPermuteIter will be null, if there is no match
        this.vertexPermuteIter =
            createPermutationIterator(
                this.graph1VertexSet,
                this.graph2.vertexSet());

        this.lableGraph1 =
            new GraphOrdering<V, E>(
                this.graph1,
                this.graph1VertexSet,
                this.graph1.edgeSet());

        this.graph2EdgeSet = new LinkedHashSet<E>(this.graph2.edgeSet());
    }

    /**
     * Creates the permutation iterator for vertexSet2 . The subclasses may make
     * either cause it to depend on equality groups or use vertexSet1 for it.
     *
     * @param vertexSet1 [i] may be reordered
     * @param vertexSet2 [i] may not.
     *
     * @return permutation iterator
     */
    protected abstract CollectionPermutationIter<V> createPermutationIterator(
        Set<V> vertexSet1,
        Set<V> vertexSet2);

    /**
     * <p>1. Creates a LabelsGraph of graph1 which will serve as a source to all
     * the comparisons which will follow.
     *
     * <p>2. extract the edge array of graph2; it will be permanent too.
     *
     * <p>3. for each permutation of the vertexes of graph2, test :
     *
     * <p>3.1. vertices
     *
     * <p>3.2. edges (in labelsgraph)