16 #ifndef UTIL_GRAPH_IO_H_
17 #define UTIL_GRAPH_IO_H_
25 #include "absl/status/status.h"
26 #include "absl/strings/numbers.h"
27 #include "absl/strings/str_cat.h"
28 #include "absl/strings/str_format.h"
29 #include "absl/strings/str_join.h"
30 #include "absl/strings/str_split.h"
31 #include "ortools/base/filelineiter.h"
32 #include "ortools/base/statusor.h"
49 template <
class Graph>
82 template <
class Graph>
84 const std::string& filename,
bool directed,
85 std::vector<int>* num_nodes_with_color_or_null);
99 template <
class Graph>
102 const std::vector<int>& num_nodes_with_color);
106 template <
class Graph>
109 std::vector<typename Graph::NodeIndex> adj;
113 if (!out.empty()) out +=
'\n';
114 absl::StrAppend(&out, node,
"->", graph.
Head(arc));
119 adj.push_back(graph.
Head(arc));
122 std::sort(adj.begin(), adj.end());
124 if (node != 0) out +=
'\n';
125 absl::StrAppend(&out, node,
": ", absl::StrJoin(adj,
" "));
131 template <
class Graph>
133 const std::string& filename,
bool directed,
134 std::vector<int>* num_nodes_with_color_or_null) {
135 std::unique_ptr<Graph> graph;
136 int64 num_nodes = -1;
137 int64 num_expected_lines = -1;
138 int64 num_lines_read = 0;
139 for (
const std::string& line : FileLines(filename)) {
141 if (num_lines_read == 1) {
142 std::vector<int64> header_ints;
151 num_nodes = header_ints[0];
152 num_expected_lines = header_ints[1];
153 if (num_nodes_with_color_or_null !=
nullptr) {
154 num_nodes_with_color_or_null->clear();
155 if (header_ints.size() == 2) {
157 num_nodes_with_color_or_null->push_back(num_nodes);
159 const int num_colors = header_ints[2];
160 if (header_ints.size() != num_colors + 2) {
162 absl::StatusCode::kInvalidArgument,
164 "There should be num_colors-1 color cardinalities in the"
166 filename,
"' (where num_colors=", num_colors,
167 "): the last color cardinality should be",
" skipped."));
169 num_nodes_with_color_or_null->reserve(num_colors);
170 int num_nodes_left = num_nodes;
171 for (
int i = 3; i < header_ints.size(); ++i) {
172 num_nodes_with_color_or_null->push_back(header_ints[i]);
173 num_nodes_left -= header_ints[i];
174 if (header_ints[i] <= 0 || num_nodes_left <= 0) {
176 absl::StatusCode::kInvalidArgument,
178 "The color cardinalities in the header of '", filename,
179 " should always be >0 and add up to less than the"
180 " total number of nodes."));
183 num_nodes_with_color_or_null->push_back(num_nodes_left);
186 const int64 num_arcs = (directed ? 1 : 2) * num_expected_lines;
187 graph.reset(
new Graph(num_nodes, num_arcs));
192 if (sscanf(line.c_str(),
"%ld %ld", &node1, &node2) != 2 || node1 < 0 ||
193 node2 < 0 || node1 >= num_nodes || node2 >= num_nodes) {
195 absl::StatusCode::kInvalidArgument,
196 absl::StrCat(
"In '", filename,
"', line ", num_lines_read,
197 ": Expected two",
" integers in the range [0, ",
204 if (num_lines_read > num_expected_lines + 1)
continue;
205 graph->AddArc(node1, node2);
206 if (!directed && node1 != node2) graph->AddArc(node2, node1);
208 if (num_lines_read == 0) {
209 return absl::Status(absl::StatusCode::kInvalidArgument,
210 "Unknown or empty file");
212 if (num_lines_read != num_expected_lines + 1) {
213 return absl::Status(absl::StatusCode::kInvalidArgument,
214 absl::StrCat(
"The number of arcs/edges in '", filename,
215 "' (", num_lines_read - 1,
216 " does not match the value announced in",
217 " the header (", num_expected_lines,
")"));
220 return graph.release();
223 template <
class Graph>
226 const std::vector<int>& num_nodes_with_color) {
227 FILE* f = fopen(filename.c_str(),
"w");
229 return absl::Status(absl::StatusCode::kInvalidArgument,
230 "Could not open file: '" + filename +
"'");
234 int num_self_arcs = 0;
238 if (graph.
Head(arc) == node) ++num_self_arcs;
241 if ((graph.
num_arcs() - num_self_arcs) % 2 != 0) {
243 return absl::Status(absl::StatusCode::kInvalidArgument,
244 "WriteGraphToFile() called with directed=false"
245 " and with a graph with an odd number of (non-self)"
250 f,
"%d %d",
static_cast<int64
>(graph.
num_nodes()),
251 static_cast<int64
>(directed ? graph.
num_arcs()
252 : (graph.
num_arcs() + num_self_arcs) / 2));
253 if (!num_nodes_with_color.empty()) {
254 if (std::accumulate(num_nodes_with_color.begin(),
255 num_nodes_with_color.end(), 0) != graph.
num_nodes() ||
256 *std::min_element(num_nodes_with_color.begin(),
257 num_nodes_with_color.end()) <= 0) {
258 return absl::Status(absl::StatusCode::kInvalidArgument,
259 "WriteGraphToFile() called with invalid coloring.");
261 fprintf(f,
" %lu", num_nodes_with_color.size());
262 for (
int i = 0; i < num_nodes_with_color.size() - 1; ++i) {
263 absl::FPrintF(f,
" %d",
static_cast<int64
>(num_nodes_with_color[i]));
271 if (directed || head >= node) {
272 absl::FPrintF(f,
"%d %d\n",
static_cast<int64
>(node),
273 static_cast<uint64
>(head));
277 if (fclose(f) != 0) {
278 return absl::Status(absl::StatusCode::kInternal,
279 "Could not close file '" + filename +
"'");
281 return ::absl::OkStatus();
286 #endif // UTIL_GRAPH_IO_H_