C++ Reference

C++ Reference: Graph

io.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// A collections of i/o utilities for the Graph classes in ./graph.h.
15
16#ifndef UTIL_GRAPH_IO_H_
17#define UTIL_GRAPH_IO_H_
18
19#include <algorithm>
20#include <memory>
21#include <numeric>
22#include <string>
23#include <vector>
24
25#include "absl/status/status.h"
26#include "absl/status/statusor.h"
27#include "absl/strings/numbers.h"
28#include "absl/strings/str_cat.h"
29#include "absl/strings/str_format.h"
30#include "absl/strings/str_join.h"
31#include "absl/strings/str_split.h"
32#include "ortools/base/filelineiter.h"
33#include "ortools/graph/graph.h"
34
35namespace util {
36
37// Returns a string representation of a graph.
39 // One arc per line, eg. "3->1".
41
42 // One space-separated adjacency list per line, eg. "3: 5 1 3 1".
43 // Nodes with no outgoing arc get an empty list.
45
46 // Ditto, but the adjacency lists are sorted.
48};
49template <class Graph>
50std::string GraphToString(const Graph& graph, GraphToStringFormat format);
51
52// Read a graph file in the simple ".g" format: the file should be a text file
53// containing only space-separated integers, whose first line is:
54// <num nodes> <num edges> [<num_colors> <index of first node with color #1>
55// <index of first node with color #2> ...]
56// and whose subsequent lines represent edges if "directed" is false, or arcs if
57// "directed" is true:
58// <node1> <node2>.
59//
60// This returns a newly created graph upon success, which the user needs to take
61// ownership of, or a failure status. See absl/status/statusor.h.
62//
63// If "num_nodes_with_color_or_null" is not nullptr, it will be filled with the
64// color information: num_nodes_with_color_or_null[i] will be the number of
65// nodes with color #i. Furthermore, nodes are sorted by color.
66//
67// Examples:
68// // Simply crash if the graph isn't successfully read from the file.
69// typedef StaticGraph<> MyGraph; // This is just an example.
70// std::unique_ptr<MyGraph> my_graph(
71// ReadGraphFile<MyGraph>("graph.g", /*directed=*/ false).ValueOrDie());
72//
73// // More complicated error handling.
74// absl::StatusOr<MyGraph*> error_or_graph =
75// ReadGraphFile<MyGraph>("graph.g", /*directed=*/ false);
76// if (!error_or_graph.ok()) {
77// LOG(ERROR) << "Error: " << error_or_graph.status().error_message();
78// } else {
79// std::unique_ptr<MyGraph> my_graph(error_or_graph.ValueOrDie());
80// ...
81// }
82template <class Graph>
83absl::StatusOr<Graph*> ReadGraphFile(
84 const std::string& filename, bool directed,
85 std::vector<int>* num_nodes_with_color_or_null);
86
87// Writes a graph to the ".g" file format described above. If "directed" is
88// true, all arcs are written to the file. If it is false, the graph is expected
89// to be undirected (i.e. the number of arcs a->b is equal to the number of arcs
90// b->a for all nodes a,b); and only the arcs a->b where a<=b are written. Note
91// however that in this case, the symmetry of the graph is not fully checked
92// (only the parity of the number of non-self arcs is).
93//
94// "num_nodes_with_color" is optional. If it is not empty, then the color
95// information will be written to the header of the .g file. See ReadGraphFile.
96//
97// This method is the reverse of ReadGraphFile (with the same value for
98// "directed").
99template <class Graph>
100absl::Status WriteGraphToFile(const Graph& graph, const std::string& filename,
101 bool directed,
102 const std::vector<int>& num_nodes_with_color);
103
104// Implementations of the templated methods.
105
106template <class Graph>
107std::string GraphToString(const Graph& graph, GraphToStringFormat format) {
108 std::string out;
109 std::vector<typename Graph::NodeIndex> adj;
110 for (const typename Graph::NodeIndex node : graph.AllNodes()) {
111 if (format == PRINT_GRAPH_ARCS) {
112 for (const typename Graph::ArcIndex arc : graph.OutgoingArcs(node)) {
113 if (!out.empty()) out += '\n';
114 absl::StrAppend(&out, node, "->", graph.Head(arc));
115 }
116 } else { // PRINT_GRAPH_ADJACENCY_LISTS[_SORTED]
117 adj.clear();
118 for (const typename Graph::ArcIndex arc : graph.OutgoingArcs(node)) {
119 adj.push_back(graph.Head(arc));
120 }
122 std::sort(adj.begin(), adj.end());
123 }
124 if (node != 0) out += '\n';
125 absl::StrAppend(&out, node, ": ", absl::StrJoin(adj, " "));
126 }
127 }
128 return out;
129}
130
131template <class Graph>
132absl::StatusOr<Graph*> ReadGraphFile(
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)) {
140 ++num_lines_read;
141 if (num_lines_read == 1) {
142 std::vector<int64> header_ints;
143 // if (!SplitStringAndParse(line, " ", &strings::safe_strto64,
144 // &header_ints) ||
145 // header_ints.size() < 2 || header_ints[0] < 0 || header_ints[1] < 0)
146 // {
147 // return absl::Status(
148 // absl::StatusCode::kInvalidArgument,
149 // absl::StrCat("First line of '", filename,
150 // "' should be at least two nonnegative integers."));
151 // }
152 num_nodes = header_ints[0];
153 num_expected_lines = header_ints[1];
154 if (num_nodes_with_color_or_null != nullptr) {
155 num_nodes_with_color_or_null->clear();
156 if (header_ints.size() == 2) {
157 // No coloring: all the nodes have the same color.
158 num_nodes_with_color_or_null->push_back(num_nodes);
159 } else {
160 const int num_colors = header_ints[2];
161 if (header_ints.size() != num_colors + 2) {
162 return absl::Status(
163 absl::StatusCode::kInvalidArgument,
164 absl::StrCat(
165 "There should be num_colors-1 color cardinalities in the"
166 " header of '",
167 filename, "' (where num_colors=", num_colors,
168 "): the last color cardinality should be", " skipped."));
169 }
170 num_nodes_with_color_or_null->reserve(num_colors);
171 int num_nodes_left = num_nodes;
172 for (int i = 3; i < header_ints.size(); ++i) {
173 num_nodes_with_color_or_null->push_back(header_ints[i]);
174 num_nodes_left -= header_ints[i];
175 if (header_ints[i] <= 0 || num_nodes_left <= 0) {
176 return absl::Status(
177 absl::StatusCode::kInvalidArgument,
178 absl::StrCat(
179 "The color cardinalities in the header of '", filename,
180 " should always be >0 and add up to less than the"
181 " total number of nodes."));
182 }
183 }
184 num_nodes_with_color_or_null->push_back(num_nodes_left);
185 }
186 }
187 const int64 num_arcs = (directed ? 1 : 2) * num_expected_lines;
188 graph.reset(new Graph(num_nodes, num_arcs));
189 continue;
190 }
191 int64_t node1 = -1;
192 int64_t node2 = -1;
193 if (sscanf(line.c_str(), "%ld %ld", &node1, &node2) != 2 || node1 < 0 ||
194 node2 < 0 || node1 >= num_nodes || node2 >= num_nodes) {
195 return absl::Status(
196 absl::StatusCode::kInvalidArgument,
197 absl::StrCat("In '", filename, "', line ", num_lines_read,
198 ": Expected two", " integers in the range [0, ",
199 num_nodes, ")."));
200 }
201 // We don't add superfluous arcs to the graph, but we still keep reading
202 // the file, to get better error messages: we want to know the actual
203 // number of lines, and also want to check the validity of the superfluous
204 // arcs (i.e. that their src/dst nodes are ok).
205 if (num_lines_read > num_expected_lines + 1) continue;
206 graph->AddArc(node1, node2);
207 if (!directed && node1 != node2) graph->AddArc(node2, node1);
208 }
209 if (num_lines_read == 0) {
210 return absl::Status(absl::StatusCode::kInvalidArgument,
211 "Unknown or empty file");
212 }
213 if (num_lines_read != num_expected_lines + 1) {
214 return absl::Status(absl::StatusCode::kInvalidArgument,
215 absl::StrCat("The number of arcs/edges in '", filename,
216 "' (", num_lines_read - 1,
217 " does not match the value announced in",
218 " the header (", num_expected_lines, ")"));
219 }
220 graph->Build();
221 return graph.release();
222}
223
224template <class Graph>
225absl::Status WriteGraphToFile(const Graph& graph, const std::string& filename,
226 bool directed,
227 const std::vector<int>& num_nodes_with_color) {
228 FILE* f = fopen(filename.c_str(), "w");
229 if (f == nullptr) {
230 return absl::Status(absl::StatusCode::kInvalidArgument,
231 "Could not open file: '" + filename + "'");
232 }
233 // In undirected mode, we must count the self-arcs separately. All other arcs
234 // should be duplicated.
235 int num_self_arcs = 0;
236 if (!directed) {
237 for (const typename Graph::NodeIndex node : graph.AllNodes()) {
238 for (const typename Graph::ArcIndex arc : graph.OutgoingArcs(node)) {
239 if (graph.Head(arc) == node) ++num_self_arcs;
240 }
241 }
242 if ((graph.num_arcs() - num_self_arcs) % 2 != 0) {
243 fclose(f);
244 return absl::Status(absl::StatusCode::kInvalidArgument,
245 "WriteGraphToFile() called with directed=false"
246 " and with a graph with an odd number of (non-self)"
247 " arcs!");
248 }
249 }
250 absl::FPrintF(
251 f, "%d %d", static_cast<int64>(graph.num_nodes()),
252 static_cast<int64>(directed ? graph.num_arcs()
253 : (graph.num_arcs() + num_self_arcs) / 2));
254 if (!num_nodes_with_color.empty()) {
255 if (std::accumulate(num_nodes_with_color.begin(),
256 num_nodes_with_color.end(), 0) != graph.num_nodes() ||
257 *std::min_element(num_nodes_with_color.begin(),
258 num_nodes_with_color.end()) <= 0) {
259 return absl::Status(absl::StatusCode::kInvalidArgument,
260 "WriteGraphToFile() called with invalid coloring.");
261 }
262 fprintf(f, " %lu", num_nodes_with_color.size());
263 for (int i = 0; i < num_nodes_with_color.size() - 1; ++i) {
264 absl::FPrintF(f, " %d", static_cast<int64>(num_nodes_with_color[i]));
265 }
266 }
267 fprintf(f, "\n");
268
269 for (const typename Graph::NodeIndex node : graph.AllNodes()) {
270 for (const typename Graph::ArcIndex arc : graph.OutgoingArcs(node)) {
271 const typename Graph::NodeIndex head = graph.Head(arc);
272 if (directed || head >= node) {
273 absl::FPrintF(f, "%d %d\n", static_cast<int64>(node),
274 static_cast<uint64>(head));
275 }
276 }
277 }
278 if (fclose(f) != 0) {
279 return absl::Status(absl::StatusCode::kInternal,
280 "Could not close file '" + filename + "'");
281 }
282 return ::absl::OkStatus();
283}
284
285} // namespace util
286
287#endif // UTIL_GRAPH_IO_H_
ArcIndexType num_arcs() const
Definition: graph.h:205
NodeIndexType num_nodes() const
Definition: graph.h:202
IntegerRange< NodeIndex > AllNodes() const
Definition: graph.h:935
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1117
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
GraphToStringFormat
Definition: io.h:38
@ PRINT_GRAPH_ARCS
Definition: io.h:40
@ PRINT_GRAPH_ADJACENCY_LISTS
Definition: io.h:44
@ PRINT_GRAPH_ADJACENCY_LISTS_SORTED
Definition: io.h:47
ListGraph Graph
Definition: graph.h:2360
std::string GraphToString(const Graph &graph, GraphToStringFormat format)
Definition: io.h:107
absl::Status WriteGraphToFile(const Graph &graph, const std::string &filename, bool directed, const std::vector< int > &num_nodes_with_color)
Definition: io.h:225
absl::StatusOr< Graph * > ReadGraphFile(const std::string &filename, bool directed, std::vector< int > *num_nodes_with_color_or_null)
Definition: io.h:132