Searching a directed graph


This post documents a simple DirectedGraph class in C# that makes ample use of generics. That should make it widely applicable.

The DirectedGraph class

I use the dynamic keyword to do run-time type checking, this is required so that I can use math operations (like addition) with the generic type. This, unfortunately, only works with .NET Framework 4.0 and beyond.

The Search method is where most of the action happens. It supports end criteria based on weight and depth. Weight is the total weight of all the edges along a path. Depth is the number of nodes after the node where the search starts. Finally, there is a boolean flag that stops search when a cycle is detected. Cycle detection is very rudimentary, it is equivalent to setting the depth to total number of nodes (with adjacent nodes) in the graph.

Here’s the code of the class without much ado.

using System;

namespace DirectedGraph
{
    /// <summary>
    /// Represents a node in a graph.
    /// </summary>
    /// <typeparam name="T">Type of value object.</typeparam>
    /// <typeparam name="W">Type of weigth object.</typeparam>
    public class Node<T, W>
    {
        T value;
        /// <summary>
        /// Sets or retrieves a value object associated with this node.
        /// </summary>
        public T Value
        {
            get
            {
                return this.value;
            }
            set
            {
                this.value = value;
            }
        }

        W weight;
        /// <summary>
        /// Sets or retrieves a weight object associated with this node.
        /// </summary>
        public W Weight
        {
            get
            {
                return weight;
            }
            set
            {
                weight = value;
            }
        }

        private LinkedList<Node<T, W>> adjacentNodes = new LinkedList<Node<T, W>>();
        /// <summary>
        /// The list of adjacent nodes of this node.
        /// </summary>
        public LinkedList<Node<T, W>> AdjacentNodes
        {
            get
            {
                return adjacentNodes;
            }
        }

        /// <summary>
        /// Creates a node given the value and weight objects.
        /// </summary>
        /// <param name="value"></param>
        /// <param name="weight"></param>
        public Node(T value, W weight)
        {
            Value = value;
            Weight = weight;
        }

        // override object.Equals
        public override bool Equals(object obj)
        {
            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }

            Node<T, W> node = (Node<T, W>)obj;
            return Value.Equals(node.Value);
        }

        // override object.GetHashCode
        public override int GetHashCode()
        {
            return Value.GetHashCode();
        }

        // override object.ToString
        public override string ToString()
        {
            return value.ToString();
        }
    }

    /// <summary>
    /// A directed graph. It contains a list of node objects with their adjacent nodes. It is a sparse
    /// structure. Requires Microsoft .NET Framework version 4 or better.
    /// </summary>
    /// <typeparam name="T">The type of value object stored in the nodes of this graph.</typeparam>
    /// <typeparam name="W">The type of weight object stored in the nodes of this graph.</typeparam>
    public class DirectedGraph<T, W>
    {
        // List of nodes
        LinkedList<Node<T, W>> nodes = new LinkedList<Node<T, W>>();

        /// <summary>
        /// Adds a edge to this graph.
        /// </summary>
        /// <param name="start">The value object of the starting node.</param>
        /// <param name="end">The value object of the ending node.</param>
        /// <param name="weight">The weight of this edge.</param>
        public void AddEdge(T start, T end, W weight)
        {
            Node<T, W> s = new Node<T, W>(start, default(W));

            Node<T, W> e = new Node<T, W>(end, weight);

            Node<T, W> result = nodes.Find(s);
            if (result != null)
                s = result;
            else
                nodes.Add(s);

            result = s.AdjacentNodes.Find(e);
            if (result == null)
                s.AdjacentNodes.Add(e);
            else
                throw new ArgumentException("The specified route already exists.");
        }

        /// <summary>
        /// Searches this graph. The search algortihm used is depth-first. Search stops only when 
        /// the specified depth or total weight has been surpassed. The call to this method is
        /// thread-safe, but adding nodes to the graph while it is executing may lead to unexpected 
        /// results.
        /// </summary>
        /// <param name="start">The node from which to start the search.</param>
        /// <param name="end">The node where a search ends.</param>
        /// <param name="depth">The depth of the graph to traverse. If the value is n then the 
        /// result contains up to n nodes after start.</param>
        /// <param name="weight">The total weight of the nodes traversed is restricted to less than weight.</param>
        /// <param name="cycle">Set to true to allow cycles, specify depth or weight otherwise infinite loops may occur.</param>
        /// <returns></returns>
        public LinkedList<LinkedList<Node<T, W>>> Search(T start, T end, int depth = 0, W weight = default(W), bool cycle = false)
        {
            Node<T, W> s = new Node<T, W>(start, default(W));
            Node<T, W> e = new Node<T, W>(end, default(W));

            LinkedList<LinkedList<Node<T, W>>> searchResults = new LinkedList<LinkedList<Node<T, W>>>();
            LinkedList<Node<T, W>> searchResult = new LinkedList<Node<T, W>>();
            searchResult.Push(s); // push start node
            searchResults.Push(searchResult);

            Search(s, e, searchResults, depth, weight, cycle);

            if (searchResults.Peek().Length == 1)
            {
                searchResults.Pop();
            }

            return searchResults;
        }

        /// <summary>
        /// <see cref="DirectedGraph.Search(T start, T end, int depth = 10, W weight, bool cycle)"/>
        /// </summary>
        private void Search(Node<T, W> start, Node<T, W> end, LinkedList<LinkedList<Node<T, W>>> searchResults, int depth, W weight, bool cycle)
        {
            Node<T, W> node = nodes.Find(start);

            if (node == null)
            {
                return;
            }

            foreach (Node<T, W> adjacentNode in node.AdjacentNodes)
            {
                // Add node to search result
                searchResults.Peek().Push(adjacentNode); // add node
                searchResults.Peek()[0].Weight = (dynamic)searchResults.Peek()[0].Weight + adjacentNode.Weight;

                // Continue search
                bool continueSearch = true;
                int length = searchResults.Peek().Length;

                if (depth != 0 && length > depth + 1)
                {
                    // Depth has been provided, and exceeded
                    continueSearch = false;
                }

                if ((dynamic)weight != default(W) && (dynamic)searchResults.Peek()[0].Weight >= weight)
                {
                    // weight has been provided, and exceeded
                    continueSearch = false;
                }

                if (!cycle && length > nodes.Length)
                {
                    // we have a cycle
                    continueSearch = false;
                }

                if (continueSearch)
                {
                    if (end.Equals(adjacentNode))
                    {
                        // Create a copy of the current result to search deeper
                        LinkedList<Node<T, W>> searchResult = searchResults.Peek().Copy();
                        searchResults.Push(searchResult);
                    }

                    // Continue to search deeper
                    Search(adjacentNode, end, searchResults, depth, weight, cycle);

                    if (length == searchResults.Peek().Length)
                    {
                        // No new node added, dead end
                        searchResults.Peek().Pop(); // remove node
                        searchResults.Peek()[0].Weight = (dynamic)searchResults.Peek()[0].Weight - adjacentNode.Weight;
                    }
                }
                else
                {
                    searchResults.Peek().Pop(); // remove node
                    searchResults.Peek()[0].Weight = (dynamic)(searchResults.Peek()[0].Weight) - adjacentNode.Weight;
                    return;
                }
            }
        }
    }
}

