Advanced Programming I Lecture Notes

21 March 2006 • Graph Basics

Outline

Some problems.
Terminology
Graph ADTs.
Graph Traversals.
Graph Implementations.

Route Finding

A more recent, fuller map.

Traffic Scheduling

Schematic Analysis

Graphs

All these problems - and more - can be solved with graphs.
Graphs can
- model the problems, and
- provide algorithms to find solutions.
The generality with which graphs do these things makes them useful and important.

The Königsberg Bridges

The Bridges Problem

Is it possible to walk all seven bridges once?
Leonhard Euler answered the question in 1735.
Model each land mass as a point.
Model each bridge as a connection between points.
A parity argument shows it's impossible.
- Such a walk is a Euler path.

Graph Terminology

A graph G is a set of vertices V and a set of edges E between the vertices in V.
- Either of V or E may be empty.
- Because V and E are sets, they contain no duplicates.
- Vertices are sometimes nodes; edges are sometimes arcs or links.
Trees are a special-case of graphs.
- A tree is a connected acyclic graph.

Graph Labels

Vertices and edges may have labels.
- The graph is known as a labeled graph
Numeric edge labels are called weights.
- The edges are weighted edges and the graph is a weighted graph.

Graph Models

When modeling, graph vertices represent entities and edges represent relations between entities.
- Vertices can represent Internet routers, terminal cities, electronic components, or land masses.
- Edges can represent networks between routers, flights between cities, wires between components, or bridges between land masses.

Graph ADTs

Graph ADTs tend to be complex.
- Graphs are complex and open ended.
- Graphs models can be complex.
- Graph algorithms can be complex.
- And then there's efficiency and convenience.
Graph ADTs tend towards the extremes.
- Either minimal or specialized ADTs.

Graph Traversal

A graph traversal is an algorithm that visits vertices in a graph.
Traversals are necessary for searching a graph.
The main idea is to follow edges from one vertex to the next.
- The result is a sequence of vertices visited: V₁, V₂, V₃, ...
Different traversals produce vertex sequences with different properties.

More Graph Terms

A directed edge provides one-way traversal.

a directed edge

A directed graph (digraph) has directed edges.

An undirected edge allows two-way traversal.
- An undirected edge is a pair of directed edges.

Paths

A path between vertices v₁ and v_n, n ≥ 1, is a sequence of vertices v₁, v₂, ..., v_n such that
- The edge (v_i, v_{i + 1}) exists for 1 ≤ i < n.
The path length is n - 1 (the number of edges).
- Paths may have arbitrary length (n > |V|).
Traversals produce paths.

Adjacency

Two vertices are adjacent if they're connected by an edge.
- Adjacency follows a directed edge.
Two vertices are neighbors if they're adjacent.

Basic Traversal

The basic idea behind traversal is:
1. Get all neighbors of the current vertex.
2. Pick one of the neighbors and make it current.
Traversal algorithms differ in
1. how neighbors are selected, and
2. how the new current vertex is selected.

One-Visit Assumption

Assume each vertex should be visited at most once.
This requires either
- a visited bit in each vertex or
- the algorithm keep track of visited vertices itself.
Selecting neighbors now inolves find all unvisited neighbors.

Graph Traversal

dt(graph g, vertex current)
  current.visiting = true
  set pending(current)
  while not pending.empty()
    current = pending.pick()
    current.visited = true
    for each n in g.neighbors(current)
      if not n.visited
        n.visited = true
	pending.add(n)

Note the graph ADT query operator neighbors().

Graph Traversal Properties

The graph traversal is discontinuous.
- It follows edges until there aren't any more.
- Then it jumps back to a pending vertex (if any).
- The jumps are known as backtracking.

Graph Algorithm Performance

The two main performance parameters for a graph are
1. The number of vertices |V|.
2. The number of edges |E|.
Graph ADT operator performance depends on implementation details.

Graph Traversal Peferformance

set pending(current)          O(1)
while not pending.empty()     O(1)×O(|V|)
  current = pending.pick()    O(1)
  nbrs = g.neighbors(current) O(|V|)
  for each n in nbrs          O(1)×O(|V|)
    if not n.visited          O(1)
      n.visited = true        O(1)
      pending.add(n)          O(log |E|)

A rough accounting gives O(|V|²log |E|).
A finer accounting gives O(|V| + |E|).

A Simple Problem

Given a graph G and a vertex v in G, find another vertex v' in G that is one of the vertices closest to v that satisfies a prediate p().
- Vertex distance is path length.
Randomly backtracking isn't going to solve this problem.

Ordered Backtracking

Backtrack to a vertex closest to v.
- The children, and then the grandchildren, and then ...
The first neighbers found should be the first vertices backtracked to.
First in, first out - queue pending neighbors.

Breadth-First Traversal

vertex
bft(graph g, vertex current)
  queue pending.enq(current)
  while not pending.empty()
    current = pending.deq()
    current.visited = true
    for each v in g.neighbors(current)
      if p(v) return v
      if not v.visited
        v.visited = true
	pending.enq(v)

Cycles

A cycle (or circuit) is a path in which v₁ = v_n.
- The path should have at least one edge.
- An Euler circuit is an Euler path that ends where it started.
A graph with no cycles is acyclic.
A path with no cycles is a simple path.

Another Simple Problem

Given a graph G determine if G contains a cycle.
A path with a cycle contains repeated vertices.
- Visiting an already visited vertex.
Random or breadth-first backtracking jump around too much.
The next vertex to visit should be one of the most recent neighbors found.
Last in, first out - use a stack

Depth-First Traversal

bool
dft(graph g, vertex current)
  stack pending.push(current)
  while not pending.empty()
    current = pending.pop()
    current.visited = true
    for each v in g.neighbors(current)
      if v.visited
        return true
      else
        n.visited = true
	pending.push(n)

Graph ADT

Stick with the basics, extended for vertices and edges.
- Don't forget labels and directedness.
Create and delete graphs, vertices, and edges.
Add and remove operations for vertices and edges.
All manner of search operations, including depth- and breadth-first searches.

Example Graph ADTs

The Graph Template Library.
The Boost Graph Library.
- There's also a parallel version.
The Adaptave Graph Library, which adjusts implementations based on applied operations.
A specialized library for representing control-flow graphs used in compilers.

Adjacency Matrix

A |V|×|V| boolean matrix indexed by vertices.
An undirected graph can use a-half diagonal matrix.

Edge Lists

Adjacency matrices are wasteful with few (or many) edges.
Slice along the rows (or columns).
Keep only the true (or false) entries.

Vertex Lists

Edge lists waste half their space for undirected graphs.
Thread the vertices through the edges.

This page last modified on 13 April 2006.
This work is covered by a
Creative Commons License.