directedacyclicgraph.java

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

            topoToVertex.clear();
        }

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

        /**
         * We translate the topological index to an ArrayList index. We have to
         * do this because topological indices can be negative, and we want to
         * do it because we can make better use of space by only needing an
         * ArrayList of size |AR|.
         *
         * @param unscaledIndex
         *
         * @return the ArrayList index
         */
        private final int translateIndex(int index)
        {
            if (index >= 0) {
                return 2 * index;
            }
            return -1 * ((index * 2) - 1);
        }
    }

    /**
     * Region is an *inclusive* range of indices. Esthetically displeasing, but
     * convenient for our purposes.
     *
     * @author gilesp
     */
    public static class Region
        implements Serializable
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        public final int start;
        public final int finish;

        public Region(int start, int finish)
        {
            if (start > finish) {
                throw new IllegalArgumentException(
                    "(start > finish): invariant broken");
            }
            this.start = start;
            this.finish = finish;
        }

        public int getSize()
        {
            return (finish - start) + 1;
        }

        public boolean isIn(int index)
        {
            return (index >= start) && (index <= finish);
        }
    }

    /**
     * This implementation is close to the performance of VisitedArrayListImpl,
     * with 1/8 the memory usage.
     *
     * @author perfecthash
     */
    public static class VisitedBitSetImpl
        implements Visited,
            VisitedFactory
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final BitSet visited = new BitSet();

        private Region affectedRegion;

        public Visited getInstance(Region affectedRegion)
        {
            this.affectedRegion = affectedRegion;

            return this;
        }

        public void setVisited(int index)
        {
            visited.set(translateIndex(index), true);
        }

        public boolean getVisited(int index)
        {
            return visited.get(translateIndex(index));
        }

        public void clearVisited(int index)
            throws UnsupportedOperationException
        {
            visited.clear(translateIndex(index));
        }

        /**
         * We translate the topological index to an ArrayList index. We have to
         * do this because topological indices can be negative, and we want to
         * do it because we can make better use of space by only needing an
         * ArrayList of size |AR|.
         *
         * @param unscaledIndex
         *
         * @return the ArrayList index
         */
        private int translateIndex(int index)
        {
            return index - affectedRegion.start;
        }
    }

    /**
     * This implementation seems to offer the best performance in most cases. It
     * grows the internal ArrayList as needed to be as large as |AR|, so it will
     * be more memory intensive than the HashSet implementation, and unlike the
     * Array implementation, it will hold on to that memory (it expands, but
     * never contracts).
     *
     * @author gilesp
     */
    public static class VisitedArrayListImpl
        implements Visited,
            VisitedFactory
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final List<Boolean> visited = new ArrayList<Boolean>();

        private Region affectedRegion;

        public Visited getInstance(Region affectedRegion)
        {
            // Make sure visited is big enough
            int minSize = (affectedRegion.finish - affectedRegion.start) + 1;
            /* plus one because the region range is inclusive of both indices */

            while (visited.size() < minSize) {
                visited.add(Boolean.FALSE);
            }

            this.affectedRegion = affectedRegion;

            return this;
        }

        public void setVisited(int index)
        {
            visited.set(translateIndex(index), Boolean.TRUE);
        }

        public boolean getVisited(int index)
        {
            Boolean result = null;

            result = visited.get(translateIndex(index));

            return result;
        }

        public void clearVisited(int index)
            throws UnsupportedOperationException
        {
            visited.set(translateIndex(index), Boolean.FALSE);
        }

        /**
         * We translate the topological index to an ArrayList index. We have to
         * do this because topological indices can be negative, and we want to
         * do it because we can make better use of space by only needing an
         * ArrayList of size |AR|.
         *
         * @param unscaledIndex
         *
         * @return the ArrayList index
         */
        private int translateIndex(int index)
        {
            return index - affectedRegion.start;
        }
    }

    /**
     * This implementation doesn't seem to perform as well, though I can imagine
     * circumstances where it should shine (lots and lots of vertices). It also
     * should have the lowest memory footprint as it only uses storage for
     * indices that have been visited.
     *
     * @author gilesp
     */
    public static class VisitedHashSetImpl
        implements Visited,
            VisitedFactory
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final Set<Integer> visited = new HashSet<Integer>();

        public Visited getInstance(Region affectedRegion)
        {
            visited.clear();
            return this;
        }

        public void setVisited(int index)
        {
            visited.add(index);
        }

        public boolean getVisited(int index)
        {
            return visited.contains(index);
        }

        public void clearVisited(int index)
            throws UnsupportedOperationException
        {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * This implementation, somewhat to my surprise, is slower than the
     * ArrayList version, probably due to its reallocation of the underlying
     * array for every topology reorder that is required.
     *
     * @author gilesp
     */
    public static class VisitedArrayImpl
        implements Visited,
            VisitedFactory
    {
        /**
         */
        private static final long serialVersionUID = 1L;

        private final boolean [] visited;

        private final Region region;

        /**
         * Constructs empty factory instance
         */
        public VisitedArrayImpl()
        {
            this(null);
        }

        public VisitedArrayImpl(Region region)
        {
            if (region == null) { // make empty instance
                this.visited = null;
                this.region = null;
            } else { // fill in the needed pieces
                this.region = region;

                // initialized to all false by default
                visited = new boolean[region.getSize()];
            }
        }

        public Visited getInstance(Region affectedRegion)
        {
            return new VisitedArrayImpl(affectedRegion);
        }

        public void setVisited(int index)
        {
            try {
                visited[index - region.start] = true;
            } catch (ArrayIndexOutOfBoundsException e) {
                /*
                log.error("Visited set operation out of region boundaries", e);
                */
                throw e;
            }
        }

        public boolean getVisited(int index)
        {
            try {
                return visited[index - region.start];
            } catch (ArrayIndexOutOfBoundsException e) {
                /*
                log.error("Visited set operation out of region boundaries", e);
                */
                throw e;
            }
        }

        public void clearVisited(int index)
            throws UnsupportedOperationException
        {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * Exception used in dfsF when a cycle is found
     *
     * @author gilesp
     */
    public static class CycleFoundException
        extends Exception
    {
        private static final long serialVersionUID = 5583471522212552754L;
    }

    /**
     * iterator which follows topological order
     *
     * @author gilesp
     */
    private class TopoIterator
        implements Iterator<V>
    {
        private int currentTopoIndex;
        private final long updateCountAtCreation;
        private Integer nextIndex = null;

        public TopoIterator()
        {
            updateCountAtCreation = topologyUpdateCount;
            currentTopoIndex = minTopoIndex - 1;
        }

        public boolean hasNext()
        {
            if (updateCountAtCreation != topologyUpdateCount) {
                throw new ConcurrentModificationException();
            }

            nextIndex = getNextIndex();
            return nextIndex != null;
        }

        public V next()
        {
            if (updateCountAtCreation != topologyUpdateCount) {
                throw new ConcurrentModificationException();
            }

            if (nextIndex == null) {
                // find nextIndex
                nextIndex = getNextIndex();
            }
            if (nextIndex == null) {
                throw new NoSuchElementException();
            }
            currentTopoIndex = nextIndex;
            nextIndex = null;
            return topoOrderMap.getVertex(currentTopoIndex); //topoToVertex.get(currentTopoIndex);
        }

        public void remove()
        {
            if (updateCountAtCreation != topologyUpdateCount) {
                throw new ConcurrentModificationException();
            }

            V vertexToRemove = null;
            if (null
                != (vertexToRemove =
                        topoOrderMap.getVertex(
                            currentTopoIndex)))
            {
                topoOrderMap.removeVertex(vertexToRemove);
            } else {
                // should only happen if next() hasn't been called
                throw new IllegalStateException();
            }
        }

        private Integer getNextIndex()
        {
            for (int i = currentTopoIndex + 1; i <= maxTopoIndex; i++) {
                if (null != topoOrderMap.getVertex(i)) {
                    return i;
                }
            }
            return null;
        }
    }
}

// End DirectedAcyclicGraph.java