12: graphs #1

Graph Basics | Graph Representation | Graph Traversals | Single-Source Shortest Paths | All-to-All Shortest Paths

Graph Basics

In trees, there is only one root and links can only go from parent to child. Graphs do not have any roots and links can exist between any two nodes.
  • Undirected Graph:
    GraphIntro
  • Directed Graph:
    GraphIntro
In graphs we call nodes "Vertices" and we call the connections "Edges".

Edges can have weights associated with them. For instance, if we made a graph with the Vertices be all the capitol cities in the US and the Edges being the major highways between them, the Edge Weights could be the distance of the connecting highways, in miles.

In graphs, the existing nodes and the connections between them are what matter, the xy-positions on a drawing of the graph are irrelevant.

Definitions:
  • Path: sequence of edges from v1 to vn
  • Circuit: a path where v1 = vn and no edge is repeated
  • Cycle: a circuit where all the vertices are different
  • Complete Graph: a graph where each distinct pair of vertices has exactly one edge connecting them. The number of edges in a complete graph is: |E| = |V|*(|V|-1) / 2 = O(|V|^2)
  • Subgraph: G' of graph G = (V, E) is a graph (V', E') where V' is a subset of V and E' is a subset of E.
  • Adjacent Vertices: Two vertices connected by and edge
  • Degree of a Vertex V: The number of edges touching V.
  • Isolated Vertex: A vertex with degree=0

Graph Representation

Most useful Graph Representations:
  • Adjacency List:

    a
    b
    c
    d
    e
    f
    g
    c    d    f
    d    e
    a    f
    a    b    e    f
    b    d
    a    c    d


    Processing all the edges in a vertex takes degree(v) steps.

  • Adjacency Matrix:
  • a    b    c    d    e    f    g
    a
    b
    c
    d
    e
    f
    g
    0    0    1    1    0    1    0
    0    0    0    1    1    0    0
    1    0    0    0    0    1    0
    1    1    0    0    1    1    0
    0    1    0    1    0    0    0
    1    0    1    1    0    0    0
    0    0    0    0    0    0    0

    Processing all the edges in a vertex takes |V| steps. There is also a lot of wasted space in sparse graphs.

Graph Traversals

In graphs, popular traversals are: 1) Depth-First Search and 2) Breadth-First Search

Depth-First Search

1:  
algorithm
 
depthFirstSearch(
)

2:  
 
 
for
 
all 
vertices 
u

3:  
 
 
 
 
visited(
u)
 
false;

4:  
 
 
while
 
there 
is 
vertex 
such 
that 
visited(
v)
 
== 
false

5:  
 
 
 
 
searchNode(
v)
;

6:  

7:  
algorithm
 
searchNode(
Node 
v)

8:  
 
 
visit 
node

9:  
 
 
for
 
all 
adjacent 
vertices 
u

10: 
 
 
 
 
searchNode(
u)

Breadth-First Search

1:  
algorithm
 
breadthFirstSearch(
)

2:  
 
 
for
 
all 
vertices 
u

3:  
 
 
 
 
visited(
u)
 
false;

4:  
 
 
edges 
null

5:  
 
 
while
 
there 
is 
vertex 
such 
that 
visited(
v)
 
== 
false

6:  
 
 
 
 
enqueue(
v)
;

7:  
 
 
 
 
while
 
queue 
is 
not 
empty

8:  
 
 
 
 
 
 
dequeue(
)
;

9:  
 
 
 
 
 
 
for
 
all 
vertices 
adjacent 
to 
v

10: 
 
 
 
 
 
 
 
 
if
 
visited(
u)
 
is 
false

11: 
 
 
 
 
 
 
 
 
 
 
visited(
u)
 
true;

12: 
 
 
 
 
 
 
 
 
 
 
enqueue(
u)
;

13: 
 
 
 
 
 
 
 
 
 
 
attach 
edge(
vu)
 
to 
edges;

