Saturday, October 20, 2012
Tuesday, September 13, 2011
Friday, October 09, 2009
Health Care Debate Analysis
Just read one of the best analogy to the Health Care debate: Who is my neighbor? A lesson from the Fire Department.
http://substitute.livejournal.com/1922188.html
http://substitute.livejournal.com/1922188.html
Friday, April 17, 2009
Kobe - A true "Worst Practices" ASP.NET MVC Example
I never comment about such things but after reading going through Kobe, I believe Microsoft has finally put out a true "Worst Practices" and "How-not-to" develop an ASP.NET MVC application. Check out these detailed analysis:
High level overiview by Karl Seguin : Kobe - Oh Dear Lord Why?!
Low level analysis by Ayende Rahien : Kobe – In the nuts & bolts and don’t really liking it.
There is nothing worse for a coding newbie than to be mislead with such ridiculous "sample reference application" especially from Microsoft.
High level overiview by Karl Seguin : Kobe - Oh Dear Lord Why?!
Low level analysis by Ayende Rahien : Kobe – In the nuts & bolts and don’t really liking it.
There is nothing worse for a coding newbie than to be mislead with such ridiculous "sample reference application" especially from Microsoft.
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:
Let's say I have an array of Field items:
So clearly we get our items in the following order:
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.
Second question: How do you detect cyclic dependencies? i.e. when
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.
So we can then test our code using something as below:
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:
- FirstName
- FullName
- Age
- LastName
- 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:
- FirstName
- LastName
- FullName
- DateOfBirth
- 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
andField2
depends on Field3
andField3
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; }
}
}
Labels:
Cyclic,
Dependencies,
Sorting,
Topological
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);
}
Thursday, November 08, 2007
Subscribe to:
Posts (Atom)