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

From: Nicolas Pouillard <[email-masked]>
Date: Mon, 22 Feb 2010 08:04:20 -0800 (PST)

On Mon, 22 Feb 2010 10:54:19 -0500, "W. Trevor King" <[email-masked]> wrote:
> On Mon, Feb 22, 2010 at 06:00:53AM -0800, Nicolas Pouillard wrote:
> > ...
> > libbe.util.graph.CyclicGraphError: cycle detected:
> >   Sun, 21 Fe  Reinier Lamers    [darcs-users] [patch167] Reintroduce UTF-8 tagging...
> >   Sun, 21 Fe  Reinier Lamers    [darcs-users] [patch167] Reintroduce UTF-8 tagging...
> > 
> > Actually the mentioned mail have Message-ID equals to In-Reply-To.
> 
> Hah.  That is great :p.
> 
> > While I'm reporting this issue and thus won't get any such messages,
> > it would be "nice" to have a more robust behavior in case of
> > cycles. In particular these auto-cycles can be just ignored.
> 
> Added a 'correct-mailbox.py' script that tries to handle all of these
> (and probably more in the future) issues in one shot.

Tried it (correct-mailbox.py) on a bigger part of my mail box and got:

libbe.util.graph.CyclicGraphError: 17 of 1000 elements not reachable from tips

-- 
Nicolas Pouillard
http://nicolaspouillard.fr
_______________________________________________
Sup-devel mailing list
[email-masked]
http://rubyforge.org/mailman/listinfo/sup-devel

---

From: "W. Trevor King" <[email-masked]>
Date: Thu, 3 Jun 2010 06:21:10 -0400

On Thu, Jun 03, 2010 at 12:27:04AM -0400, Rich Lane wrote:
> I'm not yet convinced that supporting multiple parents is worth
> the complexity. How often do you get mails like this?

I don't get mails with multiple in-reply-tos, but I send them ;).  I
*do* get mails with in-text references to multiple messages.  For some
mailing lists that I care about (be-devel), I go through and adjust
in-reply-to so that it matches the in-text references.

I think such graphs would be a nice interface to mailing lists, which
gain members not familiar with the lists history.  Browsing a curated
list, finding the critical background for a particular message would
be trivial.

> What mail clients have UI for replying to multiple messages?

In Mutt, you can tag a bunch of messages, and then ;g to reply-to-all
the tagged messages at once.  I started doing this to get the previous
text from all the messages included in my reply, so I expect this sort
of thing does occur occasionally in the wild.

> I'd have to fake up some messages to actually see the full DAG
> support in action, so could you post a screenshot of your code
> viewing a thread where the new display helps?

Attached is a small graph showing two related threads about
bzr+windows.  The multiparent replies allow responses like Matt's,
  "we discussed this last year" message.

-- 
This email may be signed or encrypted with GPG (http://www.gnupg.org).
The GPG signature (if present) will be attached as 'signature.asc'.
For more information, see http://en.wikipedia.org/wiki/Pretty_Good_Privacy

My public key is at http://www.physics.drexel.edu/~wking/pubkey.txt
_______________________________________________
Sup-devel mailing list
[email-masked]
http://rubyforge.org/mailman/listinfo/sup-devel

---

From: Nicolas Pouillard <[email-masked]>
Date: Sun, 21 Feb 2010 09:52:28 -0800 (PST)

On Sun, 21 Feb 2010 08:42:49 -0500, "W. Trevor King" <[email-masked]> wrote:
> On Sun, Feb 21, 2010 at 08:38:35AM +0200, Tero Tilus wrote:
[...]
> > Have a pointer to code?
> 
> My code is currently stuffed into an in-transition BE project, but it
> should be easy to separate.  Grab the whole repo with Bazaar:
>   bzr branch http://www.physics.drexel.edu/~wking/code/bzr/be.mailing-list
> Graphing module is libbe/util/graph.py.  My very minimal browser is
> misc/mailbox-tools/mailgraph.py.  Set up the BE version file with
>   cd be.mailing-list
>   make libbe/_version.py
> and run the browser with
>   misc/mailbox-tools/mailgraph.py *.mbox
> Press 'h' for help.

I've tried your program on a 100 messages mbox and got this:

missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
missing Message-ID: <HIDDEN>
Traceback (most recent call last):
  File "misc/mailbox-tools/mailgraph.py", line 194, in <module>
    app.run()
  File "/home/ertai/w/a/be.mailing-list/libbe/ui/util/curses_framework.py", line 487, in run
    return curses.wrapper(self._run, list(keys))
  File "/usr/lib/python2.6/curses/wrapper.py", line 44, in wrapper
    return func(stdscr, *args, **kwds)
  File "/home/ertai/w/a/be.mailing-list/libbe/ui/util/curses_framework.py", line 494, in _run
    self._run_init(stdscr)
  File "/home/ertai/w/a/be.mailing-list/libbe/ui/util/curses_framework.py", line 520, in _run_init
    window.initialize()
  File "/home/ertai/w/a/be.mailing-list/libbe/ui/util/curses_framework.py", line 172, in initialize
    self._setup_buffer()
  File "misc/mailbox-tools/mailgraph.py", line 51, in _setup_buffer
    self._buffer = self._graph.ascii_graph().splitlines()
  File "/home/ertai/w/a/be.mailing-list/libbe/util/graph.py", line 379, in ascii_graph
    for row,node in self.graph_rows():
  File "/home/ertai/w/a/be.mailing-list/libbe/util/graph.py", line 367, in graph_rows
    self.topological_sort()
  File "/home/ertai/w/a/be.mailing-list/libbe/util/graph.py", line 355, in topological_sort
    % (orig_len - final_len, orig_len))
