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


Comments (4)

  1. BillT says:

    "When the graph is directed, the adjacency relation is not necessarily symmetric."

    so adjacency could be this:

    map.AreAdjacent("foo","bar") == map.Edges.Contains(new Edge("foo", "bar")) | map.Edges.Contains(new Edge("bar", "foo"))

    That’s a bit long to be a replacement for AreAdjacent().

    Due to that "not necessarily symmetric", another property is need to define whether adjacency should be symmetric or not, perhaps:

    bool IsAdjacencySymmetric();

    And isn’t directedness important, too?

    bool IsDirected();

    I’ve been reading some of your blather since it began. [Voluminous, ain’t it 🙂 ] I’m very interesting in a good .NET graph library. Please keep us informed as you continue exploring this area.

  2. BillT: See my further post with specialized Undirected/Directed Graph interfaces.

    So in the undirected case, an Edge(a, b) is equivalent to Edge(b, a). So:

    map.Edges.Contains(new Edge("foo","bar"))

    would be equivalent to:

    map.Edges.Contains(new Edge("bar","foo"))

    In the directed case, the two calls would be separate.

  3. damien morton says:

    For those that are interested, the C5 paper canbe found here: http://www.itu.dk/~kokholm/c5/c5report.pdf

  4. Juan Felipe Machado says:

    I think you should speak with Jonathan De Halleux, he has been working with graphs in .NET a lot (not in generics, but I think he can be useful), so i’m sure he has some ideas about this (He works at Microsoft too)

    His blog : http://blog.dotnetwiki.org/

    His graph library: http://mbunit.tigris.org/