CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorydirected-acyclic-graphs
Joel
Joel

Reputation: 2824

Data structure to efficiently calculate sum of reachable weights on dynamic directed acyclic graph

I have a directed acyclic graph, where each vertex has a "weight" attribute. The reachable vertices from an initial vertex is the set of all vertices reachable by following one or more edges, starting at the initial vertex. The reachable weight sum is the sum of all weights on reachable vertices from an initial vertex. Additionally, I can add directed edges and vertices to the graph at will, however the graph will always remain acyclic.

Are there any data structures I can augment the graph with that will be useful for efficiently calculating the reachable weight sum from any given initial vertex, and updatable when the graph is updated?

Upvotes: 1

Views: 241

Answers (1)

ravenspoint
ravenspoint

Reputation: 20457

If you add a node with a link to a reachable node from an initial node, then the reachable weight increments by the weight of the new node. Otherwise, if the new node is not linked to any reachable nodes, then the reachable weight is unaffected.

So, if you have one initial node that never changes, then it would be worthwhile to store a set of all its reachable nodes. However, if you want to optimize the updating of reachable weights from any node, then it would not be worthwhile to store th reachable nodes from every node - the storage reuired would be greater than the graph.

Upvotes: 0

Related Questions