Basic Graph ADTs. MST Algorithms using Kruskal and Prim

Graph_MST.cs

//design questions:
// why is node<t> not derived from graphNode<t> . during implementaion you find that Node<t> and graphNode<t>
// are siblings rather than parent-child. 
namespace dotNetPlayGround
{
    using System;
    using System.Collections.ObjectModel;
    using System.Collections.Generic;
    using System.Text;

    public class NodeList<T> : Collection<Node<T>>
    {
        public NodeList()
            : this(new List<T>())
        {
        }

        public NodeList(IEnumerable<T> nodeList)
        {
            IEnumerator<T> iterator = nodeList.GetEnumerator();
            while (iterator.MoveNext())
            {
                Add(iterator.Current);
            }
        }

        public void Add(T item)
        {
            Node<T> newNode = new Node<T>(item);
            base.Add(newNode);
        }

        public Node<T> FindByValue(T value)
        {
            IEnumerator<Node<T>> nodeEnumerator = base.GetEnumerator();
            while (nodeEnumerator.MoveNext())
            {
                Node<T> current = nodeEnumerator.Current;
                if (current.Value.Equals(value))
                    return current;
            }
            return null;
        }
    }

    public class GraphNodeList<T> : Collection<GraphNode<T>>
    {
        public GraphNodeList() : this(new List<T>()) { }
        public GraphNodeList(IEnumerable<T> nodeList)
        {
            IEnumerator<T> iterator = nodeList.GetEnumerator();
            while (iterator.MoveNext())
            {
                this.Add(iterator.Current);
            }
        }

        public void Add(T item)
        {
            GraphNode<T> newNode = new GraphNode<T>(item);
            base.Add(newNode);
        }

        public GraphNode<T> FindByValue(T value)
        {
            IEnumerator<GraphNode<T>> nodeEnumerator = base.GetEnumerator();
            while (nodeEnumerator.MoveNext())
            {
                GraphNode<T> current = nodeEnumerator.Current;
                if (current.Value.Equals(value))
                    return current;
            }
            return null;
        }
    }
    //convert node into Inode<> . Make node<t> and graphnode<t> independant
    public class Node<T>
    {
        private T _value;
        private NodeList<T> _neighbors;

        public Node()
            : this(default(T))
        {
        }

        public Node(T value)
            : this(value, new List<T>())
        {
        }

        public Node(T value, IEnumerable<T> neighbors)
        {
            _value = value;
            _neighbors = new NodeList<T>(neighbors);
        }

        public NodeList<T> Neighbors
        {
            get { return _neighbors; }
        }

        public T Value
        {
            get { return _value; }
        }

        public override bool Equals(object obj)
        {
            Node<T> otherNode = obj as Node<T>;
            if (otherNode == null)
                return false;
            if (object.ReferenceEquals(otherNode, this))
                return true;
            if (otherNode.Value.Equals(this.Value) && otherNode.Neighbors.Count == this.Neighbors.Count)
                return true;
            return false;
        }

        public override int GetHashCode()
        {
            int hashcode = default(int);
            foreach (char c in this.Value.ToString())
                hashcode += (int)c;
            hashcode += this.Neighbors.Count;
            return hashcode;
        }
    }

    public class GraphNode<T> : Node<T>
    {
        private List<int> _costs;

        public GraphNode() : this(default(T)) { }
        public GraphNode(T value) : this(value, new List<T>()) { }
        public GraphNode(T value, IEnumerable<T> neighbors) : base(value, neighbors) { _costs = new List<int>(); }

        public IList<int> Costs { get { return _costs; } }

        public override bool Equals(object obj)
        {
            GraphNode<T> otherNode = obj as GraphNode<T>;
            if (otherNode == null || !otherNode.Costs.Count.Equals(this.Costs.Count))
                return false;
            return base.Equals(obj);
        }

        public override int GetHashCode()
        {
            int hash = base.GetHashCode();
            foreach (int cost in this.Costs)
                hash += cost;
            return hash;
        }
    }

    public class Graph<T> : IEnumerable<GraphNode<T>>
    {
        private GraphNodeList<T> _graphNodes;

        public Graph() : this(new List<T>()) { }
        public Graph(IEnumerable<T> nodes)
        {
            _graphNodes = new GraphNodeList<T>(nodes);
        }

        public GraphNode<T> AddNode(T value)
        {
            GraphNode<T> newNode = new GraphNode<T>(value);
            return AddNode(newNode);

        }
        public GraphNode<T> AddNode(GraphNode<T> newNode)
        {
            _graphNodes.Add(newNode);
            return newNode;
        }

        public void AddDirectedEdge(T from, T to)
        {
            GraphNode<T> fromNode = _graphNodes.FindByValue(from);
            GraphNode<T> toNode = _graphNodes.FindByValue(to);
            this.AddDirectedEdge(fromNode, toNode);
        }

