static boolean getConsistent ( DirectedGraph g ) { Object [ ] vertexOrdering = new Object [ g . size ( ) ] ; int voa = 0 ; for ( Iterator < ? > itr = g . iterator ( ) ; itr . hasNext ( ) ; voa ++ ) { vertexOrdering [ voa ] = itr . next ( ) ; } int vol = vertexOrdering . length ; Weight [ ] [ ] updatedEdges = new Weight [ vol ] [ vol ] ; for ( int k = vol - 1 ; k > 1 ; k -- ) { Object vk = vertexOrdering [ k ] ; for ( int i = 0 ; i < k ; i ++ ) { Object vi = vertexOrdering [ i ] ; Weight wik = getWeight ( i , k , vi , vk , g , updatedEdges ) ; if ( wik != null ) { /* * wki may be different from wik, so we can't just get the * inverse of wik. */ Weight wki = getWeight ( k , i , vk , vi , g , updatedEdges ) ; // i > j because we evaluate the vertices in order. for ( int j = i + 1 ; j < k ; j ++ ) { Object vj = vertexOrdering [ j ] ; Weight wjk = getWeight ( j , k , vj , vk , g , updatedEdges ) ; if ( wjk != null ) { Weight wkj = getWeight ( k , j , vk , vj , g , updatedEdges ) ; Weight wikj = wik . add ( wkj ) ; Weight wjki = wjk . add ( wki ) ; Weight wij = getWeight ( i , j , vi , vj , g , updatedEdges ) ; Weight wji = getWeight ( j , i , vj , vi , g , updatedEdges ) ; Weight iwjki = wjki . invertSign ( ) ; Weight iwji = null ; if ( wji != null ) { iwji = wji . invertSign ( ) ; } if ( wij != null ) { Weight intersectionMin = Weight . max ( iwji , iwjki ) ; Weight intersectionMax = Weight . min ( wij , wikj ) ; if ( intersectionMin . compareTo ( intersectionMax ) > 0 ) { return false ; } updatedEdges [ i ] [ j ] = intersectionMax ; updatedEdges [ j ] [ i ] = intersectionMin . invertSign ( ) ; } else { updatedEdges [ i ] [ j ] = wikj ; updatedEdges [ j ] [ i ] = wjki ; } } } } } } return true ; }
Returns whether a directed graph is consistent .