directedacyclicgraph.java

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

     * detection
     *
     * @throws CycleFoundException if a cycle is discovered
     */
    private void dfsF(
        V vertex,
        Set<V> df,
        Visited visited,
        Region affectedRegion)
        throws CycleFoundException
    {
        int topoIndex = topoOrderMap.getTopologicalIndex(vertex);

        // Assumption: vertex is in the AR and so it will be in visited
        visited.setVisited(topoIndex);

        df.add(vertex);

        for (E outEdge : outgoingEdgesOf(vertex)) {
            V nextVertex = getEdgeTarget(outEdge);
            Integer nextVertexTopoIndex =
                topoOrderMap.getTopologicalIndex(nextVertex);

            if (nextVertexTopoIndex.intValue() == affectedRegion.finish) {
                // reset visited
                try {
                    for (V visitedVertex : df) {
                        visited.clearVisited(
                            topoOrderMap.getTopologicalIndex(visitedVertex));
                    }
                } catch (UnsupportedOperationException e) {
                    // okay, fine, some implementations (ones that automatically
                    // clear themselves out) don't work this way
                }
                throw new CycleFoundException();
            }

            // note, order of checks is important as we need to make sure the
            // vertex is in the affected region before we check its visited
            // status (otherwise we will be causing an
            // ArrayIndexOutOfBoundsException).
            if (affectedRegion.isIn(nextVertexTopoIndex)
                && !visited.getVisited(nextVertexTopoIndex))
            {
                dfsF(nextVertex, df, visited, affectedRegion); // recurse
            }
        }
    }

    /**
     * Depth first search backward, building up the set (db) of back-connected
     * vertices in the Affected Region
     *
     * @param vertex the vertex being visited
     * @param db the set we are populating with back-connected vertices in the
     * AR
     * @param visited
     * @param topoIndexMap
     */
    private void dfsB(
        V vertex,
        Set<V> db,
        Visited visited,
        Region affectedRegion)
    {
        // Assumption: vertex is in the AR and so we will get a topoIndex from
        // the map
        int topoIndex = topoOrderMap.getTopologicalIndex(vertex);
        visited.setVisited(topoIndex);

        db.add(vertex);

        for (E inEdge : incomingEdgesOf(vertex)) {
            V previousVertex = getEdgeSource(inEdge);
            Integer previousVertexTopoIndex =
                topoOrderMap.getTopologicalIndex(previousVertex);

            // note, order of checks is important as we need to make sure the
            // vertex is in the affected region before we check its visited
            // status (otherwise we will be causing an
            // ArrayIndexOutOfBoundsException).
            if (affectedRegion.isIn(previousVertexTopoIndex)
                && !visited.getVisited(previousVertexTopoIndex))
            {
                // if prevousVertexTopoIndex != null, the vertex is in the
                // Affected Region according to our topoIndexMap

                dfsB(previousVertex, db, visited, affectedRegion);
            }
        }
    }

    @SuppressWarnings("unchecked")
    private void reorder(Set<V> df, Set<V> db, Visited visited)
    {
        List<V> topoDf = new ArrayList<V>(df);
        List<V> topoDb = new ArrayList<V>(db);

        Collections.sort(topoDf, topoComparator);
        Collections.sort(topoDb, topoComparator);

        // merge these suckers together in topo order

        SortedSet<Integer> availableTopoIndices = new TreeSet<Integer>();

        // we have to cast to the generic type, can't do "new V[size]" in java
        // 5;
        V [] bigL = (V []) new Object[df.size() + db.size()];
        int lIndex = 0; // this index is used for the sole purpose of pushing
                        // into

        // the correct index of bigL

        // assume (for now) that we are resetting visited
        boolean clearVisited = true;

        for (V vertex : topoDb) {
            Integer topoIndex = topoOrderMap.getTopologicalIndex(vertex);

            // add the available indices to the set
            availableTopoIndices.add(topoIndex);

            bigL[lIndex++] = vertex;

            if (clearVisited) { // reset visited status if supported
                try {
                    visited.clearVisited(topoIndex);
                } catch (UnsupportedOperationException e) {
                    clearVisited = false;
                }
            }
        }

        for (V vertex : topoDf) {
            Integer topoIndex = topoOrderMap.getTopologicalIndex(vertex);

            // add the available indices to the set
            availableTopoIndices.add(topoIndex);
            bigL[lIndex++] = vertex;

            if (clearVisited) { // reset visited status if supported
                try {
                    visited.clearVisited(topoIndex);
                } catch (UnsupportedOperationException e) {
                    clearVisited = false;
                }
            }
        }

        lIndex = 0; // reusing lIndex
        for (Integer topoIndex : availableTopoIndices) {
            // assign the indexes to the elements of bigL in order
            V vertex = bigL[lIndex++]; // note the post-increment
            topoOrderMap.putVertex(topoIndex, vertex);
        }
    }

    //~ Inner Interfaces -------------------------------------------------------

    /**
     * For performance tuning, an interface for storing the topological ordering
     *
     * @author gilesp
     */
    public interface TopoOrderMapping<V>
        extends Serializable
    {
        /**
         * add a vertex at the given topological index.
         *
         * @param index
         * @param vertex
         */
        public void putVertex(Integer index, V vertex);

        /**
         * get the vertex at the given topological index.
         *
         * @param index
         *
         * @return
         */
        public V getVertex(Integer index);

        /**
         * get the topological index of the given vertex.
         *
         * @param vertex
         *
         * @return the index that the vertex is at, or null if the vertex isn't
         * in the topological ordering
         */
        public Integer getTopologicalIndex(V vertex);

        /**
         * remove the given vertex from the topological ordering
         *
         * @param vertex
         *
         * @return the index that the vertex was at, or null if the vertex
         * wasn't in the topological ordering
         */
        public Integer removeVertex(V vertex);

        /**
         * remove all vertices from the topological ordering
         */
        public void removeAllVertices();
    }

    public interface TopoOrderMappingFactory<V>
    {
        public TopoOrderMapping<V> getTopoOrderMapping();
    }

    /**
     * this interface allows specification of a strategy for marking vertices as
     * visited (based on their topological index, so the vertex type isn't part
     * of the interface).
     */
    public interface Visited
    {
        /**
         * mark the given topological index as visited
         *
         * @param index the topological index
         */
        public void setVisited(int index);

        /**
         * has the given topological index been visited?
         *
         * @param index the topological index
         */
        public boolean getVisited(int index);

        /**
         * Clear the visited state of the given topological index
         *
         * @param index
         *
         * @throws UnsupportedOperationException if the implementation doesn't
         * support (or doesn't need) clearance. For example, if the factory
         * vends a new instance every time, it is a waste of cycles to clear the
         * state after the search of the Affected Region is done, so an
         * UnsupportedOperationException *should* be thrown.
         */
        public void clearVisited(int index)
            throws UnsupportedOperationException;
    }

    /**
     * interface for a factory that vends Visited implementations
     *
     * @author gilesp
     */
    public interface VisitedFactory
        extends Serializable
    {
        public Visited getInstance(Region affectedRegion);
    }

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

    /**
     * Note, this is a lazy and incomplete implementation, with assumptions that
     * inputs are in the given topoIndexMap
     *
     * @param <V>
     *
     * @author gilesp
     */
    private static class TopoComparator<V>
        implements Comparator<V>,
            Serializable
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private TopoOrderMapping<V> topoOrderMap;

        public TopoComparator(TopoOrderMapping<V> topoOrderMap)
        {
            this.topoOrderMap = topoOrderMap;
        }

        public int compare(V o1, V o2)
        {
            return topoOrderMap.getTopologicalIndex(o1).compareTo(
                topoOrderMap.getTopologicalIndex(o2));
        }
    }

    /**
     * a dual HashMap implementation
     *
     * @author gilesp
     */
    private class TopoVertexBiMap
        implements TopoOrderMapping<V>,
            TopoOrderMappingFactory<V>
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final Map<Integer, V> topoToVertex = new HashMap<Integer, V>();
        private final Map<V, Integer> vertexToTopo = new HashMap<V, Integer>();

        public void putVertex(Integer index, V vertex)
        {
            topoToVertex.put(index, vertex);
            vertexToTopo.put(vertex, index);
        }

        public V getVertex(Integer index)
        {
            return topoToVertex.get(index);
        }

        public Integer getTopologicalIndex(V vertex)
        {
            Integer topoIndex = vertexToTopo.get(vertex);
            return topoIndex;
        }

        public Integer removeVertex(V vertex)
        {
            Integer topoIndex = vertexToTopo.remove(vertex);
            if (topoIndex != null) {
                topoToVertex.remove(topoIndex);
            }
            return topoIndex;
        }

        public void removeAllVertices()
        {
            vertexToTopo.clear();
            topoToVertex.clear();
        }

        public TopoOrderMapping<V> getTopoOrderMapping()
        {
            return this;
        }
    }

    /**
     * For performance and flexibility uses an ArrayList for topological index
     * to vertex mapping, and a HashMap for vertex to topological index mapping.
     *
     * @author gilesp
     */
    public class TopoVertexMap
        implements TopoOrderMapping<V>,
            TopoOrderMappingFactory<V>
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final List<V> topoToVertex = new ArrayList<V>();
        private final Map<V, Integer> vertexToTopo = new HashMap<V, Integer>();

        public void putVertex(Integer index, V vertex)
        {
            int translatedIndex = translateIndex(index);

            // grow topoToVertex as needed to accommodate elements
            while ((translatedIndex + 1) > topoToVertex.size()) {
                topoToVertex.add(null);
            }

            topoToVertex.set(translatedIndex, vertex);
            vertexToTopo.put(vertex, index);
        }

        public V getVertex(Integer index)
        {
            return topoToVertex.get(translateIndex(index));
        }

        public Integer getTopologicalIndex(V vertex)
        {
            return vertexToTopo.get(vertex);
        }

        public Integer removeVertex(V vertex)
        {
            Integer topoIndex = vertexToTopo.remove(vertex);
            if (topoIndex != null) {
                topoToVertex.set(translateIndex(topoIndex), null);
            }
            return topoIndex;
        }

        public void removeAllVertices()
        {
            vertexToTopo.clear();