        public void AddDirectedEdge(GraphNode<T> from, GraphNode<T> to)
        {
            AddDirectedEdge(from, to, 0);
        }

        public void AddDirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
        {
            Guard(from);
            Guard(to);
            from.Neighbors.Add(to);
            from.Costs.Add(cost);
        }

        public void AddUndirectedEdge(T from, T to)
        {
            GraphNode<T> fromNode = _graphNodes.FindByValue(from);
            GraphNode<T> toNode = _graphNodes.FindByValue(to);
            this.AddUndirectedEdge(fromNode, toNode);
        }

        public void AddUndirectedEdge(GraphNode<T> from, GraphNode<T> to)
        {
            this.AddUndirectedEdge(from, to, 0);
        }

        public void AddUndirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
        {
            Guard(from);
            Guard(to);
            if (from.Neighbors.Count > 0 && to.Neighbors.Count > 0 && (from.Neighbors.Contains(to) || to.Neighbors.Contains(from)))
                throw new InvalidOperationException(string.Format("Connection already exists between {0} and {1}", from.Value, to.Value));
            from.Neighbors.Add(to);
            to.Neighbors.Add(from);
            from.Costs.Add(cost);
            to.Costs.Add(cost);
        }

        public int Count
        {
            get { return _graphNodes.Count; }
        }

        public GraphNodeList<T> Nodes
        {
            get { return _graphNodes; }
        }

        public bool Contains(T item)
        {
            return _graphNodes.FindByValue(item) != null;
        }

        public bool Contains(GraphNode<T> item)
        {
            return _graphNodes.Contains(item);
        }

        public bool Remove(T item)
        {
            GraphNode<T> searchedNode = _graphNodes.FindByValue(item) as GraphNode<T>;
            if (searchedNode != null)
                return Remove(searchedNode);
            else
                return false;
        }

        public bool Remove(GraphNode<T> item)
        {
            return _graphNodes.Remove(item);
        }

        public IEnumerator<GraphNode<T>> GetEnumerator()
        {
            return _graphNodes.GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Dump()
        {
            foreach (GraphNode<T> node in _graphNodes)
            {
                Console.WriteLine(node.Value);
                if (node.Neighbors != null && node.Neighbors.Count > 0)
                {
                    foreach (GraphNode<T> neighbor in node.Neighbors)
                    {
                        Console.Write("\t{0}", neighbor.Value);
                    }
                }
                Console.WriteLine();
            }
        }

        private void Guard(GraphNode<T> checkNode)
        {
            foreach (GraphNode<T> node in _graphNodes)
                if (object.ReferenceEquals(node, checkNode))
                    return;
            throw new KeyNotFoundException(string.Format("Node {0} not found in graph", checkNode.Value));
        }
    }
    public class MinimumSpanningTree
    {
        //kruskal
        //extract all edges
        //sort all edges in ascending order
        //make V number of sets using union-find
        // pick smallest edge an FindSet(u) != Findset(v)
        // union Tree(U) & Tree(V)
        //output union tree.
        //prim
        // start with a root node.
        // have a predecessor node
        // Graph
        // have minHeap(ordered set)  -> (GraphNode<V>,k,p)
        // have a minheap that gives your the minimum key
        private class HeapNode<T> : IComparable<HeapNode<T>>, IComparer<HeapNode<T>>
        {
            GraphNode<T> _vertex;
            int _key;
            GraphNode<T> _predecessor;

            public GraphNode<T> Vertex
            {
                get { return _vertex; }
            }

            public int Key
            {
                get { return _key; }
            }
            public GraphNode<T> Predecessor
            {
                get { return _predecessor; }
            }


            public int CompareTo(HeapNode<T> other)
            {
                if (other == null)
                    return 1;
                if (this.Key == other.Key)
                    return 0;
                else if (this.Key > other.Key)
                    return 1;
                else
                    return -1;
            }

            public HeapNode(GraphNode<T> vertex, int cost, GraphNode<T> predecessor)
            {
                _vertex = vertex;
                _key = cost;
                _predecessor = predecessor;
            }

            public HeapNode()
            {
                _vertex = default(GraphNode<T>);
                _key = default(int);
                _predecessor = default(GraphNode<T>);
            }

            public int Compare(HeapNode<T> x, HeapNode<T> y)
            {
                if (x == null && y == null)
                    return 0;
                if (x == null)
                    return -1;
                return x.CompareTo(y);
            }
        }

