| 1 | /*
|
| 2 | * Souffle - A Datalog Compiler
|
| 3 | * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
|
| 4 | * Licensed under the Universal Permissive License v 1.0 as shown at:
|
| 5 | * - https://opensource.org/licenses/UPL
|
| 6 | * - <souffle root>/licenses/SOUFFLE-UPL.txt
|
| 7 | */
|
| 8 |
|
| 9 | /************************************************************************
|
| 10 | *
|
| 11 | * @file Graph.h
|
| 12 | *
|
| 13 | * A basic digraph with edge labels.
|
| 14 | *
|
| 15 | ***********************************************************************/
|
| 16 |
|
| 17 | #pragma once
|
| 18 |
|
| 19 | #include "souffle/utility/ContainerUtil.h"
|
| 20 | #include "souffle/utility/Types.h"
|
| 21 | #include <deque>
|
| 22 | #include <functional>
|
| 23 | #include <map>
|
| 24 | #include <ostream>
|
| 25 | #include <set>
|
| 26 | #include <vector>
|
| 27 | #ifndef NDEBUG
|
| 28 | #include <algorithm>
|
| 29 | #endif
|
| 30 |
|
| 31 | namespace souffle {
|
| 32 |
|
| 33 | namespace detail {
|
| 34 |
|
| 35 | struct GraphUnitEdgeSet {};
|
| 36 |
|
| 37 | } // namespace detail
|
| 38 |
|
| 39 | /**
|
| 40 | * A simple graph structure for graph-based operations.
|
| 41 | */
|
| 42 | template <typename Vertex, typename EdgeLabel = Unit, typename CompareVertex = std::less<Vertex>,
|
| 43 | typename CompareLabel = std::less<EdgeLabel>, bool UnitEdgeLabels = std::is_same_v<Unit, EdgeLabel>>
|
| 44 | class GraphLabeled {
|
| 45 | // HACK: helper to avoid pulling in `Util.h` for `souffle::contains`
|
| 46 | template <typename C, typename E = typename C::element_type>
|
| 47 | static bool containsValue(const C& xs, const E& x) {
|
| 48 | return xs.find(x) != xs.end();
|
| 49 | }
|
| 50 |
|
| 51 | public:
|
| 52 | using self_t = GraphLabeled<Vertex, EdgeLabel, CompareVertex, CompareLabel>;
|
| 53 | using VertexSet = std::set<Vertex, CompareVertex>;
|
| 54 | using EdgeLabelSet = std::set<EdgeLabel, CompareLabel>;
|
| 55 | enum class Visit { pre, post };
|
| 56 |
|
| 57 | /**
|
| 58 | * Adds a new edge from the given vertex to the target vertex.
|
| 59 | */
|
| 60 | template <typename = std::enable_if_t<UnitEdgeLabels>>
|
| 61 | bool insert(const Vertex& from, const Vertex& to) {
|
| 62 | return insert(from, to, EdgeLabelSet{});
|
| 63 | }
|
| 64 |
|
| 65 | bool insert(const Vertex& from, const Vertex& to, EdgeLabel label) {
|
| 66 | return insert(from, to, EdgeLabelSet{std::move(label)});
|
| 67 | }
|
| 68 |
|
| 69 | bool insert(const Vertex& from, const Vertex& to, EdgeLabelSet labels) {
|
| 70 | insert(from);
|
| 71 | insert(to);
|
| 72 | bool inserted = _successors[from].insert(to).second;
|
| 73 | _predecessors[to].insert(from);
|
| 74 | if constexpr (!UnitEdgeLabels) {
|
| 75 | auto& labels_store = _labels[{from, to}]; // force creation of entry
|
| 76 | if (labels_store.empty() && !labels.empty()) {
|
| 77 | labels_store = std::move(labels);
|
| 78 | inserted = true;
|
| 79 | } else {
|
| 80 | for (auto&& l : labels)
|
| 81 | inserted |= labels_store.insert(l).second;
|
| 82 | }
|
| 83 | }
|
| 84 | return inserted;
|
| 85 | }
|
| 86 |
|
| 87 | /**
|
| 88 | * Adds a vertex.
|
| 89 | */
|
| 90 | bool insert(const Vertex& vertex) {
|
| 91 | return _vertices.insert(vertex).second;
|
| 92 | }
|
| 93 |
|
| 94 | bool insert(const self_t& g) {
|
| 95 | bool changed = false;
|
| 96 | auto combineSet = [&](auto& dst, auto&& src) {
|
| 97 | for (auto&& x : src)
|
| 98 | changed |= dst.insert(x).second;
|
| 99 | };
|
| 100 | auto combineMap = [&](auto& dst, auto&& src) {
|
| 101 | for (auto&& [v, xs] : src) {
|
| 102 | auto [it, added] = dst.insert({v, {}});
|
| 103 | changed |= added;
|
| 104 | combineSet(it->second, xs);
|
| 105 | }
|
| 106 | };
|
| 107 |
|
| 108 | combineSet(_vertices, g._vertices);
|
| 109 | combineMap(_successors, g._successors);
|
| 110 | combineMap(_predecessors, g._predecessors);
|
| 111 | if constexpr (!UnitEdgeLabels) {
|
| 112 | combineMap(_labels, g._labels);
|
| 113 | }
|
| 114 |
|
| 115 | return changed;
|
| 116 | }
|
| 117 |
|
| 118 | bool remove(const Vertex& vertex) {
|
| 119 | if (_vertices.erase(vertex) == 0) return false;
|
| 120 |
|
| 121 | if constexpr (!UnitEdgeLabels) {
|
| 122 | for (auto&& m : successors(vertex))
|
| 123 | _labels.erase({vertex, m});
|
| 124 | }
|
| 125 |
|
| 126 | _successors.erase(vertex);
|
| 127 | _predecessors.erase(vertex);
|
| 128 | return true;
|
| 129 | }
|
| 130 |
|
| 131 | size_t remove(const Vertex& src, const Vertex& dst) {
|
| 132 | auto it = _successors.find(src);
|
| 133 | if (it == _successors.end()) return 0;
|
| 134 | if (it->second.erase(dst) == 0) return 0;
|
| 135 |
|
| 136 | if (it->second.empty()) _successors.erase(it);
|
| 137 | removeExistingAdjEdge(_predecessors, dst, src);
|
| 138 |
|
| 139 | if constexpr (UnitEdgeLabels) {
|
| 140 | return 1;
|
| 141 | } else {
|
| 142 | auto it = _labels.find({src, dst});
|
| 143 | assert(it != _labels.end());
|
| 144 | assert(!it->second.empty());
|
| 145 | auto n = it->second.size();
|
| 146 | _labels.erase(it);
|
| 147 | return n;
|
| 148 | }
|
| 149 | }
|
| 150 |
|
| 151 | bool remove(const Vertex& src, const Vertex& dst, const EdgeLabel& label) {
|
| 152 | if constexpr (UnitEdgeLabels) {
|
| 153 | return 0 < remove(src, dst);
|
| 154 | } else {
|
| 155 | auto it = _labels.find({src, dst});
|
| 156 | if (it == _labels.end()) return false;
|
| 157 | if (it->second.erase(label) == 0) return false;
|
| 158 |
|
| 159 | // all edges erased -> remove from succ/pred
|
| 160 | if (it->second.empty()) {
|
| 161 | _labels.erase(it);
|
| 162 | removeExistingAdjEdge(_predecessors, dst, src);
|
| 163 | removeExistingAdjEdge(_successors, src, dst);
|
| 164 | }
|
| 165 |
|
| 166 | return true;
|
| 167 | }
|
| 168 | }
|
| 169 |
|
| 170 | size_t removeEdgesPred(const Vertex& node) {
|
| 171 | return removeEdgesIncidentTo(_predecessors, _successors, node,
|
| 172 | [](auto node, auto adj) { return std::make_pair(adj, node); });
|
| 173 | }
|
| 174 |
|
| 175 | size_t removeEdgesSucc(const Vertex& node) {
|
| 176 | return removeEdgesIncidentTo(_successors, _predecessors, node,
|
| 177 | [](auto node, auto adj) { return std::make_pair(node, adj); });
|
| 178 | }
|
| 179 |
|
| 180 | /** Obtains a reference to the set of all vertices */
|
| 181 | const VertexSet& vertices() const {
|
| 182 | return _vertices;
|
| 183 | }
|
| 184 |
|
| 185 | // set of vertices which appear as the source of an edge
|
| 186 | // i.e. { a | (a, b) \in E }
|
| 187 | VertexSet edgeSources() const {
|
| 188 | return keysOfAdjacency(_successors);
|
| 189 | }
|
| 190 |
|
| 191 | // set of vertices which appear as the target of an edge
|
| 192 | // i.e. { b | (a, b) \in E }
|
| 193 | VertexSet edgeTargets() const {
|
| 194 | return keysOfAdjacency(_predecessors);
|
| 195 | }
|
| 196 |
|
| 197 | /** Returns the set of vertices the given vertex has edges to */
|
| 198 | const VertexSet& successors(const Vertex& from) const {
|
| 199 | auto it = _successors.find(from);
|
| 200 | return it == _successors.end() ? null : it->second;
|
| 201 | }
|
| 202 |
|
| 203 | /** Returns the set of vertices the given vertex has edges from */
|
| 204 | const VertexSet& predecessors(const Vertex& to) const {
|
| 205 | auto it = _predecessors.find(to);
|
| 206 | return it == _predecessors.end() ? null : it->second;
|
| 207 | }
|
| 208 |
|
| 209 | /** Obtains the union of sources and nodes transitively reachable via the sources' successors */
|
| 210 | template <typename C>
|
| 211 | VertexSet reachableFromSucc(C&& sources) const {
|
| 212 | return reachableFrom(std::forward<C>(sources), std::mem_fn(&GraphLabeled::successors));
|
| 213 | }
|
| 214 |
|
| 215 | /** Obtains the union of sources and nodes transitively reachable via the sources' predecessors */
|
| 216 | template <typename C>
|
| 217 | VertexSet reachableFromPred(C&& sources) const {
|
| 218 | return reachableFrom(std::forward<C>(sources), std::mem_fn(&GraphLabeled::predecessors));
|
| 219 | }
|
| 220 |
|
| 221 | VertexSet reachableFromSucc(Vertex src) const {
|
| 222 | return reachableFromSucc(VertexSet{std::move(src)});
|
| 223 | }
|
| 224 |
|
| 225 | VertexSet reachableFromPred(Vertex src) const {
|
| 226 | return reachableFromPred(VertexSet{std::move(src)});
|
| 227 | }
|
| 228 |
|
| 229 | template <typename Edges>
|
| 230 | VertexSet reachableFrom(Vertex src, Edges&& edges) const {
|
| 231 | return reachableFrom(VertexSet{std::move(src)}, std::forward<Edges>(edges));
|
| 232 | }
|
| 233 |
|
| 234 | template <typename Edges>
|
| 235 | VertexSet reachableFrom(VertexSet&& sources, Edges&& edges) const {
|
| 236 | std::vector<Vertex> pending{sources.begin(), sources.end()};
|
| 237 | return reachableFrom(std::move(sources), std::move(pending), std::forward<Edges>(edges));
|
| 238 | }
|
| 239 |
|
| 240 | template <typename C, typename Edges>
|
| 241 | VertexSet reachableFrom(C&& srcs, Edges&& edges) const {
|
| 242 | // nitpick: build `pending` from `srcs` to preserve whatever iteration order is imposed by `srcs`
|
| 243 | std::vector<Vertex> pending{srcs.begin(), srcs.end()};
|
| 244 | return reachableFrom({srcs.begin(), srcs.end()}, std::move(pending), std::forward<Edges>(edges));
|
| 245 | }
|
| 246 |
|
| 247 | const EdgeLabelSet& labels(const Vertex& from, const Vertex& to) const {
|
| 248 | if constexpr (UnitEdgeLabels) {
|
| 249 | if (contains(from, to)) return _labels.unit;
|
| 250 | } else {
|
| 251 | auto it = _labels.find({from, to});
|
| 252 | if (it != _labels.end()) return it->second;
|
| 253 | }
|
| 254 |
|
| 255 | return nullLabel;
|
| 256 | }
|
| 257 |
|
| 258 | /** Determines whether the given vertex is present */
|
| 259 | bool contains(const Vertex& vertex) const {
|
| 260 | return _vertices.find(vertex) != _vertices.end();
|
| 261 | }
|
| 262 |
|
| 263 | /** Determines whether the given edge is present */
|
| 264 | bool contains(const Vertex& from, const Vertex& to) const {
|
| 265 | auto pos = _successors.find(from);
|
| 266 | if (pos == _successors.end()) {
|
| 267 | return false;
|
| 268 | }
|
| 269 | auto p2 = pos->second.find(to);
|
| 270 | return p2 != pos->second.end();
|
| 271 | }
|
| 272 |
|
| 273 | bool contains(const Vertex& from, const Vertex& to, const EdgeLabel& label) const {
|
| 274 | if constexpr (UnitEdgeLabels) {
|
| 275 | return contains(from, to);
|
| 276 | } else {
|
| 277 | auto it = _labels.find({from, to});
|
| 278 | return it != _labels.end() && containsValue(it->second, label);
|
| 279 | }
|
| 280 | }
|
| 281 |
|
| 282 | /** Determines whether there is a directed path between the two vertices */
|
| 283 | bool reaches(const Vertex& from, const Vertex& to) const {
|
| 284 | // quick check
|
| 285 | if (!contains(from) || !contains(to)) {
|
| 286 | return false;
|
| 287 | }
|
| 288 |
|
| 289 | // conduct a depth-first search starting at from
|
| 290 | bool found = false;
|
| 291 | bool first = true;
|
| 292 | visit(from, [&](const Vertex& cur) {
|
| 293 | found = !first && (found || cur == to);
|
| 294 | first = false;
|
| 295 | });
|
| 296 | return found;
|
| 297 | }
|
| 298 |
|
| 299 | /** Obtains the set of all vertices in the same clique than the given vertex */
|
| 300 | VertexSet clique(const Vertex& vertex) const {
|
| 301 | VertexSet res;
|
| 302 | res.insert(vertex);
|
| 303 | for (const auto& cur : vertices()) {
|
| 304 | if (reaches(vertex, cur) && reaches(cur, vertex)) {
|
| 305 | res.insert(cur);
|
| 306 | }
|
| 307 | }
|
| 308 | return res;
|
| 309 | }
|
| 310 |
|
| 311 | template <typename C>
|
| 312 | self_t induced(const C& nodes) const {
|
| 313 | VertexSet xs;
|
| 314 | for (auto&& n : nodes)
|
| 315 | if (containsValue(_vertices, n)) xs.insert(n);
|
| 316 |
|
| 317 | return inducedImpl(std::move(xs));
|
| 318 | }
|
| 319 |
|
| 320 | self_t inducedReachableDijkstra(const Vertex& source, const std::set<Vertex>& sinks) const {
|
| 321 | // `sink_depths` seperate from `depths` to handle case where `source \in sinks`,
|
| 322 | // otherwise we'd see a sink as having depth 0 on the backwards pass.
|
| 323 | std::map<Vertex, size_t, CompareVertex> sink_depths;
|
| 324 | std::map<Vertex, size_t, CompareVertex> depths;
|
| 325 | std::deque<Vertex> pending;
|
| 326 |
|
| 327 | auto update = [&](const Vertex& x, size_t depth) {
|
| 328 | auto it = depths.find(x);
|
| 329 | if (it != depths.end() && it->second <= depth) return false;
|
| 330 |
|
| 331 | depths[x] = depth;
|
| 332 | pending.push_back(x);
|
| 333 | return true;
|
| 334 | };
|
| 335 |
|
| 336 | update(source, 0);
|
| 337 |
|
| 338 | while (!pending.empty() && sink_depths.size() < sinks.size()) {
|
| 339 | auto x = pending.front();
|
| 340 | pending.pop_front();
|
| 341 |
|
| 342 | auto depth = depths.at(x);
|
| 343 | for (auto&& succ : successors(x)) {
|
| 344 | if (souffle::contains(sinks, succ)) {
|
| 345 | sink_depths.insert({succ, depth + 1});
|
| 346 | // Keep walking.
|
| 347 | // 1) The shortest path 'tween a src-sink pair could pass through a different sink.
|
| 348 | // 2) We want all shortest paths, not just one shortest path.
|
| 349 | // e.g. ```
|
| 350 | // a --> b --> d -> e
|
| 351 | // \-> c -/
|
| 352 | // ```
|
| 353 | // Source : `a`
|
| 354 | // Sinks : `{d, e}`
|
| 355 | }
|
| 356 |
|
| 357 | update(succ, depth + 1);
|
| 358 | }
|
| 359 | }
|
| 360 |
|
| 361 | self_t induced;
|
| 362 | std::vector<std::pair<Vertex, size_t>> rev_pending(sink_depths.begin(), sink_depths.end());
|
| 363 | while (!rev_pending.empty()) {
|
| 364 | auto [x, depth] = rev_pending.back();
|
| 365 | rev_pending.pop_back();
|
| 366 | assert(1 <= depth && "rev-walk should terminate at source");
|
| 367 |
|
| 368 | for (auto&& pred : predecessors(x)) {
|
| 369 | auto it = depths.find(pred);
|
| 370 | if (it == depths.end() || depth <= it->second) continue; // edge not in shortest-paths
|
| 371 | assert(it->second == depth - 1 && "shorter path found on reverse walk?");
|
| 372 | assert(((1 == depth) == (pred == source)) && "depth-1 vertices should only link to `source`");
|
| 373 |
|
| 374 | // 1) not already in `rev_pending` (implied by `x \in induced`)
|
| 375 | // 2) not the source
|
| 376 | if (!induced.contains(pred) && 1 < depth) {
|
| 377 | rev_pending.push_back({pred, depth - 1});
|
| 378 | }
|
| 379 |
|
| 380 | induced.insert(pred, x, labels(pred, x));
|
| 381 | }
|
| 382 | }
|
| 383 |
|
| 384 | return induced;
|
| 385 | }
|
| 386 |
|
| 387 | /** A generic utility for depth-first pre-order visits */
|
| 388 | template <typename Lambda>
|
| 389 | void visit(const Vertex& vertex, const Lambda& lambda) const {
|
| 390 | visitDepthFirst(vertex, [&](Visit e, auto&& v) {
|
| 391 | if (e == Visit::pre) lambda(v);
|
| 392 | });
|
| 393 | }
|
| 394 |
|
| 395 | /** A generic utility for depth-first visits */
|
| 396 | template <typename Lambda>
|
| 397 | void visitDepthFirst(const Vertex& vertex, const Lambda& lambda) const {
|
| 398 | VertexSet visited;
|
| 399 | visitDepthFirst(vertex, lambda, std::mem_fn(&GraphLabeled::successors), visited);
|
| 400 | }
|
| 401 |
|
| 402 | // if there are multiple sources then pretend there is a pseudo-source node with edge to each
|
| 403 | template <typename Lambda>
|
| 404 | void visitDepthFirstSources(const Lambda& lambda) const {
|
| 405 | // pseudo node can be impl by iterating over each source w/ a shared `visited`
|
| 406 | VertexSet visited;
|
| 407 | for (auto&& v : vertices())
|
| 408 | if (predecessors(v).empty()) {
|
| 409 | visitDepthFirst(v, lambda, std::mem_fn(&GraphLabeled::successors), visited);
|
| 410 | }
|
| 411 | }
|
| 412 |
|
| 413 | /** Enables graphs to be printed (e.g. for debugging) */
|
| 414 | void print(std::ostream& os) const {
|
| 415 | bool first = true;
|
| 416 | os << "{";
|
| 417 | for (auto&& curr : vertices()) {
|
| 418 | auto&& succs = successors(curr);
|
| 419 | for (auto&& succ : succs) {
|
| 420 | if (!first) os << "\n,";
|
| 421 | first = false;
|
| 422 |
|
| 423 | os << curr << "->" << succ;
|
| 424 | if constexpr (!UnitEdgeLabels) {
|
| 425 | os << " [" << join(labels(curr, succ)) << "]";
|
| 426 | }
|
| 427 | }
|
| 428 |
|
| 429 | // handle case where node is disconnected
|
| 430 | if (succs.empty() && predecessors(curr).empty()) {
|
| 431 | if (!first) os << "\n,";
|
| 432 | first = false;
|
| 433 | os << curr;
|
| 434 | }
|
| 435 | }
|
| 436 | os << "}";
|
| 437 | }
|
| 438 |
|
| 439 | friend std::ostream& operator<<(std::ostream& out, const self_t& g) {
|
| 440 | g.print(out);
|
| 441 | return out;
|
| 442 | }
|
| 443 |
|
| 444 | void DBG_sanCheck() const {
|
| 445 | #ifndef NDEBUG
|
| 446 | auto checkPeer = [&](auto&& src, auto&& peer) {
|
| 447 | for (auto&& [n, ms] : src) {
|
| 448 | assert(!ms.empty() && "shouldn't store empty sets");
|
| 449 | assert(containsValue(_vertices, n));
|
| 450 | for (auto&& m : ms) {
|
| 451 | assert(containsValue(_vertices, m));
|
| 452 | assert(containsValue(peer, m));
|
| 453 | assert(containsValue(peer.at(m), n));
|
| 454 | }
|
| 455 | }
|
| 456 | };
|
| 457 |
|
| 458 | checkPeer(_successors, _predecessors);
|
| 459 | checkPeer(_predecessors, _successors);
|
| 460 |
|
| 461 | if constexpr (!UnitEdgeLabels) {
|
| 462 | for (auto&& [kv, labels] : _labels) {
|
| 463 | auto&& [n, m] = kv;
|
| 464 | assert(!labels.empty() && "shouldn't store an empty label set");
|
| 465 | assert(containsValue(_successors.at(n), m));
|
| 466 | }
|
| 467 | }
|
| 468 | #endif
|
| 469 | }
|
| 470 |
|
| 471 | private:
|
| 472 | using Vertex2Peer = std::map<Vertex, VertexSet, CompareVertex>;
|
| 473 | using EdgeVerts = std::pair<Vertex, Vertex>;
|
| 474 | using Edge2Labels =
|
| 475 | std::conditional_t<UnitEdgeLabels, detail::GraphUnitEdgeSet, std::map<EdgeVerts, EdgeLabelSet>>;
|
| 476 |
|
| 477 | // not a very efficient but simple graph representation
|
| 478 | VertexSet null; // the empty set
|
| 479 | EdgeLabelSet nullLabel; // the empty set
|
| 480 | VertexSet _vertices; // all the vertices in the graph
|
| 481 | Vertex2Peer _successors; // all edges forward directed
|
| 482 | Vertex2Peer _predecessors; // all edges backward
|
| 483 | Edge2Labels _labels;
|
| 484 |
|
| 485 | /** The internal implementation of depth-first visits */
|
| 486 | template <typename Fn, typename Edges>
|
| 487 | void visitDepthFirst(const Vertex& v, const Fn& lambda, const Edges& edges, VertexSet& visited) const {
|
| 488 | lambda(Visit::pre, v);
|
| 489 |
|
| 490 | for (auto&& next : edges(*this, v))
|
| 491 | if (visited.insert(next).second) {
|
| 492 | visitDepthFirst(next, lambda, edges, visited);
|
| 493 | }
|
| 494 |
|
| 495 | lambda(Visit::post, v);
|
| 496 | }
|
| 497 |
|
| 498 | template <typename Edges>
|
| 499 | VertexSet reachableFrom(VertexSet visited, std::vector<Vertex> pending, Edges&& edges) const {
|
| 500 | assert(visited.size() == pending.size());
|
| 501 | assert(all_of(pending, [&](auto&& x) { return souffle::contains(visited, x); }));
|
| 502 |
|
| 503 | while (!pending.empty()) {
|
| 504 | auto curr = pending.back();
|
| 505 | pending.pop_back();
|
| 506 | for (auto&& next : edges(*this, curr))
|
| 507 | if (visited.insert(next).second) {
|
| 508 | pending.push_back(next);
|
| 509 | }
|
| 510 | }
|
| 511 |
|
| 512 | return visited;
|
| 513 | }
|
| 514 |
|
| 515 | template <typename EdgePair>
|
| 516 | size_t removeEdgesIncidentTo(Vertex2Peer& fwd, Vertex2Peer& rev, const Vertex& node, EdgePair&& edge) {
|
| 517 | auto it = fwd.find(node);
|
| 518 | if (it == fwd.end()) return 0;
|
| 519 |
|
| 520 | size_t n_edges = 0;
|
| 521 | if constexpr (UnitEdgeLabels) {
|
| 522 | n_edges = it->second.size();
|
| 523 | }
|
| 524 |
|
| 525 | for (auto&& adj : it->second) {
|
| 526 | removeExistingAdjEdge(rev, adj, node);
|
| 527 |
|
| 528 | if constexpr (!UnitEdgeLabels) {
|
| 529 | auto it_label = _labels.find(edge(node, adj));
|
| 530 | n_edges += it_label->second.size();
|
| 531 | _labels.erase(it_label);
|
| 532 | }
|
| 533 | }
|
| 534 |
|
| 535 | fwd.erase(it);
|
| 536 | return n_edges;
|
| 537 | }
|
| 538 |
|
| 539 | self_t inducedImpl(VertexSet nodes) const {
|
| 540 | DBG_sanCheck();
|
| 541 | assert(std::includes(_vertices.begin(), _vertices.end(), nodes.begin(), nodes.end()) &&
|
| 542 | "`nodes` must be a subset of `_vertices`");
|
| 543 |
|
| 544 | self_t induced;
|
| 545 | induced._vertices = std::move(nodes);
|
| 546 |
|
| 547 | for (auto&& n : induced._vertices) {
|
| 548 | auto addEdges = [&](auto&& dst_map, auto&& src) {
|
| 549 | if (src.empty()) return;
|
| 550 |
|
| 551 | auto&& [it, _] = dst_map.insert({n, {}});
|
| 552 | auto& dst = it->second;
|
| 553 | bool added_anything = false;
|
| 554 | for (auto&& m : src)
|
| 555 | if (containsValue(induced._vertices, m)) {
|
| 556 | added_anything = true;
|
| 557 | dst.insert(m);
|
| 558 | }
|
| 559 |
|
| 560 | if (!added_anything) dst_map.erase(it);
|
| 561 | };
|
| 562 |
|
| 563 | addEdges(induced._successors, successors(n));
|
| 564 | addEdges(induced._predecessors, predecessors(n));
|
| 565 |
|
| 566 | if constexpr (!UnitEdgeLabels) {
|
| 567 | for (auto&& m : induced.successors(n))
|
| 568 | induced._labels[{n, m}] = labels(n, m);
|
| 569 | }
|
| 570 | }
|
| 571 |
|
| 572 | induced.DBG_sanCheck();
|
| 573 | return induced;
|
| 574 | }
|
| 575 |
|
| 576 | static void removeExistingAdjEdge(Vertex2Peer& adj, const Vertex& a, const Vertex& b) {
|
| 577 | auto it = adj.find(a);
|
| 578 | assert(it != adj.end());
|
| 579 | [[maybe_unused]] auto n = it->second.erase(b);
|
| 580 | assert(n == 1);
|
| 581 | if (it->second.empty()) adj.erase(it);
|
| 582 | }
|
| 583 |
|
| 584 | static VertexSet keysOfAdjacency(const Vertex2Peer& adj) {
|
| 585 | VertexSet xs;
|
| 586 | for (auto&& [k, _] : adj)
|
| 587 | xs.insert(k);
|
| 588 | return xs;
|
| 589 | }
|
| 590 | };
|
| 591 |
|
| 592 | template <typename Vertex, typename Compare = std::less<Vertex>>
|
| 593 | using Graph = GraphLabeled<Vertex, Unit, Compare>;
|
| 594 |
|
| 595 | } // end of namespace souffle
|