Google OR-Tools: ortools/graph/util.h Source File

16#ifndef UTIL_GRAPH_UTIL_H_

17#define UTIL_GRAPH_UTIL_H_

19#include <algorithm>

20#include <cstdint>

21#include <limits>

22#include <memory>

23#include <set>

24#include <utility>

25#include <vector>

27#include "absl/container/btree_map.h"

28#include "absl/container/flat_hash_map.h"

29#include "absl/container/inlined_vector.h"

30#include "absl/log/check.h"

31#include "absl/types/span.h"

37namespace util {

54template <class Graph>

56template <class Graph>

58template <class Graph>

60template <class Graph>

64template <class Graph>

72template <class Graph>

74 absl::Span<const int> new_node_index);

86template <class Graph>

88 absl::Span<const int> nodes);

100

101template <class Graph>

103 public:

105 "for forward graphs, directly use `Graph::operator[]`");

106

109

110 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator ArcIterator;

112 public:

115

117 return graph_.Head(ArcIterator::operator*());

118 }

119

120 private:

121 const Graph& graph_;

122 };

123

124

126 const auto& arc_range = graph_.OutgoingOrOppositeIncomingArcs(node);

129 }

130

131 private:

132 const Graph& graph_;

133};

134

135

136template <class Graph>

139

140

141

142

143template <class Graph>

148

149

150

151

152bool IsSubsetOf0N(absl::Span<const int> v, int n);

153

154

158

159

160template <class Graph>

162

163

164

165

166

167

168

169

170

171

172

173template <class Graph>

175

176

177template <class Graph>

178bool PathHasCycle(const Graph& graph, absl::Span<const int> arc_path);

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195template <class Graph>

197 bool die_if_not_symmetric);

198

199

200

201template <class Graph>

203 for (const auto arc : graph.AllForwardArcs()) {

204 if (graph.Tail(arc) == graph.Head(arc)) return true;

205 }

206 return false;

207}

208

209template <class Graph>

213 std::vector<bool> tmp_node_mask(graph.num_nodes(), false);

214 for (const NodeIndex tail : graph.AllNodes()) {

215 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {

216 const NodeIndex head = graph.Head(arc);

217 if (tmp_node_mask[head]) return true;

218 tmp_node_mask[head] = true;

219 }

220 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {

221 tmp_node_mask[graph.Head(arc)] = false;

222 }

223 }

224 return false;

225}

226

227template <class Graph>

231

233 graph.num_arcs());

234 for (const NodeIndex node : graph.AllNodes()) {

235 for (const ArcIndex arc : graph.OutgoingArcs(node)) {

236 reverse_graph.AddArc(graph.Head(arc), node);

237 }

238 }

239 reverse_graph.Build();

240

241 std::vector<ArcIndex> count(graph.num_nodes(), 0);

242 for (const NodeIndex node : graph.AllNodes()) {

243 for (const ArcIndex arc : graph.OutgoingArcs(node)) {

244 ++count[graph.Head(arc)];

245 }

246 for (const ArcIndex arc : reverse_graph.OutgoingArcs(node)) {

247 if (--count[reverse_graph.Head(arc)] < 0) return false;

248 }

249 for (const ArcIndex arc : graph.OutgoingArcs(node)) {

250 if (count[graph.Head(arc)] != 0) return false;

251 }

252 }

253 return true;

254}

255

256template <class Graph>

259 static_assert(std::numeric_limits<NodeIndex>::max() <= INT_MAX,

260 "GraphIsWeaklyConnected() isn't yet implemented for graphs"

261 " that support more than INT_MAX nodes. Reach out to"

262 " or-core-team@ if you need this.");

263 if (graph.num_nodes() == 0) return true;

268 }

270}

271

272template <class Graph>

274 std::unique_ptr<Graph> new_graph(

276 for (const auto node : graph.AllNodes()) {

277 for (const auto arc : graph.OutgoingArcs(node)) {

278 new_graph->AddArc(node, graph.Head(arc));

279 }

280 }

281 new_graph->Build();

282 return new_graph;

283}

