29 const ArcIndex num_arcs = arc_tail_.size();

30 num_nodes_ = std::max(num_nodes_, tail + 1);

31 num_nodes_ = std::max(num_nodes_, head + 1);

32 arc_tail_.push_back(tail);

33 arc_head_.push_back(head);

34 arc_capacity_.push_back(capacity);

35 return num_arcs;

36}

41 return arc_tail_.size();

42}

45 return arc_tail_[arc];

46}

49 return arc_head_[arc];

50}

53 return arc_capacity_[arc];

54}

57 arc_capacity_[arc] = capacity;

58}

61 const ArcIndex num_arcs = arc_capacity_.size();

62 arc_flow_.assign(num_arcs, 0);

63 underlying_max_flow_.reset();

64 underlying_graph_.reset();

65 optimal_flow_ = 0;

66 if (source == sink || source < 0 || sink < 0) {

68 }

69 if (source >= num_nodes_ || sink >= num_nodes_) {

71 }

72 underlying_graph_ = std::make_unique<Graph>(num_nodes_, num_arcs);

73 underlying_graph_->AddNode(source);

74 underlying_graph_->AddNode(sink);

75 for (int arc = 0; arc < num_arcs; ++arc) {

76 underlying_graph_->AddArc(arc_tail_[arc], arc_head_[arc]);

77 }

78 underlying_graph_->Build(&arc_permutation_);

79 underlying_max_flow_ = std::make_unique<GenericMaxFlow<Graph>>(

80 underlying_graph_.get(), source, sink);

81 for (ArcIndex arc = 0; arc < num_arcs; ++arc) {

83 arc < arc_permutation_.size() ? arc_permutation_[arc] : arc;

84 underlying_max_flow_->SetArcCapacity(permuted_arc, arc_capacity_[arc]);

85 }

86 if (underlying_max_flow_->Solve()) {

87 optimal_flow_ = underlying_max_flow_->GetOptimalFlow();

88 for (ArcIndex arc = 0; arc < num_arcs; ++arc) {

90 arc < arc_permutation_.size() ? arc_permutation_[arc] : arc;

91 arc_flow_[arc] = underlying_max_flow_->Flow(permuted_arc);

92 }

93 }

94

95

96 switch (underlying_max_flow_->status()) {

107 }

109}

112 return optimal_flow_;

113}

116 return arc_flow_[arc];

117}

120 if (underlying_max_flow_ == nullptr) return;

121 underlying_max_flow_->GetSourceSideMinCut(result);

122}

125 if (underlying_max_flow_ == nullptr) return;

126 underlying_max_flow_->GetSinkSideMinCut(result);

127}

133 for (int n = 0; n < num_nodes_; ++n) {

136 if (n == source) node->set_supply(1);

138 }

139 for (int a = 0; a < arc_tail_.size(); ++a) {

144 }

145 return model;

146}

void set_capacity(::int64_t value)

void set_head(::int64_t value)

void set_tail(::int64_t value)

::operations_research::FlowNodeProto *PROTOBUF_NONNULL add_nodes()

void set_problem_type(::operations_research::FlowModelProto_ProblemType value)

::operations_research::FlowArcProto *PROTOBUF_NONNULL add_arcs()

static constexpr ProblemType MAX_FLOW

void set_supply(::int64_t value)

void set_id(::int64_t value)

FlowModelProto CreateFlowModelProto(NodeIndex source, NodeIndex sink) const

Definition max_flow.cc:129

FlowQuantity OptimalFlow() const

Definition max_flow.cc:111

void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)

Definition max_flow.cc:56

ArcIndex NumArcs() const

Definition max_flow.cc:40

void GetSinkSideMinCut(std::vector< NodeIndex > *result)

Definition max_flow.cc:124

NodeIndex Tail(ArcIndex arc) const

Definition max_flow.cc:44

ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)

Definition max_flow.cc:27

NodeIndex NumNodes() const

Definition max_flow.cc:38

NodeIndex Head(ArcIndex arc) const

Definition max_flow.cc:48

Status Solve(NodeIndex source, NodeIndex sink)

Definition max_flow.cc:60

FlowQuantity Capacity(ArcIndex arc) const

Definition max_flow.cc:52

FlowQuantity Flow(ArcIndex arc) const

Definition max_flow.cc:115

SimpleMaxFlow()

Definition max_flow.cc:25

void GetSourceSideMinCut(std::vector< NodeIndex > *result)

Definition max_flow.cc:119