libbe.util.graph.CyclicGraph: 3 of 100 elements not reachable from tips

Best regards,

---

From: "W. Trevor King" <[email-masked]>
Date: Mon, 22 Feb 2010 11:48:39 -0500

> libbe.util.graph.CyclicGraphError: 17 of 1000 elements not reachable from tips

I've moved the correct-mailbox.py/mailgraph.py bugs portion of this
thread off-list, since they are not sup-related.  Feel free to send
more bugs directly to me.

On Sun, Feb 21, 2010 at 08:38:35AM +0200, Tero Tilus wrote:
> I would love to see sup being able to do something usefull with
> multiple parent messages.

Any more comments along this line? ;).  I don't know much ruby yet,
but I can probably patch my graph code into sup if someone can tell me
where it should go (sup/graph.rb and sup/modes/thread-index-mode.rb?).

---

From: "W. Trevor King" <[email-masked]>
Date: Sun, 21 Feb 2010 08:42:49 -0500

On Sun, Feb 21, 2010 at 08:38:35AM +0200, Tero Tilus wrote:
> > 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.

It's a snip from the full list sorted by date, so there are a bunch of
through-lines when threads went out of fasion for a while ;).
If you sorted by oldest parent date first, you would probably have
fewer.

> 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?

  *-\-\-\-\-\-\-\-\ Fri May 16  Chris Ball  how to use the git backend?
  r | | | | | | | | Fri May 16  Christian Garbs  how to use the git backend?
  r-/ | | | | | | | Wed May 14  Jelmer Vernooij  [MERGE] Two tiny fixes
  r---/ | | | | | | Mon Apr 21  Ben Finney  [MERGE] Manual page for 'be' command.
  *-----/ | | | | | Mon Apr 21  Ben Finney  [MERGE] Makefile: add skeleton 'build' ..
  r       | | | | | Mon Apr 21  Ben Finney  [MERGE] Makefile: Add with 'clean' targ..
  *-------/ | | | | Fri Apr 18  Ben Finney  [MERGE] Add bug 00f (now fixed)
  r         | | | | Fri Apr 18  Ben Finney  [MERGE] Updated GPLv2 text and FSF addr..
  r---------/ | | | Fri Apr 18  Ben Finney  [MERGE] Bugs-Everywhere-Web/libbe: Fix ..
  *-----------/ | | Mon Apr 14  [email-masked]  [PATCH] Bugs-Everywhere-Web identity
  r             | | Mon Apr 14  [email-masked]  [PATCH] Bugs-Everywhere-Web identity
  r-------------/ | Mon Apr 14  [email-masked]  [MERGE] update about
  r---------------/ Mon Apr 14  [email-masked]  [MERGE] Bugs-Everywhere-Web works with .

Where Chris' mail was "...  I also merged patches from...".  Another
case that comes up is that a user will post with a problem that's been
discussed before, and we reply and link to the previous discussion.
These are both software mailing list specific though.  I don't have
examples from other settings.

> > 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.  ;)

My infant be.mailing-list branch (link below) is an attempt to address
this by leaving the spaghetti alone, and attaching entry-point tags
wherever you feel the subject makes a significant shift.  Really, you
*want* the spaghetti, since its human-generated cross-linking that
reduces duplication-of-search effort.  Assuming you trust the human in
question ;).

> > 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?

The graph module is pretty clean, but the others are not ;).

> multiple parent messages.

If you want to use this in the wild, you'll need to figure out how to
integrate multiple-parent In-Reply-To\s with your current JWZ
threading which only uses References.  From RFC 2822, section 3.6.4:

   Note: Some implementations parse the "References:" field to display
   the "thread of the discussion".  These implementations assume that
   each new message is a reply to a single parent and hence that they
   can walk backwards through the "References:" field to find the parent
   of each message listed there.  Therefore, trying to form a
   "References:" field for a reply that has multiple parents is
   discouraged and how to do so is not defined in this document.

On major benefit of JWZ-threading is that it's self-healing.  If some
users don't thread their replies, you can thread them locally and
reply, fixing the threading for others recieving your reply.  The
In-Reply-To alternative is to reply to both the broken message and the
original thread:
  *-\ fixing response
  | r broken message
  * original thread
which is needlessly uglier than
  * fixing response
  * broken message
  * original thread
if it is clear from the content of the broken message that it really
was a reply.