284

285template <class Graph>

287 absl::Span<const int> new_node_index) {

289 const int num_nodes = old_graph.num_nodes();

290 CHECK_EQ(new_node_index.size(), num_nodes);

291 std::unique_ptr<Graph> new_graph(new Graph(num_nodes, old_graph.num_arcs()));

294 for (const NodeIndex node : old_graph.AllNodes()) {

295 for (const ArcIndex arc : old_graph.OutgoingArcs(node)) {

296 new_graph->AddArc(new_node_index[node],

297 new_node_index[old_graph.Head(arc)]);

298 }

299 }

300 new_graph->Build();

301 return new_graph;

302}

303

304template <class Graph>

306 absl::Span<const int> nodes) {

310 std::vector<NodeIndex> new_node_index(old_graph.num_nodes(), -1);

311 for (NodeIndex new_index = 0; new_index < nodes.size(); ++new_index) {

312 new_node_index[nodes[new_index]] = new_index;

313 }

314

315

316 ArcIndex num_arcs = 0;

317 for (const NodeIndex node : nodes) {

318 for (const ArcIndex arc : old_graph.OutgoingArcs(node)) {

319 if (new_node_index[old_graph.Head(arc)] != -1) ++num_arcs;

320 }

321 }

322

323

324

325

326 std::unique_ptr<Graph> new_graph(new Graph(nodes.size(), num_arcs));

327 for (NodeIndex new_tail = 0; new_tail < nodes.size(); ++new_tail) {

328 const NodeIndex old_tail = nodes[new_tail];

329 for (const ArcIndex arc : old_graph.OutgoingArcs(old_tail)) {

330 const NodeIndex new_head = new_node_index[old_graph.Head(arc)];

331 if (new_head != -1) new_graph->AddArc(new_tail, new_head);

332 }

333 }

334 new_graph->Build();

335 return new_graph;

336}

337

338template <class Graph>

340 std::unique_ptr<Graph> g(new Graph(graph.num_nodes(), graph.num_arcs()));

343 std::vector<bool> tmp_node_mask(graph.num_nodes(), false);

344 for (const NodeIndex tail : graph.AllNodes()) {

345 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {

346 const NodeIndex head = graph.Head(arc);

347 if (head != tail && !tmp_node_mask[head]) {

348 tmp_node_mask[head] = true;

349 g->AddArc(tail, head);

350 }

351 }

352 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {

353 tmp_node_mask[graph.Head(arc)] = false;

354 }

355 }

356 g->Build();

357 return g;

358}

359

360template <class Graph>

362 if (arc_path->empty()) return;

363

364

365 absl::btree_map<int, int> last_arc_leaving_node;

366 for (const int arc : *arc_path) last_arc_leaving_node[graph.Tail(arc)] = arc;

367

368

369

370 last_arc_leaving_node[graph.Head(arc_path->back())] = -1;

371

372

373

374 int node = graph.Tail(arc_path->front());

375 int new_size = 0;

376 while (new_size < arc_path->size()) {

377 const int arc = gtl::FindOrDie(last_arc_leaving_node, node);

378 if (arc == -1) break;

379 (*arc_path)[new_size++] = arc;

380 node = graph.Head(arc);

381 }

382 arc_path->resize(new_size);

383}

384

385template <class Graph>

387 if (arc_path.empty()) return false;

388 std::set<int> seen;

389 seen.insert(graph.Tail(arc_path.front()));

390 for (const int arc : arc_path) {

392 }

393 return false;

394}

395

396template <class Graph>

