Directed Graphs & Algorithms

A directed graph (or digraph) is a set of vertices and a set of directed edges where each edge has a source and target vertex.
In a diagram of a directed graph, if there is an arrow from $a$ to $b$:

• $a$ is a prdecessor of $b$
• $b$ is a successor of $a$

Underlying Graph

The underlying graph of a digraph is the graph obtained by replacing arrows with (undirected) edges
A digraph is connected if its underlying graph is connected

Dijkstra’s Algorithm

Dijkstra’s algorithm computes the shortest path between two nodes:

1. Create two lists, visited and unvisited nodes
2. Give each node a “distance” value, it should be infinity at first, with the start node having a distance value of 0
3. From the list of unvisited nodes, the one with the smallest distance should be selected
   • Terminate if this is the starting node
4. For the current node, find all the unvisited nodes connected to this node
5. Update their summative weights from the start if the new weight via this path to them is smaller
6. Remove the current node from the list of unvisited nodes, and move it to the list of visited nodes

Prim’s Algorithm

Prim’s algorithm finds the minimum spanning tree for a weighted undirected graph

1. Initialise a tree with a single vertex from a graph
2. Find the cheapest edge that connectes a vertex in the tree with a vertex not in the tree
3. Add that edge and the corresponding vertex to the tree
4. Repeat until all vertices are in the tree

Longest Path Problem

Longest path between two vertices in a grpah can be a very challenging problem.

Directed Acyclic Graphs

Directed Acyclic Graphs (DAGs) are digraphs with no cycles.
The vertices of a DAG can be split into ordered layers.

A source is a vertex with no predecessors.
A sink is a vertex with no successors.

Topological Ordering

The vertices of a DAG can be ordered such that for any edge from $u$ to $v$, the vertex $u$ preceeds $v$ in the ordering.

Topological orderings can be easily found as such:

• Create an empty list, $L$
• For every source node in the graph:
  • Remove it from the graph
  • Add it to the end of the list $L$
  • Repeat until no more source nodes remain

Longest Path in DAGS

• Compute a topological ordering of the vertices
• Go over vertices in this order starting with our start vertex
• For every vertex $v$, compute the maximum length of a path from $s$ to $v$ as:
• $LP(v) = max_{(u,v) \in E(G)} LP(u)+w((u,v))$
• aka: Go over all edges with target $v$ and compute the length of the longest path using that edge

Connectivity in Digraphs

A digraph $G = (V, E)$ is weakly connected if the underlying undirected graph of $G$ is connected

A digraph $G = (V, E)$ is strongly connected if there is a walk between every pair of vertices

Connected Components

A strong component/weak component is a maximal strongly connected/weakly connected subgraph
Adding any set of vertices will make it not connected

Strong Components

In other words, vertices in the same strong component as one another define an equivalence relation.
The relation is equivalent to the symmetric relation $R \subseteq V(G) \times V(G)$ such that $(a, b) \in R$ if and only if:

• There is a walk from $a$ to $b$ and
• There is a walk from $b$ to $a$

Condensation Graph

Given a digraph $G = (V, E)$ - a condensation graph of $G$ is a graph $H$ such that:

• Vertices of $H$ are the strong components of $G$
• There is an edge from strong component $A$ to strong component $B$ in $H$ if and only if there is an edge $(a, b)$ in $G$ for some $a \in A$ and $b \in B$

In effect, every strong component in $G$ becomes a vertex in $H$, and the edges between strong components are similarly reflected in $H$

• A cycle in a condensation graph contradicts the maximality of strong components on the cycle

Finding Strong Components

• There are many ways to do this
• The simplest algorithm takes advantage of the equivalence class definition
• Such that any two vertices that can reach each other must be part of the same strong component