isomorphisminspectortest.java

来自「JAVA图论的算法包。用过觉得还不错」· Java 代码 · 共 641 行 · 第 1/2 页

/* ==========================================
 * 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.
 */
/* -----------------
 * IsomorphismInspectorTest.java
 * -----------------
 * (C) Copyright 2005-2007, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: IsomorphismInspectorTest.java 568 2007-09-30 00:12:18Z perfecthash $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.isomorphism;

import java.util.*;

import junit.framework.*;

import org.jgrapht.*;
import org.jgrapht.experimental.equivalence.*;
import org.jgrapht.experimental.isomorphism.comparators.*;
import org.jgrapht.generate.*;
import org.jgrapht.graph.*;


/**
 * @author Assaf
 * @since May 27, 2005
 */
public class IsomorphismInspectorTest
    extends TestCase
{
    //~ Constructors -----------------------------------------------------------

    /**
     * Constructor for IsomorphismInspectorTest.
     *
     * @param arg0
     */
    public IsomorphismInspectorTest(String arg0)
    {
        super(arg0);
    }

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

    /*
     * @see TestCase#setUp()
     */
    protected void setUp()
        throws Exception
    {
        super.setUp();
    }

    /**
     * Calls the same method with different (default) parameters
     * EqualityGroupChecker vertexChecker = null EqualityGroupChecker
     * edgeChecker = null
     */
    private void assertIsomorphic(
        Graph<Integer, DefaultEdge> [] graphs,
        boolean shouldTheyBeIsomorphic)
    {
        assertIsomorphic(graphs, shouldTheyBeIsomorphic, null, null);
    }

    @SuppressWarnings("unchecked")
    private void assertIsomorphic(
        Graph<Integer, DefaultEdge> [] graphs,
        boolean shouldTheyBeIsomorphic,
        EquivalenceComparator vertexChecker,
        EquivalenceComparator edgeChecker)
    {
        // System.out.println("\nassertIsomorphic:"+shouldTheyBeIsomorphic);
        Graph<Integer, DefaultEdge> g1 = graphs[0];
        Graph<Integer, DefaultEdge> g2 = graphs[1];

        // System.out.println("g1:"+g1);
        // System.out.println("g2:"+g2);
        // long beforeTime=System.currentTimeMillis();
        GraphIsomorphismInspector iso =
            AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(
                g1,
                g2,
                vertexChecker,
                edgeChecker);
        int counter = 0;
        while (iso.hasNext()) {
            IsomorphismRelation isioResult = (IsomorphismRelation) iso.next();

            if (false) {
                if (counter == 0) {
                    System.out.println(
                        "Graphs are isomorphic. Iterating over all options:");
                }
                System.out.println(counter + " : " + isioResult);
            }
            counter++;
        }

        // if (counter==0)
        // {
        // System.out.println("Graphs are NOT isomorphic.");
        // }
        // long deltaTime=System.currentTimeMillis()-beforeTime;
        // String timeDesc;
        // timeDesc= deltaTime<=10 ?  "<10ms [less than minimum measurement
        // time]": String.valueOf(deltaTime);
        // System.out.println("# Performence: Isomorphism check in
        // MiliSeconds:"+timeDesc);
        if (shouldTheyBeIsomorphic) {
            assertTrue(counter != 0);
        } else {
            assertTrue(counter == 0);
        }
    }

    @SuppressWarnings("unchecked")
    private void checkRelation(
        Graph<Integer, DefaultEdge> [] graphs,
        EquivalenceComparator vertexChecker,
        EquivalenceComparator edgeChecker)
    {
        Graph<Integer, DefaultEdge> g1 = graphs[0];
        Graph<Integer, DefaultEdge> g2 = graphs[1];

        GraphIsomorphismInspector iso =
            AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(
                g1,
                g2,
                vertexChecker,
                edgeChecker);
        IsomorphismRelation<Integer, DefaultEdge> isoResult;
        if (iso.hasNext()) {
            isoResult = (IsomorphismRelation) iso.next();

            Set<Integer> vertexSet = g1.vertexSet();
            for (
                Iterator<Integer> iter = vertexSet.iterator();
                iter.hasNext();)
            {
                Integer v1 = iter.next();
                Integer v2 = isoResult.getVertexCorrespondence(v1, true);
                if (false) {
                    System.out.println("Vertex relation " + v1 + " to " + v2);
                }
            }
            Set<DefaultEdge> edgeSet = g1.edgeSet();
            for (
                Iterator<DefaultEdge> iter = edgeSet.iterator();
                iter.hasNext();)
            {
                DefaultEdge e1 = iter.next();
                DefaultEdge e2 = isoResult.getEdgeCorrespondence(e1, true);
                if (false) {
                    System.out.println("Vertex relation " + e1 + " to " + e2);
                }
            }

            // if (counter==0)
            // {
            // System.out.println("Graphs are isomorphic. Iterating over all
            // options:");
            // }
            // System.out.println(counter+" : "+isioResult);

        }
    }

    @SuppressWarnings("unchecked")
    public void testWheelGraphAddRemoveParts()
    {
        final int NUM_OF_VERTEXES_IN_WHEEL = 6;
        final int FIRST_INTEGER_FOR_G2 = 13;

        Graph<Integer, DefaultEdge> g1 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        Graph<Integer, DefaultEdge> g2 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        WheelGraphGenerator<Integer, DefaultEdge> gen1 =
            new WheelGraphGenerator<Integer, DefaultEdge>(
                NUM_OF_VERTEXES_IN_WHEEL);
        gen1.generateGraph(g1, new IntegerVertexFactory(), null);

        // FIRST_INTEGER_FOR_G2-1 , cause first integer is always the next one.
        gen1.generateGraph(
            g2,
            new IntegerVertexFactory(FIRST_INTEGER_FOR_G2),
            null);
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            true);

        // In a wheel , the last vertex is the wheel center!
        g1.removeVertex(new Integer(NUM_OF_VERTEXES_IN_WHEEL)); // delete one vertex from g1
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            false);

        // for example: 10+4
        g2.removeVertex(
            new Integer(FIRST_INTEGER_FOR_G2
                + NUM_OF_VERTEXES_IN_WHEEL));
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            true);

        g1.removeEdge(new Integer(1), new Integer(2));
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            false);
    }

    @SuppressWarnings("unchecked")
    public void testLinear4vertexIsomorphicGraph()
    {
        Graph<Integer, DefaultEdge> g1 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        LinearGraphGenerator gen1 = new LinearGraphGenerator(4);
        gen1.generateGraph(g1, new IntegerVertexFactory(), null);

        Graph<Integer, DefaultEdge> g2 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        LinearGraphGenerator gen2 = new LinearGraphGenerator(4);
        gen2.generateGraph(g2, new IntegerVertexFactory(5), null); // start vertex from number 6
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            true);

        checkRelation(
            new Graph[] {
                g1,
                g2
            },
            null,
            null);
    }

    /**
     * Create two graphs which are topologically the same (same number of
     * vertexes and same edges connection), but the contents of the vertexes
     * belong to different eq. set. g1: 1-->2-->3-->4 g2: 2-->3-->4-->5 g3:
     * 3-->4-->5-->6 The eq-group-check is if the number is even or odd. So, g1
     * and g3 are isomorphic. g2 is not isomorphic to either of them.
     */
    @SuppressWarnings("unchecked")
    public void testLinear4vertexNonIsomorphicCauseOfVertexEqGroup()
    {
        LinearGraphGenerator<Integer, DefaultEdge> gen4 =
            new LinearGraphGenerator<Integer, DefaultEdge>(4);

        Graph<Integer, DefaultEdge> g1 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        gen4.generateGraph(g1, new IntegerVertexFactory(), null);

        Graph<Integer, DefaultEdge> g2 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        gen4.generateGraph(g2, new IntegerVertexFactory(1), null); // start vertex from number 2

        Graph<Integer, DefaultEdge> g3 =
            new DefaultDirectedGraph<Integer, DefaultEdge>(
                DefaultEdge.class);
        gen4.generateGraph(g3, new IntegerVertexFactory(2), null); // start vertex from number 3

        // first assert all are isomorphic (if vertexChecker is not used)
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            true);
        assertIsomorphic(
            new Graph[] {
                g2,