The Graph ADT

Get access to whole semester resourcesSemester Pass

Chapter Eighty-Nine

Syllabus topic Module 2, "Graph: Graph ADT"

Pages 282 to 284 of 411

In one line

The graph ADT is add and remove vertices and edges, ask whether two vertices are joined, and list a vertex's neighbours, and the last of those is what every algorithm in the following chapters actually uses.

The ADT

A Graph holds a set of vertices and a set of edges joining them.

Operation	Needs	Returns	Does
`Graph()`	nothing	an empty graph	creates it
`add_vertex(v)`	a vertex	nothing	adds it, with no edges
`add_edge(u, v)`	two vertices	nothing	joins them; error if either is absent
`remove_edge(u, v)`	two vertices	nothing	unjoins them
`remove_vertex(v)`	a vertex	nothing	removes it and every edge on it
`has_edge(u, v)`	two vertices	true or false	are they joined
`neighbours(v)`	a vertex	the vertices joined to v
`vertices()`, `edges()`	nothing	the sets
`degree(v)`	a vertex	a number	how many edges on v

For a weighted graph, add_edge takes a weight and a weight(u, v) operation is added. For a directed graph, add_edge(u, v) joins u to v only, and neighbours means successors, with a separate predecessors if needed.

Two rows carry most of the design:

remove_vertex removes its edges too. Leaving an edge pointing at a vertex that no longer exists is the standard defect, and chapter 93 measures what it costs to do properly.

neighbours(v) is the operation that matters. Every traversal, every search and every shortest path in this paper is a loop over neighbours. Its cost, not has_edge's, decides whether an algorithm is fast, which is the whole of chapter 92.

The ADT, used before it is implemented

class Graph:
    """The ADT. The representation underneath is deliberately not the point of
    this chapter; chapters 90 and 91 give two, and a caller written here works
    with either."""

    def __init__(self, directed=False):
        self._adjacent = {}
        self.directed = directed

    def add_vertex(self, v):
        self._adjacent.setdefault(v, set())

    def add_edge(self, u, v):
        if u not in self._adjacent or v not in self._adjacent:
            raise KeyError("both vertices must exist: %r, %r" % (u, v))
        self._adjacent[u].add(v)
        if not self.directed:
            self._adjacent[v].add(u)

    def remove_edge(self, u, v):
        self._adjacent[u].discard(v)
        if not self.directed:
            self._adjacent[v].discard(u)

    def remove_vertex(self, v):
        if v not in self._adjacent:
            raise KeyError("no such vertex: %r" % (v,))
        del self._adjacent[v]
        for others in self._adjacent.values():
            others.discard(v)              # every edge ON it goes too

    def has_edge(self, u, v):
        return v in self._adjacent.get(u, ())

    def neighbours(self, v):
        return sorted(self._adjacent[v])

    def vertices(self):
        return sorted(self._adjacent)

    def edges(self):
        if self.directed:
            return sorted((u, v) for u, ns in self._adjacent.items() for v in ns)
        return sorted({tuple(sorted((u, v)))
                       for u, ns in self._adjacent.items() for v in ns})

    def degree(self, v):
        return len(self._adjacent[v])


g = Graph()
for city in ("Mumbai", "Pune", "Nashik", "Nagpur", "Goa"):
    g.add_vertex(city)
for a, b in (("Mumbai", "Pune"), ("Mumbai", "Nashik"), ("Pune", "Nashik"),
             ("Nashik", "Nagpur")):
    g.add_edge(a, b)

print("vertices  :", g.vertices())
print("edges     :", ["%s-%s" % e for e in g.edges()])
print("neighbours of Nashik:", g.neighbours("Nashik"))
print("degree of Nashik    :", g.degree("Nashik"))
print("Mumbai joined to Nagpur:", g.has_edge("Mumbai", "Nagpur"))
print("Goa has no edges        :", g.neighbours("Goa") == [])

print()
g.remove_vertex("Nashik")
print("after removing Nashik:")
print("   vertices:", g.vertices())
print("   edges   :", ["%s-%s" % e for e in g.edges()])
print("   every edge ON Nashik went with it:",
      all("Nashik" not in e for e in g.edges()))
print("   Nagpur is now isolated:", g.neighbours("Nagpur") == [])

print()
try:
    g.add_edge("Mumbai", "Chennai")
except KeyError as e:
    print("adding an edge to a missing vertex is refused:", e)

The Graph ADT

