I'm trying to write an algorithm that finds the (optional) tree root from a graph structure (SwiftGraph), that could represent any graph (not necessarily a tree). If a root is found the algorithm should return its index in the vertices list, otherwise it should return null.
This is my attempt:
Union-find by rank with path compression:
fileprivate class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(elements: [Int]) {
self.parent = [Int].init(repeating: 0, count: elements.count)
self.rank = [Int].init(repeating: 0, count: elements.count)
self.makeSet(elements)
}
private final func makeSet(_ vertices: [Int]) {
for i in 0..<vertices.count {
parent[i] = i
rank[i] = 0
}
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x]) // Path compression
}
return parent[x]
}
func union(_ x: Int, _ y: Int) {
let xRoot = find(x)
let yRoot = find(y)
if xRoot == yRoot {
return
}
if rank[xRoot] < rank[yRoot] {
parent[xRoot] = yRoot
} else if rank[xRoot] > rank[yRoot] {
parent[yRoot] = xRoot
} else {
parent[yRoot] = xRoot
rank[xRoot] += 1
}
}
}
SwiftGraph extension:
extension Graph {
/// If this graph is a valid tree, this algorihtm finds and returns the index of the root vertex in `self.vertices`.
///
/// May require further testing.
///
/// - Returns: The index of the root of the tree, if this `self` is a tree, `nil` otherwise. If the graph is a degenerate tree,
/// i.e. an empty tree, this function returns nil.
///
/// - Complexity: **Time:** O(V + E⋅α(V)) where α(V) is the inverse Ackermann function, that grows extremely slowly (it is considered
/// constant for any common practical application). **Memory:** O(V) to create the sets for Union-Find by rank with path compression.
public func findTreeRoot() -> Int? {
let unionFind = UnionFind(elements: [Int](self.vertices.indices))
for vertex in 0..<self.vertices.count {
for neighbor in self.edges[vertex] {
let rootVertex = unionFind.find(vertex)
let rootNeighbor = unionFind.find(neighbor.v)
if rootVertex == rootNeighbor {
return nil
}
unionFind.union(rootVertex, rootNeighbor)
}
}
var roots = Set<Int>()
for vertex in 0..<self.vertices.count {
roots.insert(unionFind.find(vertex))
}
if roots.count == 1 {
return roots.first
} else {
return nil
}
}
}
Unfortunately though there are situations where graph.findTreeRoot() returns the wrong vertex index, that is, it returns the index of a vertex that's not the root of the tree.
What am I doing wrong here?
EDIT
An example of tests that fails:
let originalGraph = WeightedGraph<String, Float>()
for component in ["topbar", "secondary topbar", "gallery", "toolbar", "captions"] {
let _ = originalGraph.addVertex(component)
}
originalGraph.addEdge(fromIndex: 0, toIndex: 1, weight: 1.2, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 2, weight: 0.5, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 3, weight: 1.1, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 4, weight: 1.3, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 0, weight: 1.1, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 2, weight: 0.5, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 3, weight: 1.5, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 4, weight: 2.2, directed: true)
originalGraph.addEdge(fromIndex: 3, toIndex: 2, weight: 1.0, directed: true)
originalGraph.addEdge(fromIndex: 3, toIndex: 4, weight: 1.0, directed: true)
assert(originalGraph.findTreeRoot() == nil)
let msaOfTopbar = try originalGraph.msa(root: 1)
let msaAsGraph = WeightedGraph<String, Float>(vertices: originalGraph.vertices)
for edge in msaOfTopbar {
msaAsGraph.addEdge(edge, directed: true)
}
assert(msaAsGraph.findTreeRoot() == 1) // assertion failed: 0 != 1
I'm trying to write an algorithm that finds the (optional) tree root from a graph structure (SwiftGraph), that could represent any graph (not necessarily a tree). If a root is found the algorithm should return its index in the vertices list, otherwise it should return null.
This is my attempt:
Union-find by rank with path compression:
fileprivate class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(elements: [Int]) {
self.parent = [Int].init(repeating: 0, count: elements.count)
self.rank = [Int].init(repeating: 0, count: elements.count)
self.makeSet(elements)
}
private final func makeSet(_ vertices: [Int]) {
for i in 0..<vertices.count {
parent[i] = i
rank[i] = 0
}
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x]) // Path compression
}
return parent[x]
}
func union(_ x: Int, _ y: Int) {
let xRoot = find(x)
let yRoot = find(y)
if xRoot == yRoot {
return
}
if rank[xRoot] < rank[yRoot] {
parent[xRoot] = yRoot
} else if rank[xRoot] > rank[yRoot] {
parent[yRoot] = xRoot
} else {
parent[yRoot] = xRoot
rank[xRoot] += 1
}
}
}
SwiftGraph extension:
extension Graph {
/// If this graph is a valid tree, this algorihtm finds and returns the index of the root vertex in `self.vertices`.
///
/// May require further testing.
///
/// - Returns: The index of the root of the tree, if this `self` is a tree, `nil` otherwise. If the graph is a degenerate tree,
/// i.e. an empty tree, this function returns nil.
///
/// - Complexity: **Time:** O(V + E⋅α(V)) where α(V) is the inverse Ackermann function, that grows extremely slowly (it is considered
/// constant for any common practical application). **Memory:** O(V) to create the sets for Union-Find by rank with path compression.
public func findTreeRoot() -> Int? {
let unionFind = UnionFind(elements: [Int](self.vertices.indices))
for vertex in 0..<self.vertices.count {
for neighbor in self.edges[vertex] {
let rootVertex = unionFind.find(vertex)
let rootNeighbor = unionFind.find(neighbor.v)
if rootVertex == rootNeighbor {
return nil
}
unionFind.union(rootVertex, rootNeighbor)
}
}
var roots = Set<Int>()
for vertex in 0..<self.vertices.count {
roots.insert(unionFind.find(vertex))
}
if roots.count == 1 {
return roots.first
} else {
return nil
}
}
}
Unfortunately though there are situations where graph.findTreeRoot() returns the wrong vertex index, that is, it returns the index of a vertex that's not the root of the tree.
What am I doing wrong here?
EDIT
An example of tests that fails:
let originalGraph = WeightedGraph<String, Float>()
for component in ["topbar", "secondary topbar", "gallery", "toolbar", "captions"] {
let _ = originalGraph.addVertex(component)
}
originalGraph.addEdge(fromIndex: 0, toIndex: 1, weight: 1.2, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 2, weight: 0.5, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 3, weight: 1.1, directed: true)
originalGraph.addEdge(fromIndex: 0, toIndex: 4, weight: 1.3, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 0, weight: 1.1, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 2, weight: 0.5, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 3, weight: 1.5, directed: true)
originalGraph.addEdge(fromIndex: 1, toIndex: 4, weight: 2.2, directed: true)
originalGraph.addEdge(fromIndex: 3, toIndex: 2, weight: 1.0, directed: true)
originalGraph.addEdge(fromIndex: 3, toIndex: 4, weight: 1.0, directed: true)
assert(originalGraph.findTreeRoot() == nil)
let msaOfTopbar = try originalGraph.msa(root: 1)
let msaAsGraph = WeightedGraph<String, Float>(vertices: originalGraph.vertices)
for edge in msaOfTopbar {
msaAsGraph.addEdge(edge, directed: true)
}
assert(msaAsGraph.findTreeRoot() == 1) // assertion failed: 0 != 1
2 Answers
Reset to default 0I think @m.raynal has answered the question, but perhaps this will help you along in implementing it.
// Pseudo-swift (I don't know swift)
let numEdgesStartingHere = //( integer array with self.vertices.count elements; initialize all to 0 )
let numEdgesEndingHere = //( integer array with self.vertices.count elements; initialize all to 0 )
for vertex in 0..<self.vertices.count {
for neighbor in self.edges[vertex] {
let edgeStart = vertex
let edgeEnd = neighbor
numEdgesStartingHere[edgeStart]++
numEdgesEndingHere[edgeEnd]++
Union-Find is designed for undirected graphs to manage disjoint sets and detect cycles. It doesn't account for edge direction, which is crucial in directed graphs. Therefore, using Union-Find to find roots in a directed graph isn't appropriate. Instead, consider computing the in-degree of each node; nodes with an in-degree of zero are potential roots.
O(E)" I guess that's a consequence of this decision to store all nodes' edges in a single array that needs to be filtered down repeatedly. That seems like an odd way to represent it; does it has some benefits I might not know about? – Alexander Commented Dec 18, 2024 at 18:53