1 of 47

COMP 210

Lecture 19

1

2 of 47

Announcements

Bug in EX13 grader. I will fix it right after class and re-build.

No other tests should be impacted except put - chaining nodes and remove
But if you were writing your own unit tests you should be good to go :’)

Ask questions anonymously at: pollev.com/kakiryan876

2

3 of 47

Graphs

3

4 of 47

Planar Graph

All edges can be drawn on a plane with none crossing

4

5 of 47

Planar Graph

All edges can be drawn on a plane with none crossing
Determining planarity is important in laying out VLSI circuits on boards

Metal wires can’t cross!

So here’s another graph algorithm… given graph G, is it planar?

Have to solve this by wandering around in data structures for V, E you don’t have a drawing

5

6 of 47

Planar Graph

What about K5?

6

7 of 47

Planar Graph

What about K5?

7

8 of 47

Planar Graph

What about K5?

No matter which inner edge you “stretch” you get a cross (K4 is largest planar graph!)

8

9 of 47

Planar Graph

Rule of Thumb… Don’t trust your eye!
This graph “drawing” looks not planar…

The graph might still be planar… it just might be drawn poorly to show that

A graph is not the drawing… a graph is the math object

9

10 of 47

Bipartite Graph

Nodes are in two disjoint sets (types), and every edge connects different type nodes

10

11 of 47

More Bipartite

Can think of bipartite as colorable with 2 colors

Every edge goes between the 2 color collections

11

12 of 47

Are trees bipartite?

12

13 of 47

Graph Representations

Two main strategies:

Adjacency Matrix

Store vertex information as an array of vertex objects.
Each vertex associated with an index (position in the array)
Store edge information in a 2D array

Entry [i,j] represents edge from vertex i to vertex j
Adjacency List

Each vertex object maintains a list of edge objects

13

14 of 47

Adjacency Matrix (unweighted edges)

For N nodes, use an NxN array of Boolean

True = edge exists
False = edge does not exist

14

15 of 47

Adjacency Matrix (weighted edges)

Weighted edges

Value of array elements provides weight (integer or real as needed)
Special value for no edge case.
Can be generalized as matrix of edge objects that provide arbitrary information associated with edge.

15

16 of 47

Adjacency Matrix Drawbacks

Vertices must be identified by index

Problematic for applications / algorithms involving dynamic graphs
May require a separate map from other identifying information such as a vertex label to the appropriate index.

Examples on prior slides used character labels, but in reality we would need to map those labels to index values first.

Wasted space

Space required is O(|V|²)
Undirected graphs store each edge twice
OK if |E| ≈ |V|² but not if |E| << |V|²

Adjacency test is expensive

O(|V|) operation to look at all matrix entries in a given row.

16

17 of 47

Sparse vs. Dense Graphs

Dense Graph

|E| ≈ |V|²

Sparse Graph

|E| << |V|²

Is graph to the right dense or sparse?

1538 nodes, 8032 edges
(1538 nodes)^2 is 2365444
8032 edges ≪ 2365444
Sparse!

17

18 of 47

Complete Graphs are Dense

18

19 of 47

Adjacency List

Several variations, but basic idea is that vertex model includes a list of edge information associated with that vertex.
One possibility

Model vertices as list (or map) of vertex objects
Each vertex object contains a list of adjacent vertices

Another possibility

Model both vertices and edges as objects

Definition of vertex object includes a list of edges
Definition of edge object includes reference to endpoint vertexes

Weight or other edge characteristics included in edge object

19

20 of 47

Adjacency List Misc.

Space needed: O(|V| + |E|)
Directed vs Undirected Edges

Directed edges will have a “source” and “destination”

All edges on the adjacency list of a particular vertex will have the same source
Finding vertices adjacent to a particular vertex is easy because it’s always the “destination” of the edges on the adjacency list for the vertex in question.

Undirected edges will have to have some name property like “endpointA” and “endpoint B” to refer to the vertices that it connects

Edges on the adjacency list of a particular vertex may refer to that vertex either way.

Slightly complicates adjacency test because you have to check both properties to figure out which is the “adjacent” vertex.

20

21 of 47

Vertex and Edge Maps

Very often will need a map for vertexes

Allows looking up vertex structure by “name” or other identifying property.

Map<String, Vertex> vertexMap = new HashMap<String,Vertex>();
vertexMap.put(“A”, v);
Vertex v = map.get(“A”);

Many graph algorithms will be inefficient without a vertex map

If you need to find a vertex, you generally don’t want to spend O(|V|) time searching through some sort of “all vertices” list.

HashMap will provide O(1) lookup

May need similar map structure for edges depending on what you are trying to do.

21

22 of 47

Topological Sort: Our first graph algorithm

Applicable for DAGs

Ordering of vertices in a DAG such that if (u,v) is an edge in the graph then u precedes v in the ordering
Every DAG has at least 1 topological sort order

Some may have more than 1

If a graph has a cycle, then topological sort is not possible.

Which vertex in the cycle could come first in the order?
Easy check for cycle:

If there is no vertex with an “in-degree” of 0, then there must be a cycle.
In-degree = number of incoming directed edges to a vertex
Out-degree = number of outgoing directed edges from a vertex

22

23 of 47

Examples of Topo Sort (1/2)

23

24 of 47

Examples of Topo Sort (2/2)

24

25 of 47

Degree Properties

25

