Graph Algorithms the Fun Way by Jeremy Kubica

Author:Jeremy Kubica
Language: eng
Format: epub, pdf, mobi, azw
Publisher: No Starch Press

The bridge-finding algorithm checks each subtree in the depth-first search tree by recording the lowest-order indices that neighbor any node in the subtree. The only adjacent edge we exclude is the link between the subtree root u and its parent, as this is the edge we are testing.

The Code

We can implement the bridge-finding algorithm using a single pass of depth-first search. To simplify the code, we’ll use the helper data structure DFSTreeStats to track information about the order in which the depth-first search reaches various nodes, including:

parent (list) Maps each node’s index to that of its parent in the depth-first search tree

next_order_index (int) Stores the next order index to assign

order (list) Maps each node’s index to its order index

lowest (list) Maps each node to the lowest order index of any nodes in its depth-first search subtree or their immediate neighbors (excluding the node’s parent)

The data structure DFSTreeStats provides a wrapper for this information and saves us from having to pass many parameters to the search function. We can also use the object to perform basic assignments and updates. We define DFSTreeStats in the following code:

class DFSTreeStats: def __init__(self, num_nodes: int): ❶ self.parent: list = [-1] * num_nodes self.next_order_index: int = 0 self.order: list = [-1] * num_nodes self.lowest: list = [-1] * num_nodes def set_order_index(self, node_index: int): self.order[node_index] = self.next_order_index self.next_order_index += 1 ❷ self.lowest[node_index] = self.order[node_index]

The constructor sets all the information to its initial values ❶. The code initializes all entries of the lists parent, order, and lowest to -1 in order to indicate that these values are unset for each node. It sets next_order_index to 0 in preparation for the first node.

The helper method set_order_index() records the current node’s order index and increments the next one to assign. It also initializes the lowest order index seen for this node, which is initially the order index of the node itself ❷.

We use a depth-first search adapted from those in Chapter 4 to fill in the entries of DFSTreeStats and find the bridges:

def bridge_finding_dfs(g: Graph, index: int, stats: DFSTreeStats, results: list): ❶ stats.set_order_index(index) for edge in g.nodes[index].get_sorted_edge_list(): neighbor: int = edge.to_node ❷ if stats.order[neighbor] == -1: stats.parent[neighbor] = index bridge_finding_dfs(g, neighbor, stats, results) ❸ stats.lowest[index] = min(stats.lowest[index], stats.lowest[neighbor]) ❹ if stats.lowest[neighbor] >= stats.order[neighbor]: results.append(edge) elif neighbor != stats.parent[index]: ❺ stats.lowest[index] = min(stats.lowest[index], stats.order[neighbor]) def find_bridges(g: Graph) -> list: results: list = [] stats: DFSTreeStats = DFSTreeStats(g.num_nodes) for index in range(g.num_nodes): if stats.order[index] == -1: bridge_finding_dfs(g, index, stats, results) return results

The recursive helper function bridge_finding_dfs() starts by setting the current node’s order index and initial value for the lowest order index reachable in the subtree using the set_order_index() helper method ❶.

The code then uses a for loop to check each of the node’s neighbors. For consistency of ordering with other examples, we use the function get_sorted_edge_list() to traverse the neighbors in order of their index, though traversing them in sorted order is not necessary for the correctness of the algorithm. If a neighbor has not been visited (its order value is unset) ❷, the code sets its parent and recursively explores it.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.