Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Anna 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
add comment

2 Answers

up vote 1 down vote accepted

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)
share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.