Topological Sorting and Cyclic Dependencies

Recently I needed to re-arrange items in an array based on its dependencies? and also detect any cyclic dependency. To be more clear, consider the following:

Given the type:

class Field
{
    public string Name{get;set;}
    public string[] DependsOn{get;set;}
}

Let's say I have an array of Field items:

List<Field> fields = new List<Field>();
fields.Add(new Field() { Name = "FirstName" });
fields.Add(new Field() { Name = "FullName",
    DependsOn = new[] {"FirstName","LastName"}});
fields.Add(new Field() { Name = "Age",
    DependsOn = new[] { "DateOfBirth" } });
fields.Add(new Field() { Name = "LastName" });
fields.Add(new Field() { Name = "DateOfBirth" });

So clearly we get our items in the following order:

1. FirstName
2. FullName
3. Age
4. LastName
5. DateOfBirth

First question: What is the best way to re-arrange the items in my list/array so that dependent columns (FullName & Age) are placed after the columns they depend on i.e. something like this:

1. FirstName
2. LastName
3. FullName
4. DateOfBirth
5. Age

So fields like Age always come after DateOfBirth which it depends on.

Second question: How do you detect cyclic dependencies? i.e. when
Field1 depends on Field2 and
Field2 depends on Field3 and
Field3 depends on Field1
So we don't get caught in a circle.

The solution will be to sort the fields in topological order. Below is the C# sample code I adopted from the Java version found at: http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm.

class TopologicalSorter
{
    #region - Private Members -

    private readonly int[] _vertices; // list of vertices
    private readonly int[,] _matrix; // adjacency matrix
    private int _numVerts; // current number of vertices
    private readonly int[] _sortedArray;

    #endregion

    #region - CTors -

    public TopologicalSorter(int size)
    {
        _vertices = new int[size];
        _matrix = new int[size, size];
        _numVerts = 0;
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                _matrix[i, j] = 0;
        _sortedArray = new int[size]; // sorted vert labels
    }

    #endregion

    #region - Public Methods -

    public int AddVertex(int vertex)
    {
        _vertices[_numVerts++] = vertex;
        return _numVerts - 1;
    }

    public void AddEdge(int start, int end)
    {
        _matrix[start, end] = 1;
    }

    public int[] Sort() // toplogical sort
    {
        while (_numVerts > 0) // while vertices remain,
        {
            // get a vertex with no successors, or -1
            int currentVertex = noSuccessors();
            if (currentVertex == -1) // must be a cycle                
                throw new Exception("Graph has cycles");

            // insert vertex label in sorted array (start at end)
            _sortedArray[_numVerts - 1] = _vertices[currentVertex];

            deleteVertex(currentVertex); // delete vertex
        }

        // vertices all gone; return sortedArray
        return _sortedArray;
    }

    #endregion

    #region - Private Helper Methods -

    // returns vert with no successors (or -1 if no such verts)
    private int noSuccessors()
    {
        for (int row = 0; row < _numVerts; row++)
        {
            bool isEdge = false; // edge from row to column in adjMat
            for (int col = 0; col < _numVerts; col++)
            {
                if (_matrix[row, col] > 0) // if edge to another,
                {
                    isEdge = true;
                    break; // this vertex has a successor try another
                }
            }
            if (!isEdge) // if no edges, has no successors
                return row;
        }
        return -1; // no
    }

    private void deleteVertex(int delVert)
    {
        // if not last vertex, delete from vertexList
        if (delVert != _numVerts - 1)
        {
            for (int j = delVert; j < _numVerts - 1; j++)
                _vertices[j] = _vertices[j + 1];

            for (int row = delVert; row < _numVerts - 1; row++)
                moveRowUp(row, _numVerts);

            for (int col = delVert; col < _numVerts - 1; col++)
                moveColLeft(col, _numVerts - 1);
        }
        _numVerts--; // one less vertex
    }

    private void moveRowUp(int row, int length)
    {
        for (int col = 0; col < length; col++)
            _matrix[row, col] = _matrix[row + 1, col];
    }

    private void moveColLeft(int col, int length)
    {
        for (int row = 0; row < length; row++)
            _matrix[row, col] = _matrix[row, col + 1];
    }

    #endregion
}

So we can then test our code using something as below:

class Program
{
    public static void Main (string[] args)
    {
        List<Field> fields = new List<Field>();
        fields.Add(new Field() { Name = "FirstName" });
        fields.Add(new Field()
        {
            Name = "FullName",
            DependsOn = new[] { "FirstName", "LastName" }
        });
        fields.Add(new Field()
        {
            Name = "Age",
            DependsOn = new[] { "DateOfBirth" }
        });
        fields.Add(new Field() { Name = "LastName" });
        fields.Add(new Field() { Name = "DateOfBirth" });

        foreach (var field in fields)
        {
            Console.WriteLine(field.Name);
            if(field.DependsOn != null)
                foreach (var item in field.DependsOn)
                {
                    Console.WriteLine(" -{0}",item);
                }
        }

        Console.WriteLine("\n...Sorting...\n");

        int[] sortOrder = getTopologicalSortOrder(fields);

        for (int i = 0; i < sortOrder.Length; i++)
        {
            var field = fields[sortOrder[i]];
            Console.WriteLine(field.Name);
            if (field.DependsOn != null)
                foreach (var item in field.DependsOn)
                {
                    Console.WriteLine(" -{0}", item);
                }
        }

    }

    private static int[] getTopologicalSortOrder(List<Field> fields)
    {
        TopologicalSorter g = new TopologicalSorter(fields.Count);
        Dictionary<string, int> _indexes = new Dictionary<string, int>();

        //add vertices
        for (int i = 0; i < fields.Count; i++)
        {
            _indexes[fields[i].Name.ToLower()] = g.AddVertex(i);
        }

        //add edges
        for (int i = 0; i < fields.Count; i++)
        {
            if (fields[i].DependsOn != null)
            {
                for (int j = 0; j < fields[i].DependsOn.Length; j++)
                {
                    g.AddEdge(i,
                        _indexes[fields[i].DependsOn[j].ToLower()]);
                }
            }
        }

        int[] result = g.Sort();
        return result;

    }


    class Field
    {
        public string Name { get; set; }
        public string[] DependsOn { get; set; }
    }
}

Get a Random Date

static DateTime GetRandomDate(Random rand, 
    DateTime minDate, DateTime maxDate)
{
    TimeSpan ts = maxDate - minDate;
    int totalDays = (int)ts.TotalDays;
    int randomDays = rand.Next(0, totalDays);
    return minDate.AddDays(randomDays);
}