Kosaraju's SCC implementation

scc.cs

using System;
using System.Collections.Generic;
using System.IO;

namespace SCC
{
    class Node
    {
        public Node(int label) { Label = label; Descendents = new List<Node>(); Antecedents = new List<Node>(); Visited = false; }
        public int Label { get; private set; }
        public bool Visited { get; set; }
        public List<Node> Descendents { get; private set; }
        public List<Node> Antecedents { get; private set; }
    }

    class Program
    {
        const int NODES = 875714;
        //const int NODES = 11;

        static void Main(string[] args)
        {
            #region TestGraph
            /*Node a = new Node(1);
            Node b = new Node(2);
            Node c = new Node(3);
            Node d = new Node(4);
            a.Descendents.Add(b);
            a.Descendents.Add(c);
            b.Descendents.Add(d);
            c.Descendents.Add(d);
            Node[] graph = new Node[4];
            graph[0] = a;
            graph[1] = b;
            graph[2] = c;
            graph[3] = d;*/
            #endregion
            //form the graph using antecedents and descendants
            //Compute timings using antecedents.
            //Get a new graph that has elements sorted in timings.
            //Compute SCC using descendents.
            if (args.Length == 0)
            {
                Console.WriteLine("Please provide the filename");
                return;
            }

            string filename = args[0];
            if (!File.Exists(filename))
                Console.WriteLine("File {0} does not exist", filename);
            Node[] graph = new Node[NODES];
            Node[] sortedGraph = new Node[NODES];
            for (int i = 0; i < NODES; i++)
                graph[i] = new Node(i + 1);
            using (FileStream stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
            {
                using (StreamReader reader = new StreamReader(stream))
                {
                    while (reader.Peek() > -1)
                    {
                        string[] edges = reader.ReadLine().TrimEnd().Split(' ');
                        int headLabel = int.Parse(edges[0]) - 1;
                        int tailLabel = int.Parse(edges[1]) - 1;
                        graph[headLabel].Descendents.Add(graph[tailLabel]);
                        graph[tailLabel].Antecedents.Add(graph[headLabel]);
                    }
                }
            }

            ComputeNodeTimingsUsingDFS(graph, sortedGraph);
            foreach (Node n in graph)//reset the state of graph.
                n.Visited = false;

            List<int> sccSizes = ComputeSCCSize(sortedGraph);
            sccSizes.Sort((a, b) => { return b.CompareTo(a); });
            string result = "";
            for (int i = 0; i < sccSizes.Count; i++)
            {
                if (i < 5)
                    result += sccSizes[i].ToString()+",";
                else
                    break;
            }
            Console.WriteLine(result);
            //Console.Read();
        }

        static void ComputeNodeTimingsUsingDFS(Node[] graph, Node[] sortedGraph)
        {
            //level counter
            //if sink node then mark it as completed.

            Stack<Node> stack = new Stack<Node>(NODES / 2);
            bool isSinkNode = true;
            int level = 0;

            for (int i = 0; i < NODES; i++)
            {
                if (!graph[i].Visited)
                {
                    stack.Push(graph[i]);
                    graph[i].Visited = true;
                    while (stack.Count > 0)
                    {
                        Node workingNode = stack.Peek();
                        List<Node> frontierNodes = workingNode.Antecedents;
                        isSinkNode = true;
                        foreach (Node n in frontierNodes)
                        {
                            if (!n.Visited)
                            {
                                stack.Push(n);
                                n.Visited = true;
                                isSinkNode = false;
                            }
                        }
                        if (isSinkNode)
                        {
                            try
                            {
                                sortedGraph[level++] = stack.Pop();//pop stack only on sink nodes.
                            }
                            catch(IndexOutOfRangeException)
                            {
                                int n = stack.Count;
                                bool[] stackcheck = new bool[n];
                                for(int j=0;j<n;j++)
                                {
                                    Node node = stack.Pop();
                                    if (!stackcheck[node.Label])
                                        stackcheck[node.Label] = true;
                                    else
                                        Console.WriteLine("{0} am the problem", node.Label);
                                }

                            }
                        }
                    }
                }
            }
        }

        static List<int> ComputeSCCSize(Node[] graph)
        {
            Stack<Node> stack = new Stack<Node>(NODES / 2);
            //Queue<Node> queue = new Queue<Node>(NODES / 2);
            List<int> sccSizes = new List<int>();
            int sccSize = 0;

            for (int i = NODES - 1; i >= 0; i--)
            {
                sccSize = 0;
                if (!graph[i].Visited)
                {
                    stack.Push(graph[i]);
                    //queue.Enqueue(graph[i]);
                    graph[i].Visited = true;
                    while (stack.Count > 0)
                    {
                        Node workingNode = stack.Pop();
                        //Node workingNode = queue.Dequeue();
                        List<Node> frontierNodes = workingNode.Descendents;
                        foreach (Node n in frontierNodes)
                        {
                            if (!n.Visited)
                            {
                                stack.Push(n);
                                //queue.Enqueue(n);
                                n.Visited = true;
                            }
                        }
                        sccSize++;
                    }
                }
                sccSizes.Add(sccSize);
            }
            return sccSizes;
        }
    }
}