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
///pair of vertices is adjacent.
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; }
}
Comments
- Anonymous
June 16, 2004
The comment has been removed - Anonymous
June 17, 2004
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. - Anonymous
June 17, 2004
The comment has been removed - Anonymous
June 17, 2004
The comment has been removed - Anonymous
June 17, 2004
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. - Anonymous
August 18, 2005
Very nice blog. It is very helpful. http://www.bignews.com