The LinkedList class

I use the following class extensively. Why did I write my own linked list? Who doesn’t like writing their own linked list? Just kidding. The linked list class below is doubly linked and also behaves like a stack.

using System;
using System.Collections;
using System.Text;

namespace DirectedGraph
{
    /// <summary>
    /// Represents an item in the linked list.
    /// </summary>
    /// <typeparam name="T">The type of the value stored.</typeparam>
    class LinkedListItem<T>
    {
        /// <summary>
        /// The value stored in this item.
        /// </summary>
        public T value;

        /// <summary>
        /// The previous item in the list referenced by this item.
        /// </summary>
        public LinkedListItem<T> previousItem;

        /// <summary>
        /// The next item in the list referenced by this item.
        /// </summary>
        public LinkedListItem<T> nextItem;
    }

    /// <summary>
    /// A linked list.
    /// </summary>
    /// <typeparam name="T">Type of value stored in the linked list.</typeparam>
    public class LinkedList<T> : IEnumerable
    {
        /// <summary>
        /// First item in the linked list.
        /// </summary>
        private LinkedListItem<T> first;

        /// <summary>
        /// Last item in the list.
        /// </summary>
        private LinkedListItem<T> last;

        /// <summary>
        /// Total number of items in the linked list.
        /// </summary>
        private int length;

        /// <summary>
        /// Total number of items in the linked list.
        /// </summary>
        public int Length
        {
            get
            {
                return length;
            }
        }

        /// <summary>
        /// Indexer to access the linked list like an array.
        /// </summary>
        /// <param name="i">Index (zero-based) to access an item in the linked list. 
        /// Throws <see cref="System.IndexOutOfRangeException"/> if index is out of 
        /// range.</param>
        /// <returns>The value stored at the specified index.</returns>
        public T this[int i]
        {
            get {
                LinkedListItem<T> item = Find(i);

                if (item == null)
                    throw new IndexOutOfRangeException();

                return Find(i).value;
            }
            set
            {
                LinkedListItem<T> item = Find(i);

                if (item == null)
                    throw new IndexOutOfRangeException();

                item.value = value;
            }
        }

        /// <summary>
        /// Retrieves the <see cref="LinkedListItem"/> at the specified index.
        /// </summary>
        /// <param name="index"></param>
        /// <returns>The item found.</returns>
        private LinkedListItem<T> Find(int index)
        {
            // If last item index, return last
            if (index == length - 1)
                return last;

            if (first == null || index == 0)
                return first;

            // Iterate the list till the specified index is reached
            int i = 0;
            LinkedListItem<T> nextItem = first;
            while (nextItem.nextItem != null && i != index)
            {
                nextItem = nextItem.nextItem;
                i++;
            }
            if (i != index)
            {
                throw new IndexOutOfRangeException();
            }
            return nextItem;
        }

