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); in initialize()
104 LLVM_DEBUG(dbgs() << "Starting profi for " << Nodes.size() << " nodes\n"); in run()
113 for (uint64_t Src = 0; Src < Nodes.size(); Src++) { in run()
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; in computeAugmentingPathCapacity()
221 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex]; in computeAugmentingPathCapacity()
235 for (auto &Node : Nodes) { in findAugmentingPath()
244 Nodes[Source].Distance = 0; in findAugmentingPath()
245 Nodes[Source].Taken = true; in findAugmentingPath()
249 Nodes[Src].Taken = false; in findAugmentingPath()
253 // (i) Dist[Source, V] >= 0 and (ii) Dist[V, Target] >= 0 for all nodes V, in findAugmentingPath()
254 // where Dist is the length of the shortest path between two nodes. This in findAugmentingPath()
264 if (!Params.EvenFlowDistribution && Nodes[Target].Distance == 0) in findAugmentingPath()
266 if (Nodes[Src].Distance > Nodes[Target].Distance) in findAugmentingPath()
274 int64_t NewDistance = Nodes[Src].Distance + Edge.Cost; in findAugmentingPath()
275 if (Nodes[Dst].Distance > NewDistance) { in findAugmentingPath()
277 Nodes[Dst].Distance = NewDistance; in findAugmentingPath()
278 Nodes[Dst].ParentNode = Src; in findAugmentingPath()
279 Nodes[Dst].ParentEdgeIndex = EdgeIdx; in findAugmentingPath()
281 if (!Nodes[Dst].Taken) { in findAugmentingPath()
283 Nodes[Dst].Taken = true; in findAugmentingPath()
290 return Nodes[Target].Distance != INF; in findAugmentingPath()
298 uint64_t Pred = Nodes[Now].ParentNode; in augmentFlowAlongPath()
299 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex]; in augmentFlowAlongPath()
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 in findAugmentingDAG()
327 for (auto &Node : Nodes) { in findAugmentingDAG()
336 Nodes[Target].Taken = true; in findAugmentingDAG()
340 Nodes[Source].Discovery = ++Time; in findAugmentingDAG()
348 auto &Dst = Nodes[Edge.Dst]; in findAugmentingDAG()
359 Nodes[NodeIdx].Taken = true; in findAugmentingDAG()
366 if (!Nodes[NodeIdx].Taken) { in findAugmentingDAG()
367 Nodes[NodeIdx].Discovery = 0; in findAugmentingDAG()
371 Nodes[NodeIdx].Finish = ++Time; in findAugmentingDAG()
375 Nodes[Stack.top().first].Taken = true; in findAugmentingDAG()
381 // Nodes are collected decreasing Finish time, so the order is reversed in findAugmentingDAG()
389 if (Edge.OnShortestPath && Nodes[Src].Taken && Nodes[Dst].Taken && in findAugmentingDAG()
390 Nodes[Dst].Finish < Nodes[Src].Finish) { in findAugmentingDAG()
408 Nodes[Src].FracFlow = 0; in augmentFlowAlongDAG()
409 Nodes[Src].IntFlow = 0; in augmentFlowAlongDAG()
417 Nodes[Source].FracFlow = 1.0; in augmentFlowAlongDAG()
419 assert((Src == Target || Nodes[Src].FracFlow > 0.0) && in augmentFlowAlongDAG()
424 double EdgeFlow = Nodes[Src].FracFlow / Degree; in augmentFlowAlongDAG()
425 Nodes[Edge->Dst].FracFlow += EdgeFlow; in augmentFlowAlongDAG()
437 Nodes[Source].IntFlow = MaxFlowAmount; in augmentFlowAlongDAG()
445 uint64_t SuccFlow = (Nodes[Src].IntFlow + Degree - 1) / Degree; in augmentFlowAlongDAG()
448 uint64_t EdgeFlow = std::min(Nodes[Src].IntFlow, SuccFlow); in augmentFlowAlongDAG()
450 Nodes[Dst].IntFlow += EdgeFlow; in augmentFlowAlongDAG()
451 Nodes[Src].IntFlow -= EdgeFlow; in augmentFlowAlongDAG()
455 assert(Nodes[Target].IntFlow <= MaxFlowAmount); in augmentFlowAlongDAG()
456 Nodes[Target].IntFlow = 0; in augmentFlowAlongDAG()
458 // Phase 3: Send excess flow back traversing the nodes backwards. in augmentFlowAlongDAG()
467 if (Nodes[Dst].IntFlow == 0) in augmentFlowAlongDAG()
469 uint64_t EdgeFlow = std::min(Nodes[Dst].IntFlow, Edge->AugmentedFlow); in augmentFlowAlongDAG()
470 Nodes[Dst].IntFlow -= EdgeFlow; in augmentFlowAlongDAG()
471 Nodes[Src].IntFlow += EdgeFlow; in augmentFlowAlongDAG()
480 assert(Src == Source || Nodes[Src].IntFlow == 0); in augmentFlowAlongDAG()
506 for (size_t Src = 0; Src < Nodes.size(); Src++) { in identifyShortestEdges()
508 if (Nodes[Src].Distance > Nodes[Target].Distance) in identifyShortestEdges()
515 Nodes[Dst].Distance <= Nodes[Target].Distance && in identifyShortestEdges()
516 Nodes[Dst].Distance == Nodes[Src].Distance + Edge.Cost && in identifyShortestEdges()
570 /// The set of network nodes.
571 std::vector<Node> Nodes; member in __anon5aecd1f00111::MinCostMaxFlow
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 in initializeNetwork()
1074 // Initialize nodes of the flow network in initializeNetwork()
1078 // Split every block into two auxiliary nodes to allow in initializeNetwork()