26 of 47

Topological Sort Algorithm

Finds topological sort order in O(|V| + |E|) time
Build directed graph G = (V,E) with adjacency lists

Calculate / store in-degree of each vertex during build

Topo Sort Algorithm

Initialize empty list of vertices
Step 1: Pick / find a node v with in-degree 0 and add to list

If no such node, then algorithm fails

Step 2: Remove v and its outgoing edges from the graph, updating in-degree of adjacent vertices
Step 3: If graph is not empty, go to step 1.

26

27 of 47

Execute on Example (1/2)

27

28 of 47

Execute on Example (2/2)

28

29 of 47

What happens with cycles?

29

30 of 47

Topological Analysis

O(|V|+|E|)

We examine and remove each vertex, so we handle each vertex once
For each vertex, we remove its out edges, which means we operate on each edge once

In theory, this is what we hope for

Actual complexity may depend on graph implementation choices
Depends on “handle each node” being O(1)
Depends on “remove an edge” being O(1)
Depends on “find vertex with in-degree 0” being O(1)

If we have to scan some sort of list of all vertices looking for next vertex in topo order, then this will end up being O(|V|) and overall algorithm will end up being O(|V|²+|E|)

30

31 of 47

Efficient Topo Sort Implementation

Compute initial in-degree of each vertex when graph is built.

This is O(|V|) and we have to do it anyway just to build the graph.

Scan through all vertices at the beginning, identify all in-degree 0 vertices, and add them to a queue.

O(|V|) again.

While the 0-in-degree queue is not empty…

Take a vertex off the queue and add it to the topo list
Examine each edge and “remove” it by decreasing the in-degree associated with the edges destination.

If in-degree of a destination vertex falls to 0, add it to the 0-in-degree queue

When 0-in-degree queue is empty, if topo list does not contain |V| vertices, then must have found a cycle, no topo sort possible.

Otherwise, topo list is valid.

Now algorithm is O(|V| + |E|)

If successful, each vertex handled once and is added to 0-in-degree queue when last incoming edge is removed as the source of that edge was processed.

31

32 of 47

Graph from LS18

32

33 of 47

Shortest Path Algorithms

33

34 of 47

Shortest Path

Many problems require us to find the shortest path from vertex v to vertex w in a graph.
We will look at 2 situations:

digraph, unweighted edges (weight 1 on all) → this really means path length
digraph, weighted edges → this really means cheapest path

34

35 of 47

Unweighted Shortest Path

Input: An unweighted digraph G=( V, E ) and a start vertex s, where s∈V
Output: shortest paths from s to every other vertex ( there will be |𝑽 |−𝟏 paths )
Unweighted algorithm is fairly simple

Adding weights to edges complicates things
Weights is Dijkstra’s algorithm

One simple and obvious algorithm has worst case time complexity

of O( |𝑽 |² )

35

36 of 47

(Bad) Unweighted Shortest Path

First, we recognize that no “shortest path” can be longer than |V|-1

So run a loop with len going from 0 to |V|-1
One loop iteration for each possible path length

|V|-1 iterations

Inside this loop, go through all nodes and when we find one with distance “len” we mark all unmarked adjacent nodes with distant “len+1”.

Double nested loops: O(|V|-1) * O(|V|) is O( |𝑽|^𝟐)

36

37 of 47

(Bad) Unweighted Shortest Path

37

38 of 47

An Improvement

Recognize that once we deal with a node with some length (like 1) we will not work on that node again
So the outer loop revisits C, A, F (lengths 0, 1) just to get to B, D (length 2).
We can visit only the “rest of the nodes” by doing a breadth-first search

38

39 of 47

Unweighted Shortest Path (1/3)

39

40 of 47

Unweighted Shortest Path (2/3)

40

41 of 47

Unweighted Shortest Path

This algorithm visits each node once
At each node, visit each adjacent out-edge

So this is O(|V|+|E|)

Key is to efficiently find “next node”
Use a queue like in topological sort and breadth-first search in tree.
Visiting a node, enq the adjacent nodes
deq to get “next” node

41

42 of 47

Unweighted Shortest Path

This algorithm visits each node once
At each node, visit each adjacent out-edge

So this is O(|V|+|E|)

Key is to efficiently find “next node”
Use a queue like in topological sort and breadth-first search in tree.
Visiting a node, enq the adjacent nodes
deq to get “next” node

42

43 of 47

Convince ourselves queue gives Breadth First Search

43

44 of 47

Djikstra’s Algorithm

44

45 of 47

Djikstra’s Algorithm

45

46 of 47

Djikstra’s Algorithm

Put start s node in table with dist of 0
Put (0,s) on priority queue PQ
Loop: until PQ is empty:

n=PQ.getMin().node; d=PQ.getMin().dist; PQ.delMin()
Is n known? Back to Loop and get another from PQ;
Mark n as known
For each unknown node a adjacent to n

if a.dist>d+edge.weight then
update a.dist in table to be d+edge.weight and add a to PQ with priority d+edge.weight

Trace the path itself using “from” fields

46

47 of 47

Misc. Notes

Although explanation / examples today were in context of directed graph, works with undirected graph as well

Just need the notion of “adjacency”

In the last assignment, starter code provides vertex interface and implementation that supports keeping track of distance from source and prior vertex on path but you may need to add capability for keeping track of whether vertex is “known” (i.e., processed from priority queue)

47