! Tom Weeks - Math 2051, Section 01 ! u06a2 (2009.11.15) - Programming Project 2 (Page 400) ! ! For a given transportation network, determine a maximal flow ! by repeated use of the flow augmentation algorithm, starting ! with the flow that is zero along every arc. USING: accessors arrays combinators combinators.short-circuit io kernel math math.order math.parser prettyprint sequences sorting strings ; IN: u06a2 TUPLE: arc { from-to pair initial: { "" "" } } { capacity real } { flow real } ; TUPLE: label { predecessor string } { +/- string } { flow-delta real } ; TUPLE: vertex { name string } { label label } { scanned? boolean } { labeled# integer } ; ! 0 means unlabeled TUPLE: network { vertices array } { arcs array } ; : vertex-names ( network -- v-names ) vertices>> [ name>> ] map ; : vertex-pairs ( network -- v-pairs ) arcs>> [ from-to>> ] map ; : predecessors ( network -- v-names ) vertex-pairs [ first ] map ; : successors ( network -- v-names ) vertex-pairs [ second ] map ; : this-vertex ( v-name network -- v ) vertices>> [ name>> over = ] find 2nip ; : source-name ( network -- v-name ) [ successors ] [ vertex-names ] bi [ over member? not ] find 2nip ; : sink-name ( network -- v-name ) [ predecessors ] [ vertex-names ] bi [ over member? not ] find 2nip ; : source ( network -- v ) [ source-name ] keep this-vertex ; : sink ( network -- v ) [ sink-name ] keep this-vertex ; : infinity ( -- n ) 2 26 shift dup 1 - + ; inline ! fixnum max :