[Neo] A new and improved Traversal framework
Hi All, I'm new to neo4j and the mailing list. I have a simple traversal use case that I couldn't find a way to perform with the existing API. What would be your suggestion to the following scenario? I want to do a depth first traversal of the graph and want to add a property called "post_order_value" to each node during the traversal. For example, if we have a graph of A -> B , B -> C , A->D , D->C An example traverser labels the nodes with post-order values as C=1, B=2,D=3 and A=4. Because the depth first traversal first finishes C, then B, then D and finally A. What I am concerned is a slight variation of this problem. In the above example, the visitation order of the children is important. For example, if the traverser had chosen D before B while processing the children of A, the labels would end up being C=1, D=2,B=3 and A=4. I'd like to generate random traversals, so that in the DFS the traverser chooses the children in random order. By this way I will get many valid post-order labelings. Is this possible in the current traversal API or in the Improved framework? Thanks, p.s. : This email is indeed a reply to Tobias' "A new and improved Traversal framework" message. [Neo] A new and improved Traversal framework Tobias Ivarsson Tue, 30 Mar 2010 06:48:46 -0700 It seems a lot of projects have outgrown the current Traverser framework. People want to be able to do things such as visiting all relationships once instead of all nodes once (the current framework only visit each node once and leave out other relationships that go there). There has also been requests for a way to select the next relationship to traverse using a callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST to choose from. To address these requests we have started a project to implement a new traversal framework. The early prototype for this is available in my laboratory directory in the repository: https://svn.neo4j.org/laboratory/users/tobias/traversal/ The state of the prototype is very early, it supports the same features as the current Traverser framework plus being able to limit the traversal by relationships instead of nodes or based on the path to each position. This is already quite interesting. The part about having a callback for selecting the next relationship is a later feature, one that will probably change the API of the prototype a lot. For comparison the tests contain an implementation of the old Traverser framework on top of the new Traversal framework. The limited number of tests we've written indicate the performance of the old framework is still slightly better than the new framework, but analysis of the operations the different implementations make on the graph gives me high hopes that the new framework will probably beat the old one after we've worked on it some more. Even with the slightly lower performance the versatility of the new framework is substantially greater. The prototype implements a TraversalDescription class that is used to construct the traversal, these objects are immutable and implement a builder pattern making it possible to create base TraversalDescription instances that can then be reused multiple times or adapted slightly before they are used. This leads to shorter, more readable code than the current traverse(...)-methods on the Node interface. This is also the part of the prototype that is most likely to change, both to accomodate for the features that are to be added, and being revised to make it easier to work with. Most of the new traversal framework will live in a new package: org.neo4j.graphdb.traversal, but there will be a few new things introduced in org.neo4j.graphdb as well. The new traversal framework will live side by side with the current traversal framework for a while, to ease the transition. The old traversal framework will be deprecated and then removed in some future version. The additions we have made in the prototype are: * A path representation. Defined as the interface org.neo4j.graphdb.Path. A Path object represents a path of interlinking relationships. The shortest possible path is the path with no relationships, a single node. * A concept of Uniqueness. This defines how often a node or relationship can be (re)visited. The current traversal framework implements what we have called "node global uniqueness" in the new framework. This enforces the restriction that a node cannot be visited more than once. Other uniqueness kinds we introduce in the new framework are: * Relationship global uniqueness - similar to node global uniqueness * Node/Relationship path uniqueness - each node (or relationship) may occur only once in the path (yes, using the Path interface from above) traversed to get there. * Node/Relationship recent uniqueness - a node (or relationship) may not be revisited if it is among the set of recently visited ones (the size of this set is confi
Re: [Neo] A new and improved Traversal framework
Given these additions to the API, the problem in this thread would be solved something like this: http://wiki.neo4j.org/content/Traversal_HowTo#Label_all_nodes_in_a_depth_first_traversal_by_postorder btw, I intend to start adding more traversal howtos to that page, I encourage everyone to do the same :) Cheers, Tobias On Tue, May 18, 2010 at 10:19 AM, Mattias Persson wrote: > And regarding post-order, I just added post-order depth/breadth first > selectors which can be used like: > > TraversalFactory.createTraversalDescription().postorderDepthFirst(); > > or > > TraversalFactory.createTraversalDescription().postorderBreadthFirst(); > > 2010/5/18 Mattias Persson > > > The easiest way to do this would be to implement your own SourceSelector > > (just like DepthFirstSelector implements SourceSelector) and feed that to > > your TraversalDescription, like this: > > > > class MyRandomSelector implements SourceSelector > > { > > private ExpansionSource current; > > > > MyRandomSelector( ExpansionSource start ) > > { > > this.current = start; > > } > > > > public ExpansionSource nextPosition() > > { > > // Implement your random selector here > > } > > } > > > > class MyRandomSelectorFactory implements SourceSelectorFactory > > { > > public SourceSelector create( ExpansionSource start ) > > { > > return new MyRandomSelector( start ); > > } > > } > > > > Then feed it to your traversal description: > > > > TraversalDescription description = > > TraversalFactory.createTraversalDescription().sourceSelector( > > new MyRandomSelectorFactory() ); > > > > You can see how the depth first selector is implemented: > > > https://svn.neo4j.org/components/kernel/trunk/src/main/java/org/neo4j/kernel/impl/traversal/DepthFirstSelector.java > > > > 2010/5/17 hilmi yildirim > > > > Hi All, > >> > >> I'm new to neo4j and the mailing list. I have a simple traversal use > >> case that I couldn't find a way to perform with the existing API. What > >> would be your suggestion to the following scenario? > >> > >> I want to do a depth first traversal of the graph and want to add a > >> property called "post_order_value" to each node during the traversal. > >> For example, if we have a graph of > >> A -> B , B -> C , A->D , D->C > >> > >> An example traverser labels the nodes with post-order values as C=1, > >> B=2,D=3 and A=4. Because the depth first traversal first finishes C, > >> then B, then D and finally A. > >> > >> What I am concerned is a slight variation of this problem. In the > >> above example, the > >> visitation order of the children is important. For example, if the > >> traverser had chosen D before B while processing the children of A, > >> the labels would end up being C=1, D=2,B=3 and A=4. I'd like to > >> generate random traversals, so that in the DFS the traverser chooses > >> the children in random order. By this way I will get many valid > >> post-order labelings. > >> > >> Is this possible in the current traversal API or in the Improved > >> framework? > >> > >> Thanks, > >> > >> > >> p.s. : This email is indeed a reply to Tobias' "A new and improved > >> Traversal framework" message. > >> > >> > >> [Neo] A new and improved Traversal framework > >> Tobias Ivarsson > >> Tue, 30 Mar 2010 06:48:46 -0700 > >> > >> It seems a lot of projects have outgrown the current Traverser > framework. > >> People want to be able to do things such as visiting all relationships > >> once > >> instead of all nodes once (the current framework only visit each node > once > >> and leave out other relationships that go there). There has also been > >> requests for a way to select the next relationship to traverse using a > >> callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST > >> to > >> choose from. > >> > >> To address these requests we have started a project to implement a new > >> traversal framework. The early prototype for this is available in my > >> laboratory directory in the repository: > >> https://svn.neo4j.org/laboratory/users/tobias/traversal/ > >> The state of the prototype is very early, i
Re: [Neo] A new and improved Traversal framework
The easiest way to do this would be to implement your own SourceSelector (just like DepthFirstSelector implements SourceSelector) and feed that to your TraversalDescription, like this: class MyRandomSelector implements SourceSelector { private ExpansionSource current; MyRandomSelector( ExpansionSource start ) { this.current = start; } public ExpansionSource nextPosition() { // Implement your random selector here } } class MyRandomSelectorFactory implements SourceSelectorFactory { public SourceSelector create( ExpansionSource start ) { return new MyRandomSelector( start ); } } Then feed it to your traversal description: TraversalDescription description = TraversalFactory.createTraversalDescription().sourceSelector( new MyRandomSelectorFactory() ); You can see how the depth first selector is implemented: https://svn.neo4j.org/components/kernel/trunk/src/main/java/org/neo4j/kernel/impl/traversal/DepthFirstSelector.java 2010/5/17 hilmi yildirim > Hi All, > > I'm new to neo4j and the mailing list. I have a simple traversal use > case that I couldn't find a way to perform with the existing API. What > would be your suggestion to the following scenario? > > I want to do a depth first traversal of the graph and want to add a > property called "post_order_value" to each node during the traversal. > For example, if we have a graph of > A -> B , B -> C , A->D , D->C > > An example traverser labels the nodes with post-order values as C=1, > B=2,D=3 and A=4. Because the depth first traversal first finishes C, > then B, then D and finally A. > > What I am concerned is a slight variation of this problem. In the > above example, the > visitation order of the children is important. For example, if the > traverser had chosen D before B while processing the children of A, > the labels would end up being C=1, D=2,B=3 and A=4. I'd like to > generate random traversals, so that in the DFS the traverser chooses > the children in random order. By this way I will get many valid > post-order labelings. > > Is this possible in the current traversal API or in the Improved framework? > > Thanks, > > > p.s. : This email is indeed a reply to Tobias' "A new and improved > Traversal framework" message. > > > [Neo] A new and improved Traversal framework > Tobias Ivarsson > Tue, 30 Mar 2010 06:48:46 -0700 > > It seems a lot of projects have outgrown the current Traverser framework. > People want to be able to do things such as visiting all relationships once > instead of all nodes once (the current framework only visit each node once > and leave out other relationships that go there). There has also been > requests for a way to select the next relationship to traverse using a > callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST to > choose from. > > To address these requests we have started a project to implement a new > traversal framework. The early prototype for this is available in my > laboratory directory in the repository: > https://svn.neo4j.org/laboratory/users/tobias/traversal/ > The state of the prototype is very early, it supports the same features as > the current Traverser framework plus being able to limit the traversal by > relationships instead of nodes or based on the path to each position. This > is already quite interesting. The part about having a callback for > selecting > the next relationship is a later feature, one that will probably change the > API of the prototype a lot. For comparison the tests contain an > implementation of the old Traverser framework on top of the new Traversal > framework. The limited number of tests we've written indicate the > performance of the old framework is still slightly better than the new > framework, but analysis of the operations the different implementations > make > on the graph gives me high hopes that the new framework will probably beat > the old one after we've worked on it some more. Even with the slightly > lower > performance the versatility of the new framework is substantially greater. > > The prototype implements a TraversalDescription class that is used to > construct the traversal, these objects are immutable and implement a > builder > pattern making it possible to create base TraversalDescription instances > that can then be reused multiple times or adapted slightly before they are > used. This leads to shorter, more readable code than the current > traverse(...)-methods on the Node interface. This is also the part of the > prototype that is most likely to change, both to accomodate for the > features > that are to be added, and be
Re: [Neo] A new and improved Traversal framework
And regarding post-order, I just added post-order depth/breadth first selectors which can be used like: TraversalFactory.createTraversalDescription().postorderDepthFirst(); or TraversalFactory.createTraversalDescription().postorderBreadthFirst(); 2010/5/18 Mattias Persson > The easiest way to do this would be to implement your own SourceSelector > (just like DepthFirstSelector implements SourceSelector) and feed that to > your TraversalDescription, like this: > > class MyRandomSelector implements SourceSelector > { > private ExpansionSource current; > > MyRandomSelector( ExpansionSource start ) > { > this.current = start; > } > > public ExpansionSource nextPosition() > { > // Implement your random selector here > } > } > > class MyRandomSelectorFactory implements SourceSelectorFactory > { > public SourceSelector create( ExpansionSource start ) > { > return new MyRandomSelector( start ); > } > } > > Then feed it to your traversal description: > > TraversalDescription description = > TraversalFactory.createTraversalDescription().sourceSelector( > new MyRandomSelectorFactory() ); > > You can see how the depth first selector is implemented: > https://svn.neo4j.org/components/kernel/trunk/src/main/java/org/neo4j/kernel/impl/traversal/DepthFirstSelector.java > > 2010/5/17 hilmi yildirim > > Hi All, >> >> I'm new to neo4j and the mailing list. I have a simple traversal use >> case that I couldn't find a way to perform with the existing API. What >> would be your suggestion to the following scenario? >> >> I want to do a depth first traversal of the graph and want to add a >> property called "post_order_value" to each node during the traversal. >> For example, if we have a graph of >> A -> B , B -> C , A->D , D->C >> >> An example traverser labels the nodes with post-order values as C=1, >> B=2,D=3 and A=4. Because the depth first traversal first finishes C, >> then B, then D and finally A. >> >> What I am concerned is a slight variation of this problem. In the >> above example, the >> visitation order of the children is important. For example, if the >> traverser had chosen D before B while processing the children of A, >> the labels would end up being C=1, D=2,B=3 and A=4. I'd like to >> generate random traversals, so that in the DFS the traverser chooses >> the children in random order. By this way I will get many valid >> post-order labelings. >> >> Is this possible in the current traversal API or in the Improved >> framework? >> >> Thanks, >> >> >> p.s. : This email is indeed a reply to Tobias' "A new and improved >> Traversal framework" message. >> >> >> [Neo] A new and improved Traversal framework >> Tobias Ivarsson >> Tue, 30 Mar 2010 06:48:46 -0700 >> >> It seems a lot of projects have outgrown the current Traverser framework. >> People want to be able to do things such as visiting all relationships >> once >> instead of all nodes once (the current framework only visit each node once >> and leave out other relationships that go there). There has also been >> requests for a way to select the next relationship to traverse using a >> callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST >> to >> choose from. >> >> To address these requests we have started a project to implement a new >> traversal framework. The early prototype for this is available in my >> laboratory directory in the repository: >> https://svn.neo4j.org/laboratory/users/tobias/traversal/ >> The state of the prototype is very early, it supports the same features as >> the current Traverser framework plus being able to limit the traversal by >> relationships instead of nodes or based on the path to each position. This >> is already quite interesting. The part about having a callback for >> selecting >> the next relationship is a later feature, one that will probably change >> the >> API of the prototype a lot. For comparison the tests contain an >> implementation of the old Traverser framework on top of the new Traversal >> framework. The limited number of tests we've written indicate the >> performance of the old framework is still slightly better than the new >> framework, but analysis of the operations the different implementations >> make >> on the graph gives me high hopes that the new framework will probably beat >> the o
[Neo] A new and improved Traversal framework
It seems a lot of projects have outgrown the current Traverser framework. People want to be able to do things such as visiting all relationships once instead of all nodes once (the current framework only visit each node once and leave out other relationships that go there). There has also been requests for a way to select the next relationship to traverse using a callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST to choose from. To address these requests we have started a project to implement a new traversal framework. The early prototype for this is available in my laboratory directory in the repository: https://svn.neo4j.org/laboratory/users/tobias/traversal/ The state of the prototype is very early, it supports the same features as the current Traverser framework plus being able to limit the traversal by relationships instead of nodes or based on the path to each position. This is already quite interesting. The part about having a callback for selecting the next relationship is a later feature, one that will probably change the API of the prototype a lot. For comparison the tests contain an implementation of the old Traverser framework on top of the new Traversal framework. The limited number of tests we've written indicate the performance of the old framework is still slightly better than the new framework, but analysis of the operations the different implementations make on the graph gives me high hopes that the new framework will probably beat the old one after we've worked on it some more. Even with the slightly lower performance the versatility of the new framework is substantially greater. The prototype implements a TraversalDescription class that is used to construct the traversal, these objects are immutable and implement a builder pattern making it possible to create base TraversalDescription instances that can then be reused multiple times or adapted slightly before they are used. This leads to shorter, more readable code than the current traverse(...)-methods on the Node interface. This is also the part of the prototype that is most likely to change, both to accomodate for the features that are to be added, and being revised to make it easier to work with. Most of the new traversal framework will live in a new package: org.neo4j.graphdb.traversal, but there will be a few new things introduced in org.neo4j.graphdb as well. The new traversal framework will live side by side with the current traversal framework for a while, to ease the transition. The old traversal framework will be deprecated and then removed in some future version. The additions we have made in the prototype are: * A path representation. Defined as the interface org.neo4j.graphdb.Path. A Path object represents a path of interlinking relationships. The shortest possible path is the path with no relationships, a single node. * A concept of Uniqueness. This defines how often a node or relationship can be (re)visited. The current traversal framework implements what we have called "node global uniqueness" in the new framework. This enforces the restriction that a node cannot be visited more than once. Other uniqueness kinds we introduce in the new framework are: * Relationship global uniqueness - similar to node global uniqueness * Node/Relationship path uniqueness - each node (or relationship) may occur only once in the path (yes, using the Path interface from above) traversed to get there. * Node/Relationship recent uniqueness - a node (or relationship) may not be revisited if it is among the set of recently visited ones (the size of this set is configurable). This is similar to global uniqueness, but with a constraint on the amount of memory the traversal is allowed to use. * No uniqueness. The name says it all, all nodes and relationships are visited, without restriction. * PruneEvaluator - has the same role as the previous StopEvaluator, but with a more descriptive name. * RelationshipExpander - this is "what traversers are made of", given a node, a RelationshipExpander is responsible for getting the relationships from it that are relevant to the traversal. This is a utility that is used a lot in the new traversal framework, and that might also be useful on its own. The concepts we are planning to add, but have not completed the design for yet are: * A way to select/order relationships. This is an extension of DEPTH_FIRST and BREADTH_FIRST, where the user can define which relationships to traverse, and in what order to traverse them. * Relationship patterns, a way to tell the traversal to expand one relationship type first, and then another type, and so on. Try it out and give us feedback, we will keep working on the implementation, and hope to push this into the trunk of kernel as soon as possible. -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo mailing l
Re: [Neo] A new and improved Traversal framework
I just updated the code for how to choose a postorder depth first selector, so go check out the wiki page once more, It's up to date. 2010/5/18 Tobias Ivarsson > Given these additions to the API, the problem in this thread would be > solved > something like this: > > http://wiki.neo4j.org/content/Traversal_HowTo#Label_all_nodes_in_a_depth_first_traversal_by_postorder > > btw, I intend to start adding more traversal howtos to that page, I > encourage everyone to do the same :) > > Cheers, > Tobias > > On Tue, May 18, 2010 at 10:19 AM, Mattias Persson < > matt...@neotechnology.com > > wrote: > > > And regarding post-order, I just added post-order depth/breadth first > > selectors which can be used like: > > > > TraversalFactory.createTraversalDescription().postorderDepthFirst(); > > > > or > > > > TraversalFactory.createTraversalDescription().postorderBreadthFirst(); > > > > 2010/5/18 Mattias Persson > > > > > The easiest way to do this would be to implement your own > SourceSelector > > > (just like DepthFirstSelector implements SourceSelector) and feed that > to > > > your TraversalDescription, like this: > > > > > > class MyRandomSelector implements SourceSelector > > > { > > > private ExpansionSource current; > > > > > > MyRandomSelector( ExpansionSource start ) > > > { > > > this.current = start; > > > } > > > > > > public ExpansionSource nextPosition() > > > { > > > // Implement your random selector here > > > } > > > } > > > > > > class MyRandomSelectorFactory implements SourceSelectorFactory > > > { > > > public SourceSelector create( ExpansionSource start ) > > > { > > > return new MyRandomSelector( start ); > > > } > > > } > > > > > > Then feed it to your traversal description: > > > > > > TraversalDescription description = > > > TraversalFactory.createTraversalDescription().sourceSelector( > > > new MyRandomSelectorFactory() ); > > > > > > You can see how the depth first selector is implemented: > > > > > > https://svn.neo4j.org/components/kernel/trunk/src/main/java/org/neo4j/kernel/impl/traversal/DepthFirstSelector.java > > > > > > 2010/5/17 hilmi yildirim > > > > > > Hi All, > > >> > > >> I'm new to neo4j and the mailing list. I have a simple traversal use > > >> case that I couldn't find a way to perform with the existing API. What > > >> would be your suggestion to the following scenario? > > >> > > >> I want to do a depth first traversal of the graph and want to add a > > >> property called "post_order_value" to each node during the traversal. > > >> For example, if we have a graph of > > >> A -> B , B -> C , A->D , D->C > > >> > > >> An example traverser labels the nodes with post-order values as C=1, > > >> B=2,D=3 and A=4. Because the depth first traversal first finishes C, > > >> then B, then D and finally A. > > >> > > >> What I am concerned is a slight variation of this problem. In the > > >> above example, the > > >> visitation order of the children is important. For example, if the > > >> traverser had chosen D before B while processing the children of A, > > >> the labels would end up being C=1, D=2,B=3 and A=4. I'd like to > > >> generate random traversals, so that in the DFS the traverser chooses > > >> the children in random order. By this way I will get many valid > > >> post-order labelings. > > >> > > >> Is this possible in the current traversal API or in the Improved > > >> framework? > > >> > > >> Thanks, > > >> > > >> > > >> p.s. : This email is indeed a reply to Tobias' "A new and improved > > >> Traversal framework" message. > > >> > > >> > > >> [Neo] A new and improved Traversal framework > > >> Tobias Ivarsson > > >> Tue, 30 Mar 2010 06:48:46 -0700 > > >> > > >> It seems a lot of projects have outgrown the current Traverser > > framework. > > >> People want to be able to do things such as visiting all relationships > > >> once >
Re: [Neo4j] [Neo] A new and improved Traversal framework
Hi Tobias and everyone, finally found some time to catch up on my traversal and the RelationshipExpander looks simple and suitable enough. However, which relationships to return depends on the path traversed so far and in the RelationshipExpander I only have access to the current node unless I am missing something. So how can make my expander use the path info? Thanks and best regards, Georg On 19.05.2010 09:46, Tobias Ivarsson wrote: > Since the traversal framework is still a work in progress we are still > tinkering with the API around SourceSelectors and RelationshipExpander. > Mattias Persson and myself are working on creating examples and > documentation as well. > > The purpose of the SourceSelector is mainly to determine the order in which > the relationships are traversed. For pre-filtering the relationships to > traverse I would recommend implementing your own RelatiionshipExpander. This > is one of the most simple parts of the traversal framework API, and also a > very useful component, it should be pretty straight forward. Let me know if > you have any problems with that. > > Also: input and ideas on the structure and API of the traversal framework > would be interesting and welcome. > > Cheers, > Tobias > > On Tue, May 18, 2010 at 6:43 PM, Georg M. Sorst wrote: > >> Hey there, >> >> once again, a relatively new part of Neo's code seems to come along right >> when I need it :) Thanks, guys. >> >> I've recently been trying to do some traversal that sort of can be >> described with transitions ie. if the last relationship was of type A and >> direction INCOMING, the next direction to go might be type A INCOMING or >> type B INCOMING; if it was type B INCOMING the next relationship to traverse >> may only be type C OUTGOING, that kind of stuff. >> >> Now to do this I guess I need all the valid relationships in the traversal >> description, otherwise they wouldn't be traversed at all. Of course checking >> if the last transition was valid can be done in the PruneEvaluator and the >> ReturnableFilter but that's ugly and inefficient as I can only figure out >> invalid transitions after they've already been traversed. A much cleaner way >> would be to not traverse the invalid relationships at all. >> >> From what I've read from the documentation and code I feel this can be done >> with SourceSelector / ExpansionSource etc. but for the life of me I cannot >> figure out how. Unfortunately I also couldn't find any nice examples so I'm >> a bit lost here. I would greatly appreciate any pointers on how to do this >> with a SourceSelector or whatever is the right weapon of choice for this >> problem. >> >> Thanks and best regards, >> Georg >> >> >> On 30.03.2010 15:48, Tobias Ivarsson wrote: >> >>> It seems a lot of projects have outgrown the current Traverser framework. >>> People want to be able to do things such as visiting all relationships >>> once >>> instead of all nodes once (the current framework only visit each node once >>> and leave out other relationships that go there). There has also been >>> requests for a way to select the next relationship to traverse using a >>> callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST >>> to >>> choose from. >>> >>> To address these requests we have started a project to implement a new >>> traversal framework. The early prototype for this is available in my >>> laboratory directory in the repository: >>> https://svn.neo4j.org/laboratory/users/tobias/traversal/ >>> The state of the prototype is very early, it supports the same features as >>> the current Traverser framework plus being able to limit the traversal by >>> relationships instead of nodes or based on the path to each position. This >>> is already quite interesting. The part about having a callback for >>> selecting >>> the next relationship is a later feature, one that will probably change >>> the >>> API of the prototype a lot. For comparison the tests contain an >>> implementation of the old Traverser framework on top of the new Traversal >>> framework. The limited number of tests we've written indicate the >>> performance of the old framework is still slightly better than the new >>> framework, but analysis of the operations the different implementations >>> make >>> on the graph gives me high hopes that the new framework will probably beat >>> the old one after we've worked on it some more. Even with the slight
Re: [Neo] A new and improved Traversal framework
Since the traversal framework is still a work in progress we are still tinkering with the API around SourceSelectors and RelationshipExpander. Mattias Persson and myself are working on creating examples and documentation as well. The purpose of the SourceSelector is mainly to determine the order in which the relationships are traversed. For pre-filtering the relationships to traverse I would recommend implementing your own RelatiionshipExpander. This is one of the most simple parts of the traversal framework API, and also a very useful component, it should be pretty straight forward. Let me know if you have any problems with that. Also: input and ideas on the structure and API of the traversal framework would be interesting and welcome. Cheers, Tobias On Tue, May 18, 2010 at 6:43 PM, Georg M. Sorst wrote: > Hey there, > > once again, a relatively new part of Neo's code seems to come along right > when I need it :) Thanks, guys. > > I've recently been trying to do some traversal that sort of can be > described with transitions ie. if the last relationship was of type A and > direction INCOMING, the next direction to go might be type A INCOMING or > type B INCOMING; if it was type B INCOMING the next relationship to traverse > may only be type C OUTGOING, that kind of stuff. > > Now to do this I guess I need all the valid relationships in the traversal > description, otherwise they wouldn't be traversed at all. Of course checking > if the last transition was valid can be done in the PruneEvaluator and the > ReturnableFilter but that's ugly and inefficient as I can only figure out > invalid transitions after they've already been traversed. A much cleaner way > would be to not traverse the invalid relationships at all. > > From what I've read from the documentation and code I feel this can be done > with SourceSelector / ExpansionSource etc. but for the life of me I cannot > figure out how. Unfortunately I also couldn't find any nice examples so I'm > a bit lost here. I would greatly appreciate any pointers on how to do this > with a SourceSelector or whatever is the right weapon of choice for this > problem. > > Thanks and best regards, > Georg > > > On 30.03.2010 15:48, Tobias Ivarsson wrote: > >> It seems a lot of projects have outgrown the current Traverser framework. >> People want to be able to do things such as visiting all relationships >> once >> instead of all nodes once (the current framework only visit each node once >> and leave out other relationships that go there). There has also been >> requests for a way to select the next relationship to traverse using a >> callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST >> to >> choose from. >> >> To address these requests we have started a project to implement a new >> traversal framework. The early prototype for this is available in my >> laboratory directory in the repository: >> https://svn.neo4j.org/laboratory/users/tobias/traversal/ >> The state of the prototype is very early, it supports the same features as >> the current Traverser framework plus being able to limit the traversal by >> relationships instead of nodes or based on the path to each position. This >> is already quite interesting. The part about having a callback for >> selecting >> the next relationship is a later feature, one that will probably change >> the >> API of the prototype a lot. For comparison the tests contain an >> implementation of the old Traverser framework on top of the new Traversal >> framework. The limited number of tests we've written indicate the >> performance of the old framework is still slightly better than the new >> framework, but analysis of the operations the different implementations >> make >> on the graph gives me high hopes that the new framework will probably beat >> the old one after we've worked on it some more. Even with the slightly >> lower >> performance the versatility of the new framework is substantially greater. >> >> The prototype implements a TraversalDescription class that is used to >> construct the traversal, these objects are immutable and implement a >> builder >> pattern making it possible to create base TraversalDescription instances >> that can then be reused multiple times or adapted slightly before they are >> used. This leads to shorter, more readable code than the current >> traverse(...)-methods on the Node interface. This is also the part of the >> prototype that is most likely to change, both to accomodate for the >> features >> that are to be added, and being revised to make it easier to work with. &
Re: [Neo] A new and improved Traversal framework
Hey there, once again, a relatively new part of Neo's code seems to come along right when I need it :) Thanks, guys. I've recently been trying to do some traversal that sort of can be described with transitions ie. if the last relationship was of type A and direction INCOMING, the next direction to go might be type A INCOMING or type B INCOMING; if it was type B INCOMING the next relationship to traverse may only be type C OUTGOING, that kind of stuff. Now to do this I guess I need all the valid relationships in the traversal description, otherwise they wouldn't be traversed at all. Of course checking if the last transition was valid can be done in the PruneEvaluator and the ReturnableFilter but that's ugly and inefficient as I can only figure out invalid transitions after they've already been traversed. A much cleaner way would be to not traverse the invalid relationships at all. From what I've read from the documentation and code I feel this can be done with SourceSelector / ExpansionSource etc. but for the life of me I cannot figure out how. Unfortunately I also couldn't find any nice examples so I'm a bit lost here. I would greatly appreciate any pointers on how to do this with a SourceSelector or whatever is the right weapon of choice for this problem. Thanks and best regards, Georg On 30.03.2010 15:48, Tobias Ivarsson wrote: > It seems a lot of projects have outgrown the current Traverser framework. > People want to be able to do things such as visiting all relationships once > instead of all nodes once (the current framework only visit each node once > and leave out other relationships that go there). There has also been > requests for a way to select the next relationship to traverse using a > callback interface, instead of only having DEPTH_FIRST and BREADTH_FIRST to > choose from. > > To address these requests we have started a project to implement a new > traversal framework. The early prototype for this is available in my > laboratory directory in the repository: > https://svn.neo4j.org/laboratory/users/tobias/traversal/ > The state of the prototype is very early, it supports the same features as > the current Traverser framework plus being able to limit the traversal by > relationships instead of nodes or based on the path to each position. This > is already quite interesting. The part about having a callback for selecting > the next relationship is a later feature, one that will probably change the > API of the prototype a lot. For comparison the tests contain an > implementation of the old Traverser framework on top of the new Traversal > framework. The limited number of tests we've written indicate the > performance of the old framework is still slightly better than the new > framework, but analysis of the operations the different implementations make > on the graph gives me high hopes that the new framework will probably beat > the old one after we've worked on it some more. Even with the slightly lower > performance the versatility of the new framework is substantially greater. > > The prototype implements a TraversalDescription class that is used to > construct the traversal, these objects are immutable and implement a builder > pattern making it possible to create base TraversalDescription instances > that can then be reused multiple times or adapted slightly before they are > used. This leads to shorter, more readable code than the current > traverse(...)-methods on the Node interface. This is also the part of the > prototype that is most likely to change, both to accomodate for the features > that are to be added, and being revised to make it easier to work with. > > Most of the new traversal framework will live in a new > package: org.neo4j.graphdb.traversal, but there will be a few new things > introduced in org.neo4j.graphdb as well. The new traversal framework will > live side by side with the current traversal framework for a while, to ease > the transition. The old traversal framework will be deprecated and then > removed in some future version. > > > The additions we have made in the prototype are: > > * A path representation. Defined as the interface org.neo4j.graphdb.Path. A > Path object represents a path of interlinking relationships. The shortest > possible path is the path with no relationships, a single node. > > * A concept of Uniqueness. This defines how often a node or relationship can > be (re)visited. The current traversal framework implements what we have > called "node global uniqueness" in the new framework. This enforces the > restriction that a node cannot be visited more than once. Other uniqueness > kinds we introduce in the new framework are: >* Relationship global uniqueness - similar to node global unique
[Neo4j] Traversal framework suggested change
Hi all, Hopefully most of you are familiar with the traversal framework that was introduced in 1.1. It's powerful and provides for reusable traversal descriptions. It has some flaws though, and I would like to discuss one of them here. The traversal framework has this concept of pruning, which basically is an evaluation for each position, deciding whether or not to continue the traversal down this branch. The caveat here is that when you evaluate a position, you can't opt to prune before it. If you want to exclude a node based on information from that node, filtering has to be done on top of the pruning, with the same algorithm - once to stop the traversal, and once to exclude the node. So there are actually two orthogonal concepts at work here: whether to stop or not, and whether to include or not. What I'm proposing is to merge these two into one evaluator. That evaluator would return one of four values: CONTINUE_AND_INCLUDE_NODE, STOP_AND_INCLUDE_NODE, STOP_AND_EXCLUDE_NODE, or CONTINUE_AND_EXCLUDE_NODE. This would replace both the filtering and the pruning. I'm just throwing this out there to see if anyone else has had the same idea. Like / dislike? -- David Montag Neo Technology, www.neotechnology.com Cell: 650.556.4411 david.mon...@neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Traversal Framework question
Dear all, could somebody point me to more documentation on the new traversal framework (besides http://wiki.neo4j.org/content/Traversal_Framework)? Also the new Evaluator and how to use it? If we have a graph described in the pipes Co-Developers example (https://github.com/tinkerpop/pipes/wiki/Using-Pipes-to-Traverse-Graphs). Would this traversal return the co-developers? Traversal.description() .depthFirst() .relationships(RelationshipTypes.CREATED, Direction.OUTGOING) .relationships(RelationshipTypes.CREATED, Direction.INCOMING) .traverse(developer).nodes() Thanks, Alfredas ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo] A new and improved Traversal framework
Yes, one of the goals of the new traversal framework has been to make it possible to implement algorithms on top of it. You are welcome to help in that process. Mattias Persson and myself have started implementing a number of graph algorithms on top of the traversal framework. We have discussed Ford-Fulkerson, but decided that it isn't a prioritized algorithm, since the memory usage of it means that it is only useful for small graphs. If you would like to contribute to get Ford-Fulkerson and Bellman-Ford implemented that would be great! If you have questions on how to do things, that would be a suitable discussion to have here on the mailing list. Cheers, Tobias On Wed, May 19, 2010 at 3:28 AM, John Paul Lewicke wrote: > Will the new traversal framework help with implementing some new graph > algorithms? I'm most interested in Bellman-Ford and Ford-Fulkerson. > It seems like the new control over relationship selection in > traversal should help a lot. > > There's a lot of fast versions of Bellman-Ford discussed in > > http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.4171&rep=rep1&type=pdf > , and I can see how I'd implement some of them if I had the graph > entirely in memory(as in networkx for Python). I'm not sure how > different neo4j would be for implementing these. > > The instance sizes I'm interested in running these on would probably > be small enough to fit entirely in memory, but I'm really excited > about neo4j's support for persistence and transactions. > > Thanks for any input you have on this. Best, > > JP > ___ > Neo mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
2011/3/15 Craig Taverner > > > > > One question before I dive into this... Do the Traversal framework > > > involve performance improvements over the core API as shown in your > > > example? > > > > It doesn't currently, since it's using the core API. But I think the goal > > is > > to have it "drop down" one level in order to gain performance. > > > One would expect that since the traversal framework needs to keep caches of > paths already traversed, so as not to repeat itself or get into infinite > loops, it must, almost by definition, perform worse than the core API. I > assume that the difference is not great. However, if it is possible to make > the traverser perform better than the core API, I would assume that means > the core API could be optimized also. Theoretically the core API should > always be faster? > Not necessarily. The core API must always return well behaving Node/Relationship "proxies" which always must do the right thing in regards to locking and each called checks with the NodeManager before doing anyhing. If the traverser could drop down one level (to NodeImpl/RelationshipImpl) and stay there throughout the entire traversal and pop backup again only when returning results it would gain memory/performance that you couldn't gain by doing a manual traversal using the core API. Then there's the overhead that comes with traversal state and all that, but I think for not-super-small traversals there could be a gain using traversals if they could "drop down". > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
David, I have been noticing the same and came to a similar conclusion. Pruning and filtering are often used with the same logic. Maybe we could introduce a combined interface and see if that works better? /peter - From my cellphone, please excuse typos and brevity... On Nov 5, 2010 7:56 PM, "David Montag" wrote: > Hi all, > > Hopefully most of you are familiar with the traversal framework that was > introduced in 1.1. It's powerful and provides for reusable traversal > descriptions. It has some flaws though, and I would like to discuss one of > them here. > > The traversal framework has this concept of pruning, which basically is an > evaluation for each position, deciding whether or not to continue the > traversal down this branch. The caveat here is that when you evaluate a > position, you can't opt to prune before it. If you want to exclude a node > based on information from that node, filtering has to be done on top of the > pruning, with the same algorithm - once to stop the traversal, and once to > exclude the node. > > So there are actually two orthogonal concepts at work here: whether to stop > or not, and whether to include or not. What I'm proposing is to merge these > two into one evaluator. That evaluator would return one of four values: > > CONTINUE_AND_INCLUDE_NODE, > STOP_AND_INCLUDE_NODE, > STOP_AND_EXCLUDE_NODE, or > CONTINUE_AND_EXCLUDE_NODE. > > This would replace both the filtering and the pruning. I'm just throwing > this out there to see if anyone else has had the same idea. Like / dislike? > > -- > David Montag > Neo Technology, www.neotechnology.com > Cell: 650.556.4411 > david.mon...@neotechnology.com > ___ > 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
Re: [Neo4j] Traversal framework
Would you like to do a traversal where relationships of different types can be traversed? That can/should be done with one traversal, one TraversalDescription: Traversal.description() .relationships(KNOWS, Direction.OUTGOING) .relationships(LOVES) .relationships(SOMETHING, Direction.INCOMING).traverse(startNode); i.e. add more relationship types by just calling the "relationships" method multiple times. 2011/3/14 Massimo Lusetti > I'm using the Traversal framework > (http://wiki.neo4j.org/content/Traversal_Framework) and I would like > to know if I'm using it the way it has thought to be. > > I need to deeply traverse the graph going down through different > RelationshipTypes so I do a first TraversalDescription and while > iterating through its resulting Node(s) I build a second > TraversalDescription just to go deeper and then iterate through this > results... possibly I should do a third TraversalDescription for a > (third) different RelatioshipTypes. > > So my question is: Is this the correct way to use Traversal?! > > Cheers > -- > Massimo > http://meridio.blogspot.com > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
> > > One question before I dive into this... Do the Traversal framework > > involve performance improvements over the core API as shown in your > > example? > > It doesn't currently, since it's using the core API. But I think the goal > is > to have it "drop down" one level in order to gain performance. One would expect that since the traversal framework needs to keep caches of paths already traversed, so as not to repeat itself or get into infinite loops, it must, almost by definition, perform worse than the core API. I assume that the difference is not great. However, if it is possible to make the traverser perform better than the core API, I would assume that means the core API could be optimized also. Theoretically the core API should always be faster? ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
Could you describe a bit what kind of traversal you're doing? 2011/3/14 Mattias Persson > Would you like to do a traversal where relationships of different types can > be traversed? That can/should be done with one traversal, one > TraversalDescription: > > Traversal.description() > .relationships(KNOWS, Direction.OUTGOING) > .relationships(LOVES) > .relationships(SOMETHING, Direction.INCOMING).traverse(startNode); > > i.e. add more relationship types by just calling the "relationships" method > multiple times. > > > 2011/3/14 Massimo Lusetti > >> I'm using the Traversal framework >> (http://wiki.neo4j.org/content/Traversal_Framework) and I would like >> to know if I'm using it the way it has thought to be. >> >> I need to deeply traverse the graph going down through different >> RelationshipTypes so I do a first TraversalDescription and while >> iterating through its resulting Node(s) I build a second >> TraversalDescription just to go deeper and then iterate through this >> results... possibly I should do a third TraversalDescription for a >> (third) different RelatioshipTypes. >> >> So my question is: Is this the correct way to use Traversal?! >> >> Cheers >> -- >> Massimo >> http://meridio.blogspot.com >> ___ >> Neo4j mailing list >> User@lists.neo4j.org >> https://lists.neo4j.org/mailman/listinfo/user >> > > > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Traversal framework
I'm using the Traversal framework (http://wiki.neo4j.org/content/Traversal_Framework) and I would like to know if I'm using it the way it has thought to be. I need to deeply traverse the graph going down through different RelationshipTypes so I do a first TraversalDescription and while iterating through its resulting Node(s) I build a second TraversalDescription just to go deeper and then iterate through this results... possibly I should do a third TraversalDescription for a (third) different RelatioshipTypes. So my question is: Is this the correct way to use Traversal?! Cheers -- Massimo http://meridio.blogspot.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson wrote: > more advanced. If you would like to force the traversal down a very defined > path then go with the core API, like: > > for(Relationship relA : startNode.getRelationships(A)) { > Node nodeA = relA.getOtherNode(startNode); > for(Relationship relB : nodeA.getRelationships(B)) { > Node nodeB = relB.getOtherNode(nodeA); > // nodeB will be the node (3) from the above example > } > } One question before I dive into this... Do the Traversal framework involve performance improvements over the core API as shown in your example? Thanks for any clue... -- Massimo http://meridio.blogspot.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
It's a personal taste, but I'm not sure I like all those permutations in combined values. Perhaps you'll consider that the evaluator would return an object with two enums: 1. STOP / CONTINUE 2. INCLUDE / EXCLUDE This will also make it easier to extend the evaluator, so if additional state is needed to be returned, you just add another enum and don't have to change all the existing values.. Hope this makes sense. --- Yaniv On Fri, Nov 5, 2010 at 8:56 PM, David Montag wrote: > Hi all, > > Hopefully most of you are familiar with the traversal framework that was > introduced in 1.1. It's powerful and provides for reusable traversal > descriptions. It has some flaws though, and I would like to discuss one of > them here. > > The traversal framework has this concept of pruning, which basically is an > evaluation for each position, deciding whether or not to continue the > traversal down this branch. The caveat here is that when you evaluate a > position, you can't opt to prune before it. If you want to exclude a node > based on information from that node, filtering has to be done on top of the > pruning, with the same algorithm - once to stop the traversal, and once to > exclude the node. > > So there are actually two orthogonal concepts at work here: whether to stop > or not, and whether to include or not. What I'm proposing is to merge these > two into one evaluator. That evaluator would return one of four values: > > CONTINUE_AND_INCLUDE_NODE, > STOP_AND_INCLUDE_NODE, > STOP_AND_EXCLUDE_NODE, or > CONTINUE_AND_EXCLUDE_NODE. > > This would replace both the filtering and the pruning. I'm just throwing > this out there to see if anyone else has had the same idea. Like / dislike? > > -- > David Montag > Neo Technology, www.neotechnology.com > Cell: 650.556.4411 > david.mon...@neotechnology.com > ___ > 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
Re: [Neo] Traversers in the REST API
On Tue, Mar 30, 2010 at 4:20 PM, Marko Rodriguez wrote: > Hi guys, > > For what its worth > > I have yet to use the Neo4j traversal framework because it is simply is not > expressive enough. The traverser framework is like a single-relational > traverser on a multi-relational graph. You only allow or disallow certain > edge labels--not the ordered concatenation of labels. Moreover, even with > ordered labels defined, the choices that a traverser make at every element > (edge and vertex) should be predicated on general purpose > computing---predicated on the state/history of the walker, the properties of > the elements, ... anything. > Good thing we are building this on the new traversal framework that we are working on then ;) Some of the features you are mentioning that the current/previous traversal framework is lacking are supported in the new framework, and others are on the roadmap. Those features will be exposed through the REST API as well when they are ready. This will include revising the way you declare which relationships to traverse. What we would like to be able to say is: First expand relationships of type A,B or C, then of type T,U,V or W, then if the previous was T or U, the next should be X, if the previous was V or W, the next should be an arbitrary depth of Y relationships. And of course be able to have different kinds of filters in each step (on both nodes and relationships), not only selection based on relationship type. This is however not implemented yet, but as the new traversal API evolves we plan to let the REST API follow. > > > > >"relationships": [ > > { "direction": "outgoing", > > "type": "KNOWS" }, > > { "type": "LOVES" } > >], > >"max depth": 4 } > > What if I want to find all the people that love my post popular (by > eigenvector centrality) friends who also know me? Thus, simply taking > "knows" and "loves" relationships arbitrarily doesn't tell me that. What > comes into play in such situations are edge weights, ordered paths, loops, > sampling, etc. > > A general purpose traverser framework requires that you be able to define > adjacency arbitrarily. The traverser must be able to ask the engineer, at > every step (edge and vertex [1]), what do you mean by "adjacent" where > do I go next? > Exactly, depth first and breadth first are just two very basic implementations of this. The new traversal framework will eventually have support for letting the engineer provide the selector for where-to-go-next. The first use case that comes to mind for me is for implementing best first traversals, but I know that there are other things oen might want to write, and I am sure there are even more that I haven't thought of. When this is implemented we will add some means for exposing it to the users of the REST API as well, but for now our idea is to make the REST API useful with what we have, and to get the new traversal framework in front of users. > > [1] edges should be treated just as vertices---they have properties that > can be reasoned on. many times you want edges returned, not just vertices. > > Take care, > Marko. > > http://markorodriguez.com > > ___ > Neo mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
2011/3/15 Massimo Lusetti > On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson > wrote: > > > more advanced. If you would like to force the traversal down a very > defined > > path then go with the core API, like: > > > > for(Relationship relA : startNode.getRelationships(A)) { > > Node nodeA = relA.getOtherNode(startNode); > > for(Relationship relB : nodeA.getRelationships(B)) { > > Node nodeB = relB.getOtherNode(nodeA); > > // nodeB will be the node (3) from the above example > > } > > } > > One question before I dive into this... Do the Traversal framework > involve performance improvements over the core API as shown in your > example? > It doesn't currently, since it's using the core API. But I think the goal is to have it "drop down" one level in order to gain performance. > > Thanks for any clue... > -- > Massimo > http://meridio.blogspot.com > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo] A new and improved Traversal framework
Will the new traversal framework help with implementing some new graph algorithms? I'm most interested in Bellman-Ford and Ford-Fulkerson. It seems like the new control over relationship selection in traversal should help a lot. There's a lot of fast versions of Bellman-Ford discussed in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.4171&rep=rep1&type=pdf , and I can see how I'd implement some of them if I had the graph entirely in memory(as in networkx for Python). I'm not sure how different neo4j would be for implementing these. The instance sizes I'm interested in running these on would probably be small enough to fit entirely in memory, but I'm really excited about neo4j's support for persistence and transactions. Thanks for any input you have on this. Best, JP ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Framework question
On Sun, Feb 20, 2011 at 10:48 AM, Alfredas Chmieliauskas < al.fre...@gmail.com> wrote: > Dear all, > > could somebody point me to more documentation on the new traversal > framework (besides http://wiki.neo4j.org/content/Traversal_Framework)? > Also the new Evaluator and how to use it? > That page, along with the examples pages is the best there is: * http://components.neo4j.org/neo4j-examples/snapshot/traversal.html * http://wiki.neo4j.org/content/Traversal_HowTo > > If we have a graph described in the pipes Co-Developers example > (https://github.com/tinkerpop/pipes/wiki/Using-Pipes-to-Traverse-Graphs). > Would this traversal return the co-developers? > > Traversal.description() > .depthFirst() > .relationships(RelationshipTypes.CREATED, Direction.OUTGOING) > .relationships(RelationshipTypes.CREATED, Direction.INCOMING) > .traverse(developer).nodes() > No, unfortunately it wouldn't. Relationship type specifications in TraversalDescriptions are not ordered, what you have written is just a different spelling of: Traversal.description() .depthFirst() .relationships(RelationshipTypes.CREATED, Direction.BOTH) .traverse(developer).nodes() Cheers, -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
I've also thought about it, because if you think about it... pruning is just really there for performance issues and it may be possible to combine filtering/pruning somehow, yes. 2010/11/7 Yaniv Ben Yosef > It's a personal taste, but I'm not sure I like all those permutations in > combined values. > Perhaps you'll consider that the evaluator would return an object with two > enums: > > 1. STOP / CONTINUE > 2. INCLUDE / EXCLUDE > > This will also make it easier to extend the evaluator, so if additional > state is needed to be returned, you just add another enum and don't have to > change all the existing values.. > > Hope this makes sense. > --- Yaniv > > On Fri, Nov 5, 2010 at 8:56 PM, David Montag < > david.mon...@neotechnology.com > > wrote: > > > Hi all, > > > > Hopefully most of you are familiar with the traversal framework that was > > introduced in 1.1. It's powerful and provides for reusable traversal > > descriptions. It has some flaws though, and I would like to discuss one > of > > them here. > > > > The traversal framework has this concept of pruning, which basically is > an > > evaluation for each position, deciding whether or not to continue the > > traversal down this branch. The caveat here is that when you evaluate a > > position, you can't opt to prune before it. If you want to exclude a node > > based on information from that node, filtering has to be done on top of > the > > pruning, with the same algorithm - once to stop the traversal, and once > to > > exclude the node. > > > > So there are actually two orthogonal concepts at work here: whether to > stop > > or not, and whether to include or not. What I'm proposing is to merge > these > > two into one evaluator. That evaluator would return one of four values: > > > > CONTINUE_AND_INCLUDE_NODE, > > STOP_AND_INCLUDE_NODE, > > STOP_AND_EXCLUDE_NODE, or > > CONTINUE_AND_EXCLUDE_NODE. > > > > This would replace both the filtering and the pruning. I'm just throwing > > this out there to see if anyone else has had the same idea. Like / > dislike? > > > > -- > > David Montag > > Neo Technology, www.neotechnology.com > > Cell: 650.556.4411 > > david.mon...@neotechnology.com > > ___ > > 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Enhanced API rewrite
On Sat, Aug 6, 2011 at 5:51 AM, Niels Hoogeveen wrote: > ... > Every part of the database can be accessed with a traveral description. > > The standard Neo4j API only allows traversals to return Nodes given a start > Node. The Enhanced API allows traversals from any part of the graph, whether > it is a regular Vertex, an Edge or a Property (or a type thereof), to any > other part of the graph, no matter if it is a regular Vertex, an Edge or a > Property (or a type thereof). > > All that needs to be supplied are the EdgeTypes that need to be followed in > a traversal (and the regular evaluators that go with it). > > Now the big downer to this all: > > I still have to write the traversal framework, which will actually follow > the Standard Neo4j framework, but will certainly make traversals composable. > > Every Vertex is not just a Vertex, but it is also a bunch of paths. Well > not really a bunch, it is a bunch of size one, and not much of a path > either, since it only contains one path element, the Vertex itself. > > A traversal returns a bunch of paths (Iterable) and starts from a > bunch of paths (still Iterable). > > Since the output of a traversal is the same as the input of a traversal we > can now compose them. This makes it possible to write a traversal > description which states that we want to retrieve the parents of our > friends, or the neighbours of the parents of our friends, and even: the > names of the dogs of the neighbours of the parents of our friends (after > all, we can now traverse to a property). > > This can be achieved when we make traversal descriptions composable. Most > users probably don't want to manually compose traversals, they would much > rather compose traversal descriptions and let those descriptions do the > composition of the traversals. > I have to write quite complex traversal and can't do it so far. The use case quite simple, there can be several type of paths: (1) REF->GET->... (2) REF->( HAVE | IC )->... (3) IS*->REF->( HAVE | IC )->... (* - can be several IS relationships) 2 & 3 is allowed, but 1 is not. For cases 1 & 2 traversal simple to write, but as soon as adding case 3 everything crash. One of possible solution is 'state' at paths or maybe I over-engineering it =) -- Dmitriy Shabanov ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
I just spent less than two hours making this change locally and everything works and it generally feels great. Now that I've tried it out myself, this way of controlling pruning/filtering feels more awesome. I'll post some examples soon so that you can feedback :) 2010/11/10 Mattias Persson > I've also thought about it, because if you think about it... pruning is > just really there for performance issues and it may be possible to combine > filtering/pruning somehow, yes. > > 2010/11/7 Yaniv Ben Yosef > > It's a personal taste, but I'm not sure I like all those permutations in >> combined values. >> Perhaps you'll consider that the evaluator would return an object with two >> enums: >> >> 1. STOP / CONTINUE >> 2. INCLUDE / EXCLUDE >> >> This will also make it easier to extend the evaluator, so if additional >> state is needed to be returned, you just add another enum and don't have >> to >> change all the existing values.. >> >> Hope this makes sense. >> --- Yaniv >> >> On Fri, Nov 5, 2010 at 8:56 PM, David Montag < >> david.mon...@neotechnology.com >> > wrote: >> >> > Hi all, >> > >> > Hopefully most of you are familiar with the traversal framework that was >> > introduced in 1.1. It's powerful and provides for reusable traversal >> > descriptions. It has some flaws though, and I would like to discuss one >> of >> > them here. >> > >> > The traversal framework has this concept of pruning, which basically is >> an >> > evaluation for each position, deciding whether or not to continue the >> > traversal down this branch. The caveat here is that when you evaluate a >> > position, you can't opt to prune before it. If you want to exclude a >> node >> > based on information from that node, filtering has to be done on top of >> the >> > pruning, with the same algorithm - once to stop the traversal, and once >> to >> > exclude the node. >> > >> > So there are actually two orthogonal concepts at work here: whether to >> stop >> > or not, and whether to include or not. What I'm proposing is to merge >> these >> > two into one evaluator. That evaluator would return one of four values: >> > >> > CONTINUE_AND_INCLUDE_NODE, >> > STOP_AND_INCLUDE_NODE, >> > STOP_AND_EXCLUDE_NODE, or >> > CONTINUE_AND_EXCLUDE_NODE. >> > >> > This would replace both the filtering and the pruning. I'm just throwing >> > this out there to see if anyone else has had the same idea. Like / >> dislike? >> > >> > -- >> > David Montag >> > Neo Technology, www.neotechnology.com >> > Cell: 650.556.4411 >> > david.mon...@neotechnology.com >> > ___ >> > 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 >> > > > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Framework question
Thanks. On Sun, Feb 20, 2011 at 2:24 PM, Tobias Ivarsson wrote: > On Sun, Feb 20, 2011 at 10:48 AM, Alfredas Chmieliauskas < > al.fre...@gmail.com> wrote: > >> Dear all, >> >> could somebody point me to more documentation on the new traversal >> framework (besides http://wiki.neo4j.org/content/Traversal_Framework)? >> Also the new Evaluator and how to use it? >> > > That page, along with the examples pages is the best there is: > * http://components.neo4j.org/neo4j-examples/snapshot/traversal.html > * http://wiki.neo4j.org/content/Traversal_HowTo > I think that some of the examples are deprecated in the new release. > >> >> If we have a graph described in the pipes Co-Developers example >> (https://github.com/tinkerpop/pipes/wiki/Using-Pipes-to-Traverse-Graphs). >> Would this traversal return the co-developers? >> >> Traversal.description() >> .depthFirst() >> .relationships(RelationshipTypes.CREATED, Direction.OUTGOING) >> .relationships(RelationshipTypes.CREATED, Direction.INCOMING) >> .traverse(developer).nodes() >> > > No, unfortunately it wouldn't. Relationship type specifications in > TraversalDescriptions are not ordered, what you have written is just a > different spelling of: > > Traversal.description() > .depthFirst() > .relationships(RelationshipTypes.CREATED, Direction.BOTH) > .traverse(developer).nodes() > So this would be one way of finding co-developers using traversal: Traversal.description() .depthFirst() .relationships(RelationshipTypes.CREATED) .evaluator(new Evaluator() { @Override public Evaluation evaluate(Path path) { if (path.length() > 1) { // co-developer return Evaluation.INCLUDE_AND_CONTINUE; } else { // project return Evaluation.EXCLUDE_AND_CONTINUE; } } }); I can imagine a few more ways to do that. I wonder if there are any guidelines on whats the better way to do it (performance considerations). Alfredas ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Traversal Question
Hello, We are trying to use neo4j graph database in one of our applications. I think we hit a roadblock with traversal framework. It could be due to our limited knowledge of neo4j framework. Here is what we are trying to accomplish: We need to get a path(from the graph below) from the nodes A to E through relations REL1, REL2, REL3 & REL4. All we know before the traversal is: Node A, REL1, REL2, REL3, REL4..(sometime we even know the end node E) So how can we get the path A to E? I can't seem to achieve it using evaluator and/or relationships in TraversalDescription. It always returns me nodes X, P,Q since they have one my relationships(REL1, REL3). REL1REL2REL8 A -> X -> Y ---> Z REL1 REL2REL3REL4 A -> B -> C ---> D -> E REL1 REL3 REL9 REL10 A -> P -> Q ---> R -> E Nodes: A, B, C, D,E,X,Y,Z,P,Q,R, Relations: REL1REL10 Thank you for your help. John ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traverser Functions in Neo4j
2011/3/14 Massimo Lusetti > On Mon, Mar 14, 2011 at 12:39 PM, Mattias Persson > wrote: > > > Head over to http://wiki.neo4j.org/content/Traversal_Framework for more > > information. And know that the exact limitation you ran into spawned the > > creation of this new API. > > I started using this framework from day 1 since I'm new and I don't > have background from Node.traverse(). If I understand correctly this > "will be" THE traversal framework right? > > It's experimental but you use this from within Node.traverse so it's > not that experimental I guess? ... Did you suggest to use this or the > "old" API? > I think that the functionality of it is not going to change... or at least features won't be removed, only added/changed. The API can come to change quite a bit, maybe with tighter integration with the other core interfaces (Node, Path a.s.o.). So by using it you're using a stable/battle-tested traversal framework functionality-wise, but may be forced to migrate your traversal code at a later point, even though it might still be left @Deprecated so that you can decide yourself when to migrate. Nothing of what I said is decided upon so I'm speculating a bit here. In terms of stability of the API the "old" might be safer, but there are things that you just cannot do with it. So if you hit such a road block with the old API then go with new. I personally use only the new. > Plus the page you mention isn't well linked in the wiki... > I think you're right about that. When more focus is put on making a greater traversal API/engine, this will all be fixed. > > Just my 0.02Euro doubts > -- > Massimo > http://meridio.blogspot.com > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
On Mon, Mar 14, 2011 at 3:13 PM, Mattias Persson wrote: > Would you like to do a traversal where relationships of different types can > be traversed? That can/should be done with one traversal, one > TraversalDescription: > > Traversal.description() > .relationships(KNOWS, Direction.OUTGOING) > .relationships(LOVES) > .relationships(SOMETHING, Direction.INCOMING).traverse(startNode); > > i.e. add more relationship types by just calling the "relationships" method > multiple times. Cool didn't thought about that... And the order of relationships() is the order I want different Relationship should be traversed right? Going to try tomorrow... Thanks! -- Massimo http://meridio.blogspot.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] cycle detection
Hi all, I would like to detect all cycles in a traversal. I know the traversal framework has cycle avoidance built-in, but there doesn't seem to be an API for cycle detection! Has anyone already implemented a cycle detector for traversals? Thanks in advance, Wouter ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Constructing an evaluator that only takes specific nodes from a path
2011/4/7 Michael Hunger : > I think the confusing thing here is that ReturnableEvaluator talked about > including/excluding nodes > whereas when describing the Evaluations you spoke about including/excluding > paths. Oh, sorry... one major difference from the old traversal framework is that it returns nodes. The new framework returns paths leading from the start node up to that node. You still make include/exclude decisions based on the current position of the traversal, just that in the new framework you've got the full path in addition to the current node (the end node of the path). > > Which of those is correct ? > > Cheers > > Michael > > Am 07.04.2011 um 10:40 schrieb Mattias Persson: > >> 2011/4/7 Stephan Hagemann : >>> Hi guys, >>> >>> Dario and I are working together on this, so let me clarify, what we want to >>> achieve. An example query in a friend network would be: >>> >>> Retrieve a set of people P that are the direct friends of person A. P should >>> include only those friends that are also on a path between A and another >>> user B. >>> >>> We know how to find paths, but we fail at returning nodes - let alone sets >>> of nodes. >>> >>> The old ReturnableEvaluator seemed to achieve just that: "A client hook for >>> evaluating whether a specific node should be returned from a traverser.", >>> but that is deprecated in the current milestone release. We're unable to >>> find the equivalent functionality with the new Traversal framework. >> >> ReturnableEvaluator is like controlling the INCLUDE/EXCLUDE part of an >> evaluation >> StopEvaluator is like controlling the CONTINUE/PRUNE part of an evaluation >> >> The @Deprecated TraversalDescription#prune and #filter are also a >> direct mapping of StopEvaluator and ReturnableEvaluator respectively. >> Evaluator replaces those and combines them into one concept where you >> can express the same semantics. >> >>> >>> Thanks >>> Stephan >>> >>> >>> >>> On Thu, Apr 7, 2011 at 09:35, Mattias Persson >>> wrote: >>> >>>> Sory, I meant >>>> >>>> INCLUDE_AND_PRUNE >>>> the path will be included in the result set, but the traversal >>>> won't go further down that path, but will continue down other paths >>>> that haven't been pruned >>>> >>>> >>>> >>>> -- >>>> Mattias Persson, [matt...@neotechnology.com] >>>> Hacker, Neo Technology >>>> www.neotechnology.com >>>> ___ >>>> 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 >>> >> >> >> >> -- >> Mattias Persson, [matt...@neotechnology.com] >> Hacker, Neo Technology >> www.neotechnology.com >> ___ >> 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traverse API
Hi Ido, You make excellent points. The traversal API that you're referring to (Node.traverse) is however considered a legacy, stable API. What you are looking for is probably the newer, unstable API of the new traversal framework. You can read more about it here: http://wiki.neo4j.org/content/Traversal_Framework Using the traversal framework, you would typically use an Evaluator to decide whether or not to continue along a relationship. Calling path.lastRelationship() in the evaluator gives you the last relationship in the path so far. Please keep us posted on your progress, and don't hesitate to ask questions. It is after all an unstable API, and any feedback is appreciated. Let us know if you want more examples of usage. David On Wed, Jan 5, 2011 at 2:13 PM, Ido Ran wrote: > Hi, > I have a question about the traversal API: The API use ReturnableEvaluator > to decide if a node should be selected by the traverser which leave place > for developer to enter any arbitrary rules of which nodes to select. On the > other hand the implementation return from Node allow to specify only > RelationshipType and Direction to decide on which link to traverse. > > My question is why not have TraversableLink interface which will have > boolean method isTraversable (or something like that) that will get the > TraversePosition and Link and will decide if the link should be traversed. > This way things like the number of links already traversed or properties of > the link can be take into account. > > What do you think? > > Ido > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- David Montag Neo Technology, www.neotechnology.com Cell: 650.556.4411 david.mon...@neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Any method to count nodes and relationships in a traversal framework
Respected, I would to know that is there any method to count the number of nodes and relationships traversed by the traversal framework. Like path.length() ---> which gives the depth of the tree. So as like that method is there any direct one? For example, If a tree consist of several nodes and several relations. And I want to traverse from a particular node to the end of the tree and the result has only contains certain period of nodes like if the tree traverse 1000 nodes and 1 relationships from a particular node and I want only the result which contains from node 35 to node 70. So is there any direct method to get the count list of nodes and relationships. Thanks & Regards, G. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Constructing an evaluator that only takes specific nodes from a path
Thanks for clearing that up! Then I can come back to my initial comment. If the Evaluator returns paths and we are looking for nodes (sets of nodes to be specific), we have no easy mechanism that will ensure we do not return duplicate nodes (because the paths they are extracted from are not duplicates). Again, with the example: Retrieve a set of people P that are the direct friends of person A. P should include only those friends that are also on a path between A and another user B. I have attach an image that highlights this problem. As you can see from the attached image, querying for the paths that satisfy this proposition will lead to a duplication of node P in the result. If we deduplicate after the traversal, we can't stop the traversal when we have found the maximum number of nodes we wanted to return. That is... unless we specify more complex include/exclude/continue/prune rules in an Evaluator that takes into account the nodes that it has internally stored as returnables. Is that the way to go? On Thu, Apr 7, 2011 at 10:48, Mattias Persson wrote: > 2011/4/7 Michael Hunger : > > I think the confusing thing here is that ReturnableEvaluator talked about > including/excluding nodes > > whereas when describing the Evaluations you spoke about > including/excluding paths. > > Oh, sorry... one major difference from the old traversal framework is > that it returns nodes. The new framework returns paths leading from > the start node up to that node. You still make include/exclude > decisions based on the current position of the traversal, just that in > the new framework you've got the full path in addition to the current > node (the end node of the path). > > > > Which of those is correct ? > > > > Cheers > > > > Michael > > > > Am 07.04.2011 um 10:40 schrieb Mattias Persson: > > > >> 2011/4/7 Stephan Hagemann : > >>> Hi guys, > >>> > >>> Dario and I are working together on this, so let me clarify, what we > want to > >>> achieve. An example query in a friend network would be: > >>> > >>> Retrieve a set of people P that are the direct friends of person A. P > should > >>> include only those friends that are also on a path between A and > another > >>> user B. > >>> > >>> We know how to find paths, but we fail at returning nodes - let alone > sets > >>> of nodes. > >>> > >>> The old ReturnableEvaluator seemed to achieve just that: "A client hook > for > >>> evaluating whether a specific node should be returned from a > traverser.", > >>> but that is deprecated in the current milestone release. We're unable > to > >>> find the equivalent functionality with the new Traversal framework. > >> > >> ReturnableEvaluator is like controlling the INCLUDE/EXCLUDE part of an > >> evaluation > >> StopEvaluator is like controlling the CONTINUE/PRUNE part of an > evaluation > >> > >> The @Deprecated TraversalDescription#prune and #filter are also a > >> direct mapping of StopEvaluator and ReturnableEvaluator respectively. > >> Evaluator replaces those and combines them into one concept where you > >> can express the same semantics. > >> > >>> > >>> Thanks > >>> Stephan > >>> > >>> > >>> > >>> On Thu, Apr 7, 2011 at 09:35, Mattias Persson < > matt...@neotechnology.com>wrote: > >>> > >>>> Sory, I meant > >>>> > >>>> INCLUDE_AND_PRUNE > >>>>the path will be included in the result set, but the traversal > >>>>won't go further down that path, but will continue down other paths > >>>> that haven't been pruned > >>>> > >>>> > >>>> > >>>> -- > >>>> Mattias Persson, [matt...@neotechnology.com] > >>>> Hacker, Neo Technology > >>>> www.neotechnology.com > >>>> ___ > >>>> 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 > >>> > >> > >> > >> > >> -- > >> Mattias Persson, [matt...@neotechnology.com] > >> Hacker, Neo Technology > >> www.neotechnology.com > >> ___ > >> 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 > > > > > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > ___ > 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
Re: [Neo4j] Traversal Question
Thanks Peter. That was very useful. I am trying to get the path A ->B->C->D-> E in the below graph, with the following inputs Start Node: A, Relationships: REL1, REL4, REL2 (that is, order is not known) Relationship Property: relProp= "abc" in REL3 I was not able to define an evaluator which takes the combination of relationship types(without regard to order) and relationship properties to return the desired path. Can it be achievable in the current traversal framework? REL1 REL2REL8 A -> X -> Y ---> Z REL1REL2 REL3REL4 A -> B -> C ---> D -> E REL1REL3 REL9 REL10 A -> P -> Q ---> R -> E As always, appreciate your guidance. === John, if the order of the relationships doesn't matter, you could do something like this with the Traversal API (holding an ordered Path to test against in your Evaluator): public void testPath() { final ArrayList orderedPath = new ArrayList(); orderedPath.add( withName( "REL1" ) ); orderedPath.add( withName( "REL2" ) ); orderedPath.add( withName( "REL3" ) ); orderedPath.add( withName( "REL4" ) ); TraversalDescription td = Traversal.description().evaluator( new Evaluator() { public Evaluation evaluate( Path path ) { if ( path.length() == 0 ) { return Evaluation.EXCLUDE_AND_CONTINUE; } String currentName= path.lastRelationship().getType().name(); String relationshipType = orderedPath.get( path.length() - 1 ).name(); if ( path.length() == orderedPath.size() ) { if ( currentName.equals( relationshipType ) ) { return Evaluation.INCLUDE_AND_PRUNE; } else { return Evaluation.EXCLUDE_AND_PRUNE; } } else { if ( currentName.equals( relationshipType ) ) { return Evaluation.EXCLUDE_AND_CONTINUE; } else { return Evaluation.EXCLUDE_AND_PRUNE; } } } } ); Traverser t = td.traverse( getNodeWithName( "A" ) ); for ( Path path : t ) { System.out.println(path); } } I am attaching the classes for your reference, so you have full code. Also, you could try JRuby, Gremlin or other along the same lines. But this is a basic Java example in creating an ordered Path information and checking against it during the traversal. You can add in more stuff of course ... Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Tue, Jan 25, 2011 at 10:59 PM, John Howard wrote: > Hello, > > We are trying to use neo4j graph database in one of our applications. > I think we hit a roadblock with traversal framework. It could be due to our > limited knowledge of neo4j framework. > > Here is what we are trying to accomplish: > We need to get a path(from the graph below) from the nodes A to E through > relations REL1, REL2, REL3 & REL4. > All we know before the traversal is: Node A, REL1, REL2, REL3, > REL4..(sometime we even know the end node E) > So how can we get the path A to E? I can't seem to achieve it using > evaluator and/or relationships in TraversalDescription. It always returns me > nodes X, P,Q since they have one my relationships(REL1, REL3). > > > REL1REL2REL8 > A -> X -> Y ---> Z > > REL1 REL2REL3REL4 > A -> B -> C ---> D -> E > > REL1 REL3 REL9 REL10 > A -> P -> Q --->
Re: [Neo4j] Traversal framework
On Mon, Mar 14, 2011 at 3:17 PM, Mattias Persson wrote: > Could you describe a bit what kind of traversal you're doing? I got nodes that describe a base of our organization, each nodes has relationships with nodes that describe the network used in the base, each network nodes has relationships with one or more IP addressed used in the networks. The IP address nodes has relations with users nodes who have used the PC with the particular IP address and each users Nodes have relationships which Nodes identifing actions taken, domains visited, decision made etc... So I got this rel types: NETWORK, HAS_TAKEN, HAS_VISITED, HAS_TAKEN_FROM, HAS_VISITED_FROM etc... The Traversal should start from the base Node down to each user action, going through networks, IP, domains, etc... Am I have been clear enough? Cheers -- Massimo http://meridio.blogspot.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversals in REST Service vs. Traversals in neo4j.py
On 2 June 2010 16:21, Mattias Persson wrote: > I don't think the python bindings (or any other binding) has caught up > to the new traversal framework. Uniqueness is all about when to visit > a node and when not to. If the uniqueness would be NODE_GLOBAL a node > wouldn't be visited more than once in a traversal. NODE_PATH means > that a node won't be visited again for the current path (the path from > the start node to where ever the traverser is at the moment) if that > node is in the current path. It might as well be visited again in > another path. > > Also see the javadoc of Uniqueness at > > http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/Uniqueness.html > Great! Thank you so much. -- Javier de la Rosa ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
Hi, > Now that looks interesting! But why limit it to a pipe and not merge > it with the Graph Matching component, so we can find non-linear > subgraphs with the same API? Or did I misunderstand the concept? Graph matching can be seen as a subset of graph traversal. Meaning, any graph match can be represented as a graph traversal, but not all graph traversals can be represented as a graph match. You might be interested in Pipes and Gremlin as a concise way to express graph traversals and as such, express arbitrary graph matching: http://pipes.tinkerpop.com http://gremlin.tinkerpop.com With Gremlin you can do graph matching that includes operations such as union, intersect, deduplicate, math ops, equals, etc. In short, you can conveniently apply any computable criteria to your definition of a "graph pattern." For those that care: 1. Unlike languages like SPARQL (1.0), you can express recursion and thus, regular paths. 2. Unlike regular path languages, you are provided memory in your traversal and thus, can express context-free paths (there is a notion of history). 3. Unlike context-free path languages, you can brach, have arbitrary memory and thus, can compute Turing complete paths. Take care, Marko. http://markorodriguez.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
Of course, You can have a count outside your traversal description that for instance and Evaluator is updating since it is called for all traversed nodes. This is not thread safe but I think it will give you the data you want? Sent from my phone. On Apr 13, 2011 12:32 PM, "Stephan Hagemann" < stephan.hagem...@googlemail.com> wrote: > Hi Gunda, > > I believe you are asking fir the same thing I asked for a couple of days > ago. Check this thread: > > http://lists.neo4j.org/pipermail/user/2011-April/007932.html > > As the discussion shows, this feature is currently not available but > probably interesting in a lot of settings. At least for you and me ;) > > Regards, > Stephan > > > On Wed, Apr 13, 2011 at 11:23, bhargav gunda wrote: > >> Respected, >> >> I would to know that is there any method to count the number of nodes and >> relationships traversed by the traversal framework. >> Like path.length() ---> which gives the depth of the tree. So as like that >> method is there any direct one? >> >> For example, >> >> If a tree consist of several nodes and several relations. And I want to >> traverse from a particular node to the end of the tree and the result has >> only contains certain period of nodes like if the tree traverse 1000 nodes >> and 1 relationships from a particular node and I want only the result >> which contains from node 35 to node 70. >> So is there any direct method to get the count list of nodes and >> relationships. >> >> Thanks & Regards, >> G. >> ___ >> 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] sharding Neo4j graph database
Hi, We looking into the options for sharding Neo4j. Using Gizzard (which is a sharding framework from Twitter) seemed to be one of the possibilities. I posting here so that everyone can evaluate this possibility and offer suggestions. Did anyone else try sharding of Neo4j? I have the following questions and possible solutions. The problem after sharding would be representation of vertices which are outside of the a shard and querying (traversal) on top of the sharded graph. Eg: Let there be a straight line graph between 3 vertices (A --> B --> C) and vertices A, B are in shard-1 and vertex C in shard-2. Then in shard-1, the out-edge of B should point to something but the actual vertex C's info would be in shard-2. In shard-1, B can point to an alias of C and rest of C's info (i.e. property & relationship info) would be in shard-2. Further we can associate a property with each vertex which indicates whether a vertex is in local shard or foreign shard. For traversal over sharded graph, I think we can extend the Neo4j's traversal so that it handle's this case (look into another shard where vertex C is and continue the traversal). What are your suggestions on this? Thank you. Regards, Raghava. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
2010/11/18 Mattias Persson > I just spent less than two hours making this change locally and everything > works and it generally feels great. Now that I've tried it out myself, this > way of controlling pruning/filtering feels more awesome. I'll post some > examples soon so that you can feedback :) > > Well, examples are maybe unecessary. class Evaluator Evaluation evaluate(Path path); enum Evaluation INCLUDE_AND_CONTINUE INCLUDE_AND_STOP SKIP_AND_CONTINUE SKIP_AND_STOP class TraversalDescription +evaluator(Evaluator) -prune(PruneEvaluator) -filter(Predicate) Also I've added lots of useful evaluators in an "Evaluators" class, but maybe those should reside in Traversal class instead, however I think Traversal class is a little bloated as it is now. There's the decision whether or not this thing could go into 1.2 or not... For one thing it breaks the API, but then again the PruneEvaluator/Predicate (filter) can still be there, mimicing Evaluators in the background. Because a PruneEvaluator can be seen as an Evaluator which instead of true/false returns INCLUDE_AND_CONTINUE/INCLUDE_AND_STOP and a filter can be seen as an Evaluator which instead of true/false returns INCLUDE_AND_CONTINUE/SKIP_AND_CONTINUE. And you can have multiple evaluators just as you can with pruners/filters. This API seems more flexible and this will, in most cases, yield better traversal performance as well. -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Fetching Nodes from Graph Database(which was created earlier)
Karthik, You can index the nodes you are interested in as start and/or end-nodes of your traversal and then retrieve them via the index. // to add them gDB.index().forNodes("indexName").add(node,"key","value"); nodeIndex.get("key","value") returns an IndexHits that you can iterate over or use getSingle() to retrieve a single matching node. See also: http://wiki.neo4j.org/content/Index_Framework Other ways of accessing nodes in the db are getById() or traversal using the traversal framework or manual traversal starting from the reference node (gDB.getReferenceNode()) that you should connect your graph to. Cheers Michael Am 02.02.2011 um 13:34 schrieb karthik aithal: > Hi, > > I am biginner to Neo4j and eager to learn more about it. I am aware > of creating new Graph database with 1k to 10k nodes and relationship and was > successfully traverse to specific nodes. But currently I am facing difficult > to get node from existing graph DB and traverse to specific node in that DB. > > For creating new Graph DB I am using: > > GraphDatabaseService gDB = new EmbeddedGraphDatabase("target/db"); > > So, if I have 10k nodes(with relationship) in Path: "/NeoDB/store/db" then > how can I retrive nodes from this DB? > > Thanks for your help in advance, > > Karthik > ___ > 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
Re: [Neo4j] Traversal framework
I like the pipes idea. What I would like to see is nested traversers. The pipe example below seems to imply single hops at each step, but it would be nicer to allow each step to traverse until it reached a certain criteria, at which point a different traversal would take over. In the old and current API's it seems to do this you need to create a traversal, iterate over it, and create a new traversal inside the loop. We created a Ruby DSL for nested traversals a year or so ago that looks a bit like: chart 'Distribution analysis' do self.domain_axis='categories' self.range_axis='values' select 'First dataset',:categories=>'name',:values=>'value' do from { from { traverse(:outgoing,:CHILD,1) where {type=='gis' and name=='network.csv'} } traverse(:outgoing,:AGGREGATION,1) where {name=='azimuth' and get_property(:select)=='max' and distribute=='auto'} } traverse(:outgoing,:CHILD,:all) end end This is quite a complex example, but the key points are the from method which defines where to start a traversal, and the traverse method which defines the traversal itself, with the where method which is like the old ReturnableEvaluator. Will the new pipes provide something like this? On Tue, Mar 15, 2011 at 9:19 AM, Massimo Lusetti wrote: > On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson > wrote: > > > I'm positive that some nice API will enter the kernel at some point, > f.ex. > > I'm experimenting with an API like this: > > > > for(Node node : > > > PipeBuilder.fromNode(startNode).into(otherNode(A)).into(otherNode(B)).nodes()) > > { > > // node will be (3) from the example above > > } > > > > > > I hope I didn't confuse you with all this :) > > Nope, the opposite. Thanks for the clarification and that kind of API > would be a killer feature IMHO. > > It will be even more pleasant to work with neo4j... > > Cheers > -- > Massimo > http://meridio.blogspot.com > ___ > 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
Re: [Neo4j] Traversals in REST Service vs. Traversals in neo4j.py
I don't think the python bindings (or any other binding) has caught up to the new traversal framework. Uniqueness is all about when to visit a node and when not to. If the uniqueness would be NODE_GLOBAL a node wouldn't be visited more than once in a traversal. NODE_PATH means that a node won't be visited again for the current path (the path from the start node to where ever the traverser is at the moment) if that node is in the current path. It might as well be visited again in another path. Also see the javadoc of Uniqueness at http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/Uniqueness.html 2010/6/2 Javier de la Rosa : > And one more question, what's the meaning of "uniqueness": "node path" > parameter? What values does it support? Which is the equivalent en neo4j.py? > > > -- > Javier de la Rosa > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Question
John, In your example, are there any constraints on that of the four relationship types, every one need to be exactly one time in the path, or is it just any of these? Instead of using a List like in the previous example, you can the use a Map to tick the visited relationship types and check the property when you get to REL3? I can do it for you in neo4j-examples again if you give me some more details :) Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Sun, Feb 13, 2011 at 10:16 AM, John Howard wrote: > Thanks Peter. That was very useful. > > I am trying to get the path A ->B->C->D-> E in the below graph, with the > following inputs > Start Node: A, > Relationships: REL1, REL4, REL2 (that is, order is not known) > Relationship Property: relProp= "abc" in REL3 > > I was not able to define an evaluator which takes the combination of > relationship types(without regard to order) and relationship properties to > return the desired path. > Can it be achievable in the current traversal framework? > > REL1 REL2 REL8 > A -> X -> Y ---> Z > > REL1 REL2 REL3 REL4 > A -> B -> C ---> D -> E > > REL1 REL3 REL9 REL10 > A -> P -> Q ---> R -> E > > > As always, appreciate your guidance. > > > > === > John, > if the order of the relationships doesn't matter, you could do > something like this with the Traversal API (holding an ordered Path to > test against in your Evaluator): > > public void testPath() > { > final ArrayList orderedPath = new > ArrayList(); > orderedPath.add( withName( "REL1" ) ); > orderedPath.add( withName( "REL2" ) ); > orderedPath.add( withName( "REL3" ) ); > orderedPath.add( withName( "REL4" ) ); > > TraversalDescription td = Traversal.description().evaluator( > new Evaluator() > { > > public Evaluation evaluate( Path path ) > { > if ( path.length() == 0 ) > { > return Evaluation.EXCLUDE_AND_CONTINUE; > } > String currentName= > path.lastRelationship().getType().name(); > String relationshipType = orderedPath.get( > path.length() - 1 ).name(); > if ( path.length() == orderedPath.size() ) > { > if ( currentName.equals( > relationshipType ) ) > { > return Evaluation.INCLUDE_AND_PRUNE; > } > else > { > return Evaluation.EXCLUDE_AND_PRUNE; > } > } > else > { > if ( currentName.equals( > relationshipType ) ) > { > return Evaluation.EXCLUDE_AND_CONTINUE; > } > else > { > return Evaluation.EXCLUDE_AND_PRUNE; > } > } > } > } ); > Traverser t = td.traverse( getNodeWithName( "A" ) ); > for ( Path path : t ) > { > System.out.println(path); > } > > } > > I am attaching the classes for your reference, so you have full code. > > Also, you could try JRuby, Gremlin or other along the same lines. But > this is a basic Java example in creating an ordered Path information > and checking against it during the traversal. You can add in more > stuff of course ... > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.
Re: [Neo4j] cycle detection
In case you are interested, I implemented cycle detection by using Tarjan algorithm, not the traversal. The code is visible in the Italian Wikipedia, I hope it's intelligible although the language. http://it.wikipedia.org/wiki/Algoritmo_di_Tarjan_per_le_componenti_fortemente_connesse#Implementazione_in_Java Hi Jacopo Farina Il giorno ven, 25/03/2011 alle 13.51 +0100, Mattias Persson ha scritto: > I think you could implement this using RELATIONSHIP_GLOBAL uniqueness, like > (from the top of my head): > > Traversal.description().uniqueness( Uniqueness.RELATIONSHIP_GLOBAL ) > .evaluator(new Evaluator() { > public Evaluation(Path path) { > return path.length() > 0 && endNodeOccursPreviouslyInPath( > path ) ? > Evaluation.INCLUDE_AND_CONTINUE : > Evaluation.EXCLUDE_AND_CONTINUE; > } > > private boolean endNodeOccursPreviouslyInPath(Path path) { > Node endNode = path.endNode(); > int counter = 0; > for ( Node node : path.nodes() ) { > if ( counter++ < path.length() && node.equals( endNode ) ) > return true; > } > return false; > } > } ).traverse(...); > > This should (if it even compiles :) ) return paths containing cycles. > Something like this you're looking for? > > 2011/3/25 Wouter De Borger > > > Hi all, > > > > I would like to detect all cycles in a traversal. > > > > I know the traversal framework has cycle avoidance built-in, but there > > doesn't seem to be an API for cycle detection! > > > > Has anyone already implemented a cycle detector for traversals? > > > > Thanks in advance, > > Wouter > > ___ > > 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
Re: [Neo] how to get an specific node
Hi, You could implement your own returnable evaluator only to return "best match" or "complete match" nodes. If not I would pick the nested loop one since code is cleaner or write a combination of traverser + for loop in one of the evaluators. -Johan On Sat, Aug 9, 2008 at 2:28 PM, Anders Nawroth <[EMAIL PROTECTED]> wrote: > Hi! > > Johan Svensson skrev: >> >> One way would be to do a traversal from the "word-node" with the least >> number for relationships. > > OK, I implemented this. But I *do* have to iterate over the relationships to > get the count? > > At the moment I only want the search to return one best match: either the > first that matches all search words or the one matching as many words as > possible (this alternative is a bit simplistic as I start the traversal from > one point only). > > I attached some screenshots from my current IMDB node space. > > I tried two different ways performing the traversal: > 1. traverser framework > 2. nested loops > Both do have their pros and cons, I think. > > Any suggestions for improvements on the code? > Wich one would you choose?! > > /anders ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Constructing an evaluator that only takes specific nodes from a path
2011/4/7 Stephan Hagemann : > Thanks for clearing that up! > > Then I can come back to my initial comment. If the Evaluator returns paths > and we are looking for nodes (sets of nodes to be specific), we have no easy > mechanism that will ensure we do not return duplicate nodes (because the > paths they are extracted from are not duplicates). Again, with the example: > > Retrieve a set of people P that are the direct friends of person A. P should > include only those friends that are also on a path between A and another > user B. > > I have attach an image that highlights this problem. > > As you can see from the attached image, querying for the paths that satisfy > this proposition will lead to a duplication of node P in the result. If we > deduplicate after the traversal, we can't stop the traversal when we have > found the maximum number of nodes we wanted to return. Oh, so if any node in the path has been returned in any other path before if (except the start node) then exclude it? That's the first time I've heard that requirement. Love the fact that you sent a picture, guys :) So what about: int hitCount = 0; for ( Path path : ...traverse(...) ) { if ( unique( path ) ) { if ( hitCount++ >= 50 ) break; // handle the path } } ...or wrap the Iterable from traverse in: new FilteringIterable(...traverse(...), new Predicate() { public boolean accept( Path path ) { return unique( path ); } } ); and only iterate max 50 of those. Write the unique() method however you'd like... maybe just with a Set with all the nodes except the start/end nodes and add all those nodes from each path and if that set had any of those nodes then don't consider it unique. > > That is... unless we specify more complex include/exclude/continue/prune > rules in an Evaluator that takes into account the nodes that it has > internally stored as returnables. Is that the way to go? > > > On Thu, Apr 7, 2011 at 10:48, Mattias Persson > wrote: > >> 2011/4/7 Michael Hunger : >> > I think the confusing thing here is that ReturnableEvaluator talked about >> including/excluding nodes >> > whereas when describing the Evaluations you spoke about >> including/excluding paths. >> >> Oh, sorry... one major difference from the old traversal framework is >> that it returns nodes. The new framework returns paths leading from >> the start node up to that node. You still make include/exclude >> decisions based on the current position of the traversal, just that in >> the new framework you've got the full path in addition to the current >> node (the end node of the path). >> > >> > Which of those is correct ? >> > >> > Cheers >> > >> > Michael >> > >> > Am 07.04.2011 um 10:40 schrieb Mattias Persson: >> > >> >> 2011/4/7 Stephan Hagemann : >> >>> Hi guys, >> >>> >> >>> Dario and I are working together on this, so let me clarify, what we >> want to >> >>> achieve. An example query in a friend network would be: >> >>> >> >>> Retrieve a set of people P that are the direct friends of person A. P >> should >> >>> include only those friends that are also on a path between A and >> another >> >>> user B. >> >>> >> >>> We know how to find paths, but we fail at returning nodes - let alone >> sets >> >>> of nodes. >> >>> >> >>> The old ReturnableEvaluator seemed to achieve just that: "A client hook >> for >> >>> evaluating whether a specific node should be returned from a >> traverser.", >> >>> but that is deprecated in the current milestone release. We're unable >> to >> >>> find the equivalent functionality with the new Traversal framework. >> >> >> >> ReturnableEvaluator is like controlling the INCLUDE/EXCLUDE part of an >> >> evaluation >> >> StopEvaluator is like controlling the CONTINUE/PRUNE part of an >> evaluation >> >> >> >> The @Deprecated TraversalDescription#prune and #filter are also a >> >> direct mapping of StopEvaluator and ReturnableEvaluator respectively. >> >> Evaluator replaces those and combines them into one concept where you >> >> can express the same semantics. >> >> >> >>> >> >>> Thanks >> >>> Stephan >> >>> >> >>> >> >>> >> >>> On Thu, A
Re: [Neo] Traversal suggestions
On Fri, Oct 24, 2008 at 4:49 PM, Jonny Wray <[EMAIL PROTECTED]> wrote: > Hi Tobias, > I'm not sure how specifying a specific collection of relationships in a > traversal would achieve the same effect. To be more explicit, I have the > case where I would like to traverse a relationship of a specific type, but > that relationship has some concept of evidence as a property. One user > maybe > believe that evidence, and so would want to traverse the relationship, > whereas another user might not believe it so wouldn't want to. > > I'm not sure how this could be achieved currently other than by filtering > the result of the traversal after the effect. If indeed that's the most > efficient way then so be it. > Usually when you define your data model you define a set of relationship types that your application is going to use. The Guidelines [ http://wiki.neo4j.org/content/Getting_Started_Guide] suggest using an enum for this, in which case it is very simple to get an array with all the types and pass that to the traverse-method. If relationship types are created dynamically it might be more complicated. There is a method on the EmbeddedNeo class called getRelationshipTypes(), it's currently deprecated, but we have been discussing undeprecating it and exposing in though the NeoService interface. This will (probably) happen in the next release. This might be a way that you could use to create an array of all the relationship types in your system and pass to the traverse-method. One thing to note is that the main useage for relationship types is to aid traversal structure [ http://lists.neo4j.org/pipermail/user/2008-October/000848.html]. If you don't use the types for your traversals of the graph in your system it might be better to only use one and the same RelationshipType for all relationships and then filter the traversal based on other properties as you suggest. Perhaps even have something named Type (or something similar) as a property on your relationship if you have a system where users are allowed to define ther own types for relationships (but where these are insignificant for traversal). The problem with this approach is, as you say, that it's not supported by the traversal API. I agree with you that the traversal API is far from ideal in every case. On the bright side it is very possible for you to define your own traversal sytem using the getRelationship(...)-methods of Node. Doing this will not slow down your system notably (given that you don't define complex algorithms in your traversals). It is sertenly very likely to be faster than filtering the result of the traversal afterwards. If you do define your own traversal system I would be very interested at looking at your API (if I may) to see if there is some ideas that can be used to improve the traversal API of Neo4j. Or if you just have suggestions on what you think the traverser framework should be enhanced with I will gladly accept those as well. I hope this shines at least some light on this issue. Good luck, -- Tobias Ivarsson <[EMAIL PROTECTED]> Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
Hi Gunda, I believe you are asking fir the same thing I asked for a couple of days ago. Check this thread: http://lists.neo4j.org/pipermail/user/2011-April/007932.html As the discussion shows, this feature is currently not available but probably interesting in a lot of settings. At least for you and me ;) Regards, Stephan On Wed, Apr 13, 2011 at 11:23, bhargav gunda wrote: > Respected, > > I would to know that is there any method to count the number of nodes and > relationships traversed by the traversal framework. > Like path.length() ---> which gives the depth of the tree. So as like that > method is there any direct one? > > For example, > > If a tree consist of several nodes and several relations. And I want to > traverse from a particular node to the end of the tree and the result has > only contains certain period of nodes like if the tree traverse 1000 nodes > and 1 relationships from a particular node and I want only the result > which contains from node 35 to node 70. > So is there any direct method to get the count list of nodes and > relationships. > > Thanks & Regards, > G. > ___ > 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
Re: [Neo4j] Getting sorted results from a traversal
Hi Pere, To sort you need to have all your results. Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j traverser framework), results = [] g.v(1).out('friend').out('likes') >> results // what my friends like results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by name In short, once you have the result of your traversal, you can then apply a comparator to the Collection to sort it as you please --- its just Java comparators. See ya, Marko. http://markorodriguez.com On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > HI! > I am on the situation of having to traverse neo4j, and then expect the > resultset returned to be ordered in a certain order. I've been researching a > bit over the traversal API, but I did not find anything related to that. I > really will appreciate any tip on that!! > > BTW > I expect to be possible right?, as we have in relational the ordering, > or on redis, etc... > > /purbon > > -- > Pere Urbon-Bayes > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > ___ > 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
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
2011/4/13 Peter Neubauer : > Of course, > You can have a count outside your traversal description that for instance > and Evaluator is updating since it is called for all traversed nodes. This > is not thread safe but I think it will give you the data you want? > Traversals are single-threaded btw. so there is no "thread safety" issues with this solution. Make sure this evaluator gets added first because evaluators might not be called if there are others in front of it saying "no, no, no" (EXCLUDE_AND_PRUNE that is). > Sent from my phone. > On Apr 13, 2011 12:32 PM, "Stephan Hagemann" < > stephan.hagem...@googlemail.com> wrote: >> Hi Gunda, >> >> I believe you are asking fir the same thing I asked for a couple of days >> ago. Check this thread: >> >> http://lists.neo4j.org/pipermail/user/2011-April/007932.html >> >> As the discussion shows, this feature is currently not available but >> probably interesting in a lot of settings. At least for you and me ;) >> >> Regards, >> Stephan >> >> >> On Wed, Apr 13, 2011 at 11:23, bhargav gunda > wrote: >> >>> Respected, >>> >>> I would to know that is there any method to count the number of nodes and >>> relationships traversed by the traversal framework. >>> Like path.length() ---> which gives the depth of the tree. So as like > that >>> method is there any direct one? >>> >>> For example, >>> >>> If a tree consist of several nodes and several relations. And I want to >>> traverse from a particular node to the end of the tree and the result has >>> only contains certain period of nodes like if the tree traverse 1000 > nodes >>> and 1 relationships from a particular node and I want only the result >>> which contains from node 35 to node 70. >>> So is there any direct method to get the count list of nodes and >>> relationships. >>> >>> Thanks & Regards, >>> G. >>> ___ >>> 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
Yeah I know that but I want it in the traverse function itself. Based on the result again I want to do one more function. So i am trying to find in the traverse function. Thanks & Regards, G. On Wed, Apr 13, 2011 at 3:47 PM, Peter Neubauer wrote: > Of course, > You can have a count outside your traversal description that for instance > and Evaluator is updating since it is called for all traversed nodes. This > is not thread safe but I think it will give you the data you want? > > Sent from my phone. > On Apr 13, 2011 12:32 PM, "Stephan Hagemann" < > stephan.hagem...@googlemail.com> wrote: > > Hi Gunda, > > > > I believe you are asking fir the same thing I asked for a couple of days > > ago. Check this thread: > > > > http://lists.neo4j.org/pipermail/user/2011-April/007932.html > > > > As the discussion shows, this feature is currently not available but > > probably interesting in a lot of settings. At least for you and me ;) > > > > Regards, > > Stephan > > > > > > On Wed, Apr 13, 2011 at 11:23, bhargav gunda > wrote: > > > >> Respected, > >> > >> I would to know that is there any method to count the number of nodes > and > >> relationships traversed by the traversal framework. > >> Like path.length() ---> which gives the depth of the tree. So as like > that > >> method is there any direct one? > >> > >> For example, > >> > >> If a tree consist of several nodes and several relations. And I want to > >> traverse from a particular node to the end of the tree and the result > has > >> only contains certain period of nodes like if the tree traverse 1000 > nodes > >> and 1 relationships from a particular node and I want only the > result > >> which contains from node 35 to node 70. > >> So is there any direct method to get the count list of nodes and > >> relationships. > >> > >> Thanks & Regards, > >> G. > >> ___ > >> 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 mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Traversal RelationshipExpander
Im enjoying Neo4J so far. The new Traversal framework has a lot of potential. However, Id like to propose an extension to the RelationshipExpander interface or have someone tell me of another way to accomplish a task. Here is an outline of the basics of my network: Producer contributes_to => Asset <= subscribes_to Consumer (various properties on each type of Node and Relationship) A Consumer may subscribe to an Asset generically or the subscribes_to relationship may have a property, producers, which is an array of ids (long) of Producer nodes that specifically produce assets for that Consumer. Given a list of Producer nodes, I want to retrieve all paths from a Producer to all of its Consumers through Assets. When at an Asset node the subscribes_to relationship should only be traversed if the relationship has no producers property (meaning the related Consumer consumes from all producers of that asset) or if the producers property contains the id of the Producer that we started with. My first approach was to implement RelationshipExpander to determine which relationships from Asset to traverse. However, since all the Expand() method has to work with is the current Node, I dont have enough information to make the decision above. I would need the current Path in order to know what Producer related to the current Asset the Traversal came from. Right now Im using this description which will give me Producer->Asset->Consumer paths but wont exclude based on producers on subscribes_to: TraversalDescription producerToConsumer = Traversal.description() .depthFirst().uniqueness(Uniqueness.RELATIONSHIP_PATH) .relationships(RelTypes.Contributes_to, Direction.OUTGOING) .relationships(RelTypes.Subscribes_to,Direction.BOTH) .prune(Traversal.pruneAfterDepth(2)); If there is a way to accomplish what I describe above with the current framework, Im open to suggestions, including a different network design to track the Producer to Consumer relationship as it relates to Asset. Alternatively, I suggest that there may be situations where the Path context is needed to make the decision on what relationships to traverse from a Node, hence perhaps add Expand(Path p) to the RelationshipExpander interface. Thanks, Kalin -- Kalin Wilson http://www.kalinwilson.com Message sent using UebiMiau 2.7.9 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
Already though of that :) behold: PipeBuilder.fromNode(startNode).into(otherNode(A)) .into(traverse(myTraversalDescription)) .into(traverse(myOtherTraversalDescription)) .into(otherNode(B)); Or whatever. You can even use other "from", f.ex: fromNode, fromNodes, fromPath, fromPaths a.s.o. Something like that? 2011/3/15 Craig Taverner > I like the pipes idea. What I would like to see is nested traversers. The > pipe example below seems to imply single hops at each step, but it would be > nicer to allow each step to traverse until it reached a certain criteria, > at > which point a different traversal would take over. > > In the old and current API's it seems to do this you need to create a > traversal, iterate over it, and create a new traversal inside the loop. > > We created a Ruby DSL for nested traversals a year or so ago that looks a > bit like: > > > chart 'Distribution analysis' do >self.domain_axis='categories' >self.range_axis='values' >select 'First dataset',:categories=>'name',:values=>'value' do > from { >from { > traverse(:outgoing,:CHILD,1) > where {type=='gis' and name=='network.csv'} >} >traverse(:outgoing,:AGGREGATION,1) >where {name=='azimuth' and get_property(:select)=='max' and > distribute=='auto'} > } > traverse(:outgoing,:CHILD,:all) >end > end > > This is quite a complex example, but the key points are the from method > which defines where to start a traversal, and the traverse method which > defines the traversal itself, with the where method which is like the old > ReturnableEvaluator. > > Will the new pipes provide something like this? > > On Tue, Mar 15, 2011 at 9:19 AM, Massimo Lusetti > wrote: > > > On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson > > wrote: > > > > > I'm positive that some nice API will enter the kernel at some point, > > f.ex. > > > I'm experimenting with an API like this: > > > > > > for(Node node : > > > > > > PipeBuilder.fromNode(startNode).into(otherNode(A)).into(otherNode(B)).nodes()) > > > { > > > // node will be (3) from the example above > > > } > > > > > > > > > I hope I didn't confuse you with all this :) > > > > Nope, the opposite. Thanks for the clarification and that kind of API > > would be a killer feature IMHO. > > > > It will be even more pleasant to work with neo4j... > > > > Cheers > > -- > > Massimo > > http://meridio.blogspot.com > > ___ > > 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Traversal filters don't add up but replace each other
All, (I am new to this list) Looking at the Trarversal framework[1], I assumed that the TraversalDescription.filter[2] worked similarly to TraversalDescription.prune[3]. If any prune rejects a path, it is rejected - similarly I expected, that if any filter excluded a path, the path was excluded. However, I found that the documentation for the filter function[4] says "set" where the prune function[5] says "add". Thus, there is at all times only one filter in effect. I think it would make sense to implement a set of filters, and if any of them rejects a path, it is not included in the output. And maybe this filtering policy could be explained explicitly to be require-all-filters-accepting or require-any-filter-accepting (which are the only two options I can see) similarly to adding the traversel order policy[6][7]. For optimizations it might even be a good idea to give the developer some way of informing the filter policy which filters are the least and most restrictive - depending on the policy, one or the other is best to test first. This could e.g. be a second optional parameter to TraversalDescription.filter()[4] like PredicatePolicy.RESTRICTIVE, PredicatePolicy.DEFAULT and PredicatePolicy.INCLUSIVE. It is not enforced or verified in anyway, but is just a hint for the optimization of the traversal algorithm. Just an idea as it actually caught me by surprise and I had to code around it (making a predicate decorating a set of predicates). I know it is easy to code (it took 12 lines in the basic version), but would make sense to have built-in for consistency - and I'm probably not the only one who would like it. Regards, Morten Barklund [1] http://wiki.neo4j.org/content/Traversal_Framework [2] http://wiki.neo4j.org/content/Traversal_Framework#What_to_return.3F_-_filter [3] http://wiki.neo4j.org/content/Traversal_Framework#When_to_stop.3F_-_prune [4] http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#filter(org.neo4j.helpers.Predicate) [5] http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#prune(org.neo4j.graphdb.traversal.PruneEvaluator) [6] http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#breadthFirst() [7] http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#depthFirst() ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo] A new and improved Traversal framework
Hi, > I've recently been trying to do some traversal that sort of can be > described with transitions ie. if the last relationship was of type A > and direction INCOMING, the next direction to go might be type A > INCOMING or type B INCOMING; if it was type B INCOMING the next > relationship to traverse may only be type C OUTGOING, that kind of stuff. If you are interested, I added some more documentation to Pipes [ http://pipes.tinkerpop.com ]. The documentation explains how to use Pipes for the type of control you are desiring. http://bit.ly/9iJe1S This model is generally based on this idea: http://arxiv.org/abs/0803.4355 ... If you are interested, I can demonstrate some more involved examples. Take care, Marko. http://tinkerpop.com http://markorodriguez.com ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo] Evolving the graph-algo component
Our graph algorithms package has been in dire need of love for quite some time now, but it's finally starting to make it's way up the priority queue. We have made some plans regarding the direction in which we would like to take the graph algo package, but the input of the community would be worth a lot to us in this matter. The refactorings in the graph-algo component will to a large extent build on the new traversal framework. Some algorithms will be possible to implement using the new framework that were not possible to implement using the old framework. This will greatly simplify the maintainability of the graph-algo component. Others will build on the primitive building blocks that the new traversal framework provides, such as the Path abstraction and the RelationshipExpander (see http://lists.neo4j.org/pipermail/user/2010-March/003221.html for details). In order for the new traversal framework to support the changes we want to make in the graph-algo component we hope to be able to add another feature that was not mentioned in the previously mentioned email: Traversers with multiple start nodes that share state among the traversals. This will allow us to implement algorithms where we search for paths starting at both the source and target node. The main purpose of refactoring graph-algo is to improve the structure of the component and make the code easier to maintain. This means that a lot of classes and method signatures will change or be renamed, meaning that a lot of the code that uses the graph-algo package will need to be updated to utilize the next version. This is a necessary evil at this point. The main change is that we will untangle the state of the execution of an algorithm from the instances of the algorithm objects. Where you previously instantiated an algorithm class, invoked a few methods and then the instance contained the result you will in the future instantiate an algorithm class with the configuration on how it executes, then invoke a method with the input parameters from the graph (such as a start node) which will return a result set. The changes we are contemplating on the current graph-algo component are: * Unify the algorithms that search for a path (or several paths) between two nodes under a common interface: PathFinder The current implementations of this interface are: * ShortestPathFinder - finding the path with the least number of relationships * Dijkstra - finding the path(s) with the lowest cost * AStar - finding the path(s) with the lowest cost After these changes are made, it would be nice to add some more algorithms to this component, a process in which contributions are very welcome. Some of the algorithms that comes to mind are: * The Ford-Fulkerson algorithm ( http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm ), or some other flow algorithm ( http://en.wikipedia.org/wiki/Flow_network ) * Spanning tree algorithms ( http://en.wikipedia.org/wiki/Minimum_spanning_tree ) We would love to get feedback on these ideas, so what do you guys think? Cheers, -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Question
Sounds to me like the pruning is done based on the existence of property 'abc' at depth 3, and returning only nodes deeper than depth 3. On Mon, Feb 14, 2011 at 11:22 AM, Peter Neubauer < peter.neuba...@neotechnology.com> wrote: > John, > In your example, are there any constraints on that of the four > relationship types, every one need to be exactly one time in the path, > or is it just any of these? > > Instead of using a List like in the previous example, you can the use > a Map to tick the visited relationship types and check the property > when you get to REL3? I can do it for you in neo4j-examples again if > you give me some more details :) > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.org - Your high performance graph database. > http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. > > > > On Sun, Feb 13, 2011 at 10:16 AM, John Howard > wrote: > > Thanks Peter. That was very useful. > > > > I am trying to get the path A ->B->C->D-> E in the below graph, with the > > following inputs > > Start Node: A, > > Relationships: REL1, REL4, REL2 (that is, order is not known) > > Relationship Property: relProp= "abc" in REL3 > > > > I was not able to define an evaluator which takes the combination of > > relationship types(without regard to order) and relationship properties > to > > return the desired path. > > Can it be achievable in the current traversal framework? > > > > REL1 REL2REL8 > > A -> X -> Y ---> Z > > > > REL1REL2 REL3REL4 > > A -> B -> C ---> D -> E > > > > REL1REL3 REL9 REL10 > > A -> P -> Q ---> R -> E > > > > > > As always, appreciate your guidance. > > > > > > > > === > > John, > > if the order of the relationships doesn't matter, you could do > > something like this with the Traversal API (holding an ordered Path to > > test against in your Evaluator): > > > >public void testPath() > >{ > >final ArrayList orderedPath = new > > ArrayList(); > >orderedPath.add( withName( "REL1" ) ); > >orderedPath.add( withName( "REL2" ) ); > >orderedPath.add( withName( "REL3" ) ); > >orderedPath.add( withName( "REL4" ) ); > > > >TraversalDescription td = Traversal.description().evaluator( > >new Evaluator() > >{ > > > >public Evaluation evaluate( Path path ) > >{ > >if ( path.length() == 0 ) > >{ > >return Evaluation.EXCLUDE_AND_CONTINUE; > >} > >String currentName= > > path.lastRelationship().getType().name(); > >String relationshipType = orderedPath.get( > > path.length() - 1 ).name(); > >if ( path.length() == orderedPath.size() ) > >{ > >if ( currentName.equals( > >relationshipType ) ) > >{ > >return Evaluation.INCLUDE_AND_PRUNE; > >} > >else > >{ > >return Evaluation.EXCLUDE_AND_PRUNE; > >} > >} > >else > >{ > >if ( currentName.equals( > >relationshipType ) ) > >{ > >return Evaluation.EXCLUDE_AND_CONTINUE; > >} > >else > >{ > >return Evaluation.EXCLUDE_AND_PRUNE; > >} > >} > >} > >} ); > >
Re: [Neo4j] Composable traversals
There have been thoughts a long while to make something like this with the traversal framework, but time has never been allocated to evolve it. I'm adding stuff to the framework in a side track and will surely add some aspect of composable traversers also. 2011/7/29 Niels Hoogeveen > > I'd like to take a stab at implementing traversals in the Enhanced API. One > of the things I'd like to do, is to make traversals composable. > > Right now a Traverser is created by either calling the traverse method on > Node, or to call the traverse(Node) method on TraversalDescription. > > This makes traversals inherently non-composable, so we can't define a > single traversal that returns the parents of all our friends. > > To make Traversers composable we need a function: > > Traverser traverse(Traverser, TraversalDescription) > > My take on it is to make Element (which is a superinterface of Node) into a > Traverser. > > Traverser is basically another name for Iterable. > > Every Node (or more generally every Element) can be seen as an > Iterabe, returning a single Path, which contains a single > path-element, the Node/Element itself. > > Composing traversals would entail the concatenation of the paths returned > with the paths supplied, so when we ask for the parents of all our friends, > the returned paths would take the form: > > Node --FRIEND--> Node --> PARENT --> Node > > Niels > > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo] how to get an specific node
Hi! Johan Svensson skrev: One way would be to do a traversal from the "word-node" with the least number for relationships. OK, I implemented this. But I *do* have to iterate over the relationships to get the count? At the moment I only want the search to return one best match: either the first that matches all search words or the one matching as many words as possible (this alternative is a bit simplistic as I start the traversal from one point only). I attached some screenshots from my current IMDB node space. I tried two different ways performing the traversal: 1. traverser framework 2. nested loops Both do have their pros and cons, I think. Any suggestions for improvements on the code? Wich one would you choose?! /anders // use a traverser Traverser traverser = startNode.traverse( Order.DEPTH_FIRST, new StopEvaluator() { public boolean isStopNode( TraversalPosition currentPos ) { return currentPos.depth() >= 2; } }, ReturnableEvaluator.ALL_BUT_START_NODE, wordRelType, Direction.BOTH ); Node currentBase = null; int count = 0; for ( Node node : traverser ) { if ( traverser.currentPosition().depth() == 1 ) { currentBase = node; count = 0; } else if ( wordList.contains( node ) ) { count++; if ( count == listSize ) { return currentBase; } if ( count > highscore ) { bestMatch = currentBase; highscore = count; } } } // loop over relationships for ( Relationship rel : startNode.getRelationships( wordRelType ) ) { Node node = rel.getEndNode(); int count = 0; for ( Relationship innerRel : node.getRelationships( wordRelType ) ) { if ( wordList.contains( innerRel.getStartNode() ) ) { count++; if ( count == listSize ) { return node; } } } if ( count > highscore ) { bestMatch = node; highscore = count; } } <><><><>___ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework
Fantastic. Very nice. I guess this was also inspired by Marco's Gremlin and pipes? (so the use case is now well understood?) On Tue, Mar 15, 2011 at 11:33 AM, Mattias Persson wrote: > Already though of that :) behold: > > PipeBuilder.fromNode(startNode).into(otherNode(A)) > .into(traverse(myTraversalDescription)) > .into(traverse(myOtherTraversalDescription)) > .into(otherNode(B)); > > Or whatever. You can even use other "from", f.ex: fromNode, fromNodes, > fromPath, fromPaths a.s.o. > > Something like that? > > 2011/3/15 Craig Taverner > > > I like the pipes idea. What I would like to see is nested traversers. The > > pipe example below seems to imply single hops at each step, but it would > be > > nicer to allow each step to traverse until it reached a certain criteria, > > at > > which point a different traversal would take over. > > > > In the old and current API's it seems to do this you need to create a > > traversal, iterate over it, and create a new traversal inside the loop. > > > > We created a Ruby DSL for nested traversals a year or so ago that looks a > > bit like: > > > > > > chart 'Distribution analysis' do > >self.domain_axis='categories' > >self.range_axis='values' > >select 'First dataset',:categories=>'name',:values=>'value' do > > from { > >from { > > traverse(:outgoing,:CHILD,1) > > where {type=='gis' and name=='network.csv'} > >} > >traverse(:outgoing,:AGGREGATION,1) > >where {name=='azimuth' and get_property(:select)=='max' and > > distribute=='auto'} > > } > > traverse(:outgoing,:CHILD,:all) > >end > > end > > > > This is quite a complex example, but the key points are the from method > > which defines where to start a traversal, and the traverse method which > > defines the traversal itself, with the where method which is like the old > > ReturnableEvaluator. > > > > Will the new pipes provide something like this? > > > > On Tue, Mar 15, 2011 at 9:19 AM, Massimo Lusetti > > wrote: > > > > > On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson > > > wrote: > > > > > > > I'm positive that some nice API will enter the kernel at some point, > > > f.ex. > > > > I'm experimenting with an API like this: > > > > > > > > for(Node node : > > > > > > > > > > PipeBuilder.fromNode(startNode).into(otherNode(A)).into(otherNode(B)).nodes()) > > > > { > > > > // node will be (3) from the example above > > > > } > > > > > > > > > > > > I hope I didn't confuse you with all this :) > > > > > > Nope, the opposite. Thanks for the clarification and that kind of API > > > would be a killer feature IMHO. > > > > > > It will be even more pleasant to work with neo4j... > > > > > > Cheers > > > -- > > > Massimo > > > http://meridio.blogspot.com > > > ___ > > > 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 > > > > > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > ___ > 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
Re: [Neo4j] Getting sorted results from a traversal
The DB would do it in memory too, wouldn't it? In the case of a complex traversal, indexes don't really apply, since the ordering and the traversal order are unrelated, so you'd generally need to sort in memory anyway. Whether you do it as you add elements to the traversed list of "stuff" or do it after the fact is another discussion, but I think in either case, it needs to be done "after the fact". -Original Message- From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] On Behalf Of Pere Urbon Bayes Sent: Friday, July 15, 2011 11:05 AM To: Neo4j user discussions Subject: Re: [Neo4j] Getting sorted results from a traversal Well, this is great if I want to do all the math in memory, but I expect to do the computation by the db. / purbon On 15 July 2011 16:10, Marko Rodriguez wrote: > Hi Pere, > > To sort you need to have all your results. > > Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j > traverser framework), > > results = [] > g.v(1).out('friend').out('likes') >> results // what my friends like > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by name > > In short, once you have the result of your traversal, you can then apply a > comparator to the Collection to sort it as you please --- its just Java > comparators. > > See ya, > Marko. > > http://markorodriguez.com > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > HI! > > I am on the situation of having to traverse neo4j, and then expect the > > resultset returned to be ordered in a certain order. I've been > researching a > > bit over the traversal API, but I did not find anything related to that. > I > > really will appreciate any tip on that!! > > > > BTW > I expect to be possible right?, as we have in relational the > ordering, > > or on redis, etc... > > > > /purbon > > > > -- > > Pere Urbon-Bayes > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > ___ > > 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 > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ 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
Re: [Neo4j] cycle detection
I think you could implement this using RELATIONSHIP_GLOBAL uniqueness, like (from the top of my head): Traversal.description().uniqueness( Uniqueness.RELATIONSHIP_GLOBAL ) .evaluator(new Evaluator() { public Evaluation(Path path) { return path.length() > 0 && endNodeOccursPreviouslyInPath( path ) ? Evaluation.INCLUDE_AND_CONTINUE : Evaluation.EXCLUDE_AND_CONTINUE; } private boolean endNodeOccursPreviouslyInPath(Path path) { Node endNode = path.endNode(); int counter = 0; for ( Node node : path.nodes() ) { if ( counter++ < path.length() && node.equals( endNode ) ) return true; } return false; } } ).traverse(...); This should (if it even compiles :) ) return paths containing cycles. Something like this you're looking for? 2011/3/25 Wouter De Borger > Hi all, > > I would like to detect all cycles in a traversal. > > I know the traversal framework has cycle avoidance built-in, but there > doesn't seem to be an API for cycle detection! > > Has anyone already implemented a cycle detector for traversals? > > Thanks in advance, > Wouter > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Slow Traversals on Nodes with too many Relationships
That is rather a case of warming up your caches. Determining the traversal speed from the first run is not a good benchmark as it doesn't represent production usage :) The same (warming up) is true for all kinds of benchmarks (except for startup performance benchmarks). Cheers Michael Am 15.06.2011 um 14:48 schrieb Agelos Pikoulas: > I have a few "Part" nodes related with each via "HASPART" > relationship/edges. > (eg Part1---HASPART--->Part2---HASPART--->Part3 etc) . > TraversalDescription works fine, following each Part's outgoing HASPART > relationship. > > Then I add a large number (say 100.000) of "Container" Nodes, where each > "Container" has a "CONTAINS" relation to almost *every* "Part" node. > Hence each Part node now has a 100.000 incoming CONTAINS relationships from > Container nodes, > but only a few outgoing HASPART relationships to other Part nodes. > > Now my previous TraversalDescription run extremely slow (several seconds > inside each Iterator.next() call) > Note that I do define relationships(RT.HASPART, Direction.OUTGOING) on the > TraversalDescription, > but it seems its not used by neo4j as a hint. Note that on a subsequent run > of the same Traversal, its very quick indeed. > > Is there any way to use Indexing on relationships for such a scenario, to > boost things up ? > > Ideally, the Traversal framework could use automatic/declerative indexing on > Node Relationship types and/or direction to perform such traversals quicker. > > Regards > ___ > 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
Re: [Neo4j] Traversal framework suggested change
Fantastic! I have yet to try the implementation out, but I'm positive that it's an improvement. The only comment I have right now is the use of the word "SKIP". IMO it is ambiguous with respect to stopping vs excluding. I prefer EXCLUDE. Will try it out soon. Thanks Mattias! David On Thu, Nov 18, 2010 at 3:46 PM, Mattias Persson wrote: > 2010/11/18 Mattias Persson > > > I just spent less than two hours making this change locally and > everything > > works and it generally feels great. Now that I've tried it out myself, > this > > way of controlling pruning/filtering feels more awesome. I'll post some > > examples soon so that you can feedback :) > > > > > Well, examples are maybe unecessary. > > class Evaluator > Evaluation evaluate(Path path); > > enum Evaluation > INCLUDE_AND_CONTINUE > INCLUDE_AND_STOP > SKIP_AND_CONTINUE > SKIP_AND_STOP > > class TraversalDescription > +evaluator(Evaluator) > -prune(PruneEvaluator) > -filter(Predicate) > > Also I've added lots of useful evaluators in an "Evaluators" class, but > maybe those should reside in Traversal class instead, however I think > Traversal class is a little bloated as it is now. > > There's the decision whether or not this thing could go into 1.2 or not... > For one thing it breaks the API, but then again the > PruneEvaluator/Predicate (filter) can still be there, mimicing > Evaluators in the background. Because a PruneEvaluator can be seen as an > Evaluator which instead of true/false returns > INCLUDE_AND_CONTINUE/INCLUDE_AND_STOP and a filter can be seen as an > Evaluator which instead of true/false returns > INCLUDE_AND_CONTINUE/SKIP_AND_CONTINUE. And you can have multiple > evaluators > just as you can with pruners/filters. > > This API seems more flexible and this will, in most cases, yield better > traversal performance as well. > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- David Montag Neo Technology, www.neotechnology.com Cell: 650.556.4411 david.mon...@neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Getting sorted results from a traversal
But you couldn't easy do a complex traversal with an RDBMS. ;-) I suspect that even if you could write some magic SQL to do so, you'd almost certainly lose the benefits any optimized sorting/ordering that indices provide, so even the RDBMS would have to post-process the sort. If the traversal isn't complex or randomly "deep", then Neo indexing + querying might work for you the same way an RDBMS might handle it. -Original Message- From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] On Behalf Of Pere Urbon Bayes Sent: Friday, July 15, 2011 11:21 AM To: Neo4j user discussions Subject: Re: [Neo4j] Getting sorted results from a traversal Well, the thing is that the database can easy deal with that, as the relational system do. / purbon On 15 July 2011 17:08, Rick Bullotta wrote: > The DB would do it in memory too, wouldn't it? In the case of a complex > traversal, indexes don't really apply, since the ordering and the traversal > order are unrelated, so you'd generally need to sort in memory anyway. > Whether you do it as you add elements to the traversed list of "stuff" or > do it after the fact is another discussion, but I think in either case, it > needs to be done "after the fact". > > > -Original Message- > From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] > On Behalf Of Pere Urbon Bayes > Sent: Friday, July 15, 2011 11:05 AM > To: Neo4j user discussions > Subject: Re: [Neo4j] Getting sorted results from a traversal > > Well, this is great if I want to do all the math in memory, but I expect to > do the computation by the db. > > / purbon > > On 15 July 2011 16:10, Marko Rodriguez wrote: > > > Hi Pere, > > > > To sort you need to have all your results. > > > > Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j > > traverser framework), > > > > results = [] > > g.v(1).out('friend').out('likes') >> results // what my friends like > > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by > name > > > > In short, once you have the result of your traversal, you can then apply > a > > comparator to the Collection to sort it as you please --- its just Java > > comparators. > > > > See ya, > > Marko. > > > > http://markorodriguez.com > > > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > > > HI! > > > I am on the situation of having to traverse neo4j, and then expect the > > > resultset returned to be ordered in a certain order. I've been > > researching a > > > bit over the traversal API, but I did not find anything related to > that. > > I > > > really will appreciate any tip on that!! > > > > > > BTW > I expect to be possible right?, as we have in relational the > > ordering, > > > or on redis, etc... > > > > > > /purbon > > > > > > -- > > > Pere Urbon-Bayes > > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > > ___ > > > 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 > > > > > > -- > Pere Urbon-Bayes > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > ___ > 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 > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ 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
Re: [Neo4j] Traversal Question
Thanks Peter & Craig. There are no such constraints, that is, relationship types can reoccur if a path satisfies the input criteria. For ex: If there was another path in our graph example, say, REL1REL3 REL4 REL2 REL9 REL8 A -> P -> Q ---> R -> S -->T--->U we would like to see 2 paths, viz, A ->B->C->D-> E and A ->P->Q->R-> S I tried with the map suggestion, the prune logic doesn't seem to fit with the existing evaluators. Again, my understanding of the prune evaluators may be wrong. Appreciate your help. Thank you. On Mon, Feb 14, 2011 at 5:22 AM, Peter Neubauer < peter.neuba...@neotechnology.com> wrote: > John, > In your example, are there any constraints on that of the four > relationship types, every one need to be exactly one time in the path, > or is it just any of these? > > Instead of using a List like in the previous example, you can the use > a Map to tick the visited relationship types and check the property > when you get to REL3? I can do it for you in neo4j-examples again if > you give me some more details :) > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 <+46704106975> > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.org - Your high performance graph database. > http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. > > > > On Sun, Feb 13, 2011 at 10:16 AM, John Howard > wrote: > > Thanks Peter. That was very useful. > > > > I am trying to get the path A ->B->C->D-> E in the below graph, with the > > following inputs > > Start Node: A, > > Relationships: REL1, REL4, REL2 (that is, order is not known) > > Relationship Property: relProp= "abc" in REL3 > > > > I was not able to define an evaluator which takes the combination of > > relationship types(without regard to order) and relationship properties > to > > return the desired path. > > Can it be achievable in the current traversal framework? > > > > REL1 REL2REL8 > > A -> X -> Y ---> Z > > > > REL1REL2 REL3REL4 > > A -> B -> C ---> D -> E > > > > REL1REL3 REL9 REL10 > > A -> P -> Q ---> R -> E > > > > > > As always, appreciate your guidance. > > > > > > > > === > > John, > > if the order of the relationships doesn't matter, you could do > > something like this with the Traversal API (holding an ordered Path to > > test against in your Evaluator): > > > >public void testPath() > >{ > >final ArrayList orderedPath = new > > ArrayList(); > >orderedPath.add( withName( "REL1" ) ); > >orderedPath.add( withName( "REL2" ) ); > >orderedPath.add( withName( "REL3" ) ); > >orderedPath.add( withName( "REL4" ) ); > > > >TraversalDescription td = Traversal.description().evaluator( > >new Evaluator() > >{ > > > >public Evaluation evaluate( Path path ) > >{ > >if ( path.length() == 0 ) > >{ > >return Evaluation.EXCLUDE_AND_CONTINUE; > >} > >String currentName= > > path.lastRelationship().getType().name(); > >String relationshipType = orderedPath.get( > > path.length() - 1 ).name(); > >if ( path.length() == orderedPath.size() ) > >{ > >if ( currentName.equals( > >relationshipType ) ) > >{ > >return Evaluation.INCLUDE_AND_PRUNE; > >} > >else > >{ > >return Evaluation.EXCLUDE_AND_PRUNE; > >} > >} > >else > >{ > >if ( currentNam
Re: [Neo4j] Getting sorted results from a traversal
You might also try to use cypher for your traversal which is able to order (also in memory of course). See the screencast I did: http://neo4j.vidcaster.com/U2Y/introduction-to-cypher/ It's even the same domain. Cheers Michael Am 15.07.2011 um 17:24 schrieb Rick Bullotta: > But you couldn't easy do a complex traversal with an RDBMS. ;-) > > I suspect that even if you could write some magic SQL to do so, you'd almost > certainly lose the benefits any optimized sorting/ordering that indices > provide, so even the RDBMS would have to post-process the sort. > > If the traversal isn't complex or randomly "deep", then Neo indexing + > querying might work for you the same way an RDBMS might handle it. > > > -Original Message- > From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] On > Behalf Of Pere Urbon Bayes > Sent: Friday, July 15, 2011 11:21 AM > To: Neo4j user discussions > Subject: Re: [Neo4j] Getting sorted results from a traversal > > Well, the thing is that the database can easy deal with that, as the > relational system do. > > / purbon > > On 15 July 2011 17:08, Rick Bullotta wrote: > >> The DB would do it in memory too, wouldn't it? In the case of a complex >> traversal, indexes don't really apply, since the ordering and the traversal >> order are unrelated, so you'd generally need to sort in memory anyway. >> Whether you do it as you add elements to the traversed list of "stuff" or >> do it after the fact is another discussion, but I think in either case, it >> needs to be done "after the fact". >> >> >> -Original Message- >> From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] >> On Behalf Of Pere Urbon Bayes >> Sent: Friday, July 15, 2011 11:05 AM >> To: Neo4j user discussions >> Subject: Re: [Neo4j] Getting sorted results from a traversal >> >> Well, this is great if I want to do all the math in memory, but I expect to >> do the computation by the db. >> >> / purbon >> >> On 15 July 2011 16:10, Marko Rodriguez wrote: >> >>> Hi Pere, >>> >>> To sort you need to have all your results. >>> >>> Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j >>> traverser framework), >>> >>> results = [] >>> g.v(1).out('friend').out('likes') >> results // what my friends like >>> results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by >> name >>> >>> In short, once you have the result of your traversal, you can then apply >> a >>> comparator to the Collection to sort it as you please --- its just Java >>> comparators. >>> >>> See ya, >>> Marko. >>> >>> http://markorodriguez.com >>> >>> On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: >>> >>>> HI! >>>> I am on the situation of having to traverse neo4j, and then expect the >>>> resultset returned to be ordered in a certain order. I've been >>> researching a >>>> bit over the traversal API, but I did not find anything related to >> that. >>> I >>>> really will appreciate any tip on that!! >>>> >>>> BTW > I expect to be possible right?, as we have in relational the >>> ordering, >>>> or on redis, etc... >>>> >>>> /purbon >>>> >>>> -- >>>> Pere Urbon-Bayes >>>> moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany >>>> Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 >>>> ___ >>>> 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 >>> >> >> >> >> -- >> Pere Urbon-Bayes >> moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany >> Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 >> ___ >> 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 >> > > > > -- > Pere Urbon-Bayes > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > ___ > 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
Re: [Neo4j] Getting sorted results from a traversal
Well, the thing is that the database can easy deal with that, as the relational system do. / purbon On 15 July 2011 17:08, Rick Bullotta wrote: > The DB would do it in memory too, wouldn't it? In the case of a complex > traversal, indexes don't really apply, since the ordering and the traversal > order are unrelated, so you'd generally need to sort in memory anyway. > Whether you do it as you add elements to the traversed list of "stuff" or > do it after the fact is another discussion, but I think in either case, it > needs to be done "after the fact". > > > -Original Message- > From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] > On Behalf Of Pere Urbon Bayes > Sent: Friday, July 15, 2011 11:05 AM > To: Neo4j user discussions > Subject: Re: [Neo4j] Getting sorted results from a traversal > > Well, this is great if I want to do all the math in memory, but I expect to > do the computation by the db. > > / purbon > > On 15 July 2011 16:10, Marko Rodriguez wrote: > > > Hi Pere, > > > > To sort you need to have all your results. > > > > Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j > > traverser framework), > > > > results = [] > > g.v(1).out('friend').out('likes') >> results // what my friends like > > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by > name > > > > In short, once you have the result of your traversal, you can then apply > a > > comparator to the Collection to sort it as you please --- its just Java > > comparators. > > > > See ya, > > Marko. > > > > http://markorodriguez.com > > > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > > > HI! > > > I am on the situation of having to traverse neo4j, and then expect the > > > resultset returned to be ordered in a certain order. I've been > > researching a > > > bit over the traversal API, but I did not find anything related to > that. > > I > > > really will appreciate any tip on that!! > > > > > > BTW > I expect to be possible right?, as we have in relational the > > ordering, > > > or on redis, etc... > > > > > > /purbon > > > > > > -- > > > Pere Urbon-Bayes > > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > > ___ > > > 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 > > > > > > -- > Pere Urbon-Bayes > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > ___ > 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 > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Slow Traversals on Nodes with too many Relationships
I have a few "Part" nodes related with each via "HASPART" relationship/edges. (eg Part1---HASPART--->Part2---HASPART--->Part3 etc) . TraversalDescription works fine, following each Part's outgoing HASPART relationship. Then I add a large number (say 100.000) of "Container" Nodes, where each "Container" has a "CONTAINS" relation to almost *every* "Part" node. Hence each Part node now has a 100.000 incoming CONTAINS relationships from Container nodes, but only a few outgoing HASPART relationships to other Part nodes. Now my previous TraversalDescription run extremely slow (several seconds inside each Iterator.next() call) Note that I do define relationships(RT.HASPART, Direction.OUTGOING) on the TraversalDescription, but it seems its not used by neo4j as a hint. Note that on a subsequent run of the same Traversal, its very quick indeed. Is there any way to use Indexing on relationships for such a scenario, to boost things up ? Ideally, the Traversal framework could use automatic/declerative indexing on Node Relationship types and/or direction to perform such traversals quicker. Regards ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] How to traverse by the number of relationships between nodes?
Hi Tim! Maybe you can use the new traversal framework, this interface comes to mind: http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/SourceSelector.html Regarding the number of relationships, it could be a good idea to store it as a property on the node. /anders > Is there any way I can write a ReturnableEvaluator that can examine the > collection of nodes related to the current node? Is this even the correct > approach? > > I actually want to be able to return the 10 most popular routes to the > registration page. For the most popular, I can use the above algorithm, but > for > the second it's going to be more tricky. > > Would I be able to search for all 10 routes in a single pass, or should I > perform multiple passes? > > Any help would be really appreciated since I'm not really sure how to > approach > this. > > Thanks, > Tim > > > > > ___ > 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] How to filter the duplicated nodes or relationship in traverser?
Hi, I setup a traversal description with Uniqueness.NODE_PATH and the side effect is duplicated nodes output. How to filter the duplicated output in nodes and relationship under your Transversal Framework? Also, this link isn't working http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/kernel/Traversal.html#returnAllButStartNode() Regards, Brendan ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
There's no such statistics in the traversal framework, no. But your solution with your own counter in the Evaluator would show you how many nodes was encountered during the traversal (for the selected uniqueness setting). 2011/4/18 bhargav gunda > Respected, > > here is the case which I want to count total number of nodes and dragging > only some level (in between) of nodes from total. > > The sample code looks like this: > > public Traverser testCase(Node node, int limitFrom) { > TravesalDescription td = null; > try{ > td = Traversal.description(). > breadthFirst().relationships(relType.Knows, Direction.BOTH) > .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL) > .evaluator(new Evaluator() >{ >int max = 0; >public Evaluation evaluate(Path path) { >Relationship lastRelation = path.lastRelationship(); >if(lastRelation == null){ > return Evaluation.EXCLUDE_AND_CONTINUE; >} >if(max >= limitFrom){ >max++; >return Evaluation.INCLUDE_AND_CONTINUE; >}else { > max++; > return Evaluation.EXCLUDE_AND_CONTINUE; > } > } > }); > }catch(Exception ex){ > ex.printStrackTrace(); > } > return td.traverse(node) > } > > This traverse function returns the certain limited number of nodes > traversed > in the total number of nodes (I am not sure with the code & I just wrote > code to give an idea). > So my question is before passing the value to limitFrom, we need to know > the > total number of nodes(If count is in Thousands or Lakhs). So is their any > direct method to find the total number of nodes traversed by the traverse > function itself in the traverse function. > For this I added a max variable in the evaluator class function (May be it > not works, I am not sure). > > So if you have any ideas or if I done any mistake kindly let me know. > > Regards, > Bhargav. > > > On Sun, Apr 17, 2011 at 11:29 PM, Peter Neubauer < > peter.neuba...@neotechnology.com> wrote: > > > Bhargav, > > I'm not sure I am following you. Could you maybe write some pseudo > > code to highlight the case? > > > > Cheers, > > > > /peter neubauer > > > > GTalk: neubauer.peter > > Skype peter.neubauer > > Phone +46 704 106975 > > LinkedIn http://www.linkedin.com/in/neubauer > > Twitter http://twitter.com/peterneubauer > > > > http://www.neo4j.org - Your high performance graph > database. > > http://startupbootcamp.org/- Öresund - Innovation happens HERE. > > http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. > > > > > > > > On Wed, Apr 13, 2011 at 7:18 PM, bhargav gunda > > wrote: > > > Yeah I know that but I want it in the traverse function itself. Based > on > > the > > > result again I want to do one more function. So i am trying to find in > > the > > > traverse function. > > > > > > Thanks & Regards, > > > G. > > > > > > On Wed, Apr 13, 2011 at 3:47 PM, Peter Neubauer < > > neubauer.pe...@gmail.com>wrote: > > > > > >> Of course, > > >> You can have a count outside your traversal description that for > > instance > > >> and Evaluator is updating since it is called for all traversed nodes. > > This > > >> is not thread safe but I think it will give you the data you want? > > >> > > >> Sent from my phone. > > >> On Apr 13, 2011 12:32 PM, "Stephan Hagemann" < > > >> stephan.hagem...@googlemail.com> wrote: > > >> > Hi Gunda, > > >> > > > >> > I believe you are asking fir the same thing I asked for a couple of > > days > > >> > ago. Check this thread: > > >> > > > >> > http://lists.neo4j.org/pipermail/user/2011-April/007932.html > > >> > > > >> > As the discussion shows, this feature is currently not available but > > >> > probably interesting in a lot of settings. At least for you and me > ;) > > >> > > > >> > Regards, > > >> > Stephan > > >> > > > >> > > &g
Re: [Neo4j] Slow Traversals on Nodes with too many Relationships
I would respectfully disagree that it doesn't necessarily represent production usage, since in some cases, each query/traversal will be unique and isolated to a part of a subgraph, so in some cases, a "cold" query may be the norm -Original Message- From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] On Behalf Of Michael Hunger Sent: Wednesday, June 15, 2011 10:25 AM To: Neo4j user discussions Subject: Re: [Neo4j] Slow Traversals on Nodes with too many Relationships That is rather a case of warming up your caches. Determining the traversal speed from the first run is not a good benchmark as it doesn't represent production usage :) The same (warming up) is true for all kinds of benchmarks (except for startup performance benchmarks). Cheers Michael Am 15.06.2011 um 14:48 schrieb Agelos Pikoulas: > I have a few "Part" nodes related with each via "HASPART" > relationship/edges. > (eg Part1---HASPART--->Part2---HASPART--->Part3 etc) . > TraversalDescription works fine, following each Part's outgoing HASPART > relationship. > > Then I add a large number (say 100.000) of "Container" Nodes, where each > "Container" has a "CONTAINS" relation to almost *every* "Part" node. > Hence each Part node now has a 100.000 incoming CONTAINS relationships from > Container nodes, > but only a few outgoing HASPART relationships to other Part nodes. > > Now my previous TraversalDescription run extremely slow (several seconds > inside each Iterator.next() call) > Note that I do define relationships(RT.HASPART, Direction.OUTGOING) on the > TraversalDescription, > but it seems its not used by neo4j as a hint. Note that on a subsequent run > of the same Traversal, its very quick indeed. > > Is there any way to use Indexing on relationships for such a scenario, to > boost things up ? > > Ideally, the Traversal framework could use automatic/declerative indexing on > Node Relationship types and/or direction to perform such traversals quicker. > > Regards > ___ > 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
Re: [Neo] Traversal suggestions
Hi Tobias, and thanks for the reply. I wasn't actually suggesting using dynamic relationships, although maybe that's what it boils down to. I do have a fixed set of relationships, but some of them may have properties that can affect traversal. To make it explicit I'll use an example. The graph I have consists of biological entities and their relationships. For example, gene nodes can be connected by a 'coexpressed_with' relationship. Coexpression is determined statistically from experimental measurements and so each coexpression relationship has a probability associated with it, modeled as a property on the relationship. What I was suggesting is that it would be useful to be able to change the probability threshold of relationships traversed. One of the features of Neo that attracted me in the first place coming from an RDF solution was that individual relationships had state, as opposed to just a type. It seems the current traversal solution dosen't take advantage of that feature. As you mention, I could experiment with implementing my own traversal system and if I do I'll be sure to share the results. Also, thanks for the link to the discussion on node types, that was new to me. I am currently defining my own node property specifing a type so I should think some more about the modeling approach outlined in that thread. thanks for the discussion, Jonny On Mon, Oct 27, 2008 at 6:19 AM, Tobias Ivarsson < [EMAIL PROTECTED]> wrote: > On Fri, Oct 24, 2008 at 4:49 PM, Jonny Wray <[EMAIL PROTECTED]> > wrote: > > > Hi Tobias, > > I'm not sure how specifying a specific collection of relationships in a > > traversal would achieve the same effect. To be more explicit, I have the > > case where I would like to traverse a relationship of a specific type, > but > > that relationship has some concept of evidence as a property. One user > > maybe > > believe that evidence, and so would want to traverse the relationship, > > whereas another user might not believe it so wouldn't want to. > > > > I'm not sure how this could be achieved currently other than by filtering > > the result of the traversal after the effect. If indeed that's the most > > efficient way then so be it. > > > > > Usually when you define your data model you define a set of relationship > types that your application is going to use. The Guidelines [ > http://wiki.neo4j.org/content/Getting_Started_Guide] suggest using an enum > for this, in which case it is very simple to get an array with all the > types > and pass that to the traverse-method. If relationship types are created > dynamically it might be more complicated. There is a method on the > EmbeddedNeo class called getRelationshipTypes(), it's currently deprecated, > but we have been discussing undeprecating it and exposing in though the > NeoService interface. This will (probably) happen in the next release. This > might be a way that you could use to create an array of all the > relationship > types in your system and pass to the traverse-method. > > One thing to note is that the main useage for relationship types is to aid > traversal structure [ > http://lists.neo4j.org/pipermail/user/2008-October/000848.html]. If you > don't use the types for your traversals of the graph in your system it > might > be better to only use one and the same RelationshipType for all > relationships and then filter the traversal based on other properties as > you > suggest. Perhaps even have something named Type (or something similar) as a > property on your relationship if you have a system where users are allowed > to define ther own types for relationships (but where these are > insignificant for traversal). > > The problem with this approach is, as you say, that it's not supported by > the traversal API. I agree with you that the traversal API is far from > ideal > in every case. On the bright side it is very possible for you to define > your > own traversal sytem using the getRelationship(...)-methods of Node. Doing > this will not slow down your system notably (given that you don't define > complex algorithms in your traversals). It is sertenly very likely to be > faster than filtering the result of the traversal afterwards. > > If you do define your own traversal system I would be very interested at > looking at your API (if I may) to see if there is some ideas that can be > used to improve the traversal API of Neo4j. Or if you just have suggestions > on what you think the traverser framework should be enhanced with I will > gladly accept those as well. > > I hope this shines at least some light on this issue. > Good luck, > -- > Tobias Ivarsson <[EMAIL PROTECTED]> > H
Re: [Neo4j] traversal framework question
Hi Joshi, the problem may be that your traversal description will traverse from actor to director (in both directions) and also from director to actors (also in both directions). Your "manual" traverser traverses actors to directors in both directions and then only incoming relationships from director to actor. So there's a difference there. In your case it may be better to do the manual thing, or instead have two relationship types, actor_worked_with_director and director_worked_with_actor so that you can specify a more granular traversal description with: actor_worked_with_director: BOTH director_worked_with_actor: INCOMING 2010/12/7, Joshi Hemant - hjoshi : > I have graph of 2 types of nodes : actors and directors. The graph is > constructed such that an actor may have worked with multiple directors > and the director may have worked with different actors. The objective is > to find the list of actors (sorted by frequency) who have shared the > most number of directors (for the given Actor1). The traversal > description I wrote looks like : > Actor1 --> Director1 <-- Actor2 > Actor1 --> Director2 <--Actor2 > Actor1 --> Director3 <-- Actor2 > Actor1 --> Director4 <-- Actor3 > ... and so on > > for(Node otherActorNode : Traversal.description().relationships( > MyRelationshipTypes.WORKED_WITH,Direction.BOTH) > .breadthFirst().uniqueness(Uniqueness.NODE_PATH) > .prune( Traversal.pruneAfterDepth( 2 ) ) > .traverse(givenActorNode).nodes()){ > //Keep frequency updated for otherActorNode > } > // Display sorted list of otherActorNode that have worked with common > director > > The problem is that I am getting higher (incorrect) scores of the shared > number of unique directors for a given 2 actors. I used node_path > uniqueness to make sure that we do not traverse same path twice. > Instead of one traverser call if I split it into 2 calls: > 1. Get all directors the givenActorNode has worked_with > 2. For all director nodes, get incoming worked_with relationship and > count frequencies (except givenActorNode) > I get the correct results: > > Am I missing in the single traversal description above? > -Hemant > > *** > The information contained in this communication is confidential, is > intended only for the use of the recipient named above, and may be legally > privileged. > > If the reader of this message is not the intended recipient, you are > hereby notified that any dissemination, distribution or copying of this > communication is strictly prohibited. > > If you have received this communication in error, please resend this > communication to the sender and delete the original message or any copy > of it from your computer system. > > Thank You. > > > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traverser Functions in Neo4j
On Mon, Mar 14, 2011 at 12:39 PM, Mattias Persson wrote: > Head over to http://wiki.neo4j.org/content/Traversal_Framework for more > information. And know that the exact limitation you ran into spawned the > creation of this new API. I started using this framework from day 1 since I'm new and I don't have background from Node.traverse(). If I understand correctly this "will be" THE traversal framework right? It's experimental but you use this from within Node.traverse so it's not that experimental I guess? ... Did you suggest to use this or the "old" API? Plus the page you mention isn't well linked in the wiki... Just my 0.02Euro doubts -- Massimo http://meridio.blogspot.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] cycle detection
Cool! Would be great to maybe add this to the graph-algo package, if you don't mind? Just fork and add it from https://github.com/neo4j/graphdb/tree/master/graph-algo and do a merge request ... Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Sun, Mar 27, 2011 at 10:56 PM, Jacopo wrote: > In case you are interested, I implemented cycle detection by using > Tarjan algorithm, not the traversal. > The code is visible in the Italian Wikipedia, I hope it's intelligible > although the language. > http://it.wikipedia.org/wiki/Algoritmo_di_Tarjan_per_le_componenti_fortemente_connesse#Implementazione_in_Java > > > Hi > Jacopo Farina > > Il giorno ven, 25/03/2011 alle 13.51 +0100, Mattias Persson ha scritto: >> I think you could implement this using RELATIONSHIP_GLOBAL uniqueness, like >> (from the top of my head): >> >> Traversal.description().uniqueness( Uniqueness.RELATIONSHIP_GLOBAL ) >> .evaluator(new Evaluator() { >> public Evaluation(Path path) { >> return path.length() > 0 && endNodeOccursPreviouslyInPath( >> path ) ? >> Evaluation.INCLUDE_AND_CONTINUE : >> Evaluation.EXCLUDE_AND_CONTINUE; >> } >> >> private boolean endNodeOccursPreviouslyInPath(Path path) { >> Node endNode = path.endNode(); >> int counter = 0; >> for ( Node node : path.nodes() ) { >> if ( counter++ < path.length() && node.equals( endNode ) ) >> return true; >> } >> return false; >> } >> } ).traverse(...); >> >> This should (if it even compiles :) ) return paths containing cycles. >> Something like this you're looking for? >> >> 2011/3/25 Wouter De Borger >> >> > Hi all, >> > >> > I would like to detect all cycles in a traversal. >> > >> > I know the traversal framework has cycle avoidance built-in, but there >> > doesn't seem to be an API for cycle detection! >> > >> > Has anyone already implemented a cycle detector for traversals? >> > >> > Thanks in advance, >> > Wouter >> > ___ >> > 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
Re: [Neo4j] Getting sorted results from a traversal
Well, this is great if I want to do all the math in memory, but I expect to do the computation by the db. / purbon On 15 July 2011 16:10, Marko Rodriguez wrote: > Hi Pere, > > To sort you need to have all your results. > > Thus, in Gremlin (and hopefully you can do the mapping to the core Neo4j > traverser framework), > > results = [] > g.v(1).out('friend').out('likes') >> results // what my friends like > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by name > > In short, once you have the result of your traversal, you can then apply a > comparator to the Collection to sort it as you please --- its just Java > comparators. > > See ya, > Marko. > > http://markorodriguez.com > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > HI! > > I am on the situation of having to traverse neo4j, and then expect the > > resultset returned to be ordered in a certain order. I've been > researching a > > bit over the traversal API, but I did not find anything related to that. > I > > really will appreciate any tip on that!! > > > > BTW > I expect to be possible right?, as we have in relational the > ordering, > > or on redis, etc... > > > > /purbon > > > > -- > > Pere Urbon-Bayes > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > ___ > > 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 > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] traversal framework question
I have graph of 2 types of nodes : actors and directors. The graph is constructed such that an actor may have worked with multiple directors and the director may have worked with different actors. The objective is to find the list of actors (sorted by frequency) who have shared the most number of directors (for the given Actor1). The traversal description I wrote looks like : Actor1 --> Director1 <-- Actor2 Actor1 --> Director2 <--Actor2 Actor1 --> Director3 <-- Actor2 Actor1 --> Director4 <-- Actor3 ... and so on for(Node otherActorNode : Traversal.description().relationships( MyRelationshipTypes.WORKED_WITH,Direction.BOTH) .breadthFirst().uniqueness(Uniqueness.NODE_PATH) .prune( Traversal.pruneAfterDepth( 2 ) ) .traverse(givenActorNode).nodes()){ //Keep frequency updated for otherActorNode } // Display sorted list of otherActorNode that have worked with common director The problem is that I am getting higher (incorrect) scores of the shared number of unique directors for a given 2 actors. I used node_path uniqueness to make sure that we do not traverse same path twice. Instead of one traverser call if I split it into 2 calls: 1. Get all directors the givenActorNode has worked_with 2. For all director nodes, get incoming worked_with relationship and count frequencies (except givenActorNode) I get the correct results: Am I missing in the single traversal description above? -Hemant *** The information contained in this communication is confidential, is intended only for the use of the recipient named above, and may be legally privileged. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please resend this communication to the sender and delete the original message or any copy of it from your computer system. Thank You. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] R-Tree indexing performance
Hi all, Yes, there are some plans for improvements to the index. However, I should start by saying that we have not done extensive benchmarking of the RTree against the PostGIS implementation, so the work done by Dave is very interesting and I would like to learn more about his test case. One thing that would be interesting to find out is whether the performance differences are due to the RTree implementation itself, or due to some other underlying geometry test code, JTS versus something else, or Java versus C. Peter points out that we currently have a search algorithm that does not perhaps make the best use of the graph, since it does not use traversals, but uses recursion and produces a result-set instead of a result stream. It is not completely clear all the ways this might affect performance, but it seems likely that two two cases we should see performance issues, large result sets and deep traversals. Moving the logic to a real traverser, as used in some other indexes we have tried, will resolve those issues. But, it is possible this has nothing to do with Dave's case. So in summary, I think there are a few areas that can account for these differences: - General database performance, and I see others have answered with suggestions on dealing with that. Neo4j is generally very fast, but sometimes needs some tuning. - The RTree implementation itself - I know RTree's are not all equal, so there may be room for general RTree improvements and optimizations. As mentioned we have not put much time into optimizing the RTree very much, so hopefully there is room to move here. - The search algorithm's known issues with not leveraging the Neo4j traversal framework which is a very good, and high performance framework. Peter mentions a new multi-dimensional index I am working on, which I call a 'composite index'. I think this will not out-perform the RTree because it is targeting a very different data domain, primarily point data with large numbers of attributes to be indexed in the same index and queried with complex queries. For purely spatial queries, the RTree should perform much better. But for combined spatial and statistical queries, the new index should perform better. But there are a few tricks we are using to improve the performance of the composite index that might be reused for the RTree, but they require first porting it to the traversal framework, and then fine tuning the traversal performance. So, my preference is to complete the composite index, optimize it and then see if some of those optimizations can be ported to the RTree at the same time as moving the RTree to the traverser framework. Regards, Craig On Fri, Dec 17, 2010 at 6:15 PM, Peter Neubauer < peter.neuba...@neotechnology.com> wrote: > Dave, > Craig is planning to improve the R-Tree index in several ways: > > - introduce streaming instead of set based returns from the traversal > - work on generic multidimensional indexing. > > Craig, what do you say? > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.org - Your high performance graph database. > http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. > > > > On Fri, Dec 17, 2010 at 3:43 PM, Dave Hesketh > wrote: > > I'm currently comparing the performance of R-Tree indexing in Neo4j with > > PostGIS/PostgreSQL. The database and index has been created and searched > in > > Neo4j using Davide Savazzi routines : ShapefileImported and SearchWithin. > > The test dataset is 28,000 points (clustered around San Franciso and > > Vancouver) and the search is for the points within 1000 randomly > generated > > 'circles' (ie 16 sided polygons). On average, each search in Neo4j takes > 4 > > times longer than in PostGIS. Now I know the processing is working > correctly > > I want to progressively increase the number of points to 10,000,000. > > Can anybody give me advice/tips on improving the performance in Neo4j > before > > I start scaling-up the test? At this stage, I am only interested in the > > search performance. > > Neo4j Version: 1.2.M05 > > Environment: Windows 7, i5 64bit processor, quad core 4GB > > Thanks Dave > > ___ > > 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
Re: [Neo4j] Traversal framework
2011/3/15 Craig Taverner > Fantastic. Very nice. > > I guess this was also inspired by Marco's Gremlin and pipes? > > (so the use case is now well understood?) > Absolutely, haven't looked at Marcos pipes code though... be conceptually it's right up that ally. > > On Tue, Mar 15, 2011 at 11:33 AM, Mattias Persson < > matt...@neotechnology.com > > wrote: > > > Already though of that :) behold: > > > > PipeBuilder.fromNode(startNode).into(otherNode(A)) > > .into(traverse(myTraversalDescription)) > > .into(traverse(myOtherTraversalDescription)) > > .into(otherNode(B)); > > > > Or whatever. You can even use other "from", f.ex: fromNode, fromNodes, > > fromPath, fromPaths a.s.o. > > > > Something like that? > > > > 2011/3/15 Craig Taverner > > > > > I like the pipes idea. What I would like to see is nested traversers. > The > > > pipe example below seems to imply single hops at each step, but it > would > > be > > > nicer to allow each step to traverse until it reached a certain > criteria, > > > at > > > which point a different traversal would take over. > > > > > > In the old and current API's it seems to do this you need to create a > > > traversal, iterate over it, and create a new traversal inside the loop. > > > > > > We created a Ruby DSL for nested traversals a year or so ago that looks > a > > > bit like: > > > > > > > > > chart 'Distribution analysis' do > > >self.domain_axis='categories' > > >self.range_axis='values' > > >select 'First dataset',:categories=>'name',:values=>'value' do > > > from { > > >from { > > > traverse(:outgoing,:CHILD,1) > > > where {type=='gis' and name=='network.csv'} > > >} > > >traverse(:outgoing,:AGGREGATION,1) > > >where {name=='azimuth' and get_property(:select)=='max' and > > > distribute=='auto'} > > > } > > > traverse(:outgoing,:CHILD,:all) > > >end > > > end > > > > > > This is quite a complex example, but the key points are the from method > > > which defines where to start a traversal, and the traverse method which > > > defines the traversal itself, with the where method which is like the > old > > > ReturnableEvaluator. > > > > > > Will the new pipes provide something like this? > > > > > > On Tue, Mar 15, 2011 at 9:19 AM, Massimo Lusetti > > > wrote: > > > > > > > On Tue, Mar 15, 2011 at 9:11 AM, Mattias Persson > > > > wrote: > > > > > > > > > I'm positive that some nice API will enter the kernel at some > point, > > > > f.ex. > > > > > I'm experimenting with an API like this: > > > > > > > > > > for(Node node : > > > > > > > > > > > > > > > PipeBuilder.fromNode(startNode).into(otherNode(A)).into(otherNode(B)).nodes()) > > > > > { > > > > > // node will be (3) from the example above > > > > > } > > > > > > > > > > > > > > > I hope I didn't confuse you with all this :) > > > > > > > > Nope, the opposite. Thanks for the clarification and that kind of API > > > > would be a killer feature IMHO. > > > > > > > > It will be even more pleasant to work with neo4j... > > > > > > > > Cheers > > > > -- > > > > Massimo > > > > http://meridio.blogspot.com > > > > ___ > > > > 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 > > > > > > > > > > > -- > > Mattias Persson, [matt...@neotechnology.com] > > Hacker, Neo Technology > > www.neotechnology.com > > ___ > > 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal filters don't add up but replace each other
Hi Morten! Welcome to the mailing list! Good suggestion, I agree. Add an then require-all makes most sense. For "require-any" I think it would be better to have a simple way of composing a filter that accepts a path if any of the participating filters accepts it. I've created a ticket for this in the issue tracking system: https://trac.neo4j.org/ticket/260 Cheers, Tobias On Mon, Sep 13, 2010 at 10:58 AM, Morten Barklund wrote: > All, > > (I am new to this list) > > Looking at the Trarversal framework[1], I assumed that the > TraversalDescription.filter[2] worked similarly to > TraversalDescription.prune[3]. If any prune rejects a path, it is > rejected - similarly I expected, that if any filter excluded a path, > the path was excluded. However, I found that the documentation for the > filter function[4] says "set" where the prune function[5] says "add". > Thus, there is at all times only one filter in effect. > > I think it would make sense to implement a set of filters, and if any > of them rejects a path, it is not included in the output. And maybe > this filtering policy could be explained explicitly to be > require-all-filters-accepting or require-any-filter-accepting (which > are the only two options I can see) similarly to adding the traversel > order policy[6][7]. > > For optimizations it might even be a good idea to give the developer > some way of informing the filter policy which filters are the least > and most restrictive - depending on the policy, one or the other is > best to test first. This could e.g. be a second optional parameter to > TraversalDescription.filter()[4] like PredicatePolicy.RESTRICTIVE, > PredicatePolicy.DEFAULT and PredicatePolicy.INCLUSIVE. It is not > enforced or verified in anyway, but is just a hint for the > optimization of the traversal algorithm. > > Just an idea as it actually caught me by surprise and I had to code > around it (making a predicate decorating a set of predicates). I know > it is easy to code (it took 12 lines in the basic version), but would > make sense to have built-in for consistency - and I'm probably not the > only one who would like it. > > Regards, > Morten Barklund > > [1] http://wiki.neo4j.org/content/Traversal_Framework > [2] > http://wiki.neo4j.org/content/Traversal_Framework#What_to_return.3F_-_filter > [3] > http://wiki.neo4j.org/content/Traversal_Framework#When_to_stop.3F_-_prune > [4] > http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#filter(org.neo4j.helpers.Predicate) > [5] > http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#prune(org.neo4j.graphdb.traversal.PruneEvaluator) > [6] > http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#breadthFirst() > [7] > http://components.neo4j.org/neo4j-kernel/apidocs/org/neo4j/graphdb/traversal/TraversalDescription.html#depthFirst() > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Framework question
Hi, Just to be picky: >> The easiest way to do that in this case is by adding: >> .uniqueness(Uniqueness.NODE_PATH) A co-creator's co-creator can be you. Thus, marko's co-creator's co-creator is marko (amongst other people). In this case, unique on a path would not fail, no? Can you do something like .filter("from two steps ago")? Thanks, Marko. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] How to trim first couple nodes from path in traversal framework?
Hi Brendan, At least over REST API you could do something like this (untested code): "return filter" : { "language" : "javascript", "body" : "position.length() > 0 && position.lastRelationship().hasProperty('timestamp') && position.lastRelationship().getProperty('timestamp') > '1530'" } About performance: if you need to do such a query very often, at least I would do some indexing to make it possible to start the traversal as close as possible. In general: find this kind of chronological, timestamped data series better to be stored in MySQL or similar for queries. Ok, Peter & other guys from Neo, please correct me. ;) Ville 2011/4/7 Brendan Cheng : > Hi, > > I would like to fetch a ending portion of a path where the timestamp > of the relationship match. for example: > > (Node 1)---<2pm>>(Node 3)---<3PM>--->(Node 4)<4PM>--->(Node 64) > > from the above , I only want the subpath starting from Node 4 onward > for the timestamp greater than 3:30PM > > > How could I code evaluator to do it? > > Thanks in advance, > > Brendan > ___ > 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
Re: [Neo4j] Any method to count nodes and relationships in a traversal framework
Bhargav, I'm not sure I am following you. Could you maybe write some pseudo code to highlight the case? Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Wed, Apr 13, 2011 at 7:18 PM, bhargav gunda wrote: > Yeah I know that but I want it in the traverse function itself. Based on the > result again I want to do one more function. So i am trying to find in the > traverse function. > > Thanks & Regards, > G. > > On Wed, Apr 13, 2011 at 3:47 PM, Peter Neubauer > wrote: > >> Of course, >> You can have a count outside your traversal description that for instance >> and Evaluator is updating since it is called for all traversed nodes. This >> is not thread safe but I think it will give you the data you want? >> >> Sent from my phone. >> On Apr 13, 2011 12:32 PM, "Stephan Hagemann" < >> stephan.hagem...@googlemail.com> wrote: >> > Hi Gunda, >> > >> > I believe you are asking fir the same thing I asked for a couple of days >> > ago. Check this thread: >> > >> > http://lists.neo4j.org/pipermail/user/2011-April/007932.html >> > >> > As the discussion shows, this feature is currently not available but >> > probably interesting in a lot of settings. At least for you and me ;) >> > >> > Regards, >> > Stephan >> > >> > >> > On Wed, Apr 13, 2011 at 11:23, bhargav gunda >> wrote: >> > >> >> Respected, >> >> >> >> I would to know that is there any method to count the number of nodes >> and >> >> relationships traversed by the traversal framework. >> >> Like path.length() ---> which gives the depth of the tree. So as like >> that >> >> method is there any direct one? >> >> >> >> For example, >> >> >> >> If a tree consist of several nodes and several relations. And I want to >> >> traverse from a particular node to the end of the tree and the result >> has >> >> only contains certain period of nodes like if the tree traverse 1000 >> nodes >> >> and 1 relationships from a particular node and I want only the >> result >> >> which contains from node 35 to node 70. >> >> So is there any direct method to get the count list of nodes and >> >> relationships. >> >> >> >> Thanks & Regards, >> >> G. >> >> ___ >> >> 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 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
Re: [Neo4j] Getting sorted results from a traversal
Yes the graph structure is relevant, but I am just saying I don't know how the structure can help me in this use case. All that I want is to do a traversal, and then order the expected result. It will be possible If I only use neo4j as a traversal thing, and then another system as a property store, but I think the hole neo4j should be able to deal with that, right? / purbon On 15 July 2011 17:16, Rick Bullotta wrote: > I would think that the graph structure definitely matters, in that there > may be optimizations that can be achieved via indexing/querying vs traversal > and sorting (or a hybrid of the two) depending on the specifics. > > -Original Message- > From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] > On Behalf Of Pere Urbon Bayes > Sent: Friday, July 15, 2011 11:14 AM > To: Neo4j user discussions > Subject: Re: [Neo4j] Getting sorted results from a traversal > > Well the graph structure is not relevant here, I think. The property I > expect to be sorting is on the destination node, so I can do the traversal > and then expect to run the sorting. > > Please, tell me how the data structure can help me to deal with that order, > please? > > / purbon > > On 15 July 2011 17:10, David Montag > wrote: > > > Hi Pere, > > > > Can you elaborate on your graph structure? > > > > Thanks, > > David > > > > On Fri, Jul 15, 2011 at 8:04 AM, Pere Urbon Bayes > >wrote: > > > > > Well, this is great if I want to do all the math in memory, but I > expect > > to > > > do the computation by the db. > > > > > > / purbon > > > > > > On 15 July 2011 16:10, Marko Rodriguez wrote: > > > > > > > Hi Pere, > > > > > > > > To sort you need to have all your results. > > > > > > > > Thus, in Gremlin (and hopefully you can do the mapping to the core > > Neo4j > > > > traverser framework), > > > > > > > > results = [] > > > > g.v(1).out('friend').out('likes') >> results // what my friends like > > > > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by > > > name > > > > > > > > In short, once you have the result of your traversal, you can then > > apply > > > a > > > > comparator to the Collection to sort it as you please --- its just > Java > > > > comparators. > > > > > > > > See ya, > > > > Marko. > > > > > > > > http://markorodriguez.com > > > > > > > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > > > > > > > HI! > > > > > I am on the situation of having to traverse neo4j, and then expect > > the > > > > > resultset returned to be ordered in a certain order. I've been > > > > researching a > > > > > bit over the traversal API, but I did not find anything related to > > > that. > > > > I > > > > > really will appreciate any tip on that!! > > > > > > > > > > BTW > I expect to be possible right?, as we have in relational the > > > > ordering, > > > > > or on redis, etc... > > > > > > > > > > /purbon > > > > > > > > > > -- > > > > > Pere Urbon-Bayes > > > > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > > > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > > > > ___ > > > > > 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 > > > > > > > > > > > > > > > > -- > > > Pere Urbon-Bayes > > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > > ___ > > > Neo4j mailing list > > > User@lists.neo4j.org > > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > > > > > > -- > > David Montag > > Neo Technology, www.neotechnology.com > > Cell: 650.556.4411 > > Skype: ddmontag > > ___ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > -- > Pere Urbon-Bayes > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > ___ > 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 > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal framework suggested change
Maybe instead: INCLUDE_AND_CONTINUE, INCLUDE_AND_PRUNE, EXCLUDE_AND_CONTINUE, EXCLUDE_AND_PRUNE, because "stop" sounds that the traverser is stopping, where it's really just stopping that particular branch, i.e. prunes that branch. Or maybe even: INCLUDE, INCLUDE_AND_PRUNE, EXCLUDE, EXCLUDE_AND_PRUNE, 2010/11/19 David Montag > Fantastic! I have yet to try the implementation out, but I'm positive that > it's an improvement. The only comment I have right now is the use of the > word "SKIP". IMO it is ambiguous with respect to stopping vs excluding. I > prefer EXCLUDE. Will try it out soon. Thanks Mattias! > > David > > On Thu, Nov 18, 2010 at 3:46 PM, Mattias Persson > wrote: > > > 2010/11/18 Mattias Persson > > > > > I just spent less than two hours making this change locally and > > everything > > > works and it generally feels great. Now that I've tried it out myself, > > this > > > way of controlling pruning/filtering feels more awesome. I'll post some > > > examples soon so that you can feedback :) > > > > > > > > Well, examples are maybe unecessary. > > > > class Evaluator > > Evaluation evaluate(Path path); > > > > enum Evaluation > > INCLUDE_AND_CONTINUE > > INCLUDE_AND_STOP > > SKIP_AND_CONTINUE > > SKIP_AND_STOP > > > > class TraversalDescription > > +evaluator(Evaluator) > > -prune(PruneEvaluator) > > -filter(Predicate) > > > > Also I've added lots of useful evaluators in an "Evaluators" class, but > > maybe those should reside in Traversal class instead, however I think > > Traversal class is a little bloated as it is now. > > > > There's the decision whether or not this thing could go into 1.2 or > not... > > For one thing it breaks the API, but then again the > > PruneEvaluator/Predicate (filter) can still be there, mimicing > > Evaluators in the background. Because a PruneEvaluator can be seen as an > > Evaluator which instead of true/false returns > > INCLUDE_AND_CONTINUE/INCLUDE_AND_STOP and a filter can be seen as an > > Evaluator which instead of true/false returns > > INCLUDE_AND_CONTINUE/SKIP_AND_CONTINUE. And you can have multiple > > evaluators > > just as you can with pruners/filters. > > > > This API seems more flexible and this will, in most cases, yield better > > traversal performance as well. > > > > -- > > Mattias Persson, [matt...@neotechnology.com] > > Hacker, Neo Technology > > www.neotechnology.com > > ___ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > -- > David Montag > Neo Technology, www.neotechnology.com > Cell: 650.556.4411 > david.mon...@neotechnology.com > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] allSimplePaths performance
There are several optimizations that the shortest path algo does that allSimplePaths doesn't, f.ex: * Traversal is bidirectional (it starts from the start AND the end simultaneously, although in the same thread) which means that the deeper the traversal goes the more it gains compared to a single directional traversal * It stops on the depth it finds the first hit on Shortest path algo is implemented from scratch to be optimized for just that, but allSimplePaths uses traversal framework which doesn't support bidirectional traversals yet, although there have been some experiments with that too so perhaps soon! 2011/11/24 Peter Neubauer > Petar, > very cool if this worked out. Maybe you could write up a testcase that > verifies that the results are the same, and then put this as a fork to > the graphalgo package? Sounds like a great addition if this works out? > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.org - NOSQL for the Enterprise. > http://startupbootcamp.org/- Öresund - Innovation happens HERE. > > > > On Thu, Nov 24, 2011 at 11:42 AM, Petar Dobrev > wrote: > > Hi guys, > > > > I have a graph of about 2.5M nodes and 8M relationships and I am trying > to > > find all simple paths between two nodes with maximum depth of 8. > > > > The allSimplePaths graph algo works well for maximum depth of 5, but for > 8 > > it runs really long (I didn't even wait for it to finish). So I thought > > it's just that the graph is too complicated and the search operation is > > very expensive. > > > > On the other hand I noticed that shortestPath and pathsWithLength both > work > > fast. So I tried this experiment: > > > > - Run shortestPath and record the shortest length > > - Iterate from the shortest length to max_depth > > - Run pathsWithLength and append the results > > - > > > > And it turns out to be working really well.. much, much faster than the > > allSimplePaths solution, which I found quite baffling, since the latter > > solution should be doing more work to accomplish the same task. > > > > Maybe it's just with my graph, but it's still weird. > > > > Best regards, > > Petar > > ___ > > 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 > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Getting sorted results from a traversal
I would think that the graph structure definitely matters, in that there may be optimizations that can be achieved via indexing/querying vs traversal and sorting (or a hybrid of the two) depending on the specifics. -Original Message- From: user-boun...@lists.neo4j.org [mailto:user-boun...@lists.neo4j.org] On Behalf Of Pere Urbon Bayes Sent: Friday, July 15, 2011 11:14 AM To: Neo4j user discussions Subject: Re: [Neo4j] Getting sorted results from a traversal Well the graph structure is not relevant here, I think. The property I expect to be sorting is on the destination node, so I can do the traversal and then expect to run the sorting. Please, tell me how the data structure can help me to deal with that order, please? / purbon On 15 July 2011 17:10, David Montag wrote: > Hi Pere, > > Can you elaborate on your graph structure? > > Thanks, > David > > On Fri, Jul 15, 2011 at 8:04 AM, Pere Urbon Bayes >wrote: > > > Well, this is great if I want to do all the math in memory, but I expect > to > > do the computation by the db. > > > > / purbon > > > > On 15 July 2011 16:10, Marko Rodriguez wrote: > > > > > Hi Pere, > > > > > > To sort you need to have all your results. > > > > > > Thus, in Gremlin (and hopefully you can do the mapping to the core > Neo4j > > > traverser framework), > > > > > > results = [] > > > g.v(1).out('friend').out('likes') >> results // what my friends like > > > results.sort{a,b -> a.name <=> b.name} // sort resultant vertices by > > name > > > > > > In short, once you have the result of your traversal, you can then > apply > > a > > > comparator to the Collection to sort it as you please --- its just Java > > > comparators. > > > > > > See ya, > > > Marko. > > > > > > http://markorodriguez.com > > > > > > On Jul 15, 2011, at 8:06 AM, Pere Urbon Bayes wrote: > > > > > > > HI! > > > > I am on the situation of having to traverse neo4j, and then expect > the > > > > resultset returned to be ordered in a certain order. I've been > > > researching a > > > > bit over the traversal API, but I did not find anything related to > > that. > > > I > > > > really will appreciate any tip on that!! > > > > > > > > BTW > I expect to be possible right?, as we have in relational the > > > ordering, > > > > or on redis, etc... > > > > > > > > /purbon > > > > > > > > -- > > > > Pere Urbon-Bayes > > > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > > > ___ > > > > 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 > > > > > > > > > > > -- > > Pere Urbon-Bayes > > moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany > > Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 > > ___ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > -- > David Montag > Neo Technology, www.neotechnology.com > Cell: 650.556.4411 > Skype: ddmontag > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Pere Urbon-Bayes moviepilot GmbH | Mehringdamm 33 | 10961 Berlin | Germany Telefon +49 30 616 512 -110 | Fax +49 30 616 512 -133 ___ 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
Re: [Neo4j] Constructing an evaluator that only takes specific nodes from a path
Hi guys, Dario and I are working together on this, so let me clarify, what we want to achieve. An example query in a friend network would be: Retrieve a set of people P that are the direct friends of person A. P should include only those friends that are also on a path between A and another user B. We know how to find paths, but we fail at returning nodes - let alone sets of nodes. The old ReturnableEvaluator seemed to achieve just that: "A client hook for evaluating whether a specific node should be returned from a traverser.", but that is deprecated in the current milestone release. We're unable to find the equivalent functionality with the new Traversal framework. Thanks Stephan On Thu, Apr 7, 2011 at 09:35, Mattias Persson wrote: > Sory, I meant > > INCLUDE_AND_PRUNE >the path will be included in the result set, but the traversal >won't go further down that path, but will continue down other paths > that haven't been pruned > > > > -- > Mattias Persson, [matt...@neotechnology.com] > Hacker, Neo Technology > www.neotechnology.com > ___ > 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
Re: [Neo4j] Traversing all relationship types
Thank you Tobias. This "new" traversal framework looks much more powerful and "fluent" then the traverser I have been playing with so far. The getting started guide should definitively point to it. Best regards, James 2011/5/11 Tobias Ivarsson > There is a tentative new traversal API included in Neo4j that features this > functionality: > > org.neo4j.kernel.Traversal.description().expand( >org.neo4j.kernel.Traversal.expanderForAllTypes( Direction.OUTGOING ) ); > > You can read more about it here: > http://wiki.neo4j.org/content/Traversal_Framework > > Cheers, > Tobias > > On Wed, May 11, 2011 at 9:08 AM, Jean-Pierre Bergamin > wrote: > > > Hello neo4j users > > > > I'm just diving into neo4j and playing around with graph algorithms and > > traversers. > > As a start, I just wanted to traverse the whole graph with all > relationship > > types in the OUTGOING direction. The traverse() method always expects a > > RelationshipType. > > Is there a simpler way to traverse all RelationshipTypes then building up > > an > > array that contains all types and the outgoing direction (as described > here > > http://sujitpal.blogspot.com/2009/06/custom-traverser-for-neo4j.html)? > > > > > > Thanks for the help, > > James > > ___ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > > > > -- > Tobias Ivarsson > Hacker, Neo Technology > www.neotechnology.com > Cellphone: +46 706 534857 > ___ > 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
Re: [Neo4j] DefaultExpander.java replacement?
It should use the factory methods in TraversalFactory instead. How come we exposed DefaultExpander to begin with? Wasn't that class just supposed to be an implementation detail? The fact that it had the weird behavior of expanding all RelationshipTypes when it was empty turns on the "implementation detail" warning light for me. I'm working on refactoring the new traversal framework, so expect things to change (and break) more. It's good that you report this though, since examples should be updated to match the "best practices". The new traversal API is after all not stable yet (since 1.1 has not been released), but I apologize for the inconvenience anyhow. Cheers, Tobias On Wed, Jun 23, 2010 at 9:21 AM, Paddy wrote: > Hi, > > DefaultExpander.java was removed from the latest build > https://trac.neo4j.org/changeset/4590 > > How can i get the example from github working without the DefaultExpander ? > http://github.com/neo4j-examples/java-astar-routing > > DefaultExpander relExpander = new DefaultExpander(); > relExpander.add( RelationshipTypes.ROAD, Direction.BOTH ); > AStar sp = new AStar( graphDb, relExpander, costEval, estimateEval ); > Path path = sp.findSinglePath( NYC.getUnderlyingNode(), > SF.getUnderlyingNode() ); > > thanks > Paddy > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Composable traversals
I see what you mean. At the same time, I find it a funny reason, considering the fact that it is actually _the_ traver framework under the hood. If I am not mistaken, the original traverer is implemented on top of the TraversalDesription framework in org.neo4j.kernel.impl.traversal.OldTraversalWrapper. Anyway, it would be nice to have composable traversals no matter how it is actually implemented. So I am looking forward seeing the results of your work. Niels > Date: Wed, 3 Aug 2011 09:04:08 +0200 > From: matt...@neotechnology.com > To: user@lists.neo4j.org > Subject: Re: [Neo4j] Composable traversals > > Well, I've got none of those concerns really. Just the fact that > TraversalDescription is viewed as "that other" traversal framework makes it > slightly odd to use its interface in the core API. When it will be _the_ > framework, or another one is built upon it (I sometimes more look at it as > an engine which one can build a better API on) something like what you > propose will happen, I'm sure. > > And Node/Relationship/Path should all extend the same traversable interface > then IMHO. But just to add these methods to TraversalDescription will in > effect do the same thing up until the time where Neo4j is less ambivalent > regarding traversal frameworks. > > 2011/8/2 Niels Hoogeveen > > > > > It looks like this does the same I suggested. It's a bit clunkier, but I > > understand you don't want to changed the Node interface. OTOH is there any > > reason not to extend the Node interface, after all it is only one "extends" > > more? Since Nodes are all created in the neo4j-kernel component, there is no > > real reason to maintain strict binary backwards compatibility between > > versions, or do you expect people having projects with two separate > > neo4j-kernel jars having different versions? > > Niels > > > > > Date: Tue, 2 Aug 2011 23:05:17 +0200 > > > From: matt...@neotechnology.com > > > To: user@lists.neo4j.org > > > Subject: Re: [Neo4j] Composable traversals > > > > > > Cool. To not mess around with interfaces too much I'm thinking of having: > > > > > > TraversalDescription#traverse( Node startNode, Node... > > > additionalStartNodes ); > > > TraversalDescription#traverse( Path startPath, Path... > > > additionalStartPaths ); > > > TraversalDescription#traverse( Iterable startPaths ); > > > > > > that would be rather similar, wouldn't it? > > > > > > 2011/7/30 Niels Hoogeveen > > > > > > > > > > > I would be all for it if this could become part of 1.5. > > > > I am willing to put time into this. > > > > > Date: Sat, 30 Jul 2011 11:33:01 +0200 > > > > > From: matt...@neotechnology.com > > > > > To: user@lists.neo4j.org > > > > > Subject: Re: [Neo4j] Composable traversals > > > > > > > > > > Yes, FYI that's the exact thing we've been discussing :) > > > > > > > > > > 2011/7/29 Niels Hoogeveen > > > > > > > > > > > > > > > > > Great, I would much rather see this become part of the core API > > than > > > > have > > > > > > this as part of the Enhanced API. > > > > > > To make things work correctly, one important change to core is > > needed: > > > > The > > > > > > Node interface needs to extends Traverser (the interface in > > > > > > org.neo4j.graphdb.traversal, not the one in org.neo4j.graphdb). > > > > > > This is actually not a big deal. There Traverser interface supports > > > > three > > > > > > methods: > > > > > > Iterator iterator() [return 1 path with 1 element in the > > path, > > > > being > > > > > > the node itself]Iterable nodes() [return an iterable over the > > > > node > > > > > > itself]Iterable relationships() [return an empty > > > > iterable] > > > > > > With that addition, it's not all too difficult to enhance the > > current > > > > > > implementation of Traverser. It only adds one more iteration level > > over > > > > the > > > > > > current implementation. Instead of having one start node, we now > > have > > > > > > multiple start paths. When returning values from the Traverser, the > > > > start > > > > > > p
[Neo4j] How to trim first couple nodes from path in traversal framework?
Hi, I would like to fetch a ending portion of a path where the timestamp of the relationship match. for example: (Node 1)---<2pm>>(Node 3)---<3PM>--->(Node 4)<4PM>--->(Node 64) from the above , I only want the subpath starting from Node 4 onward for the timestamp greater than 3:30PM How could I code evaluator to do it? Thanks in advance, Brendan ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Traversal Framework question
Hi, > Traversal.description() > .depthFirst() > .relationships(RelationshipTypes.CREATED, Direction.BOTH) > .traverse(developer).nodes() To be clear, a co-creator is someone is who has created the same things as you and who is not you. Thus, you need to go outgoing CREATED, then incoming CREATED, then you need to make sure that the vertex you land at is not the one you left from -- thus, you need to filter the originating vertex. See ya, Marko. http://markorodriguez.com ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] NODE_PATH Uniqueness in Neo4j traversals
Hi folks, just commited some example code to show the use of Uniqueness.NODE_PATH in the Neo4j traversal framework in order to return paths that share nodes. http://docs.neo4j.org/chunked/snapshot/examples-uniqueness-of-paths-in-traversals.html Enjoy! Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user