Algorithm for searching the neighbors neighbor of a directed graph

Question

Is there an algorithm to search a directed graph (tree) for its neighbors neighbor?

My current brute-force solution works as follows:

for each node n:
   for each child c of n
      for each parent p of c
         if (p != n)
           insert edge (p,n)

I am dealing with ca. 700.000 nodes each having between 1 to 1000 edges and currently I am facing too long running times: which is mainly due to the reason I am executing this algorithm on a graph database, since it would require too much memory.

Answer 1

Are "for each child" and "for each parent" equally fast? If "for each parent" is slower, try this:

for each node p
  for each child c1 of p
     for each child c2 of p
       if (c1 != c2)
         insert edge (c1,c2)

EDIT: The above version creates a different result, a list of siblings. Now for another approach...

for each node c
  ps:=c.parents()   
  for each p1 in ps
     for each p2 in ps
       if (p1 != p2)
         insert edge (p1,p2)

Answer 2

Try substracting:

surroundings = list[]

for each node p
  for each child c1 of p
    for each child c2 of c1
      if c2 not in surroundings
        surroundings->add(c2) # Add everything, don't mind if it's on the border or inside.
    if c1 in surroundings
      surroundings->remove(c1) # Remove what's not on the border.
  if p in surroundings
    surroundings->remove(p) # Remove the initial node.

for each node border in list
  # Do whatever you want.

I'm sorry, I don't think you'll find anything smaller than an algorith in O(n³).