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:
My 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:
So fields like Age always come after DateOfBirth which it depends on.
My second question:
Is there a way to 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. e.g. when you finish college, you need 2 years of working experience to get a job. But to get the working experience, you first of all need to have the job.
Thanks for the tip Grzenio I actually found something similar in java at http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm
Below is the C# adaptation:
class Class1
{
public static void Run()
{
doTopologicalTest();
}
private static void doTopologicalTest()
{
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; }
}
}
And the Code for TopologicalSort.cs
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("ERROR: 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
}
....