The next version of TestFu will feature a DataSet graph object (DataGraph class) , i.e. a bidirectional directed graph G(V,E) where

• V is the set of vertices, one vertex per DataTable in the DataSet, (DataTableVertex class)
• E is the set of edges, one edge per DataRelation in the DataSet (DataRelationEdge class). The source vertex of the edge is the ParentTable, while the target is the ChildTable.

Why do we need a graph ?

Once you have the graph structure of the database, you use all the algorithms contained in the QuickGraph.Algorithms project: shortest path, topological sort, etc... In fact, you can even use it to draw the graph using the NGraphviz. There are of course other very interresting applications of this structure. For example, you can use the graph to create a table creation order such that will not violate the constraints, or you estimate the complixity of a join, etc...

Let's see some examples..

Creating a graph and basic usage

DataGraph lives in the TestFu.Data.Graph namespace and is built from a DataSet instance:

using Test.Data.Graph;
...
DataSet ds = ...;
DataGraph graph = DataGraph.Create(ds);

Now that we have a graph, we can iterate over it's vertices and edges:

// iterating the vertices (DataTableVertex)
foreach(DataTableVertex v in graph.Vertices)
{
    DataTable table = v.Table;
    ...
}

// iterating the edges
foreach(DataRelationEdge e in graph.Edges)
{
   DataRelation relation = e.Relation;
   ...
}

Let's see what other things we could do with graph.

Drawing the table structure:

This is an obvious usage of the graph and can be done quite easily using the QuickGraph.Algorithms.Graphviz.GraphvizAlgorithm class:

GraphvizAlgorithm gv = new GraphvizAlgorithm(this.graph);
gv.FormatVertex+=new FormatVertexEventHandler(gv_FormatVertex);
gv.FormatEdge+=new FormatEdgeEventHandler(gv_FormatEdge);
System.Diagnostics.Process.Start(gv.Write(dataSource.DataSetName));

...

void gv_FormatVertex(object sender, FormatVertexEventArgs e)
{
    DataTableVertex v = (DataTableVertex)e.Vertex;
    e.VertexFormatter.Shape = NGraphviz.Helpers.GraphvizVertexShape.Box;
    e.VertexFormatter.Label = v.Table.TableName;
}
void gv_FormatEdge(object sender, FormatEdgeEventArgs e)
{
    DataRelationEdge edge = (DataRelationEdge)e.Edge;
    e.EdgeFormatter.Label.Value = edge.Relation.RelationName;
}

The result on a sample DataSet is displayed below:

DataTable ordering

Another interresting application is to create an ordering of the DataTable such that if you fill the tables using this ordering, you will not break any constraint. This solves the old problem "which table should I populate first?". For example, in the example above, the ordering result would be:

1. Users,
2. Orders,
3. Categories,
4. Products,
5. OrderProducts

Since this feature has a major interrest in TestFu, it is built-in in the DataGraph class:

DataTable[] tables = graph.GetSortedTables();

In the background, graph uses the QuickGraph.Algorithms.SourceFirstTopologicalSortAlgorithm algorithm class which creates a topological ordering of the vertices of a graph by choosing the vertices with least in degree (very simple algo, home made):

// sort tables
SourceFirstTopologicalSortAlgorithm topo = new SourceFirstTopologicalSortAlgorithm(graph);
topo.Compute();

// output results
DataTable[] result = new DataTable[topo.SortedVertices.Count];
int i = 0;
foreach (DataTableVertex v in topo.SortedVertices)
{
    result[i++] = v.Table;
}
return result;

The SourceFirstTopologicalSortAlgorithm takes a IVertexAndEdgeListGraph instance which graph implements. As you can see, having a graph representation of your DataSet, compatible with QuickGraph opens a realm interresting applications of existing graph theory algorithms.

Next step: "Smart" Random Data generation

Once the table ordering is computed, you can safely generate "smart" random data and feed your DataSet...