I am looking for an efficient algorithm to create a graph like this:
Initially the graph is filled with
gs and finally with
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
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
g2 and then it finds out
f is directly dependent to
My naive algorithm to insert new vertex like
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 ?