<p>You can use the following idea.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-03-23T19:26:28.637Z
Thanks for your answer. Would you please elaborate what is `v` here ?
ARH
CC BY-SA 3.0
2014-03-24T04:27:49.930Z
While doing the Breadth first search, $v$ is the current node which is visited.
Dibyayan
CC BY-SA 3.0
2014-03-23T18:27:41.400Z
2014-03-23T18:27:41.400Z
Dibyayan
<p>I am looking for an efficient algorithm to create a graph like this: 
<img src="https://i.sstatic.net/UPiMd.png" alt="enter image description here"></p>

<p>Initially the graph is filled with <code>x</code> then <code>h</code>s then <code>g</code>s and finally with <code>f</code></p>

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

<p>The key challenging point here is that <code>f</code> is also dependent to <code>h</code> and <code>x</code> 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. </p>

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

<p>My naive algorithm to insert new vertex like <code>f</code> is:</p>

<blockquote>
  <p>list all graph vertices based on their insertion order</p>
  
  <p>FOR every vertex X from most recently inserted vertex to least recently inserted:</p>

<pre><code> if f is dependent to X but not reachable from X: 
      add X-&gt;f edge
</code></pre>
</blockquote>

<p>Can you please help me to improve this naive algorithm ?</p>

<graph-theory><graph-algorithms><directed-acyclic-graph><graph-drawing>
Efficient algorithm to create a directed dependency graph
ARH
# Efficient algorithm to create a directed dependency graph

(Asked by: username_0 on 2014-03-23)

I am looking for an efficient algorithm to create a graph like this: 

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 ?

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph, graph-drawing


---

## 1 answers

### Answer by username_1 on 2014-03-23. Score: 0

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.

> **Comments:**
> **username_0**: Thanks for your answer. Would you please elaborate what is `v` here ?  
> **username_1**: While doing the Breadth first search, $v$ is the current node which is visited.  

---

