fork download

copy

import java.*;
import java.util.*;
import java.io.*;
 
 
// Written by: Yancy Vance M. Paredes.
 
// Finding all strongly connected components using Tarjan's algorithm.
 
public class StronglyConnectedTarjan {
 
    public static int index;
    public static Stack<Node> stack;
    public static Vector<Vector<Node>> set;
 
    public static void main(String[] args) throws Exception {
        Scanner iFile = new Scanner(new FileReader("stronglyConnectedTarjan.in"));
        Graph graph = new Graph();
        graph.setDirected();
        graph.setSortedNeighbors(true);
 
        while(iFile.hasNext()) {
            Node<String> a = new Node<String>(iFile.next());
            Node<String> b = new Node<String>(iFile.next());
 
            int aPos = graph.indexOf(a);
            int bPos = graph.indexOf(b);
 
            // If a does not exist in the graph yet.
            if(aPos == -1)
                aPos = graph.addNode(a);
 
            // If b does not exist in the graph yet.
            if(bPos == -1)
                bPos = graph.addNode(b);
 
            Edge edge = new Edge(graph.getNodeAt(aPos), graph.getNodeAt(bPos));
 
            graph.addEdge(edge);
        }
 
        //graph.printNodes();
        //graph.printEdges();
 
        Vector<Node> nodes = graph.getNodes();
        index = 0;
        stack = new Stack<Node>();
        set = new Vector<Vector<Node>>();
 
        // Use all the different nodes as the root or source node. 
        for(int i = 0; i < nodes.size(); i++) {
            Node node = nodes.elementAt(i);
 
            if(node.index == null)
                strongConnect(graph, node);
        }
 
        for(int i = 0; i < set.size(); i++)
            System.out.println("Set " + i + ": " + set.elementAt(i));
 
        iFile.close();      
    }
 
    public static void strongConnect(Graph graph, Node node) {
        node.index = index;
        node.lowlink = index;
        index++;
        stack.push(node);
 
        Vector<Node> neighbors = graph.getNeighbors(node);
 
        for(int i = 0; i < neighbors.size(); i++) {
            Node neighbor = neighbors.elementAt(i);
 
            if(neighbor.index == null) {
                strongConnect(graph, neighbor);
                node.lowlink = Math.min(node.lowlink, neighbor.lowlink);
            }
            else if(stack.contains(neighbor)) {
                node.lowlink = Math.min(node.lowlink, neighbor.index);
            }
        }
 
        if(node.lowlink == node.index) {
            Vector<Node> subset = new Vector<Node>();
            Node neighbor = null;
 
            while(node != neighbor) {
                neighbor = stack.pop();
                subset.add(neighbor);
            }
 
            set.add(subset);
        }
 
    }
 
}

Main.java:10: error: class StronglyConnectedTarjan is public, should be declared in a file named StronglyConnectedTarjan.java
public class StronglyConnectedTarjan {
       ^
Main.java:13: error: cannot find symbol
    public static Stack<Node> stack;
                        ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:14: error: cannot find symbol
    public static Vector<Vector<Node>> set;
                                ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:64: error: cannot find symbol
    public static void strongConnect(Graph graph, Node node) {
                                     ^
  symbol:   class Graph
  location: class StronglyConnectedTarjan
Main.java:64: error: cannot find symbol
    public static void strongConnect(Graph graph, Node node) {
                                                  ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:18: error: cannot find symbol
        Graph graph = new Graph();
        ^
  symbol:   class Graph
  location: class StronglyConnectedTarjan
Main.java:18: error: cannot find symbol
        Graph graph = new Graph();
                          ^
  symbol:   class Graph
  location: class StronglyConnectedTarjan
Main.java:23: error: cannot find symbol
            Node<String> a = new Node<String>(iFile.next());
            ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:23: error: cannot find symbol
            Node<String> a = new Node<String>(iFile.next());
                                 ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:24: error: cannot find symbol
            Node<String> b = new Node<String>(iFile.next());
            ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:24: error: cannot find symbol
            Node<String> b = new Node<String>(iFile.next());
                                 ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:37: error: cannot find symbol
            Edge edge = new Edge(graph.getNodeAt(aPos), graph.getNodeAt(bPos));
            ^
  symbol:   class Edge
  location: class StronglyConnectedTarjan
Main.java:37: error: cannot find symbol
            Edge edge = new Edge(graph.getNodeAt(aPos), graph.getNodeAt(bPos));
                            ^
  symbol:   class Edge
  location: class StronglyConnectedTarjan
Main.java:45: error: cannot find symbol
        Vector<Node> nodes = graph.getNodes();
               ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:47: error: cannot find symbol
        stack = new Stack<Node>();
                          ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:48: error: cannot find symbol
        set = new Vector<Vector<Node>>();
                                ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:52: error: cannot find symbol
            Node node = nodes.elementAt(i);
            ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:70: error: cannot find symbol
        Vector<Node> neighbors = graph.getNeighbors(node);
               ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:73: error: cannot find symbol
            Node neighbor = neighbors.elementAt(i);
            ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:85: error: cannot find symbol
            Vector<Node> subset = new Vector<Node>();
                   ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:85: error: cannot find symbol
            Vector<Node> subset = new Vector<Node>();
                                             ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
Main.java:86: error: cannot find symbol
            Node neighbor = null;
            ^
  symbol:   class Node
  location: class StronglyConnectedTarjan
22 errors

Standard output is empty