crossarcher's blog

By crossarcher, history, 5 weeks ago, In English

We are given a graph. Initially graph is empty. There are three type of operation we can perform on graph.

  1. insertType1 value
  2. insertType2 value parentNodeId
  3. query nodeId maxDistance

Both insertType1 and insertType2 adds node to the graph. Newly added node will have new NodeId which will be auto incremented (starting from 0).

For example, 
first node inserted will have nodeId = 0
second node inserted will have nodeId = 1
third node inserted will have nodeId = 2
and so on.

insertType2 takes parent node id as second argument. So there will be directed edge from parent node to newly generated node.

These insert operations will form graph which contains multiple directed tree graph.

insertType1 and insertType2 operator should print nodeId. query operator should print sum of values of all nodes which are descendent of node with id equals to nodeId and descendents should not be far more than maxDistance.

Sample Input:

insertType1 11
insertType2 12 0
insertType2 13 0
query 0 0
query 0 1
insertType2 14 1
insertType2 15 2
insertType2 16 3
insertType2 17 3
insertType2 18 3
query 3 1
query 0 2
query 1 1

Sample Output:

0
1
2
11
36
3
4
5
6
7
65
65
26

example tree:

          11 
         /  \
        12   13
       /      \
      14       15
    /  |  \ 
  16  17  18

Brute for approach for query operation will require breadth first search for every query.

Any Idea how to answer queries efficiently? Looking for an online algorithm.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

First you can build final graph by processing all inserts with 0 values. Then flatten it using dfs order and build something like kd-tree or merge sort tree on flattened array. Then process queries in given order but now insert type 1 = insert type 2 = update of value in a tree. Query = sum in rectangle (depth from root in node..+maxDistance, dfs time in time_in[node]..time_out[node])

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for reply. To run DFS we will need all the nodes before hand. Any idea how to design a data structure to process these queries as online? (cause we don't know how many nodes will be added)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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