> Date: Tue, 2 Jul 2002 00:35:46 -0700 (PDT) > From: Phil Carmody <[EMAIL PROTECTED]> > > If the relation is a partial order, and reflexive, then the following > needs changing: > <<< > There may be no possible order of nodes that will satisfy the input > line requirements (the nodes contain a cycle). > In this case, the program shall exit with > a non-zero exit code. > >>> > > because > a b > b a > is satisfied by > a > b > and > b > a > in every model. > > i.e. It is explicitly _not_ the case that "no possible order of nodes > [...] will satisfy the input line requirements".
Now you're being clever. It's true that if the input is a partial order, you can conclude that a=b; but why do you output the element twice, then? If you insist on proper mathematical terms, the input is not a partial order. It's a subset of a preorder, and the implied task is first to find a smallest reflexive partial preorder that includes it (closure), and the smallest set it can be a preorder on (which are both unique). Then you either find a cycle, or conclude that the preorder is in fact a proper partial order. In the latter case, you find some linear order that respects it (of which there's at least one), and print it. Doing it like that won't win the tournament, of course. Coming up with the right data structure is the whole fun of graph algorithms. Lars Mathiesen (U of Copenhagen CS Dep) <[EMAIL PROTECTED]> (Humour NOT marked)
