Ideas on a Graph API
Went to an interesting talk about C5 (The Copenhagen Comprehensive C# Collection Classes). It had some very interesting idea presented, but I was dissapointed to see that there were no implementations of graphs or trees in the library. These types come up very commonly in a lot of the work that gets done. For example, the semantic links in a program form a graph. A parse 'tree' is exactly that, a 'tree'. To not have support to such primitives (along with algorithms to operate over them) means that we will have to implement them, others will have to implement them, and in general there will be about 50,000 implementations all over the world of a tree or a graph. I whipped out my copy of CLR and took a look at the chapters on graphs. From that I noticed that they described in general what a graph was and then showed a couple of implementations specifically one based on adjacency lists and one based on a bitmap to say if there were edges between vertices. Seemed a lot like a description of an interface and two actual concrete implementations. Based on that I came up with the following definitions:
public interface IEdge<A> {
A From { get; }
A To { get; }
bool SelfLoop { get; }
IEdge<A> Reverse { get; }
}
/// A Graph G is a pair (V, E), where V is a finite set and E is a
/// binary relation on V. The set V is called the vertex set of
/// G, and its elements are called vertices (singular:
/// vertex). The set E is called the edge set of G,
/// and its elements are called edges.
public interface IGraph<A> {
/// For a graph G = (V, E), this returns V
ISet<A> Vertices {
get;
}
/// For a graph G = (V, E), this return E
ISet<IEdge<A>> Edges {
get;
}
/// The set of states directly connected by one edge to this node.
/// This includes incoming and outgoing edges
Set<A> AllConnections(A vertex);
///If (u, v) is an edge in a Graph G = (V, E), we say that vertex v is
///adjacent to vertex u. When the graph is undirected, the
///adjacency relation is symmetric. When the graph is directed, the
///adjacency relation is not necessarily symmetric. If v is adjacent to u
///in a directed graph, we sometimes write u → v.
bool AreAdjacent(A u, A v);
///The degree of a vertex in an undirected graph is the
///number of of edges incident on it. The degree of a vertex
///in a directed graph is its in-degree plus its out-degree.
int Degree(A vertex);
/// We say that a graph G' = (V', E') is a subgraph of G =
/// (V, E) if V' ⊆ V and E' ⊆ E.
bool IsSubgraph(IGraph<A> g_prime);
///Given a set V' ⊆ V, the subgraph of g induced is the
///graph G' = (V', E'), where:
///
///E' = { (u, v) ∈ E : u, v ∈ V' }
IGraph<A> Induce(ISet<A> v_prime);
/// If there is a path p from u to u' we say that
/// u' is reachable from u via p.
bool IsReachable(A u, A u_prime);
}
Note: there may be some reducible redundancy in the API. For example, instead of: map.AreAdjacent("foo","bar"), you could write. map.Edges.Contains(new Edge("foo", "bar")). Personally, I like the latter. At first i was leaning more toward the former because i was thinking that there might be an asymptotic perf difference between the two. However, since I would be able to return a Set with specialized knowledge of the underlying graph, then the latter call could just be converted to the former call under the covers. So i think I'll go for the simplified API where graph focussed calls are kept on the graph, and information that could be gleaned from the Vertices/Edges can be called on those properties instead.
Edit: Damien provides a link to their paper