Week 13

VL 24 - 08.07.25

Connected Components

Searching and Identifying Connected Components

1. Idea: each component has a label (a running number) and an anchor (representative of the equivalence class)
2. Scan the nodes in increasing order, until a new anchor is found. This is a node whose connected component is not known
3. DFS or BFS starting from an anchor, in order to find the other nodes in the equivalence class.

• Homework: Segmentation of a microscope image with connected components
• how to represent additional properties of nodes and edges?
  • visited[node]: was the node visited?
  • anchor[node], label[node]: anchor and the label of the connected component to which the node belongs
  • brightness[node]: the brightness of a pixel
  • `distance[(node1, node2)]: shortest paths frmo node1 to node2
• above are called ‘property maps’ via containers like arrays, dictionaries. It is a lightweight approach. A separate property map for each property.

First we will look at the recursive version

def connected_component(graph) : # graph given as an adjecency list
    labels = [None] * len(graph)
    anchors = [None] * len(graph)
    def visit(node, anchor):
        if anchors[node] is not None: return # already visited / known component
        labels[node] = labels[anchor]
        anchors[node] = anchor
        for neighbor in graph[node] :
            visit(neighbor, anchor)
    current_label = 0
    for node in range(len(graph)) :
        if labels[node] is not None: continue
        labels[node] = current_label
        visit(node, node) # a compnent is now complete
        current_label += 1
    return labels, anchors

Problem “Maximum Recursion Depth Exceeded” \(\Rightarrow\) a variant with iteration and a stack DS:

def connected_components(graph):
    labels = [None] * len(graph)
    anchors = [None] * len(graph)
    current_label = 0
    for node in range(len(graph)) :
        if labels[node] is not None : continue
        stack = deque() # from collections
        stack.append(node)
        while len(stack) != 0 :
            new_node = stack.popright() # pop() in newer python
            if labels[new_node] is not None: continue
            labels[new_node] = current_label
            anchors[new_node] = node
            for neighbor in graph[new_node] : 
                if labels[neighbor] is not None: continue
                stack.append(neighbor)
        # end while: stack is now empty, DFS for the component is complete.
        current_label += 1 # proceed to the next label
    # end for: all components are complete
    return labels, anchors

Next problem we will take on is shortest path

Shortest Path

• 3 types of SP problems:
  1. unweighted graph (ungewichtet): all edges are equally expensive: shortest path = the least number of edges \(\Rightarrow\) BFS
  2. weighted graph, all weights are positive (\(w_{uv}> 0\)), Path length = Sum of the weights \(\Rightarrow\) Dijsktra Algorithm, or A* algorithm
  3. weighted graph with arbitrary weights (positive and negative) \(\Rightarrow\) length = sum of weights. Danger of an infinite loop when the sum of weights of a cycle is negative. solution: Bellman-Ford Algorithm (this algorithm terminates when a negative cycle is detected)

Example: negative cycle in Arbtrage-companies:

arbitrage

what happens:

• we have x$,
  • exhnage to Eu => y yen = \(w_{\$eu}\) x$.
  • exchange to Yen => z yen = w_{eu, yen}w_{$,eu} x $
  • exhnage to $ => w_{yen, \(} w_{eu, yen} w_{\), eu} x $
• there is profit when w1w2w3 > 1
• shortest paht: -log(x’) < -log(x) <=> -log(w1 * w2 * w3) < negative cycle

Now we need ne property maps for shortest paths. Each node knows it’s predecessor in the path \(\Rightarrow\) parents[node]

def shortest_path(graph, start, target): # graph is undirected
    parents = [None] * len(graph)
    parents[start] = start
    queue = deque()
    queue.append(start)
    while len(queue) != 0 :
        node = queue.popleft()
        if node == target : break # success 
        for neighbor in graph[node] : 
            if parents[neighbor] is None :
                parents[neighbor] = node
                queue.append(neighbor)
    if parents[target] is None : 
        return None # start & target are in the same connected component
    path = [target]
    while path[-1] != start : # not yet finished
        path.append(parents[path[-1]])
    path.reverse() # target not 
    return path

Why doesn’t shortest path work with DFS?

VL 25 - 10.07.25

BFS (cont)

Why does BFS find the shortest path?

• undirected & unweighted graph

bfs propagation

Obersvations:

• BFS expands / propagates in phases around the start node.
• BFS doesn’t only find the shortest path from start to target, but all shortest paths with length \(l < \text{length}(\text{start}\rightsquigarrow\text{target})\) (shortest paths to all nodes that are closer to start than the target)

Shortest Paths in Weighted Graphs (Dijkstra & A* - Alg)

• Edge weights represent the lenghts of edges \(w_{uv} > 0\)
• Property maps: weights[(u,v)] with node pairs as keys

Alternatively adjacency matrix. Entries are weights of the edges:

\[ \begin{bmatrix} 0 & 4 & 7 \\ 4 & 0 & 2 \\ 7 & 2 & 0 \\ \end{bmatrix} \]

But we will use adjacency lists and property maps .

Idea: Replace the queue in BFS by a MinHeap (priority queue), where the priority of a node = length(start -> node). (in the lecture we had max heaps, but now we need a min heap - in python this is already the case in the module haepq ).

algorithm:

def dijkstra(graph, weights, start, target) :
    parents = [None] * len(graph) #
    heap = []
    heapq.heappush(heap, (0.0, start, start)) # 0.0 = priority, start = current, start = parent
    while len(heap) != 0 :
        length, node, parent = heapq.heappop(heap)
        if parents[node] is not None : continue 
        parents[node] = parent
        if node == target: break # success 
        for neighbor in graph[node] : 
            if parents[neighbor] is not None: continue
            new.length = length + weights[(node, neighbor)]
            heapq.heappush(heap, (new_length, neighbor, node))
    # end while
    if parents[target] is None : return None, None
    path = [target]
    while path[-1] != start : path.append(parents[path[-1]])
    path.reverse()
    return path, length

Complexity of Dijkstra Shorteste Path

while len(heap) != 0:

• In the heap we add edges, and we do not re-add edges multiple times. Therefore the number of iterations is \(\mathcal{O}(|E|)\)

heappop(): \(\log{len(heap)} \Rightarrow \mathcal{O}(|E|)\):

• in usual graphs (no multiedges): \(|E| \in \mathcal{O}(|V|^2) = \mathcal{O}(\log({|V|})\)

for neighbor: \(\mathcal{O}(degree(node)) \in \mathcal{O}(|V|)\)

\(\Rightarrow\) overall complexity: \(\mathcal{O}(|E|\log{|V|})\)

Correctness of Dijkstra Shortest Path

• Lemma: in the (i + 1)-st iteration of the while-Loop: \(length_{i + 1} \geq length_{i}\)

• Proof (indirect, proof by contradiction): asssume \(l_{i + 1} < l_i\) for some \(i\). This means that \(l_i\) was at the Top in the heap at the iteration \(i\), \(l_{i + 1}\) was at the top at the iteration \(i+1\)

  • case 1: the path with the length \(l_{i+1}\) was already known during the iteration \(\Rightarrow\) \(l_i\) could not have been top \(\Rightarrow \quad \bot\)
  • case 2: path of length \(l_{i + 1}\) was discovered during the itration \(i\). Then we have \(l_{i + 1} = l_i + W_{parent_i, node_i} > l_i\) \(\Rightarrow \quad \bot\) \(\Rightarrow l_{i + 1} < l_{i}\) is impossible.

• Theorem: Dijstras response: \(node \rightarrow parent \rightsquigarrow start\) is the shortest path from \(node \rightsquigarrow start\), length \(l_D\).

  True shortest path: \(node \rightarrow x \rightsquigarrow start\) with length \(l_N < l_D\) shows that is impssible via a contradiction. we know who \((l_{D}, node, parent)\) at the top of the heap is

  • case 1: \(x \rightsquigarrow start\) is already in heap, if \(w_{node, x} + len(x \rightsquigarrow start) = l_w < l_D\), would have been already found in an earlier iteration \(\Rightarrow \quad \bot\)
  • case 2: $x