Simple, standard TreeNode interface and traversals

[GoogleCodeExporter]

As a suggestion; I find it quite useful!

/**
 * returns a depth-first iterator for a tree of T
 * @param f a function that returns the children of node of the tree
 * @param root The root element of the tree
 * @return
 */
public static <T> Iterable<T> walk(final T root,
    final Function<? super T, ? extends Iterable<? extends T>> getChildren) 
{
  final Function<T, Iterable<? extends T>> walkFunc =
      new Function<T, Iterable<? extends T>>() {
    public Iterable<? extends T> apply(final T from) {
      return walk(from, getChildren, this);
    }
  };
  return walk(root, getChildren, walkFunc);
}

private static <T> Iterable<T> walk(final T root,
  final Function<? super T, ? extends Iterable<? extends T>> getChildren,
    final Function<T, Iterable<? extends T>> walkFunction) {
  return Iterables.concat(
    Collections.singleton(root),
    Iterables.concat(
      Iterables.transform(
        getChildren.apply(root),
        walkFunction)));
}

And a shortcut in case the nodes implement Iterable:

@SuppressWarnings("unchecked")
public static <T extends Iterable<T>> Iterable<T> walk(final T root) {
  return walk(root, Functions.identity(), WalkIterableFunction.INSTANCE);
}

@SuppressWarnings("unchecked")
private static enum WalkIterableFunction implements Function {
  INSTANCE;

  public Object apply(final Object from) {
    return walk(from, Functions.identity(), this);
  }
};

Original issue reported on code.google.com by jvdne...@gmail.com on 25 May 2009 at 2:34

[GoogleCodeExporter]

Maybe it would be useful to have a Tree interface 

Tree<T> {
  T getParent();
  Collection<T> getChildren();

}

also see issue 187

Original comment by zeitlin...@gmail.com on 10 Jun 2009 at 7:46

[GoogleCodeExporter]

Tree's are inherently recursive by definition. Each child of a node a Tree 
itself,
with or without children nodes. As a result, the above interface wouldn't 
really be
expressive enough (especially as the "key" value for the is not considered).

The next point to consider is that tree traversal can consist of pre-order, 
in-order
and post-order traversals, not to mention breadth-first.

Original comment by gpampara@gmail.com on 22 Jul 2009 at 4:02

[GoogleCodeExporter]

I have always very much wanted to have a standard TreeNode<T> interface. I will 
give 
it more thought when I can. I think that is a far better approach than the 
Function-
based one.

The interface _might_ end up needing to be something like this

  interface TreeNode<T extends TreeNode<T, C>, C extends Iterable<T>> {
    // optional; returns null if root
    TreeNode<T, C> parent();

    C children();
  }

This way, different types of trees can use different types of collections 
(list, set, 
multiset, what-have-you).  It's a little confusing to grasp at first though.  
We'll 
see what shakes out.

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:41

• Changed title: Simple, standard TreeNode interface and traversals
• Changed state: Accepted
• Added labels: post-1.0

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:45

• Added labels: Milestone-Post1.0
• Removed labels: post-1.0

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:57

• Added labels: Type-Enhancement

[GoogleCodeExporter]

You don't really need a defined data structure to implement the most common 
traversals (breadth, pre/post-
order, and full depth-first - tracking start/finish times), as the original 
poster points out. I would implement 
it differently (see below), but the principle holds.

That's not to say there isn't a good use case for a tree data structure, just 
that those traversals don't require 
it. If adding both things, it would be a good idea for some static utils 
methods that simplify the common use 
case when you do want to traverse an explicit tree structure instead of the 
functional way. There's no reason 
the API can't be expressive enough for both strategies.

Additionally, if going down that data structure road, you may seriously want to 
consider keeping it consistent 
with the Collections model of data structures being containers for 
user-supplied objects. In that light, I think 
TreeNode is inappropriate for the same reason that ListNode would be. You don't 
ask the elements of a List 
for previous/next elements, you ask the List data structure itself.

One drawback to this is that it can be very difficult to maintain the invariant 
of being a Tree while building 
one. My mutable structures tend to be either general graphs or forests, with an 
ability to get tree views (tree 
rooted at a given forest node, e.g.).

As an aside, I'm in the process of a complete overhaul of my own graph library, 
having been inspired by your 
excellent work with GCL - in particular the realization of how much readability 
can improve an API (and 
having written it pre-generics). This is a working concept for how traversals 
would look (not compilable, 
poorly formatted, no method bodies - keeping it terse). For everyone out there, 
feel free to use any ideas you 
like.

public interface Step< E >
{
  E from();
  E to();
}

public interface PruningIterator< E > extends Iterator< E >
{
  // Don't explore beyond the last object returned by next()
  public void prune();
}

public class Steps
{
  // convenience methods, so users don't have to explicitly create Steps

  public static Iterator< Step< E > > wrap
    ( E from,
      Iterator< E > toIterator )

  public static Function< E, Iterator< Step< E > > > wrap
    ( Function< E, Iterator< E > > adjacencyFunction )
}

public class Traversals
{
  public static PruningIterator< Step< E > > preOrder
    ( E start,
      Function< E, Iterator< Step< E > > > adjacencyFunction )

  // can't prune() a post-order traversal
  public static Iterator< Step< E > > postOrder
    ( E start,
      Function< E, Iterator< Step< E > > > adjacencyFunction )

  public static Iterator< Step< E > > topologicalSort
    ( Iterator< E > nodeIterator,
      Function< E, Iterator< Step< E > > > adjacencyFunction )

  // etc. plus similar methods taking just Function< E, Iterator< E > > and doing the wrapping for you.
}

All of these can be implemented using stacks, no recursion, without too much 
difficulty. The primary reason 
for the Step interface is that you often want to know from which node you 
traversed, and this information
would not otherwise be available.

I can use this same API to traverse the file system, up a tree instead of down, 
or any other graph-like 
structure, without creating an explicit data structure to do it. All I need to 
define is that function which takes 
a node and returns an iterator of adjacent nodes. Not creating an actual data 
structure (like a Collection) is 
useful when the backing data is huge, and perhaps not even queryable in a 
global way. Having to implement 
things like size() can really be a pain sometimes, and at work we've often just 
decided to throw an 
UnsupportedOperationException instead.

At any rate, a work in progress, but that's the general flavor. The edges in my 
data structures also contain 
user-defined objects, so I need to allow for that without polluting the rest of 
the API. Still working through 
the implications of that.

Original comment by ray.a.co...@gmail.com on 2 Oct 2009 at 11:35

[GoogleCodeExporter]

I recently needed a version of my walk iterable from above with a possibility 
to get 
the path of a node to the root. So I needed a TreeNode interface, without 
needing the 
children (although it could easily be added).

I'm attaching the relevant bits (thrown together so it would compile, but i did 
not 
spend too much time on it so please excuse for errors). Scroll down for an 
example in 
printWalkWithParentsTest()

Original comment by jvdne...@gmail.com on 10 Dec 2009 at 5:34

Attachments:

• Ita.java

[GoogleCodeExporter]

This issue has been moved to the Guava project (keeping the same id number). 
Simply replace 'google-collections' with 'guava-libraries' in your address 
bar and it should take you there.

Original comment by kevinb@google.com on 5 Jan 2010 at 11:09

• Changed state: Moved