isomorphisminspectortest.java

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

                g3
            },
            true);
        assertIsomorphic(
            new Graph[] {
                g1,
                g3
            },
            true);

        // create a functor according to odd even
        EquivalenceComparator vertexEqChecker = new OddEvenGroupComparator();
        assertIsomorphic(
            new Graph[] {
                g1,
                g2
            },
            false,
            vertexEqChecker,
            null);
        assertIsomorphic(
            new Graph[] {
                g2,
                g3
            },
            false,
            vertexEqChecker,
            null);
        assertIsomorphic(
            new Graph[] {
                g1,
                g3
            },
            true,
            vertexEqChecker,
            null);
    }

    /**
     * Passes an EdgeComparator, which compares according to odd-even edge
     * weight. The generated graphs are: A-(12)->B-(10)->C-(5)->D
     * A-(10)->B-(18)->C-(3)->D A-(11)->B-(10)->C-(5)->D (the first here is odd)
     *
     * @author Assaf
     * @since Aug 12, 2005
     */
    @SuppressWarnings("unchecked")
    public void testEdgeComparator()
    {
        int LINEAR_GRAPH_VERTEX_NUM = 4;
        Graph [] graphsArray = new DirectedGraph[3];
        Character [] charArray =
            new Character[] {
                new Character('A'),
                new Character('B'),
                new Character('C'),
                new Character('D')
            };
        int [][] weigthsArray =
            new int[][] {
                {
                    12,
                    10,
                    5
                },
                {
                    10,
                    18,
                    3
                },
                {
                    11,
                    10,
                    5
                }
            };

        for (int i = 0; i < graphsArray.length; i++) {
            Graph<Character, DefaultEdge> currGraph =
                graphsArray[i] =
                    new DefaultDirectedWeightedGraph<Character,
                        DefaultWeightedEdge>(
                        DefaultWeightedEdge.class);
            for (int j = 0; j < LINEAR_GRAPH_VERTEX_NUM; j++) {
                currGraph.addVertex(charArray[j]);
            }

            // create the 3 edges with weights
            for (int j = 0; j < 3; j++) {
                Graphs.addEdge(
                    currGraph,
                    charArray[j],
                    charArray[j + 1],
                    weigthsArray[i][j]);
            }
        }

        // first assert all are isomorphic (if vertexChecker is not used)
        assertIsomorphic(new Graph[] { graphsArray[0], graphsArray[1] },
            true);
        assertIsomorphic(new Graph[] { graphsArray[0], graphsArray[2] },
            true);
        assertIsomorphic(new Graph[] { graphsArray[1], graphsArray[2] },
            true);

        // create a functor according to odd even
        EquivalenceComparator edgeEqChecker =
            new DirectedEdgeWeightOddEvenComparator(graphsArray[0]);
        assertIsomorphic(
            new Graph[] { graphsArray[0], graphsArray[1] },
            true,
            null,
            edgeEqChecker);
        assertIsomorphic(
            new Graph[] { graphsArray[0], graphsArray[2] },
            false,
            null,
            edgeEqChecker);
        assertIsomorphic(
            new Graph[] { graphsArray[1], graphsArray[2] },
            false,
            null,
            edgeEqChecker);
    }

    @SuppressWarnings("unchecked")
    private void assertIsomorphicStopAfterFirstMatch(
        Graph [] graphs,
        boolean assertActive,
        boolean shouldTheyBeIsomorphic,
        EquivalenceComparator vertexChecker,
        EquivalenceComparator edgeChecker)
    {
        if (assertActive) {
            System.out.println("\nassertIsomorphic:"
                + shouldTheyBeIsomorphic);
        }
        Graph g1 = graphs[0];
        Graph 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);
        boolean isoResult = iso.isIsomorphic();
        if (isoResult) {
            System.out.println("Graphs are isomorphic. ");
        } else {
            System.out.println("Graphs are NOT isomorphic.");
        }

        long deltaTime = System.currentTimeMillis() - beforeTime;
        String timeDesc;
        timeDesc =
            (deltaTime <= 10) ? "<10ms [less than minumun measurement time]"
            : String.valueOf(deltaTime);
        System.out.println(
            "# Performence: Isomorphism check in MiliSeconds:" + timeDesc);
        if (assertActive) {
            assertEquals(shouldTheyBeIsomorphic, isoResult);
        }
    }

    /**
     * Performance test with different number of vertex, edges. For each number
     * pair, 3 graphs are generated. The first two, using the same generator,
     * the third using a different generator. Note: the 1st and 2nd must be
     * isomorphic. The 3rd will most likely not be isomorphic , but on special
     * occasaions may be, so do not assert it. (example: empty graph, full mesh
     * , rare case that they are not real random). NOTE: RENAME TO testXXX to
     * make it work. It shows output and not assertions, so it cannot be used by
     * automatic tests.
     */
    @SuppressWarnings("unchecked")
    public void performanceTestOnRandomGraphs()
        throws Exception
    {
        final int [] numOfVertexesArray =
            new int[] {
                6,
                6,
                6,
                8,
                8,
                8,
                10,
                10,
                10,
                12,
                14,
                20,
                30,
                99
            };
        final int [] numOfEdgesArray =
            new int[] {
                0,
                4,
                12,
                1,
                15,
                54,
                0,
                40,
                90,
                130,
                50,
                79,
                30,
                234
            };

        // there will be two different generators. The first will be used for
        // 1st,2nd graph
        // the other for the3rd graph
        final int NUM_OF_GENERATORS = 2;
        RandomGraphGenerator [] genArray =
            new RandomGraphGenerator[NUM_OF_GENERATORS];

        String [] graphConctereClassesFullName =
            new String[] { // "org.jgrapht.graph.SimpleGraph" ,
                "org.jgrapht.graph.SimpleDirectedGraph",
                "org.jgrapht.graph.DefaultDirectedGraph",
                // "org.jgrapht.graph.Multigraph",
                // "org.jgrapht.graph.Pseudograph"
            };

        // 3 graphs. 1st,2nd must be isomorphic .3rd probably not iso.
        final int SIZE_OF_GENERATED_GRAPH_ARRAY = 3;

        // graphsArray rows are different graph types. Columns are few
        // instances of that type
        Graph [][] graphsArray =
            new Graph[graphConctereClassesFullName.length][SIZE_OF_GENERATED_GRAPH_ARRAY];

        Graph [] currIsoTestArray = new Graph[2];
        for (int testNum = 0; testNum < numOfVertexesArray.length; testNum++) {
            // recreate the graphs (empty)
            try {
                for (int i = 0; i < graphConctereClassesFullName.length; i++) {
                    for (int j = 0; j < SIZE_OF_GENERATED_GRAPH_ARRAY; j++) {
                        graphsArray[i][j] =
                            (Graph) Class.forName(
                                graphConctereClassesFullName[i]).newInstance();
                    }
                }
            } catch (Exception e) {
                throw new Exception("failed to initilized the graphs", e);
            }

            // create generators for the new vertex/edges number
            for (int i = 0; i < genArray.length; i++) {
                genArray[i] =
                    new RandomGraphGenerator(
                        numOfVertexesArray[testNum],
                        numOfEdgesArray[testNum]);
            }

            for (
                int graphType = 0;
                graphType < graphConctereClassesFullName.length;
                graphType++)
            {
                System.out.println(
                    "### numOfVertexes= " + numOfVertexesArray[testNum]);
                System.out.println(
                    "### numOfEdges= " + numOfEdgesArray[testNum]);
                System.out.println(
                    "######### Graph Type:"
                    + graphConctereClassesFullName[graphType]);
                System.out.println(
                    "# # # # # # # # # # # # # # # # # # # # # # # # # # # #");

                // 1st and 2nd from genArray[0]
                genArray[0].generateGraph(
                    graphsArray[graphType][0],
                    new IntegerVertexFactory(),
                    null);
                genArray[0].generateGraph(
                    graphsArray[graphType][1],
                    new IntegerVertexFactory(),
                    null);

                // 3rd from genArray[1]
                genArray[1].generateGraph(
                    graphsArray[graphType][2],
                    new IntegerVertexFactory(),
                    null);

                // now start testing
                currIsoTestArray[0] = graphsArray[graphType][0];
                currIsoTestArray[1] = graphsArray[graphType][1];

                assertIsomorphicStopAfterFirstMatch(
                    currIsoTestArray,
                    true,
                    true,
                    null,
                    null);

                // remember it is not a MUST - it can be true . DEGUG REASON
                // ONLY , and with care
                currIsoTestArray[1] = graphsArray[graphType][2];
                assertIsomorphicStopAfterFirstMatch(
                    currIsoTestArray,
                    false,
                    false,
                    null,
                    null);
            }
        }
    }
}

// End IsomorphismInspectorTest.java