Re: [sup-devel] email threading - tree vs. graph

[Tero Tilus <tero@tilus.net>]

W. Trevor King, 2010-02-18 13:49:
> Since email can have multiple parents [1], why does everyone make
> threads trees rather than directed, acyclic graphs (DAGs)?

Trees are easier to render and multi-parent messages are a rare
exception, not the rule.  Heck, many widely used mailclients are
totally missing the option to reply to many messages at once.

> DAGs seem really common for version control systems, and completely
> missing for email clients, even though the inheritence structure is
> identical.

Failing to visually present merges would be far more fundamental
failure than failing to present multi-parent mails.

> For example, here's a slice from the recent be-devel list as a graph:
>   ...............
>   | *-|-\     | | Mon Jan 25  W. Trevor King  Re: Project releases
>   | * | |     | | Sat Jan 23  Gianluca Montecchi  Re: Project releases
>   | | | | t   | | Sat Jan 23  Gianluca Montecchi  Re: Project releases
>   | *-|-|-|-\ | | Fri Jan 22  Ben Finney  Re: Project releases
>   | | | * | | | | Fri Jan 22  W. Trevor King  Re: Project releases
>   | | | *-/ | | | Thu Jan 21  Ben Finney  Re: Project releases
>   | * | |   | | | Thu Jan 21  Gianluca Montecchi  Re: Project releases
>   *-|-|-/   | | | Thu Jan 21  W. Trevor King  Re: Project releases
>   ...............
>          ^--- inheritence graph.
> You can see that Ben's Fri message and my Mon message both have two
> parents.

Honestly.  That took fair bit of staring and prolly wouldn't have
opened to me without your explanation.  :) But that might only be due
to the external noise in the graph.  Without those extra through-lines
it looks a bit more readable.

 .........
 | *-\     Mon Jan 25  W. Trevor King  Re: Project releases
 | * |     Sat Jan 23  Gianluca Montecchi  Re: Project releases
 | | | t   Sat Jan 23  Gianluca Montecchi  Re: Project releases
 | *-|-|-\ Fri Jan 22  Ben Finney  Re: Project releases
 | | * | | Fri Jan 22  W. Trevor King  Re: Project releases
 | | *-/ | Thu Jan 21  Ben Finney  Re: Project releases
 | * |   | Thu Jan 21  Gianluca Montecchi  Re: Project releases
 *-|-/   | Thu Jan 21  W. Trevor King  Re: Project releases
 .........

> On a sup-specific level, problems with the graph (vs. tree) is that
> it may make threads too 'sticky'.

I can't really see how this would lump significantly more mail into
one thread.  Do you have examples of otherwise disconnected trees
connected only by multi-parent mail?

> With your thread-centric approach, you'll want to break threads when
> the topic mutates too far from the original, and that could be
> difficult for meshy-graphs.

Topic-mutation happens within a tree as well.  And pruning (boy I've
wanted to do that quite a few times, I notice) afaik essentially
requires scanning (and potentially modifying) all the messages in the
thread.  Technically I don't see how this is very different.
"Politically" it however could be.  If your mail graph is one big lump
of spaghetti, it might be difficult to decide where to cut it off.  ;)

> On an implementation level, I've got the above graph browser going
> in python/curses, so it should be easy to port to ruby/curses.

Have a pointer to code?

I would love to see sup being able to do something usefull with
multiple parent messages.

-- 
Tero Tilus ## 050 3635 235 ## http://tero.tilus.net/
_______________________________________________
Sup-devel mailing list
Sup-devel@rubyforge.org
http://rubyforge.org/mailman/listinfo/sup-devel