Topological Sort

Topics: algorithm
Oct 18, 2007 at 12:44 AM
I am able to show a Graph in the glee graph viewer but I can't iterate the topological sort. See F A I L S H E R E below. I also tried with an AdjacencyGraph but got the same error "Error in the application". Can you tell me whatm I am doing wrong?

Thanks
Rich

BidirectionalGraph<DataTable, DataRelationEdge> g;
g = new BidirectionalGraph<DataTable,DataRelationEdge>();

DataSetGraphPopulatorAlgorithm dsGPA =
new DataSetGraphPopulatorAlgorithm(g, dsSchema);

dsGPA.Compute();

GleeGraphPopulator<DataTable, DataRelationEdge> populator =
GleeGraphUtility.Create<DataTable, DataRelationEdge>(dsGPA.VisitedGraph);
populator.Compute();

Graph graph = populator.GleeGraph;
gViewer1.Graph = graph;

F A I L S H E R E
foreach (DataTable t in QuickGraph.Algorithms.AlgoUtility.TopologicalSort(dsGPA.VisitedGraph))
{
Console.WriteLine(t.TableName);
}

Oct 18, 2007 at 6:27 PM
Hi,

I found out what caused the failure. It failed on a DataRelationshipEdge where a table joined to itself. (Employees.ID is joined to Employees.ReportsTo). When I bypassed that relationship it ran to completion. This is a valid conditions for a Table Relationship...do I need to change something?

Also, I'm not sure the TopologicalSort helps me here? What I want to find out is.....say A user selects fields from two tables to query but those tables do not have a relationship. What is the best way to discover the additional tables needed for the join?

Thanks
Rich
Coordinator
Oct 21, 2007 at 1:40 AM
Ooops topological sort works on DAG only. In fact, it won't help you.

You're looking for undirecteddepthfirstsearch algorithm. I think there's one in the library. It's been a while, I'll have to look around