11 // and edge counts that satisfy flow conservation rules, while minimally modify
67 /// A value indicating an infinite flow/capacity/weight of a block/edge.
84 /// of nodes (source and sink). The output is the flow along each edge of the
85 /// minimum total cost respecting the given edge capacities.
96     Edges = std::vector<std::vector<Edge>>(NodeCount, std::vector<Edge>());  in initialize()
99           std::vector<std::vector<Edge *>>(NodeCount, std::vector<Edge *>());  in initialize()
114       for (auto &Edge : Edges[Src]) {  in run()  local
115         if (Edge.Flow > 0) {  in run()
116           TotalCost += Edge.Cost * Edge.Flow;  in run()
118             TotalFlow += Edge.Flow;  in run()
130   /// Adding an edge to the network with a specified capacity and a cost.
134     assert(Capacity > 0 && "adding an edge of zero capacity");  in addEdge()
135     assert(Src != Dst && "loop edge are not supported");  in addEdge()
137     Edge SrcEdge;  in addEdge()
144     Edge DstEdge;  in addEdge()
155   /// Adding an edge to the network of infinite capacity and a given cost.
164     for (const auto &Edge : Edges[Src]) {  in getFlow()  local
165       if (Edge.Flow > 0)  in getFlow()
166         Flow.push_back(std::make_pair(Edge.Dst, Edge.Flow));  in getFlow()
174     for (const auto &Edge : Edges[Src]) {  in getFlow()  local
175       if (Edge.Dst == Dst) {  in getFlow()
176         Flow += Edge.Flow;  in getFlow()
192           // Identify node/edge candidates for augmentation  in applyFlowAugmentation()
221       auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];  in computeAugmentingPathCapacity()  local
223       assert(Edge.Capacity >= Edge.Flow && "incorrect edge flow");  in computeAugmentingPathCapacity()
224       uint64_t EdgeCapacity = uint64_t(Edge.Capacity - Edge.Flow);  in computeAugmentingPathCapacity()
271         auto &Edge = Edges[Src][EdgeIdx];  in findAugmentingPath()  local
272         if (Edge.Flow < Edge.Capacity) {  in findAugmentingPath()
273           uint64_t Dst = Edge.Dst;  in findAugmentingPath()
274           int64_t NewDistance = Nodes[Src].Distance + Edge.Cost;  in findAugmentingPath()
276             // Update the distance and the parent node/edge  in findAugmentingPath()
299       auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];  in augmentFlowAlongPath()  local
300       auto &RevEdge = Edges[Now][Edge.RevEdgeIndex];  in augmentFlowAlongPath()
302       Edge.Flow += PathCapacity;  in augmentFlowAlongPath()
311   /// edge out of a node, continue search at Edge.Dst endpoint if it has not
321     //  - the next edge to scan is Edges[NodeIdx][EdgeIdx]  in findAugmentingDAG()
347         auto &Edge = Edges[NodeIdx][EdgeIdx];  in findAugmentingDAG()  local
348         auto &Dst = Nodes[Edge.Dst];  in findAugmentingDAG()
351         if (Edge.OnShortestPath) {  in findAugmentingDAG()
352           // If we haven't seen Edge.Dst so far, continue DFS search there  in findAugmentingDAG()
355             Stack.emplace(Edge.Dst, 0);  in findAugmentingDAG()
358             // Else, if Edge.Dst already have a path to Target, so that NodeIdx  in findAugmentingDAG()
363         // If we are done scanning all edge out of NodeIdx  in findAugmentingDAG()
387       for (auto &Edge : Edges[Src]) {  in findAugmentingDAG()  local
388         uint64_t Dst = Edge.Dst;  in findAugmentingDAG()
389         if (Edge.OnShortestPath && Nodes[Src].Taken && Nodes[Dst].Taken &&  in findAugmentingDAG()
391           AugmentingEdges[Src].push_back(&Edge);  in findAugmentingDAG()
404   /// After the update at least one edge is saturated.
410       for (auto &Edge : AugmentingEdges[Src]) {  in augmentFlowAlongDAG()  local
411         Edge->AugmentedFlow = 0;  in augmentFlowAlongDAG()
423       for (auto &Edge : AugmentingEdges[Src]) {  in augmentFlowAlongDAG()  local
425         Nodes[Edge->Dst].FracFlow += EdgeFlow;  in augmentFlowAlongDAG()
426         if (Edge->Capacity == INF)  in augmentFlowAlongDAG()
428         uint64_t MaxIntFlow = double(Edge->Capacity - Edge->Flow) / EdgeFlow;  in augmentFlowAlongDAG()
446       for (auto &Edge : AugmentingEdges[Src]) {  in augmentFlowAlongDAG()  local
447         uint64_t Dst = Edge->Dst;  in augmentFlowAlongDAG()
449         EdgeFlow = std::min(EdgeFlow, uint64_t(Edge->Capacity - Edge->Flow));  in augmentFlowAlongDAG()
452         Edge->AugmentedFlow += EdgeFlow;  in augmentFlowAlongDAG()
463       // Try to send excess flow back along each edge.  in augmentFlowAlongDAG()
465       for (auto &Edge : AugmentingEdges[Src]) {  in augmentFlowAlongDAG()  local
466         uint64_t Dst = Edge->Dst;  in augmentFlowAlongDAG()
469         uint64_t EdgeFlow = std::min(Nodes[Dst].IntFlow, Edge->AugmentedFlow);  in augmentFlowAlongDAG()
472         Edge->AugmentedFlow -= EdgeFlow;  in augmentFlowAlongDAG()
481       for (auto &Edge : AugmentingEdges[Src]) {  in augmentFlowAlongDAG()  local
482         assert(uint64_t(Edge->Capacity - Edge->Flow) >= Edge->AugmentedFlow);  in augmentFlowAlongDAG()
483         // Update flow values along the edge and its reverse copy  in augmentFlowAlongDAG()
484         auto &RevEdge = Edges[Edge->Dst][Edge->RevEdgeIndex];  in augmentFlowAlongDAG()
485         Edge->Flow += Edge->AugmentedFlow;  in augmentFlowAlongDAG()
486         RevEdge.Flow -= Edge->AugmentedFlow;  in augmentFlowAlongDAG()
487         if (Edge->Capacity == Edge->Flow && Edge->AugmentedFlow > 0)  in augmentFlowAlongDAG()
492     // The augmentation is successful iff at least one edge becomes saturated  in augmentFlowAlongDAG()
507       // An edge cannot be augmenting if the endpoint has large distance  in identifyShortestEdges()
511       for (auto &Edge : Edges[Src]) {  in identifyShortestEdges()  local
512         uint64_t Dst = Edge.Dst;  in identifyShortestEdges()
513         Edge.OnShortestPath =  in identifyShortestEdges()
516             Nodes[Dst].Distance == Nodes[Src].Distance + Edge.Cost &&  in identifyShortestEdges()
517             Edge.Capacity > Edge.Flow &&  in identifyShortestEdges()
518             uint64_t(Edge.Capacity - Edge.Flow) >= MinCapacity;  in identifyShortestEdges()
532     /// The index of the edge between ParentNode and the current node.
550   /// An edge in a flow network.
551   struct Edge {  struct in __anon5aecd1f00111::MinCostMaxFlow
552     /// The cost of the edge.
554     /// The capacity of the edge.
556     /// The current flow on the edge.
558     /// The destination node of the edge.
560     /// The index of the reverse edge between Dst and the current node.
564     /// Whether the edge is currently on a shortest path from Source to Target.
566     /// Extra flow along the edge.
573   std::vector<std::vector<Edge>> Edges;
579   std::vector<std::vector<Edge *>> AugmentingEdges;
1183 /// Extract resulting block and edge counts from the flow network.
1351   // Extract flow values for every block and every edge  in applyFlowInference()