course-web-page-Fall-2021

Repository for the Fall 2021 course web page

View the Project on GitHub IUDataStructuresCourse/course-web-page-Fall-2021

Lecture: Graphs and Topological Sorting

The standard mathematical way to represent a graph G is with a set of vertices V and a set of edges E, that is, G = (V,E).

In a directed graph, each edge is a pair of vertices where the first vertex is called the source and the second is the target.

In an undirected graph, each edge is a set containing two distinct vertices.

I often use n for the number of vertices and m for the number of edges.

**Example of a directed graph.**

The set of vertices for this graph is

{0,1,2,3,4,5}.

The set of edges is

{(0,0), (1,2),(1,4),  (2,5),  (3,5),(3,0),  (4,2),  (5,4),  }.

Given edge (u,v) in a directed graph, we say v is adjacent to u. We sometimes write u to v for the edge (u,v).

The edge (u,v) is an out-edge of u and an in-edge of v.

The out-degree of a vertex is the number of its out-edges.

The in-degree of a vertex is the number of its in-edges.

**Example of an undirected graph.**

The set of vertices is {0,1,2,3,4}.

The set of edges is { {1,2},{1,0}, {2,3},{2,4},{2,0}, {3,4}, {4,0} }.

We often writes an undirected edge as (1,2) or 1-2 instead of {1,2}.

Given edge {u,v} in an undirected graph, we say u and v are adjacent to each other.

We say that edge {u,v} is incident on vertex u and v.

The degree of a vertex is the number of edges incident on it.

Adjacency List

The Adjacency List representation of a graph is an array of linked lists.

Example: for the above directed graph the adjacency list representation is

 |0| -> 0
 |1| -> 2 -> 4
 |2| -> 5
 |3| -> 0 -> 5
 |4| -> 2
 |5| -> 4

Example: for the above undirected graph the adjacency list representation is

 |0| -> 1 -> 2 -> 4
 |1| -> 0 -> 2
 |2| -> 1 -> 4 -> 3 -> 0
 |3| -> 2 -> 4
 |4| -> 0 -> 3 -> 2

(Each edge is stored twice.)

Adjacency lists are good for storing sparse graphs.

Adjacency Matrix

The Adjacency Matrix representation of a graph is a Boolean matrix.

Example, for the directed graph above.

  0 1 2 3 4 5
0 1 0 0 0 0 0
1 0 0 1 0 1 0
2 0 0 0 0 0 1
3 1 0 0 0 0 1
4 0 0 1 0 0 0
5 0 0 0 0 1 0

Example, for the undirected graph above.

  0 1 2 3 4
0 0 1 1 0 1
1 1 0 1 0 0
2 1 1 0 1 1
3 0 0 1 0 1
4 1 0 1 1 0

Note that the matrix is symmetric.

Adjacency matrices are good for dense graphs.

How could we represent Adjacency Matrices in Java?

Topological sorting

Makefile example for building software (a) zig.cpp (b) boz.h (c) zag.cpp (d) zig.o (e) zag.o (f) libzigzag.a

**Graph of the makefile dependencies.**

Recall that a topological ordering is an ordering A of the vertices such that if A[i] -> A[j], then i < j.

In other words, a vertex needs to come before every other vertex that depends on it.

Here are many (all?) of the topological orderings:

a,b, c, d,e, f
b,a, c, d,e, f
a,b, c, e,d, f
b,a, c, e,d, f
a,b, d, c,e, f
b,a, d, c,e, f
c,e, a,b, d, f
c,e, b,a, d, f

Knuth’s version of Kahn’s algorithm for topological sort

static <V> void topo_sort(Graph<V> G, 
						  Consumer<V> output,
						  Map<V,Integer> num_pred) {
	// initialize the in-degrees to zero
	for (V u : G.vertices()) {
		num_pred.put(u, 0);
	}
	// compute the in-degree of each vertex
	for (V u : G.vertices())
		for (V v : G.adjacent(u))
		num_pred.put(v, num_pred.get(v) + 1);

	// collect the vertices with zero in-degree
	LinkedList<V> zeroes = new LinkedList<V>();
	for (V v : G.vertices())
		if (num_pred.get(v) == 0)
		zeroes.push(v);

	// The main loop outputs a vertex with zero in-degree and subtracts
	// one from the in-degree of each of its successors, adding them to
	// the zeroes bag when they reach zero.
	while (zeroes.size() != 0) {
		V u = zeroes.pop();
		output.accept(u);
		for (V v : G.adjacent(u)) {
		num_pred.put(v, num_pred.get(v) - 1);
		if (num_pred.get(v) == 0)
			zeroes.push(v);
		}
	}
}

Time Complexity of Topological Sort (Knuth’s version)

  1. Compute in-degrees

    Outer loop processes every vertex: O(n)

    Outer + inner loop processes every edge: O(m)

    Total: O(n + m)

  2. Collect vertices with zero in-degree: O(n)

  3. Main loops (while + for) processes each edge just once: O(m)

Total: O(n + m) or because m in O(n²), total is O(n²).

Student Exercise

topologically sort the following graph

V = { belt, jacket, pants, socks, shoes, shirt, tie, undershorts, watch }

E = { belt -> jacket,
	  pants -> shoes, pants -> belt,
	  socks -> shoes,
	  shirt -> tie, shirt -> belt,
	  tie -> jacket,
	  undershorts -> pants, undershorts -> shoes }

solution: (one of many)

socks, undershorts, pants, shoes, watch, shirt, belt, tie, jacket