14: 
 
 
output 
edges;

Single-Source Shortest Paths

A classical problem in graph theory is to find the shortest paths from one starting vertex to every other vertex in the graph. The solution to this problem is useful in internet routers.

There are two main categories of solutions
  • label-setting methods: in each pass through the vertices still to be processed, one vertex is set and never changes.
  • label-correcting methods: any label may be changed during a pass
Label-setting methods only work with positive weights, while label-correcting works also with negative weights as long as there are no negative cycles (a cycle whose weights add up to a negative number).

Dijkstra's Algorithm

Dijkstra's Algorithm is one of the first label-setting methods.
1:  
algorithm
 
dijkstra(
weighted 
simple 
digraph, 
vertex 
first)

2:  
 
 
for
 
all 
vertices 
v

3:  
 
 
 
 
currDist(
v)
 
infinity;

4:  
 
 
currDist(
first)
 
0;

5:  
 
 
toBeChecked 
all 
vertices;

6:  
 
 
while
 
toBeChecked 
is 
not 
empty

7:  
 
 
 
 
vertex 
in 
toBeChecked 
with 
minimal 
currDist(
v)
;

8:  
 
 
 
 
remove 
from 
toBeChecked;

9:  
 
 
 
 
for
 
all 
vertices 
adjacent 
to 
and 
in 
toBeChecked

10: 
 
 
 
 
 
 
if
 
currDist(
u)
 
>
 
currDist(
v)
 
weight(
edge(
vu)
)

11: 
 
 
 
 
 
 
 
 
currDist(
u)
 
currDist(
v)
 
weight(
edge(
vu)
)
;

12: 
 
 
 
 
 
 
 
 
predecessor(
u)
 
v;
 
 
 
 
 
 
 
 
 
 

Example:
Dijkstra
iteration: init 1 2 3 4 5 6 7 8 9 10
active vertex: d h a e f b i c j g
a inf 4
b inf inf inf inf inf 9
c inf inf inf inf inf 11 11
d 0
e inf inf 6 5
f inf inf inf inf 8
g inf inf inf inf inf 15 15 15 15 12
h inf 1
i inf inf 10 10 10 9
j inf inf inf inf inf inf inf 11

Order:
d h a e f b i c j g

Dijkstra's Algorithm Time Complexity

  • Using a simple data structure for currDist that requires O(|V|) to find the min:
    • The while at line 6 is executed O(|V|) times. Then for each of these executions, the search for min requires O(|V|) time.
    • The for loop at line 9 is executed O(|E|) times.
    • Total time: O(|V|^2+|E|)
  • Using a min-heap for currDist:
    • The outer while executes O(|V|) times and for each of those, removing from the min-heap takes O(lg|V|) time. This step takes O(|V|*lg|V|) time.
    • Updating currDist when a min distance is found, updating the key in the min-heap takes O(lg|V|) time. This is executed for every edge in the graph so this step takes O(|E|*lg|V|) time
    • Total time: O((|V|+|E|)*lg|V|)
  • The total number of edges in a complete graph: |E| = O(|V|^2)
  • In a complete graph, using a min-heap takes O((|V|+|V|^2)*lg|V|), but with a sparse graph, using a min-heap is faster. In sparse graphs, dijkstra's algorithm with a min-heap is the fastest known single-source shortest-path algorithm for graphs with nonnegative weights. [1]

Bellman-Ford Algorithm

The Bellman-Ford's Algorithm is a label-correcting algorithm (so it can process graphs with negative weights).
1: 
algorithm
 
bellmanFord(
weighted 
simple 
digraph, 
vertex 
first)

2: 
 
 
for
 
all 
vertices 
v

3: 
 
 
 
 
currDist(
v)
 
infinity;

4: 
 
 
currDist(
first)
 
0;

5: 
 
 
while
 
there 
is 
an 
edge(
vu)
 
such 
that 
currDist(
u)
 
>
 
