# Algorithm for searching the neighbors neighbor of a directed graph

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.

-
Which graph database are you working on? Neo4j? – c0da Dec 7 '11 at 10:21
@c0da exactly. I am using it embedded with two Traversal objects: one walking down the nodes edges BFS to depth 1, and then one walking the the nodes back edges up BFS to depth 1. – platzhirsch Dec 7 '11 at 10:26
In response to flags: algorithm design at the conceptual level (like here, with pseudocode, etc.) is on topic here. – Adam Lear Dec 7 '11 at 16:42
@platzhirsch Sorry for the late reply, but have you tried Cypher, Neo4j's query language? I think that will be you best bet... – c0da Dec 21 '11 at 9:32

## 2 Answers

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)
``````
-
But then I don't inspect the parent nodes, do I? I am sorry that I did not point this out more clearly, but since this is a directed graph, it's not the same relationship I am analysising. – platzhirsch Dec 7 '11 at 10:22
Yes yes yes... a neighbour for you is someone with a common child... must fix it... – user281377 Dec 7 '11 at 10:23

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³).

-