Wednesday, February 18, 2009

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; }
}
}

6 comments:

Pål said...

Thanks man, just what I needed.

Robert Fidler said...

Outstanding post - very help and exactly what i was looking for, thanks again.

On a side note, i new to blogging on blogspot and have been looking for an easy way to post code-snippets without using html. How do you post your code-snippets? I really like the format and clip-board functionality.

Angel Eyes said...

Thank you!
I was just in need of something similar, this will be a nice base to build on.

Sam said...

The output of this is below. I expected it to be firstname, lastname, fullname etc. Instead its Age, DateOfBirth, FullName, LastName, FirstName which is the reverse of the expected.

FirstName
FullName
-FirstName
-LastName
Age
-DateOfBirth
LastName
DateOfBirth

...Sorting...

Age
-DateOfBirth
DateOfBirth
FullName
-FirstName
-LastName
LastName
FirstName

Jesus said...

Thanks men, you saved the day

YouLoseBellyFat said...

cplusplus code examples