        /// <summary>
        /// Find an item in the linked list.
        /// </summary>
        /// <param name="match">The delegate used for performing the match.</param>
        /// <returns>Item found or else null.</returns>
        public T Find(Predicate<T> match)
        {
            LinkedListItem<T> nextItem = first;
            while (nextItem != null)
            {
                if (match(nextItem.value))
                {
                    return nextItem.value;
                }
                nextItem = nextItem.nextItem;
            }
            return default(T);
        }

        /// <summary>
        /// A simpler version of the Find method. Checks if the object specified 
        /// exists in the linked list based on the Equals method.
        /// </summary>
        /// <param name="obj">Object to search for.</param>
        /// <returns>The matching object found or null.</returns>
        public T Find(T obj)
        {
            return Find(delegate(T match)
            {
                if (obj.Equals(match))
                    return true;
                else
                    return false;
            });
        }

        /// <summary>
        /// Adds the specified object to the end of the linked list.
        /// </summary>
        /// <param name="obj">Object value to add.</param>
        public void Add(T obj)
        {
            LinkedListItem<T> item = new LinkedListItem<T>();
            item.value = obj;
            if (first == null)
            {
                first = item;
                last = item;
            }
            else
            {
                last.nextItem = item;
                item.previousItem = last;
                last = item;
            }
            length++;
        }

        /// <summary>
        /// Removes the specified item from the linked list. 
        /// </summary>
        /// <param name="obj">Index of the item to remove.</param>
        /// <returns>The item to remove.</returns>
        public T Remove(int index)
        {
            LinkedListItem<T> item = Find(index);
            if (item == null)
                throw new IndexOutOfRangeException();

            item.previousItem.nextItem = item.nextItem;
            item.nextItem.previousItem = item.previousItem;
            item.previousItem = null;
            item.nextItem = null;

            return item.value;
        }

        /// <summary>
        /// Pushes an object to the end of the linked list, or the top of the stack.
        /// </summary>
        /// <param name="obj">Object of type T.</param>
        public void Push(T obj)
        {
            Add(obj);
        }

        /// <summary>
        /// Peek at the object at the end of the linked list, or top of the stack.
        /// </summary>
        /// <returns>Object of type T.</returns>
        public T Peek()
        {
            return last.value;
        }

        /// <summary>
        /// Retrieves the top most item in the stack or else null if the stack is empty.
        /// </summary>
        /// <returns>Object of type T.</returns>
        public T Pop()
        {
            if (last == null)
            {
                return default(T);
            }

            T obj = last.value;
            last = last.previousItem;
            if (last != null)
                last.nextItem = null;
            else
                first = null;
            length--;
            return obj;
        }

        /// <summary>
        /// Support for foreach.
        /// </summary>
        /// <returns>The enumerator for this list.</returns>
        public IEnumerator GetEnumerator()
        {
            return new LinkedListEnumerator<T>(this);
        }

        /// <summary>
        /// Creates a copy of this linked list.
        /// </summary>
        /// <returns>A copy of this linked list.</returns>
        public LinkedList<T> Copy()
        {
            LinkedList<T> copy = new LinkedList<T>();

            LinkedListItem<T> nextItem = first;
            while (nextItem != null)
            {
                copy.Add(nextItem.value);
                nextItem = nextItem.nextItem;
            }

            return copy;
        }

        /// <summary>
        /// Override ToString.
        /// </summary>
        /// <returns>Concatenation of result of call to ToString for all objects stored.</returns>
        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            LinkedListItem<T> nextItem = first;
            while (nextItem != null)
            {
                s.Append(nextItem.value.ToString());
                nextItem = nextItem.nextItem;
            }
            return s.ToString();
        }

        /// <summary>
        /// Compare this linked to another. Lists with the same length and objects are considered equals.
        /// Objects are compared using object.Equals.
        /// </summary>
        /// <param name="other"></param>
        /// <returns>true if the lists have the same length and objects.</returns>
        public bool Compare(LinkedList<T> other)
        {
            bool equal = true;

            if (Length != other.Length) 
                return false;

            for (int i = 0; i < Length; i++)
            {
                if (!this[i].Equals(other[i])) 
                    return false;
            }

            return equal;
        }
    }

    /// <summary>
    /// Enumerator for <see cref="LinkedList"/>.
    /// </summary>
    /// <typeparam name="T">The type of object stored in <see cref="LinkedList"/>.</typeparam>
    class LinkedListEnumerator<T> : IEnumerator
    {
        LinkedList<T> list;
        int index;

        /// <summary>
        /// Constructor for the enumerator.
        /// </summary>
        /// <param name="list">The linked list being enumerated.</param>
        public LinkedListEnumerator(LinkedList<T> list)
        {
            this.list = list;
            index = -1;
        }

        public object Current
        {
            get
            {
                return list[index];
            }
        }

        public bool MoveNext()
        {
            index++;
            return (index < list.Length);
        }

        public void Reset()
        {
            index = -1;
        }
    }
}

Conclusion

I have yet to analyze the cost of the search algorithm in big-O notation. Being brute-force depth-first search, it may have characteristics similar to those published in popular algorithm text books. Memory usage is something else I haven’t yet evaluated. The use of recursion should limit it to relatively shallow depths.

I have also posted the code at GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s