Re: [Neo4j] Relationship Check During Traversal

2010-09-15 Thread Morten Barklund 
Hi,

My suggestion is to look at the BestFirstSelectorFactory abstract
classhttp://components.neo4j.org/neo4j-graph-algo/apidocs/org/neo4j/graphalgo/util/BestFirstSelectorFactory.html.
Extend that and fill in the methods.

It worked wonders for me trying to traverse a weighted graph and worked much
faster than dijkstra or A* factory methods as I could control traversal much
more fine-grained with pruners and a filter.

My $0.02

Regards,
Morten Barklund

On Wed, Sep 15, 2010 at 07:51, Paddy paddyf...@gmail.com wrote:

 Hi ,
 I'm trying to setup a Traversal in a time dependant graph
 with multiple weighted connections between nodes representing
 minutes. I want to only traverse the first relationship with a
 value greater than the weight of the traversal's current position.
 i.e if the path.weight()=100 only traverse the first relationship
 with a departure time property =100

 I have implemented a modified BranchSelector to identify the next
 relationship to traverse depending on the path weight. But once i have
 identified this relationship in BranchSelector.next(), how can
 I return a new TraversalBranch using this node.

 As i see the TraversalBranch is created in ExpansionSourceImpl using:
 TraversalBranch next = new ExpansionSourceImpl( traverser, this,
 depth + 1, node,traverser.description.expander, relationship );

 Would I need to create a modified ExpansionSourceImpl?
 Please let me know if i am going down the right path :-/

 thanks
 Paddy

 On Sat, Sep 11, 2010 at 1:51 PM, Paddy paddyf...@gmail.com wrote:

  Hi David,
  Thanks for your help, I got it working using the following code. I tested
  it on a small graph with the neo4j java-dijkstra example and it works :)
 
  Cheers
  Paddy
 
public static PruneEvaluator pruneAfterTransfer()
  {
  return new PruneEvaluator()
  {
  public boolean pruneAfter( Path path )
  {
   System.out.println(path  + path);
  int count=0;
 
  if(path.lastRelationship().isType(RelationshipTypes.TRANSFER))
   {
   IterableRelationship relationships =
  path.relationships();
   for(Relationship relationship : relationships)
   {
   if(relationship.isType(RelationshipTypes.TRANSFER))
   {
if (++count == 2) {
System.out.println(Breaking!!);
return true;
  }
   }
 
 
   }
   }
  return false;
  }
  };
  }
 
 
  PruneEvaluator prunerAfterTransfer = pruneAfterTransfer();
  private static final TraversalDescription TRAVERSAL =
  Traversal.description().uniqueness(
  Uniqueness.NONE ).prune(pruneAfterTransfer());
 
  On Fri, Sep 10, 2010 at 10:11 PM, David Montag 
  david.mon...@neotechnology.com wrote:
 
  Hi Paddy,
 
  One idea is to prune the traversal by looking at whether the path so far
  already has a transfer relationship or not. You would then do some kind
 of
  filtering of the resulting paths, e.g. only accepting those with correct
  end
  nodes. I don't know if the computational complexity of this is
 acceptable
  or
  not though.
 
  And I don't know if this answer was relevant or not. I hope it was :)
 
  David
 
  On Sat, Sep 11, 2010 at 4:09 AM, Paddy paddyf...@gmail.com wrote:
 
   Hi just a quick question regarding the use of the PruneEvaluator
  
   I was wondering what would be the best way to modify the
   TraversalDescription in the Dijkstra
   algorithm in order to prune a traversal when a branch has reached a
  second
   transfer relationship.
   I want to avoid multiple transfers in a bus network.
  
   If the graph is arranged as:
  
   (stop:1) --bus (stop:2) --transfer (stop:3) --bus (stop:4)
 --transfer
  
   (stop:5)
  
   Is it possible to prune the traversal branch when the 2nd transfer
   relationship is reached after (stop:4)
   Could this be achieved using a PruneEvaluator? Or am I approaching
 this
  the
   wrong way?
  
   thanks
   Paddy
   ___
   Neo4j mailing list
   User@lists.neo4j.org
   https://lists.neo4j.org/mailman/listinfo/user
  
  ___
  Neo4j mailing list
  User@lists.neo4j.org
  https://lists.neo4j.org/mailman/listinfo/user
 
 
 
 ___
 Neo4j mailing list
 User@lists.neo4j.org
 https://lists.neo4j.org/mailman/listinfo/user




-- 
Morten Barklund
___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user

Re: [Neo4j] Relationship Check During Traversal

2010-09-14 Thread Paddy 
Hi ,
I'm trying to setup a Traversal in a time dependant graph
with multiple weighted connections between nodes representing
minutes. I want to only traverse the first relationship with a
value greater than the weight of the traversal's current position.
i.e if the path.weight()=100 only traverse the first relationship
with a departure time property =100

I have implemented a modified BranchSelector to identify the next
relationship to traverse depending on the path weight. But once i have
identified this relationship in BranchSelector.next(), how can
I return a new TraversalBranch using this node.

