001package algs42;
002import stdlib.*;
003import algs13.Stack;
004/* ***********************************************************************
005 *  Compilation:  javac ShortestDirectedCycle.java
006 *  Execution:    java DirectedCycle < input.txt
007 *  Dependencies: Digraph.java BreadthFirstDirectedPaths.java Stack.java StdOut.java In.java
008 *  Data files:   http://algs4.cs.princeton.edu/42directed/tinyDG.txt
009 *                http://algs4.cs.princeton.edu/42directed/tinyDAG.txt
010 *
011 *  Finds a shortest directed cycle in a digraph.
012 *  Runs in O(V * (E + V)) time.
013 *
014 *  % java ShortestDirectedCycle tinyDG.txt
015 *  Shortest directed cycle: 2 3 2
016 *
017 *  %  java ShortestDirectedCycle tinyDAG.txt
018 *  No cycle
019 *
020 *************************************************************************/
021
022public class XShortestDirectedCycle {
023        private Stack<Integer> cycle;    // directed cycle (or null if no such cycle)
024        private int length;
025
026        public XShortestDirectedCycle(Digraph G) {
027                Digraph R = G.reverse();
028                length = G.V() + 1;
029                for (int v = 0; v < G.V(); v++) {
030                        BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
031                        for (int w : G.adj(v)) {
032                                if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
033                                        length = bfs.distTo(w) + 1;
034                                        cycle = new Stack<>();
035                                        for (int x : bfs.pathTo(w))
036                                                cycle.push(x);
037                                        cycle.push(v);
038                                }
039                        }
040                }
041        }
042
043
044        public boolean hasCycle()        { return cycle != null;   }
045        public Iterable<Integer> cycle() { return cycle;           }
046        public int length()              { return length;          }
047
048        public static void main(String[] args) {
049                args = new String[] { "data/tinyDG.txt" };
050
051                Digraph G;
052                if (args.length == 1) {
053                        In in = new In(args[0]);
054                        G = DigraphGenerator.fromIn(in);
055                } else {
056                        int V = Integer.parseInt(args[0]);
057                        int E = Integer.parseInt(args[1]);
058                        G = DigraphGenerator.simple(V, E);
059                }
060
061                XShortestDirectedCycle finder = new XShortestDirectedCycle(G);
062                if (finder.hasCycle()) {
063                        StdOut.print("Shortest directed cycle: ");
064                        for (int v : finder.cycle()) {
065                                StdOut.print(v + " ");
066                        }
067                        StdOut.println();
068                }
069
070                else {
071                        StdOut.println("No cycle");
072                }
073        }
074
075}