private void initPathsInternal ( ) { synchronized ( LOCK ) { if ( _incomingPathsInternal == null ) { AMap < N , AList < AEdgePath < N , E > > > incomingPaths = AHashMap . empty ( ) ; //noinspection unchecked incomingPaths = incomingPaths . withDefaultValue ( AList . nil ) ; AMap < N , AList < AEdgePath < N , E > > > outgoingPaths = AHashMap . empty ( ) ; //noinspection unchecked outgoingPaths = outgoingPaths . withDefaultValue ( AList . nil ) ; AList < AEdgePath < N , E > > cycles = AList . nil ( ) ; for ( N curNode : nodes ( ) ) { // iterate over nodes, treat 'curNode' as a target final Iterable < E > curIncoming = incomingEdges ( curNode ) ; List < AEdgePath < N , E > > unfinishedBusiness = new ArrayList <> ( ) ; for ( E incomingEdge : curIncoming ) { unfinishedBusiness . add ( AEdgePath . create ( incomingEdge ) ) ; } AList < AEdgePath < N , E > > nonCycles = AList . nil ( ) ; while ( unfinishedBusiness . size ( ) > 0 ) { final List < AEdgePath < N , E > > curBusiness = unfinishedBusiness ; for ( AEdgePath < N , E > p : unfinishedBusiness ) { if ( ! p . hasCycle ( ) || p . isMinimalCycle ( ) ) nonCycles = nonCycles . cons ( p ) ; if ( p . isMinimalCycle ( ) ) cycles = cycles . cons ( p ) ; } unfinishedBusiness = new ArrayList <> ( ) ; for ( AEdgePath < N , E > curPath : curBusiness ) { final Iterable < E > l = incomingEdges ( curPath . getFrom ( ) ) ; for ( E newEdge : l ) { final AEdgePath < N , E > pathCandidate = curPath . prepend ( newEdge ) ; if ( ! pathCandidate . hasNonMinimalCycle ( ) ) { unfinishedBusiness . add ( pathCandidate ) ; } } } } incomingPaths = incomingPaths . updated ( curNode , nonCycles ) ; for ( AEdgePath < N , E > p : nonCycles ) { outgoingPaths = outgoingPaths . updated ( p . getFrom ( ) , outgoingPaths . getRequired ( p . getFrom ( ) ) . cons ( p ) ) ; } } _incomingPathsInternal = incomingPaths ; _outgoingPathsInternal = outgoingPaths ; _cyclesInternal = cycles ; } } }
This method does the reachability analysis in a way that is useful for many other methods .