As i see the TraversalBranch is created in ExpansionSourceImpl using:
TraversalBranch next = new ExpansionSourceImpl( traverser, this,
depth + 1, node,traverser.description.expander, relationship );

Would I need to create a modified ExpansionSourceImpl?
Please let me know if i am going down the right path :-/

thanks
Paddy

On Sat, Sep 11, 2010 at 1:51 PM, Paddy paddyf...@gmail.com wrote:

 Hi David,
 Thanks for your help, I got it working using the following code. I tested
 it on a small graph with the neo4j java-dijkstra example and it works :)

 Cheers
 Paddy

   public static PruneEvaluator pruneAfterTransfer()
 {
 return new PruneEvaluator()
 {
 public boolean pruneAfter( Path path )
 {
  System.out.println(path  + path);
 int count=0;

 if(path.lastRelationship().isType(RelationshipTypes.TRANSFER))
  {
  IterableRelationship relationships =
 path.relationships();
  for(Relationship relationship : relationships)
  {
  if(relationship.isType(RelationshipTypes.TRANSFER))
  {
   if (++count == 2) {
   System.out.println(Breaking!!);
   return true;
 }
  }


  }
  }
 return false;
 }
 };
 }


 PruneEvaluator prunerAfterTransfer = pruneAfterTransfer();
 private static final TraversalDescription TRAVERSAL =
 Traversal.description().uniqueness(
 Uniqueness.NONE ).prune(pruneAfterTransfer());

 On Fri, Sep 10, 2010 at 10:11 PM, David Montag 
 david.mon...@neotechnology.com wrote:

 Hi Paddy,

 One idea is to prune the traversal by looking at whether the path so far
 already has a transfer relationship or not. You would then do some kind of
 filtering of the resulting paths, e.g. only accepting those with correct
 end
 nodes. I don't know if the computational complexity of this is acceptable
 or
 not though.

 And I don't know if this answer was relevant or not. I hope it was :)

 David

 On Sat, Sep 11, 2010 at 4:09 AM, Paddy paddyf...@gmail.com wrote:

  Hi just a quick question regarding the use of the PruneEvaluator
 
  I was wondering what would be the best way to modify the
  TraversalDescription in the Dijkstra
  algorithm in order to prune a traversal when a branch has reached a
 second
  transfer relationship.
  I want to avoid multiple transfers in a bus network.
 
  If the graph is arranged as:
 
  (stop:1) --bus (stop:2) --transfer (stop:3) --bus (stop:4) --transfer
 
  (stop:5)
 
  Is it possible to prune the traversal branch when the 2nd transfer
  relationship is reached after (stop:4)
  Could this be achieved using a PruneEvaluator? Or am I approaching this
 the
  wrong way?
 
  thanks
  Paddy
  ___
  Neo4j mailing list
  User@lists.neo4j.org
  https://lists.neo4j.org/mailman/listinfo/user
 
 ___
 Neo4j mailing list
 User@lists.neo4j.org
 https://lists.neo4j.org/mailman/listinfo/user



___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user

[Neo4j] Relationship Check During Traversal

2010-09-10 Thread Paddy 
Hi just a quick question regarding the use of the PruneEvaluator

I was wondering what would be the best way to modify the
TraversalDescription in the Dijkstra
algorithm in order to prune a traversal when a branch has reached a second
transfer relationship.
I want to avoid multiple transfers in a bus network.

If the graph is arranged as:

(stop:1) --bus (stop:2) --transfer (stop:3) --bus (stop:4) --transfer 
(stop:5)

Is it possible to prune the traversal branch when the 2nd transfer
relationship is reached after (stop:4)
Could this be achieved using a PruneEvaluator? Or am I approaching this the
wrong way?

thanks
Paddy
___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user

Re: [Neo4j] Relationship Check During Traversal

2010-09-10 Thread David Montag 
Hi Paddy,

One idea is to prune the traversal by looking at whether the path so far
already has a transfer relationship or not. You would then do some kind of
filtering of the resulting paths, e.g. only accepting those with correct end
nodes. I don't know if the computational complexity of this is acceptable or
not though.

And I don't know if this answer was relevant or not. I hope it was :)

David

On Sat, Sep 11, 2010 at 4:09 AM, Paddy paddyf...@gmail.com wrote:

 Hi just a quick question regarding the use of the PruneEvaluator

 I was wondering what would be the best way to modify the
 TraversalDescription in the Dijkstra
 algorithm in order to prune a traversal when a branch has reached a second
 transfer relationship.
 I want to avoid multiple transfers in a bus network.

 If the graph is arranged as:

 (stop:1) --bus (stop:2) --transfer (stop:3) --bus (stop:4) --transfer 
 (stop:5)

 Is it possible to prune the traversal branch when the 2nd transfer
 relationship is reached after (stop:4)
 Could this be achieved using a PruneEvaluator? Or am I approaching this the
 wrong way?

 thanks
 Paddy
 ___
 Neo4j mailing list
 User@lists.neo4j.org
 https://lists.neo4j.org/mailman/listinfo/user

___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user