I think it would be best to leave view-graph and
browse-to-other-parent as peripheral options, to be used on curated
archives where you can trust In-Reply-To to be RFC 2822 compliant
(e.g. the eventual be.mailing-list ;).

---

From: Nicolas Pouillard <[email-masked]>
Date: Tue, 23 Feb 2010 02:29:20 -0800 (PST)

> where it should go (sup/graph.rb and sup/modes/thread-index-mode.rb?).

I find that this is a nice idea. If it can be done without changing
to much of the current code of sup, and without performance loss for those
who don't want to use it, I think it could be a nice addition.

Best regards,

---

From: "W. Trevor King" <[email-masked]>
Date: Sun, 21 Feb 2010 14:29:47 -0500

> missing Message-ID: <HIDDEN>

You probably had a bunch of emails in you mbox with
  In-Reply-To: <HIDDEN>
But no message(s) with
  Message-ID: <HIDDEN>

If mailgraph.py can't find the parent message, it prints that warning
and continues, so you can probably just ignore it.

> libbe.util.graph.CyclicGraph: 3 of 100 elements not reachable from tips

You have a cyclic reference in your mbox somewhere.  I've added some
really inefficient code to actually *find* cycles (rather than just
deducing their existence) and print useful error messages.  Pull my
current repo and try:

  $ misc/mailbox-tools/mailgraph.py --check-for-cycle *.mbox

Then you'll have to go through the mbox (or a copy) by hand and break
the cycle.  The check only finds one cycle at a time, so you may need
to iterate...

---

From: "W. Trevor King" <[email-masked]>
Date: Mon, 22 Feb 2010 10:54:19 -0500

Hah.  That is great :p.

---

From: Rich Lane <[email-masked]>
Date: Thu, 03 Jun 2010 00:27:04 -0400

Excerpts from W. Trevor King's message of 2010-05-25 14:50:27 -0400:
> I got some good feedback from Nicolas Pouillard on the Python tidbit I
> posted, but after waiting optimisticly for some enterprising Rubist to
> port it to Ruby and merge it into Sup, I've finally taught myself
> enough Ruby to do it myself ;).  Here's DAG-supporting Sup (+ a few
> glaring documentation updates)

Thanks for the doc updates, I've applied them to master.

I'm not yet convinced that supporting multiple parents is worth
the complexity. How often do you get mails like this? What mail clients
have UI for replying to multiple messages? I'd have to fake up some
messages to actually see the full DAG support in action, so could you
post a screenshot of your code viewing a thread where the new display
helps?

> We could also resurect the old indentation-style display in the thread
> viewer, if people dislike my tig-style ascii graph.

Actually, I think the tig-style display is very interesting and could be
useful even without the generic graph support.
_______________________________________________
Sup-devel mailing list
[email-masked]
http://rubyforge.org/mailman/listinfo/sup-devel

---

From: Tero Tilus <[email-masked]>
Date: Sun, 21 Feb 2010 08:38:35 +0200

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.

 .........
 | *-\     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'.

Have a pointer to code?

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

---

From: "W. Trevor King" <[email-masked]>
Date: Thu, 18 Feb 2010 06:49:44 -0500

Hey all,

I thought I'd ask this on sup-devel, since you guys have been thinking
about email organization and "a better mutt" sounds pretty awesome ;).
Sorry if it's too far off topic.

Since email can have multiple parents [1], why does everyone make
threads trees rather than directed, acyclic graphs (DAGs)?  DAGs seem
really common for version control systems, and completely missing for
email clients, even though the inheritence structure is identical.
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.

On a sup-specific level, problems with the graph (vs. tree) is that it
may make threads too 'sticky'.  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.  Perhaps you
will want to leave the sup guts unchanged, tack on an optional graph
view, and add an 'other-parents' option when browsing from messages
with multiple parents.

Thoughs?

Thanks,
Trevor

[1] RFC 2822, section 3.6.4, http://www.faqs.org/rfcs/rfc2822.html

  The "In-Reply-To:" field will contain the contents of the
  "Message-ID:" field of the message to which this one is a reply (the
  "parent message").  If there is more than one parent message, then
  the "In-Reply-To:" field will contain the contents of all of the
  parents' "Message-ID:" fields.

---

From: Nicolas Pouillard <[email-masked]>
Date: Mon, 22 Feb 2010 06:00:53 -0800 (PST)

> the cycle.  The check only finds one cycle at a time, so you may need

I get:

...

While I'm reporting this issue and thus won't get any such messages, it would be
"nice" to have a more robust behavior in case of cycles. In particular these
auto-cycles can be just ignored.

---

From: "W. Trevor King" <[email-masked]>
Date: Tue, 25 May 2010 14:50:27 -0400

http://www.physics.drexel.edu/~wking/code/git/git.php?p=sup.git

I haven't done any benchmarking vs the tree-threading code, but if it
turns out to be too slow, we can always use:
  if @graph_thread
    ...general...code...
  else
    ...old...tree...code...
  end
for bottleneck methods.

Cheers,
Trevor