solve_flow_model.cc File Reference

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <sstream>
#include <string>
#include <vector>
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/strings/match.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "ortools/base/commandlineflags.h"
#include "ortools/base/file.h"
#include "ortools/base/filesystem.h"
#include "ortools/base/helpers.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/base/options.h"
#include "ortools/base/path.h"
#include "ortools/base/timer.h"
#include "ortools/graph/flow_graph.h"
#include "ortools/graph/flow_problem.pb.h"
#include "ortools/graph/generic_max_flow.h"
#include "ortools/graph/graph.h"
#include "ortools/graph/min_cost_flow.h"
#include "ortools/util/file_util.h"
#include "ortools/util/filelineiter.h"
#include "ortools/util/stats.h"

Go to the source code of this file.

Classes
class	TimeDistribution

Namespaces
namespace	operations_research
	In SWIG mode, we don't want anything besides these top-level includes.

Typedefs
typedef util::ReverseArcStaticGraph	operations_research::Graph
	Type of graph to use.

Functions
	ABSL_FLAG (std::string, input, "", "Input file of the problem.")
	ABSL_FLAG (std::string, output_dimacs, "", "Output problem as a dimacs file.")
	ABSL_FLAG (std::string, output_proto, "", "Output problem as a flow proto.")
	ABSL_FLAG (bool, use_flow_graph, true, "Use special kind of graph.")
	ABSL_FLAG (bool, sort_heads, false, "Sort outgoing arcs by head.")
	ABSL_FLAG (bool, detect_reverse_arcs, true, "Detect reverse arcs.")
void	operations_research::ConvertFlowModelToDimacs (const FlowModelProto &flow_model, std::string *dimacs)
bool	operations_research::ConvertDimacsToFlowModel (absl::string_view file, FlowModelProto *flow_model)
void	operations_research::SolveMinCostFlow (const FlowModelProto &flow_model, double *loading_time, double *solving_time)
	Loads a FlowModelProto proto into the MinCostFlow class and solves it.
template<typename GraphType>
void	operations_research::SolveMaxFlow (const FlowModelProto &flow_model, double *loading_time, double *solving_time, std::function< void(GraphType *graph)> configure_graph_options=nullptr)
	Loads a FlowModelProto proto into the MaxFlow class and solves it.
int	main (int argc, char **argv)
template<typename GraphType>
void	SolveMaxFlow (const FlowModelProto &flow_model, double *loading_time, double *solving_time, std::function< void(GraphType *graph)> configure_graph_options=nullptr)
	Loads a FlowModelProto proto into the MaxFlow class and solves it.
void	SolveMinCostFlow (const FlowModelProto &flow_model, double *loading_time, double *solving_time)
	Loads a FlowModelProto proto into the MinCostFlow class and solves it.

Function Documentation

ABSL_FLAG() [1/6]

ABSL_FLAG	(	bool	,
		detect_reverse_arcs	,
		true	,
		"Detect reverse arcs."	)

ABSL_FLAG() [2/6]

ABSL_FLAG	(	bool	,
		sort_heads	,
		false	,
		"Sort outgoing arcs by head."	)

ABSL_FLAG() [3/6]

ABSL_FLAG	(	bool	,
		use_flow_graph	,
		true	,
		"Use special kind of graph."	)

ABSL_FLAG() [4/6]

ABSL_FLAG	(	std::string	,
		input	,
		""	,
		"Input file of the problem."	)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This code loads flow-graph models (as Dimacs file or binary FlowModel proto) and solves them with the OR-tools flow algorithms.

Note(user): only min-cost flow is supported at this point.

Todo

(user): move this DIMACS parser to its own class, like the ones in routing/. This change would improve searchability of the parser.

ABSL_FLAG() [5/6]

ABSL_FLAG	(	std::string	,
		output_dimacs	,
		""	,
		"Output problem as a dimacs file."	)

ABSL_FLAG() [6/6]

ABSL_FLAG	(	std::string	,
		output_proto	,
		""	,
		"Output problem as a flow proto."	)

main()

int main	(	int	argc,
		char **	argv )

Parse the input as a proto.

Todo

(user): improve code to convert many files.

Definition at line 300 of file solve_flow_model.cc.

SolveMaxFlow()

template<typename GraphType>

void operations_research::SolveMaxFlow	(	const FlowModelProto &	flow_model,
		double *	loading_time,
		double *	solving_time,
		std::function< void(GraphType *graph)>	configure_graph_options = nullptr )

Loads a FlowModelProto proto into the MaxFlow class and solves it.

Build the graph.

Find source & sink.

Create the max flow instance and set the arc capacities.

Definition at line 235 of file solve_flow_model.cc.

SolveMinCostFlow()

void operations_research::SolveMinCostFlow	(	const FlowModelProto &	flow_model,
		double *	loading_time,
		double *	solving_time )

Loads a FlowModelProto proto into the MinCostFlow class and solves it.

Compute the number of nodes.

Build the graph.

Definition at line 187 of file solve_flow_model.cc.