Transitive Closure

[Aaron3154518]

We want to implement transitive closure on graphs. This may require change the graph structure to use an adjacency list

[Aaron3154518]

Transitive closure using an adjacency matrix: http://taco.cse.tamu.edu/utsa-www/cs3343/lecture20.html

Transitive-Closure (G)
    n = |V|
    t(0) = the adjacency matrix for G

    // there is always an empty path from a vertex to itself,
    // make sure the adjacency matrix reflects this

    for i in 1..n do
        t(0)[i,i] = True
    end for

    // step through the t(k)'s

    for k in 1..n do
        for i in 1..n do
            for j in 1..n do
                t(k)[i,j] = t(k-1)[i,j] OR
                    (t(k-1)[i,k] AND t(k-1)[k,j])
            end for
        end for
    end for
    return t(n)

O(n^3)

[Aaron3154518]

With object-oriented graph structure (current structure):

Graph::Transitive-Closure () {
        // Edges will be stored in std::forward_lists, which are singly-linked lists
    // No need for paths from each node to itself as we are reusing the same graph.

    // step through the t(k)'s

        // t(k-1)[i,j] maintain for existing edges
        //         - just leave current edges alone
        // (t(k-1)[i,k] AND t(k-1)[k,j]): connect nodes through k
        //         - just connect IN(k) X OUT(k) where IN(k) and OUT(k) are the set of incoming
        //           and outgoing nodes for k, respectively
        // Worst case time: O(n^3),
    foreach stmt:
        foreach inStmt in IN(stmt):
                        foreach outStmt in OUT(stmt):
                                inStmt->addEdge(outStmt) // Constant time, possible repetition
                        endfor
               endfor
    end for

        // Remove repetition
        // Worst case time: O(n^3), Worst case writes: O(n^2), Worst case reads: O(n^3)
        foreach stmt:
                stmt->removeDuplicates() // O(n) time
        end for
}

Node::removeDuplicates() {
        bool arr[n] = {false}
        std::list newList
        foreach edge in edgeList: // Note edgeList can represent outEdges or inEdges
                if (!arr[edge]) {
                        arr[edge] = true
                        newList.insert(edge)
                }
        end for
}

O(n^3) in worst case (transitive closure produces a complete directed graph). list docs: https://www.cplusplus.com/reference/list/

Benefits:

• Can achieve better than O(n^3) time in some cases (vs. always O(n^3)) - both time and read/writes
• Allows use of object-oriented graph structure without also needing an adjacency matrix.

[Aaron3154518]

The big reason I'm trying to avoid an adjacency matrix is because:

• It is difficult to delete nodes from adjacency matrices, which we do for reducing produce consumer relations
• It is slow to iterate over edges in an adjacency matrix, which we in most graph operations

It's only benefit is constant-time edge access. So far transitive closure is the only method that needs that, and I've identified a workaround that actually has slightly optimized run-time and read/write complexity.