private int buildPath ( int [ ] path , int i , int start , int goal ) { while ( true ) { // lift the path through the contracted blossom while ( odd [ start ] != NIL ) { Tuple bridge = bridges . get ( start ) ; // add to the path from the bridge down to where 'start' // is - we need to reverse it as we travel 'up' the blossom // and then... int j = buildPath ( path , i , bridge . first , start ) ; reverse ( path , i , j - 1 ) ; i = j ; // ... we travel down the other side of the bridge start = bridge . second ; } path [ i ++ ] = start ; // root of the tree if ( matching . unmatched ( start ) ) return i ; path [ i ++ ] = matching . other ( start ) ; // end of recursive if ( path [ i - 1 ] == goal ) return i ; start = odd [ path [ i - 1 ] ] ; } }
Builds the path backwards from the specified start vertex until the goal . If the path reaches a blossom then the path through the blossom is lifted to the original graph .