Abstract Grpah / Graph ADT

Relation: explicitly defined adjacency relation

The Abstract Graph defined on a set of objects called vertices and if tex:$$ a \rightarrow b $$ then the data structure stores a edge from tex:$$ a $$ to tex:$$ b $$. The collection of vertices and edges are denoted G and E, respectively, and the number of vertices and edges are denoted |G| and |E|, respectively.

In the case of a symmetric graph, edges are bidirectional.

In the case of a weighted graph, each edge is associated with a (usually a strictly positive numeric) weight.

Operations Relevant for Abstract Graphs

  • Add an edge between two vertices.
    void insert_edge( Vertex, Vertex );
  • Determine if there is an edge from one vertex to another.
    bool adjacent( Vertex, Vertex ) const;
  • Return an iterator which walks through the adjacent vertices.
    iterator adjacent( Vertex ) const;
  • Return the number of adjacent vertices (the degree) of a vertex.
    int degree( Vertex ) const;
  • Remove an edge.
    void remove( Vertex, Vertex ) const;

Operations Relevant for Abstract Weighted Graphs

These are simply modifications of insertions and verification.

  • Add an edge between two vertices.
    void insert_edge( Vertex, Vertex, double );
  • Determine if there is an edge from one vertex to another.
    double adjacent( Vertex, Vertex ) const;

In the last case, the value numeric_limits::infinity() is used to denote that two vertices are not adjacent/connected (there is an infinite distance between the two).

Operations Relevant for Abstract Directed Graphs

  • Return the number of adjacent vertices (the out-degree) of a vertex.
    int out_degree( Vertex ) const;
  • Return the number of vertices for which this vertex is adjacent to it (the in degree).
    int in_degree( Vertex ) const;

Queries Relevant to the Entire Graph

  • Are two vertices connected?
    bool are_connected( Vertex, Vertex ) const;
  • Return an iterator which walks through the path connecting two vertices in order.
    iterator connected( Vertex, Vertex ) const;
  • Is the graph connected?
    bool is_connected() const;
  • Is the graph connected?
    bool is_connected() const;
  • Is a directed graph strongly connected? (For each pair tex:$$ a $$ and tex:$$ b $$, is there a path from tex:$$ a $$ to tex:$$ b $$ and a path from tex:$$ b $$ to tex:$$ a $$?)
    bool is_strongly_connected() const;
  • Is a directed graph weakly connected? (For each pair tex:$$ a $$ and tex:$$ b $$, is there at least one path from from either tex:$$ a $$ to tex:$$ b $$ or from tex:$$ b $$ to tex:$$ a $$?)
    bool is_weakly_connected() const;

The operation to determine if two vertices are connected would similarly change for a weighted graph: double are_connected( Vertex, Vertex ) const;.

Example Data Structures

A graph data structure stores vertices and edges separately and edges may be stored in either:

  • A dense matrix,
  • An array of linked lists, or
  • A sparse matrix.

Some comments on these are:

  • A dense adjacency matrix uses the most amount of memory but is also the fastest (basic operations are O(1)) with the exception of determining those vertices adjacent to a given vertex.
  • An array of linked lists uses less memory for sparse graphs but is also significantly slower (basic operations are O(|E|/|V|). Determining those vertices adjacent to a given vertex, however, is significantly faster than that for a dense adjacency matrix.
  • A sparse adjacency matrix is appropriate if the edges are not added or removed too often and if they can be inserted in an order appropriate for the sparse matrix implementation (basic operations are O(ln(|E|/|V|)).