Graph Data Structures

interface

interface UndirectedGraph extends PositionalContianer {
    // global information 
    public VertexIterator vertices();
    public EdgeIterator edges();
    ...
     // local accessor methods
    public Vertex opposite(Vertex v, Edge e);
    public Vertex[] endVertices(Edge e);    // size is 2
    public EdgeIterator adjacentEdges(Vertex v);
    public boolean areAdjacent(Vertex v, Vertex w); 
    ...
    // local mutate methods
    public Object replace(Vertex v, Obect x) // returns old object
    public Object replace(Edge e, Obect x) // returns old object
    public Vertex insertVertex(Object o); 
    public Edge insertEdge(Vertex v, Vertex w, Object o); 
    public Vertex removeVertex(Vertex v);  // also removes all incident edges
    public void removeEdge(Edge e);
    ...
}

Note the author talks about edges and vertices as positions. :)

Data Structures for Graphs

There are three popular types:  all three have a container of all the vertices, V,  space requirement is O(n)

edge list: contains also a container for edges so space is O(n + m)
adjacency list: equivalent to edges so space is O(n + m)
adjacency matrix: contains all possible pairs of vertices so space is O(n²)  (although there are efficient ways to store sparse matrices)

Edge List Data Structure

Classes

class EdgeListVertex{
    private Object o; // Object stored at vertex

    // edge counts
    private int numIncidentEdges;
    // Note no reference to an EdgeIterators

    private Position vertex; // position of vertex in vertices container, V

    // set, get and is  public methods
}

class EdgeListEdge{
    private Object o; // Object stored at edge
    private boolean d; // true if directed edge

    // Positions in V for edges
    private Position[] endpoints(Edge e);   // in V

    private Position edge; // position of edge in edge list

    // set, get and is methods
}

Illustrate edge and vertex lists structures.
Note the list may be dictionaries for fast access.

Performance

The edge list is fast, O(1), access of vertices for a particular edge.
So the structure is good for edge based graph methods, for example, endVertices().

But access of edges incident on a vertex is slow, O(sizeof(EdgeList)) requiring a search through the edge list, for example:

incidentEdges()
areAdjcent()
removeVertex()

Edge List Performance:
 

n is the size of vertex container and m the size of the edge container so total size is O(n + m)

Adjacency List Data Structure

Classes

class AdjacencyListVertex {
    private Object o; // Object stored at this vertex

    private Position vertex; // position of vertex in vertex container, V

    // access for vertex to edges
    private EdgeContianer I;        // incident edge container for this vertex
    // space for edge container is the degree of this vertex

  // methods ...
}

class AdjacencyListEdge extends EdgeListEdge {
    // can be the same as for edge-list edge graph DS
}

Forms of Adjacency List data structure

• Modern - as above, with edge objects

• Traditional - edges, implied

Performance

The adjacency list structure provides direct access to edges form the vertices.
 

n is the size of vertex container and m the size of the edge container so total size is O(n + m)

Adjacency Matrix Data Structures

The adjacency list becomes a matrix

Classes

// Vertix class for adjacency-matrix graph DS
class AdjanceyMatrixVertex{
      private Object o;
      private Integer index;  //  0 <= index <= n-1,
                                       // key for this vertex in the adjacency in matrix
     ...
}

class AdjanceyMatrix{
      private Edge[][] A;  // size is nxn
      private int n; // number of Vertices
     ...
}

Forms of Adjacency Matrix

• Modern, as above the matrix stores edges

• Traditional, boolean or integer matrix, represents the existance of an edge

Performance

Now areAdjacent is direct and O(1)  but space requirement is O(n²)