CODEWITHSUNDEEP
algorithmgraphgraph-theory
ricklane
ricklane

Reputation: 183

Cost of building a "connected matrix"

I'm sure there is an abundance of information on how to do exactly what I'm after, but it's a matter of not knowing the technical term for it. Basically what I want to create is an adjacency matrix for a directed graph, however rather than simply storing whether or not each vertex pair has a direct adjacency, for every vertex pair in the matrix I want to store if there is ANY path connecting the two (and what those paths are).

This would give me constant time complexity for lookups which is desirable, however what's not immediately clear to me is what the expected optimal time complexity of building this matrix will be.

Also, is there a formal name for such a matrix?

Playing this out in my head, it seems like a dynamic programming problem. If I want to know if A is connected to Z, I should be able to ask each of A's neighbors, B, C and D if they are (in some way) connected to Z, and if so, then I know A is. And if B doesn't have this answer stored, then he would ask the same question of his direct neighbors, and so on. I would memoize the results along the way, so subsequent lookups would be constant.

I haven't spent time to implement this yet, because it feels like ϴ(n^n) to build a complete matrix, so my question is whether or not I'm going about this the right way, and if indeed there is a lower-cost way to build such a matrix?

Upvotes: 0

Views: 129

Answers (2)

Rusty Rob
Rusty Rob

Reputation: 17173

Using networkx connected components

G = nx.path_graph(4)
G.add_path([10, 11, 12])
d = {}
for group in idx, group in enumerate(nx.connected_components(G)):
    for node in group:
        d[node] = idx

def connected(node1, node2):
    return d[node1]==d[node2]

Generation should be O(N) lookup should be O(1)

Upvotes: 0

Quentin Fortier
Quentin Fortier

Reputation: 163

The transitive closure of a graph (https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory) can indeed be computed by dynamic programming with a variation of Floyd Warshall algorithm: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm.

Using |V| DFS (or BFS) is more efficient, though.

Upvotes: 1

Related Questions