From: Charles Lindsey (chl@clerew.man.ac.uk)
Date: Mon Mar 29 2004 - 08:49:27 CST
In <4065FA65.4050308@erols.com> Bruce Lilly <blilly@erols.com> writes:
>Charles Lindsey wrote:
>> Indeed so. But the whole point is that it is not necessary to construct
>> the entire dependency graph in order to provide an acceptable presentation
>> of articles within a newsreader.
>It is if the definition of "acceptable" includes conformance to
>reality rather than some arbitrary presentation.
What is "reality"?
The whole point is that, if followups to multiple precursors are going to
be recognized, then what you have is a DAG rather than a tree. In which
case, reading agents are going to have to display that DAG in some manner.
So what is a reasonable way to display a DAG, especially it there are lots
of bits inside it that are purely tree-like?
Displaying a tree is easily done (you can convey it exactly by proper
indentation). The least you can do to it is to flatten it following some
depth-first walk.
Displaying a DAG is hard. There is no single "best" way to do it. You can
certainly flatten it, but there is no "best" way to do that either. And
flattening it (even though that may turn out to be the only viable method)
loses all structure of any genuine sub-trees within it, which would be a
pity.
So the proper way to proceed would be to consider some typical threads
that might occur and to look at ways of presenting them. Compare the
various methods. Is there one which clearly is the best in all cases (I
would rather doubt it)? Is there a compromise that does an acceptable job
most of the time? How, for example, would you present the example that you
gave?
When you know how you want to present the information, then you can decide
whether or not you actually need the complete dependency graph (which is
expensive to obtain), or whether some lesser (and cheaper) description
will work nearly as well (given that the "perfect" presentation method
does not exist). My expectation is that the additional expense of
obtaining the full graph will not provide sufficient benefit to justify
it - certainly not so if the best viable presentation turns out to be
flat.
-- Charles H. Lindsey ---------At Home, doing my own thing------------------------ Tel: +44 161 436 6131 Fax: +44 161 436 6133 Web: http://www.cs.man.ac.uk/~chl Email: chl@clerew.man.ac.uk Snail: 5 Clerewood Ave, CHEADLE, SK8 3JU, U.K. PGP: 2C15F1A9 Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5