MinWaitingTimeKepSolver.java 文件源码

/**
 * 
 * @param nonZeroEdgeValues
 * @return A list of lists of length 3. A returned list of [u,v,w] indicates
 *         that the constraint delta_uv + delta_vw <= delta_uw + 1 should be
 *         added.
 */
public List<List<V>> checkFractionalSolution(
    Map<E, Double> nonZeroEdgeValues,
    ImmutableTable<V, V, Double> precVarVals) {
  Set<V> retainedVertices = Sets.newHashSet(kepInstance.getGraph()
      .getVertices());
  Set<E> retainedEdges = Maps.filterValues(nonZeroEdgeValues,
      Range.<Double> atLeast(.51)).keySet();
  // In the below graph, each node will have in degree and out degree
  // at most one
  DirectedSparseMultigraph<V, E> inUseEdges = SubgraphUtil.subgraph(
      kepInstance.getGraph(), retainedVertices, retainedEdges);
  CycleChainDecomposition<V, E> decomposition = new CycleChainDecomposition<V, E>(
      inUseEdges);
  List<List<V>> ans = checkCycleChainDecomposition(decomposition,
      precVarVals, checkChains);
  fractionalCutsAdded += ans.size();
  return ans;
}