Two things

1st thing: what ever happened to the tsort cycle problem?  I remember
people stating that longest path was NP-hard, and then giving up.
Are we certain that it is NP-hard?  Can Tarjan's algorithm be used
(more later)

2nd thing: I'm looking for hints on setting up a CVS repository for a
collection of source code contributed to by several people at 4 (or
more) different sites distributed internationally.
(more later)




Ok, now that the table of contents is over... here's the long version.
Thing 1:
While looking into some stuff for my compiler project here at UT, I
encountered the following statement in a book by Michael Wolfe...

  "[Tarjan's Algorithm] takes linear time and space with respect to the
  number of arcs and nodes in the dependence graph.  Each maximal cycle
  in the dependence graph will be identified, either as a
  multi-statement cycle or a single statement self-cycle.  This allows
  each cycle to be attacked individually to either classify it as a
  known type of recurrence or to try to break the cycle"

I'm not sure if the self cycles are relevant to the tsort problem.
Anyway, this algorithm is alledgedly O(v+e) and presumably would be
adequate for tsort?  The complete reference is given as:

  Tarjan, R. "Depth-First Search and Linear Graph Algorithms," SIAM
  Journal of Computing, Vol 1, No 2, pp. 146-160, June 1972.

I've not looked at this algorithm to figure out exactly what's going
on.   Perhaps the explanation is that finding the largest cycle on a
*weighted* graph is NP-hard, but that finding the largest cycle on a
graph with unit edge weights is polynomial?  The dependence graph for
tsort is unweighted, yes?


Thing 2:
Researches at Oregon, Indiana, Texas and Rennes France (and possibly
others too, soon) are working on a compiler toolkit that does things
like dependence analysis, data flow analysis and the like.  It seems
like it would be swell to have CVS keep track of the different
versions, and allow us to sync up periodically with the latest and
greatest stuff from the remote sites.

Anyone have any suggestions about how to go about doing this?  One
possibility would be to have a main trunk, and a distinct revision
branch for each of the sites... e.g. a Texas branch, an Oregon branch,
etc.  

Let's say that I've added some new features into foo.c, and have made
three "cvs commits" on the Texas branch.  Then a colleague in Rennes
has a bug fix that I'd like to incorperate.  What is the best way to
ship me a diff?  "cvs rdiff MAIN RENNES foo.c" to get the diffs from
his bug fix, then mail me those diffs, and let me try and merge them?

Any experience from the NetBSD configuration management effort that
might shed some light...


Also, a real naive question... how is the NetBSD CVS tree set up with
file permissions.  Is there a group of developers that have write
access to the CVS repository, and each of these developers can "cvs
commit"?

Thanks,

Craig


------------------------------------------------------------------------------