After the initial graph implementation i started looking more at the the specializations and cabilities that were added to graphs to make them appropriate for certain situations. Two of those that came up were the directed and undirected graphs.

So far these are what I've come up with:

public interface IUndirectedGraph<A> : IGraph<A> { ///Ais an undirected graph in which every ///pair of vertices is adjacent. bool Complete { get; } ///Acomplete graphis an undirected graph G = (V, E) in ///which V can be partitioned into two sets Vbipartite graph_{1}and ///V_{2}such that (u, v) ∈ E implies that either ///(u ∈ V_{1}and v ∈ V_{2}) or ///(u ∈ V_{2}and v ∈ V_{1}). That is, all edges ///go between the two sets V_{1}and V_{2}. bool Bipartite { get; } ///An undirected graph isif every pair of vertices ///is connected by a path. bool Connected { get; } }connected

The directed graph allows for further operations:

public interface IDirectedGraph<A> : IGraph<A> { ///Given a directed graph G = (V, E), theof ///G is the undirected graph G' = (V, E'), where (u, v) ∈ E' if and ///only if u ≠ v and (u, v) ∈ E. That is, the undirected version ///contains the edges of G "with their directions removed" and with ///self-loops eliminated. (Since (u, v) and (v, u) are the same edge in an ///undirected graph, the undirected version of a directed graph contains it ///only once, even if the directed graph contains both edges (u, v) and ///(v, u).) IUndirectedGraph<A> ToUndirectedGraph(); ///A directed class isundirected graphif every two ///vertices are reachable from each other. bool StronglyConnected { get; } ///Given a directed graph D=(V, E), a subgraph S=(V', E') is a strongly connected component if ///a) S is strongly connected, and, ///b) for all vertices u such that u ∈ V and u ∉ V' for which (u,v) ∈ E ///This returns the set of all strongly connected components in this directed graph ISet<ISet<A>> StronglyConnectedComponents { get; } ///In a directed graph, thestrongly connectedof a vertex is the ///number of edges leaving it int OutDegree(A vertex); ///In a directed graph, theout-degreeof a vertex is the ///number of edges entering it. int InDegree(A vertex); ///Returns all the vertices that have an edge pointing to this vertex ISet<A> InConnections(A vertex); ///Returns all the vertices that this vertex has an edge to ISet<A> OutConnections(A vertex); ///Returns G transpose, which is defined to be the graph G' = (V,E tranpose), ///where E transpose = {(u,v) : (v,u) \in E} DirectedGraph<A> Transpose { get; } ISet<IList<A>> SimpleCycles { get; } }in-degree