directedacyclicgraphtest.java

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

        int trialsPerConfiguration = 10;
        int maxVertices = 1024;
        int maxConnectednessFactor = 4;

        for (
            int numVertices = 1024;
            numVertices <= maxVertices;
            numVertices *= 2)
        {
            for (
                int connectednessFactor = 1;
                (connectednessFactor <= maxConnectednessFactor)
                && (connectednessFactor < (numVertices - 1));
                connectednessFactor *= 2)
            {
                long dynamicDagTime = 0;
                long staticDagTime = 0;

                for (int seed = 0; seed < trialsPerConfiguration; seed++) { // test with random graph configurations
                    setUpWithSeed(
                        numVertices,
                        numVertices * connectednessFactor,
                        seed);

                    DirectedAcyclicGraph<Long, DefaultEdge> dag =
                        new DirectedAcyclicGraph<Long, DefaultEdge>(
                            DefaultEdge.class);

                    long dynamicOpStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        dag.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        dag.addEdge(edgeSource, edgeTarget);
                    }

                    dynamicDagTime += System.nanoTime() - dynamicOpStart;

                    SimpleDirectedGraph<Long, DefaultEdge> compareGraph =
                        new SimpleDirectedGraph<Long, DefaultEdge>(
                            DefaultEdge.class);

                    long staticOpStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        compareGraph.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        DefaultEdge compareEdge =
                            compareGraph.addEdge(edgeSource, edgeTarget);
                        CycleDetector<Long, DefaultEdge> cycleDetector =
                            new CycleDetector<Long, DefaultEdge>(compareGraph);

                        boolean cycleDetected = cycleDetector.detectCycles();

                        if (cycleDetected) {
                            // remove the edge from the compareGraph
                            compareGraph.removeEdge(compareEdge);
                        }
                    }

                    staticDagTime += System.nanoTime() - staticOpStart;
                }

                System.out.println(
                    "vertices = " + numVertices + "  connectednessFactor = "
                    + connectednessFactor + "  trialsPerConfiguration = "
                    + trialsPerConfiguration);
                System.out.println(
                    "total static DAG time   =  " + staticDagTime + " ns");
                System.out.println(
                    "total dynamic DAG time  =  " + dynamicDagTime + " ns");
                System.out.println();
            }
        }
    }

    /**
     * A somewhat frivolous test of the performance difference between doing a
     * full cycle detection (non-dynamic algorithm) for each edge added versus
     * the dynamic algorithm used by DirectedAcyclicGraph.
     */
    public void _testVisitedImplementationPerformance()
    {
        int trialsPerConfiguration = 10;
        int maxVertices = 1024;
        int maxConnectednessFactor = 4;

        for (
            int numVertices = 64;
            numVertices <= maxVertices;
            numVertices *= 2)
        {
            for (
                int connectednessFactor = 1;
                (connectednessFactor <= maxConnectednessFactor)
                && (connectednessFactor < (numVertices - 1));
                connectednessFactor *= 2)
            {
                long arrayDagTime = 0;
                long arrayListDagTime = 0;
                long hashSetDagTime = 0;
                long bitSetDagTime = 0;

                for (int seed = 0; seed < trialsPerConfiguration; seed++) { // test with random graph configurations
                    setUpWithSeed(
                        numVertices,
                        numVertices * connectednessFactor,
                        seed);

                    DirectedAcyclicGraph<Long, DefaultEdge> arrayDag =
                        new DirectedAcyclicGraph<Long, DefaultEdge>(
                            DefaultEdge.class,
                            new DirectedAcyclicGraph.VisitedArrayImpl(),
                            null);
                    DirectedAcyclicGraph<Long, DefaultEdge> arrayListDag =
                        new DirectedAcyclicGraph<Long, DefaultEdge>(
                            DefaultEdge.class,
                            new DirectedAcyclicGraph.VisitedArrayListImpl(),
                            null);
                    DirectedAcyclicGraph<Long, DefaultEdge> hashSetDag =
                        new DirectedAcyclicGraph<Long, DefaultEdge>(
                            DefaultEdge.class,
                            new DirectedAcyclicGraph.VisitedHashSetImpl(),
                            null);
                    DirectedAcyclicGraph<Long, DefaultEdge> bitSetDag =
                        new DirectedAcyclicGraph<Long, DefaultEdge>(
                            DefaultEdge.class,
                            new DirectedAcyclicGraph.VisitedBitSetImpl(),
                            null);

                    long arrayStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        arrayDag.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        try {
                            arrayDag.addDagEdge(edgeSource, edgeTarget);
                        } catch (DirectedAcyclicGraph.CycleFoundException e) {
                            // okay
                        }
                    }

                    arrayDagTime += System.nanoTime() - arrayStart;

                    long arrayListStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        arrayListDag.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        try {
                            arrayListDag.addDagEdge(edgeSource, edgeTarget);
                        } catch (DirectedAcyclicGraph.CycleFoundException e) {
                            // okay
                        }
                    }

                    arrayListDagTime += System.nanoTime() - arrayListStart;

                    long hashSetStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        hashSetDag.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        try {
                            hashSetDag.addDagEdge(edgeSource, edgeTarget);
                        } catch (DirectedAcyclicGraph.CycleFoundException e) {
                            // okay
                        }
                    }

                    hashSetDagTime += System.nanoTime() - hashSetStart;

                    long bitSetStart = System.nanoTime();

                    for (Long vertex : sourceGraph.vertexSet()) {
                        bitSetDag.addVertex(vertex);
                    }

                    for (DefaultEdge edge : sourceGraph.edgeSet()) {
                        Long edgeSource = sourceGraph.getEdgeSource(edge);
                        Long edgeTarget = sourceGraph.getEdgeTarget(edge);

                        try {
                            bitSetDag.addDagEdge(edgeSource, edgeTarget);
                        } catch (DirectedAcyclicGraph.CycleFoundException e) {
                            // okay
                        }
                    }

                    bitSetDagTime += System.nanoTime() - bitSetStart;
                }

                System.out.println(
                    "vertices = " + numVertices + "  connectednessFactor = "
                    + connectednessFactor + "  trialsPerConfiguration = "
                    + trialsPerConfiguration);
                System.out.println(
                    "total array time       =  " + arrayDagTime + " ns");
                System.out.println(
                    "total ArrayList time   =  " + arrayListDagTime + " ns");
                System.out.println(
                    "total HashSet time     =  " + hashSetDagTime + " ns");
                System.out.println(
                    "total BitSet time     =  " + bitSetDagTime + " ns");
                System.out.println();
            }
        }
    }

    //~ Inner Classes ----------------------------------------------------------

    private static class LongVertexFactory
        implements VertexFactory<Long>
    {
        private long nextVertex = 0;

        public Long createVertex()
        {
            return nextVertex++;
        }
    }

    // it is nice for tests to be easily repeatable, so we use a graph generator
    // that we can seed for specific configurations
    private static class RepeatableRandomGraphGenerator<V, E>
        extends RandomGraphGenerator<V, E>
    {
        public RepeatableRandomGraphGenerator(
            int vertices,
            int edges,
            long seed)
        {
            super(vertices, edges);
            randomizer = new Random(seed);
        }

        @Override public void generateGraph(
            Graph<V, E> graph,
            VertexFactory<V> vertexFactory,
            Map<String, V> namedVerticesMap)
        {
            List<V> vertices = new ArrayList<V>(numOfVertexes);
            Set<Integer> edgeGeneratorIds = new HashSet<Integer>();

            for (int i = 0; i < numOfVertexes; i++) {
                V vertex = vertexFactory.createVertex();
                vertices.add(vertex);
                graph.addVertex(vertex);
            }

            for (int i = 0; i < numOfEdges; i++) {
                Integer edgeGeneratorId;
                do {
                    edgeGeneratorId =
                        randomizer.nextInt(numOfVertexes * (numOfVertexes - 1));
                } while (edgeGeneratorIds.contains(edgeGeneratorId));

                int fromVertexId = edgeGeneratorId / numOfVertexes;
                int toVertexId = edgeGeneratorId % (numOfVertexes - 1);
                if (toVertexId >= fromVertexId) {
                    ++toVertexId;
                }

                try {
                    graph.addEdge(
                        vertices.get(fromVertexId),
                        vertices.get(toVertexId));
                } catch (IllegalArgumentException e) {
                    // okay, that's fine; omit cycle
                }
            }
        }
    }
}

// End DirectedAcyclicGraphTest.java