directedacyclicgraph.java

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

/* ==========================================
 * 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-2008, 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.
 */
/* -------------------
 * DirectedAcyclicGraph.java
 * -------------------
 * (C) Copyright 2008-2008, by Peter Giles and Contributors.
 *
 * Original Author:  Peter Giles
 * Contributor(s):   John V. Sichi
 *
 * $Id: DirectedAcyclicGraph.java 637 2008-09-28 22:23:11Z perfecthash $
 *
 * Changes
 * -------
 * 17-Mar-2008 : Initial revision (PG);
 * 23-Aug-2008 : Added VisitedBitSetImpl and made it the default (JVS);
 *
 */
package org.jgrapht.experimental.dag;

import java.io.*;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;


/**
 * <p>DirectedAcyclicGraph implements a DAG that can be modified (vertices &amp;
 * edges added and removed), is guaranteed to remain acyclic, and provides fast
 * topological order iteration.</p>
 *
 * <p>This is done using a dynamic topological sort which is based on the
 * algorithm PK described in "D. Pearce &amp; P. Kelly, 2007: A Dynamic
 * Topological Sort Algorithm for Directed Acyclic Graphs", (see <a
 * href="http://www.mcs.vuw.ac.nz/~djp/files/PK-JEA07.pdf">Paper</a> or <a
 * href="http://doi.acm.org/10.1145/1187436.1210590">ACM link</a> for details).
 * </p>
 *
 * <p>The implementation differs from the algorithm specified in the above paper
 * in some ways, perhaps most notably in that the topological ordering is stored
 * by default using two HashMaps, which will have some effects on runtime, but
 * also allows for vertex addition and removal, and other operations which are
 * helpful for manipulating or combining DAGs. This storage mechanism is
 * pluggable for subclassers.</p>
 *
 * <p>This class makes no claims to thread safety, and concurrent usage from
 * multiple threads will produce undefined results.</p>
 *
 * @author Peter Giles, [e-mail]
 */
