Fixed MSA when the root can reach a subset of all vertices

davecom · NickTheFreak97 · Jun 15, 2024 · Jun 24, 2024 · Jun 24, 2024 · Jun 24, 2024
commit 615085465d81f7a7ff176f13029b19f873773409
diff --git a/Sources/SwiftGraph/Arbok/Gabow/Gabow.swift b/Sources/SwiftGraph/Arbok/Gabow/Gabow.swift
@@ -257,7 +257,7 @@ internal final class Gabow<T> where T: AdditiveArithmetic & Comparable & Numeric
     }
 
 
-    internal func reconstruct(root: Int) -> [Int] {
+    internal func reconstruct(root: Int) -> [Gabow.Edge] {
         let n = self.chosen.count
 
         // build leafs arary (first chosen edge for each node)
@@ -282,7 +282,7 @@ internal final class Gabow<T> where T: AdditiveArithmetic & Comparable & Numeric
         ); // assert each node has an incoming edge
         #endif
 
-        var res: [Int] = .init()
+        var res: [Gabow.Edge] = .init()
         var del: [Bool] = .init(repeating: false, count: n)
 
         // we exploit here that parent has always higher index; -> larger index first results in top-to-bottom traversal
@@ -294,7 +294,7 @@ internal final class Gabow<T> where T: AdditiveArithmetic & Comparable & Numeric
 
                 let edge = self.edges[ self.chosen[r] ]
                 if edge.to != root {
-                    res.append(self.chosen[r])
+                    res.append(self.edges[self.chosen[r]])
                 }
 
                 let leafEdgePos = leaf[edge.to]

diff --git a/Sources/SwiftGraph/FindTreeRoot.swift b/Sources/SwiftGraph/FindTreeRoot.swift
@@ -0,0 +1,95 @@
+import Foundation
+
+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
+        }
+    }
+}
+
+
+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 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
+        }
+    }
+
+
+
+    public func findTreeRootVertex() -> V? {
+        guard let root = findTreeRoot() else {
+            return nil
+        }
+
+        return self.vertices[root]
+    }
+}
diff --git a/Sources/SwiftGraph/MSA.swift b/Sources/SwiftGraph/MSA.swift
@@ -21,13 +21,12 @@ public extension WeightedGraph where V: Hashable, W: Comparable & Numeric  {
         assert(root >= 0 && root < self.vertexCount)
 
         var reachable = Set<V>()
-        var directMap = [V: Int].init()
-        var inverseMap: [Int: Int] = .init()
-        var reachableVertexToIndexMap: [V: Int] = .init()
-        
+        var directMap = [V: Int].init() // directMap[K] = V means that the vertex K from `self` is found at index V in `reachableGraph`
+        var inverseMap: [Int: Int] = .init() // inverseMap[K] = V means that the edge at index K from `reachableGraph` is found at index V in `self`
+        var inverseVerticesMap: [Int: Int] = .init() // inverseMap[K] = V means that the vertex at index K from `reachableGraph` is found at index V in `self`
+
         let _ = self.ivBfs(fromIndex: root) { vertexIndex, vertex in
             reachable.insert(vertex)
-            reachableVertexToIndexMap[vertex] = vertexIndex
             return false
         }
 
@@ -40,7 +39,12 @@ public extension WeightedGraph where V: Hashable, W: Comparable & Numeric  {
 
             reachable.enumerated().forEach { i, vertex in
                 directMap[vertex] = i
-                let _ = reachableGraph.addVertex(vertex)
+                let newIndexOfV = reachableGraph.addVertex(vertex)
+
+                assert(reachableGraph.indexOfVertex(vertex) == directMap[vertex])
+                inverseVerticesMap[newIndexOfV] = self.indexOfVertex(vertex)
+
+                assert(self[inverseVerticesMap[newIndexOfV]!] == vertex)
             }
 
             allEdges.enumerated().forEach { i, edge in
@@ -54,24 +58,25 @@ public extension WeightedGraph where V: Hashable, W: Comparable & Numeric  {
                         weight: edge.weight,
                         directed: true
                     )
-
-                    inverseMap[reachableGraph.edgeCount-1] = i
                 }
             }
 
             return try reachableGraph.msaFromConnectedRoot(
                 directMap[self.vertices[root]]!
-            ).map { edgeID in
-                return allEdges[inverseMap[edgeID]!]
+            ).map { edge in
+                return WeightedEdge(
+                    u: inverseVerticesMap[edge.u]!,
+                    v: inverseVerticesMap[edge.v]!,
+                    directed: true,
+                    weight: edge.weight
+                )
             }
         } else {
-            return try msaFromConnectedRoot(root).map { edgeID in
-                return allEdges[edgeID]
-            }
+            return try msaFromConnectedRoot(root)
         }
     }
 
