17f1ccc5bSespie#!/usr/bin/perl 27f1ccc5bSespie 37f1ccc5bSespie# Written by Marc Espie, 2001. 47f1ccc5bSespie# Public domain 57f1ccc5bSespie 67f1ccc5bSespie%order=(); 77f1ccc5bSespie 8*ba92bf80Sespie%exception=(); 9*ba92bf80Sespie%ok=(); 10*ba92bf80Sespie 11*ba92bf80Sespie 127f1ccc5bSespieopen(SORTED, shift) or die "No sorted output\n"; 137f1ccc5bSespiewhile(<SORTED>) { 147f1ccc5bSespie chomp; 15*ba92bf80Sespie while (m/^tsort: cycle in data/) { 16*ba92bf80Sespie @list = (); 17*ba92bf80Sespie while (<SORTED>) { 18*ba92bf80Sespie chomp; 19*ba92bf80Sespie last if m/^tsort: cycle in data/; 20*ba92bf80Sespie last unless m/^tsort:\s+/; 21*ba92bf80Sespie push(@list, $'); 22*ba92bf80Sespie } 23*ba92bf80Sespie for $i (1 .. @list) { 24*ba92bf80Sespie $exception{$list[$i-1].' '.$list[$i % @list]} = 1; 25*ba92bf80Sespie } 26*ba92bf80Sespie $break{$list[1]} = 1; 27*ba92bf80Sespie } 287f1ccc5bSespie $order{$_} = $i++; 297f1ccc5bSespie} 307f1ccc5bSespieclose(SORTED); 317f1ccc5bSespie 32*ba92bf80Sespie@pairs=(); 33*ba92bf80Sespie 347f1ccc5bSespieopen(PAIRS, shift) or die "No pairs\n"; 353a58f8dfSespiewhile (<PAIRS>) { 363a58f8dfSespie chomp; 373a58f8dfSespie push(@pairs, split(/\s+/, $_)); 383a58f8dfSespie while (@pairs >= 2) { 39*ba92bf80Sespie $b = pop @pairs; 40*ba92bf80Sespie $a = pop @pairs; 41*ba92bf80Sespie if (defined $exception{"$a $b"}) { 42*ba92bf80Sespie $ok{"$a $b"} = 1; 43*ba92bf80Sespie } 44*ba92bf80Sespie next if $break{$a} = 1; 457f1ccc5bSespie next unless $order{$a} < $order{$b}; 467f1ccc5bSespie die "Bad pair $a $b\n"; 477f1ccc5bSespie } 483a58f8dfSespie} 493a58f8dfSespieclose(PAIRS); 50*ba92bf80Sespie 51*ba92bf80Sespiewhile (($key, $v) = each %exception) { 52*ba92bf80Sespie next if $v != 1; 53*ba92bf80Sespie die "Bogus cycle edge $key\n" unless $ok{$key}; 54*ba92bf80Sespie} 55