currDist(
v)
 
weight(
edge(
vu)
)

6: 
 
 
 
 
currDist(
u)
 
currDist(
v)
 
weight(
edge(
vu)
)
;

Example:
FordAlgorithm
iteration
init 1 2 3 4
a inf 3 2 1
b inf 4 3 2
c 0
d inf 1 0 -1
e inf 5 4 3
f inf 9 3 8 2 1
g inf 1 0
h inf 1
i inf 2 1 0

To impose an order on the edges, alphabetical order can be used.

The order of the edges used here: ab cd cg ch da de di ef gd hg if

Each iteration, all edges are visited. If a distance is infinity in a source edge, it is skipped (anything plus infinity is still infinity and nothing can be greater than infinity).

In the Bellman-Ford algorithm, the first pass finds all the one edge shortest paths, the second: two edge shortest paths, etc.

The time complexity is: O(|V|*|E|). There will be at most |V|-1 passes through the sequence of |E| edges, because |V|-1 is the largest number of edges in any path.

All-to-All Shortest Path Problem

The Warshall-Floyd-Ingerman algorithm is a simple way to compute the all-to-all shortest paths.
  • An adjacency matrix (rather than adjacency list) is required
1: 
algorithm
 
warshalFloydIngerman(
adjacency 
matrix 
weight)

2: 
 
 
for
 
to 
|V|

3: 
 
 
 
 
for
 
to 
|V|

4: 
 
 
 
 
 
 
for
 
to 
|V|

5: 
 
 
 
 
 
 
 
 
if
 
weight[
j]
[
k]
 
weight[
j]
[
i]
 
weight[
i]
[
k]

6: 
 
 
 
 
 
 
 
 
 
 
weight[
j]
[
k]
 
weight[
j]
[
i]
 
weight[
i]
[
k]
;

  • The outermost loop refers to vertices that may be on a path between the vertex with index j and index k
WfiAlgorithmGraph

  1. Start:
    a b c d e
    a 0 2 inf -4 inf
    b inf 0 -2 1 3
    c inf inf 0 inf 1
    d inf inf inf 0 4
    e inf inf inf inf 0


  2. i == 1, all paths: v_j ... v_1 ... v_k are considered. a has no incoming edges, so the table remains the same.
    a b c d e
    a 0 2 inf -4 inf
    b inf 0 -2 1 3
    c inf inf 0 inf 1
    d inf inf inf 0 4
    e inf inf inf inf 0


  3. i == 2, all paths: v_j ... v_2 ... v_k are considered. (abc, abe, abd)
    a b c d e
    a 0 2 0 -4 5
    b inf 0 -2 1 3
    c inf inf 0 inf 1
    d inf inf inf 0 4
    e inf inf inf inf 0


  4. i == 3, all paths: v_j ... v_3 ... v_k are considered. (bce)
    a b c d e
    a 0 2 0 -4 5
    b inf 0 -2 1 1
    c inf inf 0 inf 1
    d inf inf inf 0 4
    e inf inf inf inf 0


  5. i == 4, all paths: v_j ... v_4 ... v_k are considered. (ade, bde). (no changes)
    a b c d e
    a 0 2 0 -4 5
    b inf 0 -2 1 1
    c inf inf 0 inf 1
    d inf inf inf 0 4
    e inf inf inf inf 0


  6. i == 5, all paths: v_j ... v_5 ... v_k are considered. (no paths)
The time complexity of the WFI-Algorithm is O(|V|^3). This is good for dense graphs, but for sparse graphs we can repeatedly use a single-source method on all the vertices to get something like O((|V|^2+|E||V|)*lg|V|) (this uses dijkstra's algorithm with a heap).

The WFI-Algorithm can be used to detect cycles in a graph if the diagonal is initialized to infinity. If any of the diagonal values are changed, the graph contains a cycle.

References

  1. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  2. http://en.wikipedia.org/wiki/Complete_graph