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 <matt...@neotechnology.com>
> 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 <hilmiyildi...@gmail.com>
>
> 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 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 <tobias.ivars...@neotechnology.com>
>> Hacker, Neo Technology
>> www.neotechnology.com
>> Cellphone: +46 706 534857
>> _______________________________________________
>> Neo mailing list
>> User@lists.neo4j.org
>> https://lists.neo4j.org/mailman/listinfo/user
>> _______________________________________________
>> Neo 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
_______________________________________________
Neo mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