vertices  : ['Goa', 'Mumbai', 'Nagpur', 'Nashik', 'Pune']
edges     : ['Mumbai-Nashik', 'Mumbai-Pune', 'Nagpur-Nashik', 'Nashik-Pune']
neighbours of Nashik: ['Mumbai', 'Nagpur', 'Pune']
degree of Nashik    : 3
Mumbai joined to Nagpur: False
Goa has no edges        : True

after removing Nashik:
   vertices: ['Goa', 'Mumbai', 'Nagpur', 'Pune']
   edges   : ['Mumbai-Pune']
   every edge ON Nashik went with it: True
   Nagpur is now isolated: True

adding an edge to a missing vertex is refused: "both vertices must exist: 'Mumbai', 'Chennai'"

Removing Nashik removed three edges with it, and Nagpur, which was only reachable through Nashik, became isolated. Removing a vertex can disconnect a graph, which no other removal in this paper could do.

The directed case

class Graph:
    def __init__(self, directed=False):
        self._adjacent = {}
        self.directed = directed

    def add_vertex(self, v):
        self._adjacent.setdefault(v, set())

    def add_edge(self, u, v):
        self._adjacent[u].add(v)
        if not self.directed:
            self._adjacent[v].add(u)

    def neighbours(self, v):
        return sorted(self._adjacent[v])

    def predecessors(self, v):
        return sorted(u for u, ns in self._adjacent.items() if v in ns)

    def in_degree(self, v):
        return len(self.predecessors(v))

    def out_degree(self, v):
        return len(self._adjacent[v])


d = Graph(directed=True)
for page in ("home", "notes", "papers", "chapter"):
    d.add_vertex(page)
for a, b in (("home", "notes"), ("home", "papers"),
             ("notes", "chapter"), ("papers", "chapter")):
    d.add_edge(a, b)

print("%-9s %-22s %-22s %s" % ("page", "links to", "linked from", "out/in"))
for page in ("home", "notes", "papers", "chapter"):
    print("%-9s %-22s %-22s %d/%d"
          % (page, str(d.neighbours(page)), str(d.predecessors(page)),
             d.out_degree(page), d.in_degree(page)))

print()
print("'home' has out-degree 2 and in-degree 0: nothing links to it.")
print("'chapter' has out-degree 0 and in-degree 2: it is a dead end.")
print()
print("finding predecessors cost a scan of the WHOLE graph, which successors did not.")
print("that asymmetry is real and chapter 92 measures it.")

page      links to               linked from            out/in
home      ['notes', 'papers']    []                     2/0
notes     ['chapter']            ['home']               1/1
papers    ['chapter']            ['home']               1/1
chapter   []                     ['notes', 'papers']    0/2

'home' has out-degree 2 and in-degree 0: nothing links to it.
'chapter' has out-degree 0 and in-degree 2: it is a dead end.

finding predecessors cost a scan of the WHOLE graph, which successors did not.
that asymmetry is real and chapter 92 measures it.

The asymmetry at the end is worth noticing: a directed graph stores its edges one way, so successors are immediate and predecessors cost a scan of everything. A structure needing both commonly stores the graph twice, once forwards and once reversed.

The Graph ADT

Quick revision

The graph ADT: add and remove vertices and edges, has_edge, neighbours, vertices, edges, degree.
Weighted graphs add a weight to add_edge and a weight(u, v) operation; directed graphs make add_edge

one way and add predecessors.

remove_vertex must remove every edge on the vertex, or edges are left pointing at something that no

longer exists.

Removing a vertex can disconnect the graph, which no removal in the earlier structures could do.
neighbours(v) is the operation that matters: every traversal and search is a loop over it, and its

cost decides whether an algorithm is fast.

In a directed graph, successors are immediate and predecessors cost a full scan, so a structure needing

both stores the graph twice.

Test yourself

1. Write the graph ADT. add_vertex, add_edge, remove_edge, remove_vertex, has_edge, neighbours, vertices, edges and degree, with a weight on edges for a weighted graph and one-way edges plus predecessors for a directed one.

2. What must remove_vertex do beyond removing the vertex, and what happens if it does not? It must remove every edge on that vertex. Otherwise edges are left pointing at a vertex that no longer exists.

3. Which operation do the later algorithms actually depend on, and why does that matter? neighbours(v). Every traversal, search and shortest path is a loop over it, so its cost, rather than has_edge's, decides the complexity of the algorithms.

4. What can removing a vertex do that no removal from the earlier structures could? Disconnect the structure, leaving vertices that are no longer reachable, as removing Nashik isolated Nagpur.

5. Why are predecessors expensive in a directed graph? Because edges are stored at their source only, so finding what points at a vertex means scanning every vertex's list.

6. How is that usually solved in practice? By storing the graph twice, once as given and once with every edge reversed, so both directions are immediate.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue