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

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

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.