        public static Graph<T> PrimsAlgorithms<T>(Graph<T> graph, GraphNode<T> root) where T : IComparable<T>
        {
            Graph<T> minSpanningTree = new Graph<T>();
            SortedSet<HeapNode<T>> heap = new SortedSet<HeapNode<T>>(new HeapNode<T>());
            Dictionary<GraphNode<T>, bool> traversedNodes = new Dictionary<GraphNode<T>, bool>(graph.Count);
            foreach (GraphNode<T> gNode in graph)
            {
                if (traversedNodes.ContainsKey(gNode))
                    throw new Exception(string.Format("Problem in hashing.{0} has a contention.", gNode.Value));
                traversedNodes.Add(gNode, false);
            }
            heap.Add(new HeapNode<T>(root, 0, null));
            while (heap.Count > 0)
            {
                HeapNode<T> minNode = heap.Min;
                GraphNode<T> parentNode;
                traversedNodes[root] = true;
                if (minNode.Predecessor == null)
                    parentNode = minSpanningTree.AddNode(minNode.Vertex.Value);
                else
                {
                    parentNode = new GraphNode<T>(minNode.Vertex.Value);
                    minNode.Predecessor.Neighbors.Add(parentNode);
                }
                for (int i = 0; i < minNode.Vertex.Neighbors.Count; i++)
                {
                    GraphNode<T> adjacent = minNode.Vertex.Neighbors[i] as GraphNode<T>;
                    Console.WriteLine("adj:{0},val:{1}",adjacent.Value,traversedNodes[adjacent]);
                    if (!traversedNodes[adjacent])
                    {
                        //Fails here. Check if the IComparer  & hashcode works correctly works correctly.
                        Console.WriteLine(heap.Add(new HeapNode<T>(adjacent, adjacent.Costs[i], parentNode)));
                    }
                }
                Console.WriteLine(heap.Count);
                heap.Remove(minNode);
            }
            return minSpanningTree;
        }
    }

    public static class ArrayExtensions
    {
        public static void QuickSort<T>(this T[] unsorted, int head, int tail) where T : IComparable<T>
        {
            //bottom out : sorted.
            //find pivot
            //create left array
            //create right array
            //quicksort(left)
            //quicksort(right)
            if (head < tail)
            {
                Pivot<T>(unsorted, head, tail);
                T pivot = unsorted[tail];
                int i = head;
                int medianMarker = head;
                while (head < tail - 1)
                {
                    if (unsorted[i].CompareTo(unsorted[tail]) < 0)
                    {
                        Swap<T>(unsorted, medianMarker, i);
                        medianMarker++;
                    }
                    i++;
                }
                Swap<T>(unsorted, medianMarker, tail);
                QuickSort<T>(unsorted, head, medianMarker - 1);
                QuickSort<T>(unsorted, medianMarker + 1, tail);
            }
        }

        private static void Pivot<T>(T[] unsorted, int head, int tail) where T : IComparable<T>
        {
            //find middle
            //check lowest with middle
            // check lowest with end
            // check middle with end
            // swap middle with end.
            int middle = (head + tail) / 2;
            if (unsorted[head].CompareTo(unsorted[middle]) > 0)
                Swap<T>(unsorted, head, middle);
            if (unsorted[head].CompareTo(unsorted[tail]) > 0)
                Swap<T>(unsorted, head, tail);
            if (unsorted[middle].CompareTo(unsorted[tail]) > 0)
                Swap<T>(unsorted, middle, tail);
            Swap<T>(unsorted, middle, tail);

        }

        private static void Swap<T>(T[] collection, int i, int j)
        {
            T temp = collection[i];
            collection[i] = collection[j];
            collection[j] = temp;
        }

    }
    public class Client
    {
        static void Main()
        {
            BuildCityMap();
        }

        private static void BuildCityMap()
        {
            string[] cityNames = { "SF", "LA", "CHI", "SM", "DL", "DE", "NYC", "MI" };
            Graph<string> cities = new Graph<string>(cityNames);
            cities.AddUndirectedEdge("SF", "CHI");
            cities.AddUndirectedEdge("SF", "LA");
            cities.AddUndirectedEdge("SF", "DE");
            cities.AddUndirectedEdge("CHI", "DE");
            cities.AddUndirectedEdge("DE", "LA");
            cities.AddUndirectedEdge("LA", "SM");
            cities.AddUndirectedEdge("SM", "DL");
            cities.AddUndirectedEdge("DL", "MI");
            cities.AddUndirectedEdge("DL", "NYC");
            cities.AddUndirectedEdge("MI", "NYC");
            cities.AddUndirectedEdge("CHI", "NYC");
            //cities.Dump();
            GraphNode<string> NYC= null;
            foreach(GraphNode<string> city in cities)
                if(city.Value.Equals("NYC"))
                    NYC = city;

            Graph<string> spanningTree = MinimumSpanningTree.PrimsAlgorithms<string>(cities, NYC);
            spanningTree.Dump();

        }
        private void BuildWebSite()
        {
            Graph<string> webSite = new Graph<string>();
            GraphNode<string> privacy = webSite.AddNode("privacy.html");
            GraphNode<string> people = webSite.AddNode("people.aspx");
            GraphNode<string> product = webSite.AddNode("product.aspx");
            webSite.AddDirectedEdge(people, privacy);
            webSite.AddDirectedEdge(product, people);

        }
    }
}