398 const Graph& graph, bool die_if_not_symmetric) {

399 std::vector<int> reverse_arc(graph.num_arcs(), -1);

400

401

402

403 absl::flat_hash_map<std::pair< int, int>,

404 absl::InlinedVector<int, 4>>

405 arc_map;

406

407 for (int arc = 0; arc < graph.num_arcs(); ++arc) {

408 const int tail = graph.Tail(arc);

409 const int head = graph.Head(arc);

410 if (tail == head) {

411

412 reverse_arc[arc] = arc;

413 continue;

414 }

415

416 auto it = arc_map.find({head, tail});

417 if (it != arc_map.end()) {

418

419

420 reverse_arc[arc] = it->second.back();

421 reverse_arc[it->second.back()] = arc;

422 if (it->second.size() > 1) {

423 it->second.pop_back();

424 } else {

425 arc_map.erase(it);

426 }

427 } else {

428

429 arc_map[{tail, head}].push_back(arc);

430 }

431 }

432

434 int64_t num_unmapped_arcs = 0;

435 for (const auto& p : arc_map) {

436 num_unmapped_arcs += p.second.size();

437 }

438 DCHECK_EQ(std::count(reverse_arc.begin(), reverse_arc.end(), -1),

439 num_unmapped_arcs);

440 }

441 if (die_if_not_symmetric) {

442 CHECK_EQ(arc_map.size(), 0)

443 << "The graph is not symmetric: " << arc_map.size() << " of "

444 << graph.num_arcs() << " arcs did not have a reverse.";

445 }

446 return reverse_arc;

447}

448

449}

450

451#endif

bool AddEdge(int node1, int node2)

void SetNumberOfNodes(int num_nodes)

int GetNumberOfComponents() const

NodeIndexType num_nodes() const

ArcIndexType num_arcs() const

IntegerRange< NodeIndex > AllNodes() const

static constexpr bool kHasNegativeReverseArcs

BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const

NodeIndexType Head(ArcIndexType arc) const

ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)

IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const

void Build(std::vector< ArcIndexType > *permutation) final

NodeIndexType Head(ArcIndexType arc) const

AdjacencyListIterator(const Graph &graph, ArcIterator &&arc_it)

Definition util.h:113

Graph::NodeIndex operator*() const

Definition util.h:116

Graph::OutgoingOrOppositeIncomingArcIterator ArcIterator

Definition util.h:110

UndirectedAdjacencyListsOfDirectedGraph(const Graph &graph)

Definition util.h:107

BeginEndWrapper< AdjacencyListIterator > operator[](int node) const

Definition util.h:125

bool InsertIfNotPresent(Collection *const collection, const typename Collection::value_type &value)

const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)

void RemoveCyclesFromPath(const Graph &graph, std::vector< int > *arc_path)

Definition util.h:361

bool IsValidPermutation(absl::Span< const int > v)

Definition util.h:155

std::unique_ptr< Graph > CopyGraph(const Graph &graph)

Definition util.h:273

std::vector< int > GetConnectedComponents(int num_nodes, const UndirectedGraph &graph)

UndirectedAdjacencyListsOfDirectedGraph(const Graph &) -> UndirectedAdjacencyListsOfDirectedGraph< Graph >

bool PathHasCycle(const Graph &graph, absl::Span< const int > arc_path)

Definition util.h:386

bool GraphHasDuplicateArcs(const Graph &graph)

Definition util.h:210

bool GraphIsSymmetric(const Graph &graph)

Definition util.h:228

std::unique_ptr< Graph > RemapGraph(const Graph &graph, absl::Span< const int > new_node_index)

Definition util.h:286

std::unique_ptr< Graph > RemoveSelfArcsAndDuplicateArcs(const Graph &graph)

Definition util.h:339

std::vector< int > GetWeaklyConnectedComponents(const Graph &graph)

Definition util.h:144

bool GraphIsWeaklyConnected(const Graph &graph)

Definition util.h:257

bool GraphHasSelfArcs(const Graph &graph)

Definition util.h:202

bool IsSubsetOf0N(absl::Span< const int > v, int n)

std::unique_ptr< Graph > GetSubgraphOfNodes(const Graph &graph, absl::Span< const int > nodes)

Definition util.h:305

std::vector< int > ComputeOnePossibleReverseArcMapping(const Graph &graph, bool die_if_not_symmetric)

Definition util.h:397