Lines Matching full:nodes
84 /// of nodes (source and sink). The output is the flow along each edge of the
95 Nodes = std::vector<Node>(NodeCount);
104 LLVM_DEBUG(dbgs() << "Starting profi for " << Nodes.size() << " nodes\n");
113 for (uint64_t Src = 0; Src < Nodes.size(); Src++) {
131 /// Multiple edges between a pair of nodes are allowed but self-edges
171 /// Get the total flow between a pair of nodes.
220 uint64_t Pred = Nodes[Now].ParentNode;
221 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];
235 for (auto &Node : Nodes) {
244 Nodes[Source].Distance = 0;
245 Nodes[Source].Taken = true;
249 Nodes[Src].Taken = false;
253 // (i) Dist[Source, V] >= 0 and (ii) Dist[V, Target] >= 0 for all nodes V,
254 // where Dist is the length of the shortest path between two nodes. This
264 if (!Params.EvenFlowDistribution && Nodes[Target].Distance == 0)
266 if (Nodes[Src].Distance > Nodes[Target].Distance)
274 int64_t NewDistance = Nodes[Src].Distance + Edge.Cost;
275 if (Nodes[Dst].Distance > NewDistance) {
277 Nodes[Dst].Distance = NewDistance;
278 Nodes[Dst].ParentNode = Src;
279 Nodes[Dst].ParentEdgeIndex = EdgeIdx;
281 if (!Nodes[Dst].Taken) {
283 Nodes[Dst].Taken = true;
290 return Nodes[Target].Distance != INF;
298 uint64_t Pred = Nodes[Now].ParentNode;
299 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];
313 /// runs in O(MaxDfsCalls * |Edges| + |Nodes|) time.
314 /// It returns an Augmenting Order (Taken nodes in decreasing Finish time)
320 // - we are currently visiting Nodes[NodeIdx] and
327 for (auto &Node : Nodes) {
336 Nodes[Target].Taken = true;
340 Nodes[Source].Discovery = ++Time;
348 auto &Dst = Nodes[Edge.Dst];
359 Nodes[NodeIdx].Taken = true;
366 if (!Nodes[NodeIdx].Taken) {
367 Nodes[NodeIdx].Discovery = 0;
371 Nodes[NodeIdx].Finish = ++Time;
375 Nodes[Stack.top().first].Taken = true;
381 // Nodes are collected decreasing Finish time, so the order is reversed
389 if (Edge.OnShortestPath && Nodes[Src].Taken && Nodes[Dst].Taken &&
390 Nodes[Dst].Finish < Nodes[Src].Finish) {
408 Nodes[Src].FracFlow = 0;
409 Nodes[Src].IntFlow = 0;
417 Nodes[Source].FracFlow = 1.0;
419 assert((Src == Target || Nodes[Src].FracFlow > 0.0) &&
424 double EdgeFlow = Nodes[Src].FracFlow / Degree;
425 Nodes[Edge->Dst].FracFlow += EdgeFlow;
437 Nodes[Source].IntFlow = MaxFlowAmount;
445 uint64_t SuccFlow = (Nodes[Src].IntFlow + Degree - 1) / Degree;
448 uint64_t EdgeFlow = std::min(Nodes[Src].IntFlow, SuccFlow);
450 Nodes[Dst].IntFlow += EdgeFlow;
451 Nodes[Src].IntFlow -= EdgeFlow;
455 assert(Nodes[Target].IntFlow <= MaxFlowAmount);
456 Nodes[Target].IntFlow = 0;
458 // Phase 3: Send excess flow back traversing the nodes backwards.
467 if (Nodes[Dst].IntFlow == 0)
469 uint64_t EdgeFlow = std::min(Nodes[Dst].IntFlow, Edge->AugmentedFlow);
470 Nodes[Dst].IntFlow -= EdgeFlow;
471 Nodes[Src].IntFlow += EdgeFlow;
480 assert(Src == Source || Nodes[Src].IntFlow == 0);
506 for (size_t Src = 0; Src < Nodes.size(); Src++) {
508 if (Nodes[Src].Distance > Nodes[Target].Distance)
515 Nodes[Dst].Distance <= Nodes[Target].Distance &&
516 Nodes[Dst].Distance == Nodes[Src].Distance + Edge.Cost &&
570 /// The set of network nodes.
571 std::vector<Node> Nodes;
595 /// An unknown subgraph is such that for every two nodes u and v:
598 /// - all inner-nodes of all (u,v)-paths are unknown.
1053 /// Every block is split into two nodes that are responsible for (i) an
1064 // The nodes corresponding to blocks of the function have indices in
1074 // Initialize nodes of the flow network
1078 // Split every block into two auxiliary nodes to allow