public class DirectedAcyclicGraph<V, E>
    extends SimpleDirectedGraph<V, E>
{
    //~ Static fields/initializers ---------------------------------------------

    private static final long serialVersionUID = 4522128427004938150L;

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

    private TopoComparator<V> topoComparator;

    private TopoOrderMapping<V> topoOrderMap;

    private int maxTopoIndex = 0;
    private int minTopoIndex = 0;

    // this update count is used to keep internal topological iterators honest
    private long topologyUpdateCount = 0;

    /**
     * Pluggable VisitedFactory implementation
     */
    private VisitedFactory visitedFactory = new VisitedBitSetImpl();

    /**
     * Pluggable TopoOrderMappingFactory implementation
     */
    private TopoOrderMappingFactory<V> topoOrderFactory = new TopoVertexBiMap();

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

    public DirectedAcyclicGraph(Class<? extends E> arg0)
    {
        super(arg0);
        initialize();
    }

    DirectedAcyclicGraph(
        Class<? extends E> arg0,
        VisitedFactory visitedFactory,
        TopoOrderMappingFactory<V> topoOrderFactory)
    {
        super(arg0);
        if (visitedFactory != null) {
            this.visitedFactory = visitedFactory;
        }
        if (topoOrderFactory != null) {
            this.topoOrderFactory = topoOrderFactory;
        }
        initialize();
    }

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

    /**
     * set the topoOrderMap based on the current factory, and create the
     * comparator;
     */
    private void initialize()
    {
        topoOrderMap = topoOrderFactory.getTopoOrderMapping();
        topoComparator = new TopoComparator<V>(topoOrderMap);
    }

    /**
     * iterator will traverse the vertices in topological order, meaning that
     * for a directed graph G = (V,E), if there exists a path from vertex va to
     * vertex vb then va is guaranteed to come before vertex vb in the iteration
     * order.
     *
     * @return an iterator that will traverse the graph in topological order
     */
    public Iterator<V> iterator()
    {
        return new TopoIterator();
    }

    /**
     * adds the vertex if it wasn't already in the graph, and puts it at the top
     * of the internal topological vertex ordering
     */
    @Override public boolean addVertex(V v)
    {
        boolean added = super.addVertex(v);

        if (added) {
            // add to the top
            ++maxTopoIndex;
            topoOrderMap.putVertex(maxTopoIndex, v);

            ++topologyUpdateCount;
        }

        return added;
    }

    /**
     * adds the vertex if it wasn't already in the graph, and puts it either at
     * the top or the bottom of the topological ordering, depending on the value
     * of addToTop. This may provide useful optimizations for merging
     * DirectedAcyclicGraphS that become connected.
     *
     * @param v
     * @param addToTop
     *
     * @return
     */
    public boolean addVertex(V v, boolean addToTop)
    {
        boolean added = super.addVertex(v);

        if (added) {
            int insertIndex;

            // add to the top
            if (addToTop) {
                insertIndex = ++maxTopoIndex;
            } else {
                insertIndex = --minTopoIndex;
            }
            topoOrderMap.putVertex(insertIndex, v);

            ++topologyUpdateCount;
        }
        return added;
    }

    /**
     * <p>Adds the given edge and updates the internal topological order for
     * consistency IFF
     *
     * <UL>
     * <li>there is not already an edge (fromVertex, toVertex) in the graph
     * <li>the edge does not induce a cycle in the graph
     * </ul>
     * </p>
     *
     * @return null if the edge is already in the graph, else the created edge
     * is returned
     *
     * @throws IllegalArgumentException If either fromVertex or toVertex is not
     * a member of the graph
     * @throws CycleFoundException if the edge would induce a cycle in the graph
     *
     * @see Graph#addEdge(Object, Object, Object)
     */
    public E addDagEdge(V fromVertex, V toVertex)
        throws CycleFoundException
    {
        Integer lb = topoOrderMap.getTopologicalIndex(toVertex);
        Integer ub = topoOrderMap.getTopologicalIndex(fromVertex);

        if ((lb == null) || (ub == null)) {
            throw new IllegalArgumentException(
                "vertices must be in the graph already!");
        }

        if (lb < ub) {
            Set<V> df = new HashSet<V>();
            Set<V> db = new HashSet<V>();

            // Discovery
            Region affectedRegion = new Region(lb, ub);
            Visited visited = visitedFactory.getInstance(affectedRegion);

            // throws CycleFoundException if there is a cycle
            dfsF(toVertex, df, visited, affectedRegion);

            dfsB(fromVertex, db, visited, affectedRegion);
            reorder(df, db, visited);
            ++topologyUpdateCount; // if we do a reorder, than the topology has
                                   // been updated
        }

        return super.addEdge(fromVertex, toVertex);
    }

    /**
     * identical to {@link #addDagEdge(Object, Object)}, except an unchecked
     * {@link IllegalArgumentException} is thrown if a cycle would have been
     * induced by this edge
     */
    @Override public E addEdge(V sourceVertex, V targetVertex)
    {
        E result = null;
        try {
            result = addDagEdge(sourceVertex, targetVertex);
        } catch (CycleFoundException e) {
            throw new IllegalArgumentException(e);
        }
        return result;
    }

    /**
     * <p>Adds the given edge and updates the internal topological order for
     * consistency IFF
     *
     * <UL>
     * <li>the given edge is not already a member of the graph
     * <li>there is not already an edge (fromVertex, toVertex) in the graph
     * <li>the edge does not induce a cycle in the graph
     * </ul>
     * </p>
     *
     * @return true if the edge was added to the graph
     *
     * @throws CycleFoundException if adding an edge (fromVertex, toVertex) to
     * the graph would induce a cycle.
     *
     * @see Graph#addEdge(Object, Object, Object)
     */
    public boolean addDagEdge(V fromVertex, V toVertex, E e)
        throws CycleFoundException
    {
        if (e == null) {
            throw new NullPointerException();
        } else if (containsEdge(e)) {
            return false;
        }

        Integer lb = topoOrderMap.getTopologicalIndex(toVertex);
        Integer ub = topoOrderMap.getTopologicalIndex(fromVertex);

        if ((lb == null) || (ub == null)) {
            throw new IllegalArgumentException(
                "vertices must be in the graph already!");
        }

        if (lb < ub) {
            Set<V> df = new HashSet<V>();
            Set<V> db = new HashSet<V>();

            // Discovery
            Region affectedRegion = new Region(lb, ub);
            Visited visited = visitedFactory.getInstance(affectedRegion);

            // throws CycleFoundException if there is a cycle
            dfsF(toVertex, df, visited, affectedRegion);

            dfsB(fromVertex, db, visited, affectedRegion);
            reorder(df, db, visited);
            ++topologyUpdateCount; // if we do a reorder, than the topology has
                                   // been updated
        }

        return super.addEdge(fromVertex, toVertex, e);
    }

    /**
     * identical to {@link #addDagEdge(Object, Object, Object)}, except an
     * unchecked {@link IllegalArgumentException} is thrown if a cycle would
     * have been induced by this edge
     */
    @Override public boolean addEdge(V sourceVertex, V targetVertex, E edge)
    {
        boolean result;
        try {
            result = addDagEdge(sourceVertex, targetVertex, edge);
        } catch (CycleFoundException e) {
            throw new IllegalArgumentException(e);
        }
        return result;
    }

    // note that this can leave holes in the topological ordering, which
    // (depending on the TopoOrderMap implementation) can degrade performance
    // for certain operations over time
    @Override public boolean removeVertex(V v)
    {
        boolean removed = super.removeVertex(v);

        if (removed) {
            Integer topoIndex = topoOrderMap.removeVertex(v);

            // contract minTopoIndex as we are able
            if (topoIndex == minTopoIndex) {
                while (
                    (minTopoIndex < 0)
                    && (null == topoOrderMap.getVertex(minTopoIndex)))
                {
                    ++minTopoIndex;
                }
            }

            // contract maxTopoIndex as we are able
            if (topoIndex == maxTopoIndex) {
                while (
                    (maxTopoIndex > 0)
                    && (null == topoOrderMap.getVertex(maxTopoIndex)))
                {
                    --maxTopoIndex;
                }
            }

            ++topologyUpdateCount;
        }

        return removed;
    }

    @Override public boolean removeAllVertices(Collection<? extends V> arg0)
    {
        boolean removed = super.removeAllVertices(arg0);

        topoOrderMap.removeAllVertices();

        maxTopoIndex = 0;
        minTopoIndex = 0;

        ++topologyUpdateCount;

        return removed;
    }

    /**
     * Depth first search forward, building up the set (df) of forward-connected
     * vertices in the Affected Region
     *
     * @param vertex the vertex being visited
     * @param df the set we are populating with forward connected vertices in
     * the Affected Region
     * @param visited a simple data structure that lets us know if we already
     * visited a node with a given topo index
     * @param topoIndexMap for quick lookups, a map from vertex to topo index in
     * the AR
     * @param ub the topo index of the original fromVertex -- used for cycle