saharshluthra's blog

Dynamic Graph Problem | Is it solvable ?
By saharshluthra, history, 4 years ago, In English

Hi,

I came with this subproblem while working on something else. Can someone help me understand if it's solvable problem ?

Difficulty: Hard

Design a data structure that maintains a directed graph. A node with node_id=0 is created by default, having no edges. The data-structure supports following queries:

  1. Create() : Create a new node, with node_id assigned from an auto-incrementing counter. Add a directed edge from node-0 to this new node; return node_id of new node.

  2. Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there is already an edge from x to y.

  3. Delete(x, y) : Delete the directed edge from node-x to node-y, and also delete all the nodes (and their edges) of graph which are not reachable from node-0. return the list of deleted edges and nodes.

All APIs should work in amortized complexity O(log(N)) , where N is the number of nodes in the graph at the time of query.

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by saharshluthra (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
"an directed graph"
Is it "a directed graph" or "an undirected graph"?
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saharshluthra (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets store two sets for every node V with edges (from; V) and (V; to).

Adding edge U->V: insert V to U's set of "to" vertices and U to V's set of "from" vertices.

Removing U->V: delete same vertices and go recursively to V, if |V's "from" set| = 0.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Assuming From(x) represents the set of all nodes reachable to x and To(x) represents the set of all nodes node-x can reach.

    It has two problems:

    1. Doesn't satisfy time complexity requirement. Consider the query set: {create(); create(); create(); create(); create();.. N times ; add(1,2); add(2,3); add(3,4); add(4,5); ....N-1 times} Time complexity = N^2

    2. Handler of deletion is wrong. What you are suggesting works only in acyclic graph.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Garbage collector?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nah, unless you want $$$O(N+M)$$$ for operations of type 3 — GC has scheduled passes that erase nodes. It also doesn't forbid duplicate edges.

    → Reply