public static Map getCirculation()

in graphLayout/jetbrains.mps.graphLayout.graph/source_gen/jetbrains/mps/graphLayout/algorithms/MinCostCirculation.java [15:79]
46 lines of code
13 McCabe index (conditional complexity)

  public static Map<Edge, Integer> getCirculation(Graph graph, Map<Edge, Integer> low, Map<Edge, Integer> initialCapacity, Map<Edge, Integer> cost) {
    Map<Edge, Integer> capacity = MapSequence.fromMap(new HashMap<Edge, Integer>());
    Node source = graph.createNode();
    Node target = graph.createNode();
    for (Edge edge : ListSequence.fromList(graph.getEdges())) {
      MapSequence.fromMap(capacity).put(edge, MapSequence.fromMap(initialCapacity).get(edge) - MapSequence.fromMap(low).get(edge));
    }
    for (Node node : ListSequence.fromList(graph.getNodes())) {
      if (node == source || node == target) {
        continue;
      }
      int diff = 0;
      for (Edge edge : ListSequence.fromList(node.getInEdges())) {
        diff += MapSequence.fromMap(low).get(edge);
      }
      for (Edge edge : ListSequence.fromList(node.getOutEdges())) {
        diff -= MapSequence.fromMap(low).get(edge);
      }
      Edge newEdge = null;
      if (diff > 0) {
        newEdge = graph.connect(source, node);
      }
      if (diff < 0) {
        newEdge = graph.connect(node, target);
      }
      if (newEdge != null) {
        MapSequence.fromMap(capacity).put(newEdge, Math.abs(diff));
        MapSequence.fromMap(cost).put(newEdge, 0);
      }
    }
    Map<Edge, Integer> flow;
    if (TEST_MODE > 0) {
      flow = MinCostMaxFlowWithPotentials.getFlow(graph, source, target, capacity, cost);
      /*
        Map<Edge, Integer> anotherFlow = MinCostMaxFlow.getFlow(graph, source, target, capacity, cost);
        int flowCost = 0;
        int anotherFlowCost = 0;
        for (Edge edge : ListSequence.fromList(graph.getEdges())) {
          flowCost += MapSequence.fromMap(flow).get(edge) * MapSequence.fromMap(cost).get(edge);
          anotherFlowCost += MapSequence.fromMap(anotherFlow).get(edge) * MapSequence.fromMap(cost).get(edge);
        }
        if (anotherFlowCost != flowCost) {
          throw new RuntimeException("dijkstra result is different than ford-bellman");
        }
      */
    } else {
      flow = MinCostMaxFlow.getFlow(graph, source, target, capacity, cost);
    }
    /*
      for (Edge edge : ListSequence.fromList(source.getOutEdges())) {
        if (MapSequence.fromMap(flow).get(edge) != MapSequence.fromMap(capacity).get(edge)) {
          throw new RuntimeException("failed to find circulation");
        }
      }
    */
    for (Edge edge : ListSequence.fromList(source.getEdges()).concat(ListSequence.fromList(target.getEdges()))) {
      MapSequence.fromMap(flow).removeKey(edge);
    }
    graph.deleteNode(source);
    graph.deleteNode(target);
    for (Edge edge : ListSequence.fromList(graph.getEdges())) {
      MapSequence.fromMap(flow).put(edge, MapSequence.fromMap(flow).get(edge) + MapSequence.fromMap(low).get(edge));
    }
    return flow;
  }