I am looking for an efficient algorithm to create a graph like this: enter image description here

Initially the graph is filled with x then hs then gs and finally with f

for every new vertex like f the algorithm should traverse all existing vertex in the graph to find out which vertices can be parent of f. Once it finds direct parents of f, then it can add f into the graph and draw dependency edges.

The key challenging point here is that f is also dependent to h and x but they are considered as grand parents. Therefore, the algorithm does not draw dependency edges between child and grand parents. It only add dependency edges for between child and parents.

In the above picture, the algorithm checks all vertices from x to g2 and then it finds out f is directly dependent to g1 and g2.

My naive algorithm to insert new vertex like f is:

list all graph vertices based on their insertion order

FOR every vertex X from most recently inserted vertex to least recently inserted:

 if f is dependent to X but not reachable from X: 
      add X->f edge

Can you please help me to improve this naive algorithm ?


You can use the following idea.

Maintain a graph,say $G^{'}$ similar to the graph that you are constructing,(say $G$) but the edges being reveresed and an extra dummy root node with a directed edge from that to last inserted node. Now when a new node comes,say $f$ in do a Breadth first search from the dummy root on $G^{'}$. Whenever a search node, say $v$ is found during BFS on which $f$ is dependent create an edge in $G$ and update $G^{'}$ accordingly.

The idea is similar to you but if implemented properly runs in linear time( in number of nodes). Hope it helps.

  • $\begingroup$ Thanks for your answer. Would you please elaborate what is v here ? $\endgroup$ – ARH Mar 23 '14 at 19:26
  • $\begingroup$ While doing the Breadth first search, $v$ is the current node which is visited. $\endgroup$ – Dibyayan Mar 24 '14 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.