Specialized interface for graphs

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> {
///A complete graph is an undirected graph in which every
bool Complete { get; }

///A bipartite graph is an undirected graph G = (V, E) in
///which V can be partitioned into two sets V1 and
///V2 such that (u, v) ∈ E implies that either
///(u ∈ V1 and v ∈ V2) or
///(u ∈ V2 and v ∈ V1).  That is, all edges
///go between the two sets V1 and V2.
bool Bipartite { get; }

///An undirected graph is connected if every pair of vertices
///is connected by a path.
bool Connected { get; }
}


The directed graph allows for further operations:

        public interface IDirectedGraph<A> : IGraph<A> {
///Given a directed graph G = (V, E), the undirected graph of
///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 is strongly connected if 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, the out-degree of a vertex is the
///number of edges leaving it
int OutDegree(A vertex);

///In a directed graph, the in-degree of 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; }
}


1. 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

2. 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.

3. 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)

🙂

4. 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.

5. 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.

6. mirela says:

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