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

Hi Cyrus,

I don’t think you should "hard code" strongly connected components into your graph interface. This property is more algorithm that acts on the structure than the structure itself.

Cheers,

Jonathan

Jonathan: I’ll have to see about that. I would think specialized graph implementations would provide knowledgable methods to determine if it was StronglyConnected. For example, if I had a ‘SingletonVertexGraph’ or ‘SingletonEdgeGraph’ they they could just respond with "true" to that call. However, for graphs that couldn’t provide an implementation dependent method, they would be passed off to something like:

new StrongConnectedComponentsFinder(graph).Run()

Or something like that.

Having it on the graph ittself means that if the graph figures out what’s strongly connected by using some sort of dynamic programming algorithm, then those results will be avilable for other algorithms you might need. By using weak references you can cache that information but not at the expense of extra memory usage since they can be reclaimed if not needed.

There are other advantages of separating algo from strongly connected components:

1. Strong component is just one of mannnny other graph related algorithms, you interface is going to get overcrowed soon,

2. You usually want to attach visitors that record predecessors, distance, etc.. to algo,

3. It’s not dynamic programming algorithm. It’s just an application of Depth first search( Tarjan algo) (see http://www.boost.org/libs/graph/doc/strong_components.html)

ðŸ™‚

Hrmm… I’m unconvinced (so far). The strong components of a graph are a property of that graph that are well expressed as just that, a property. The implementation is free to do whatever it wants. It can solve the problem itself, or it can call out to another class to execute wahtever algorithm it deems fit to produce the result.

Note: By allowing this to operate on graphs, and to add constraints like persistent/immutable graphs, then you can have the added nicity of caching the strongly connected components after you calculate them the first time. This way you don’t have recomute it every time asked.

i.e. I could see someone doing the following:

public abstract class AbstractDirectedGraph<A> : IDirectedGraph<A> {

public virtual ISet<ISet<A>> StronglyConnectedComponents {

get {

return new StronglyConnectedGraphFinder(this).TarjansMethod();

}

}

}

Thus you can get the benefit of a general algorithm that will work on any graph, and specialized versions that are tailored for the specific graph implementation. For example, with many graph problems you change the approach you use based on whether hte graph is implemented as an adjacency list or an adjacency matrix (bitmap). Rather than having someone eremember "should i use StronglyConnectedGraphFinder(this).MethodForAdjacencyList(); or MethodForAdjacencyMatrix();", that logic can be left up to the actual concrete class which knows how it was implemented.

Note: I am not trying to produce a change in the graph with these methods. I.e. they are not equivalent to a ‘sort’ method that ends up changing the underlying representation. Rather they are expressions of traits that the graph has. I can’t imagine a better place for that expression than on the interface itself.

Very nice blog. It is very helpful. http://www.bignews.com