-    private func msaFromConnectedRoot(_ root: Int) throws -> [Int] {
+    private func msaFromConnectedRoot(_ root: Int) throws -> [WeightedGraph<V, W>.E] {
         let gabow = Gabow<W>(verticesCount: self.vertexCount)
 
         try self.edgeList().forEach { edge in
@@ -87,7 +92,9 @@ public extension WeightedGraph where V: Hashable, W: Comparable & Numeric  {
 
         assert(edges.count == self.vertexCount - 1)
 
-        return edges
+        return edges.map { gabowEdge in
+            return WeightedEdge(u: gabowEdge.from, v: gabowEdge.to, directed: true, weight: gabowEdge.weight)
+        }
     }
 
 }

diff --git a/Tests/SwiftGraphTests/MSATests.swift b/Tests/SwiftGraphTests/MSATests.swift
@@ -7212,7 +7212,7 @@ final class MSATests: XCTestCase {
 
         let root = 0
 
-        let answer = gabow.run(root: root)
+        let _ = gabow.run(root: root)
         let msaEdges = gabow.reconstruct(root: root)
         // Verify the number of edges in the result
         XCTAssertEqual(msaEdges.count, verticesCount - 1)
@@ -7293,5 +7293,77 @@ final class MSATests: XCTestCase {
 
         print("MSA \(msaValue)")
     }
+
+
+    func testMSAFromForest() throws {
+        let dependencyGraph = WeightedGraph<String, Float>()
+
+        // MARK: FOREST 1
+        let selectACharm = dependencyGraph.addVertex("Select a charm topbar")
+        let dbLoader = dependencyGraph.addVertex("db loader")
+        let viewModel = dependencyGraph.addVertex("Memory charms viewModel")
+
+        dependencyGraph.addEdge(.init(u: selectACharm, v: dbLoader, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: dbLoader, v: selectACharm, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: dbLoader, v: viewModel, directed: true, weight: 1.0), directed: true)
+
+        // MARK: FOREST 2
+        let messHallBenchBinoculars = dependencyGraph.addVertex("mess.hall.bench.binoculars")
+        let recreationalAreaBinoculars = dependencyGraph.addVertex("recreational.area.crate.binoculars")
+
+        let recreationalAreaBinocularsBottomBar = dependencyGraph.addVertex("recreational.area.crate.binoculars bottom bar")
+        let messHallBinocularsBottomBar = dependencyGraph.addVertex("mess.hall.bench.binoculars bottom bar")
+
+        let recreationalAreaBinocularsOutline = dependencyGraph.addVertex("recreational.area.crate.binoculars outline")
+        let recreationalAreaBinocularsBoundingCircle = dependencyGraph.addVertex("recreational.area.crate.binoculars bounding circle")
+
+        let messHallBinocularsOutline = dependencyGraph.addVertex("mess.hall.bench.binoculars outline")
+        let messHallBinocularsBoundingCircle = dependencyGraph.addVertex("mess.hall.bench.binoculars bounding circle")
+
+        // "mess.hall.bench.binoculars bottom bar" -> { "recreational.area.crate.binoculars outline", "recreational.area.crate.binoculars bounding circle", "mess.hall.bench.binoculars bounding circle" };
+        dependencyGraph.addEdge(.init(u: messHallBinocularsBottomBar, v: recreationalAreaBinocularsOutline, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: messHallBinocularsBottomBar, v: recreationalAreaBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: messHallBinocularsBottomBar, v: messHallBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+
+        //"mess.hall.bench.binoculars" -> { "recreational.area.crate.binoculars outline",
9938
 "recreational.area.crate.binoculars bounding circle", "mess.hall.bench.binoculars bounding circle" };
+        dependencyGraph.addEdge(.init(u: messHallBenchBinoculars, v: recreationalAreaBinocularsOutline, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: messHallBenchBinoculars, v: recreationalAreaBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: messHallBenchBinoculars, v: messHallBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+
+        //"recreational.area.crate.binoculars bottom bar" -> { "recreational.area.crate.binoculars outline", "recreational.area.crate.binoculars bounding circle", "mess.hall.bench.binoculars bounding circle" };
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinocularsBottomBar, v: recreationalAreaBinocularsOutline, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinocularsBottomBar, v: recreationalAreaBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinocularsBottomBar, v: messHallBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+
+        //"recreational.area.crate.binoculars" -> { "recreational.area.crate.binoculars outline", "recreational.area.crate.binoculars bounding circle", "mess.hall.bench.binoculars bounding circle" };
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinoculars, v: recreationalAreaBinocularsOutline, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinoculars, v: recreationalAreaBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+        dependencyGraph.addEdge(.init(u: recreationalAreaBinoculars, v: messHallBinocularsBoundingCircle, directed: true, weight: 1.0), directed: true)
+
+        let msa = try? dependencyGraph.msa(root: selectACharm)
+
+        var allMSAVertices: Set<String> = .init()
+
+        msa?.forEach { edge in
+            allMSAVertices.insert(dependencyGraph[edge.u])
+            allMSAVertices.insert(dependencyGraph[edge.v])
+        }
+
+        let msaGraph = WeightedGraph<String, Float>(vertices: Array(allMSAVertices))
+        msa?.forEach { msaEdge in
+            msaGraph.addEdge(from: dependencyGraph[msaEdge.u], to: dependencyGraph[msaEdge.v], weight: msaEdge.weight, directed: msaEdge.directed)
+        }
+
+        msaGraph.edgeList().forEach { edge in
+            print("\(msaGraph[edge.u]) --> \(msaGraph[edge.v])")
+        }
+
+        assert(msaGraph.isDAG)
+
+        print("----------------------")
+        msa?.forEach { edge in
+            print("\(dependencyGraph[edge.u]) -> \(dependencyGraph[edge.v])")
+        }
+    }
 }