SmartGraph.Dag An implementation of Directed Acyclic Graphs

Contents

1. Introduction
2. Directed Acyclic Graphs
3. The SmartGraph.Dag implementation
4. SmartGraph.Dag.Algorithm

Introduction

The SmartGraph.Dag library contains classes and algorithms for building and manipulating Directed Acyclic Graphs (or DAGs).

Directed Acyclic Graphs

A graph, in general, is a container of vertices and edges. A vertex is an object i.e. whatever you want it to be, and an edge is a tuple of vertices (source, target) where the order of the items in the tuple does not matter. A DAG is a type of graph where an edge is an ordered tuple. A DAG thus specifies a set of relationships on a set of objects. The 'relationship' says that one object is dependent on another ie the target depends on the source.

SmartGraph.Dag implementation

An interface-based approach to implementation has been used throught the library. The following interfaces are defined:

• IDAGObject - defines a base for all other 'DAGObjects'.
• IVertex (derived from IDAGObject) - defines a vertex (or node).
• IEdge (derived from IDAGObject) - defines an edge (source, target).
• IGraph (derived from IDAGObject) - defines a container of vertices and edges.
• IGraphFactory - defines a set of methods for creating IGraph's.

SmartGraph.Dag.Algorithm

The following algorithms have been implemented:

• DepthFirstSearch - performs a depth-first-search (or DFS). This means following the out-edges (from source to target) of vertices.
• ToplogicalSort - sorts the vertices of a graph based on the edges. The creates an ordering on the vertices of the graph based on their inter-dependencies which is a kind of DFS. The difference is that each node is 'noted' *after* all its children have been 'noted' and not *before* like in DFS.
• EquivalenceClasses - sorts vertices of a graph into lists of vertices. Nodes in the same list have a 'connection' in other words directedness of edges is not taken into account.