graph_adjacency.hh 41.9 KB
Newer Older
1 2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
4
//
5 6 7 8
// This program is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the Free
// Software Foundation; either version 3 of the License, or (at your option) any
// later version.
9
//
10 11 12 13
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
// details.
14
//
15
// You should have received a copy of the GNU Lesser General Public License
16 17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18 19 20 21 22 23 24
#ifndef GRAPH_ADJACENCY_HH
#define GRAPH_ADJACENCY_HH

#include <vector>
#include <deque>
#include <utility>
#include <numeric>
Tiago Peixoto's avatar
Tiago Peixoto committed
25
#include <tuple>
26 27 28 29 30 31 32 33
#include <boost/iterator.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/range/irange.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/iterator_facade.hpp>

34 35 36 37
#ifdef __clang__
#include <boost/algorithm/minmax_element.hpp>
#endif

38 39
#include "transform_iterator.hh"

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
namespace boost
{

// ========================================================================
// Forward declarations
// ========================================================================

template <class Vertex>
class adj_list;

// forward declaration of manipulation functions
template <class Vertex>
std::pair<typename adj_list<Vertex>::vertex_iterator,
          typename adj_list<Vertex>::vertex_iterator>
vertices(const adj_list<Vertex>& g);

template <class Vertex>
std::pair<typename adj_list<Vertex>::edge_iterator,
          typename adj_list<Vertex>::edge_iterator>
edges(const adj_list<Vertex>& g);

template <class Vertex>
62
std::pair<typename adj_list<Vertex>::edge_descriptor, bool>
63 64 65 66 67 68 69 70
edge(Vertex s, Vertex t, const adj_list<Vertex>& g);

template <class Vertex>
size_t out_degree(Vertex v, const adj_list<Vertex>& g);

template <class Vertex>
size_t in_degree(Vertex v, const adj_list<Vertex>& g);

71 72 73
template <class Vertex>
size_t degree(Vertex v, const adj_list<Vertex>& g);

74 75 76 77 78 79 80 81 82 83
template <class Vertex>
std::pair<typename adj_list<Vertex>::out_edge_iterator,
          typename adj_list<Vertex>::out_edge_iterator>
out_edges(Vertex v, const adj_list<Vertex>& g);

template <class Vertex>
std::pair<typename adj_list<Vertex>::in_edge_iterator,
          typename adj_list<Vertex>::in_edge_iterator>
in_edges(Vertex v, const adj_list<Vertex>& g);

84 85 86 87 88 89 90 91 92 93
template <class Vertex>
std::pair<typename adj_list<Vertex>::out_edge_iterator,
          typename adj_list<Vertex>::out_edge_iterator>
_all_edges_out(Vertex v, const adj_list<Vertex>& g);

template <class Vertex>
std::pair<typename adj_list<Vertex>::in_edge_iterator,
          typename adj_list<Vertex>::in_edge_iterator>
_all_edges_in(Vertex v, const adj_list<Vertex>& g);

94 95 96 97 98 99 100 101 102 103
template <class Vertex>
std::pair<typename adj_list<Vertex>::all_edge_iterator,
          typename adj_list<Vertex>::all_edge_iterator>
all_edges(Vertex v, const adj_list<Vertex>& g);

template <class Vertex>
std::pair<typename adj_list<Vertex>::all_edge_iterator_reversed,
          typename adj_list<Vertex>::all_edge_iterator_reversed>
_all_edges_reversed(Vertex v, const adj_list<Vertex>& g);

104 105 106 107 108
template <class Vertex>
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
adjacent_vertices(Vertex v, const adj_list<Vertex>& g);

109 110 111
template <class Vertex>
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
112
out_neighbors(Vertex v, const adj_list<Vertex>& g);
113 114 115 116

template <class Vertex>
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
117
in_neighbors(Vertex v, const adj_list<Vertex>& g);
118

119 120 121
template <class Vertex>
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
122
all_neighbors(Vertex v, const adj_list<Vertex>& g);
123

124 125 126 127 128 129 130 131 132 133 134 135
template <class Vertex>
size_t num_vertices(const adj_list<Vertex>& g);

template <class Vertex>
size_t num_edges(const adj_list<Vertex>& g);

template <class Vertex>
Vertex add_vertex(adj_list<Vertex>& g);

template <class Vertex>
void clear_vertex(Vertex v, adj_list<Vertex>& g);

136 137 138
template <class Vertex, class Pred>
void clear_vertex(Vertex v, adj_list<Vertex>& g, Pred&& pred);

139 140 141
template <class Vertex>
void remove_vertex(Vertex v, adj_list<Vertex>& g);

142 143 144
template <class Vertex>
void remove_vertex_fast(Vertex v, adj_list<Vertex>& g);

145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
template <class Vertex>
std::pair<typename adj_list<Vertex>::edge_descriptor, bool>
add_edge(Vertex s, Vertex t, adj_list<Vertex>& g);

template <class Vertex>
void remove_edge(Vertex s, Vertex t, adj_list<Vertex>& g);

template <class Vertex>
void remove_edge(const typename adj_list<Vertex>::edge_descriptor& e,
                 adj_list<Vertex>& g);

// ========================================================================
// adj_list<Vertex>
// ========================================================================
//
// adj_list is a very simple adjacency list implementation for bidirectional
// graphs based on std::vector, meant to be reasonably efficient both
// memory-wise and computationally. It maintains a list of in and out-edges for
// each vertex, and each edge has a built-in index (which is replicated in both
// lists). For each edge, a total of 4 integers is necessary: the source and
// target vertices, in the in_edges and out_edges lists, respectively, and the
// (same) edge index in both lists. The integer type is given by the Vertex
// template parameter. It achieves about half as much memory as
// boost::adjacency_list with an edge index property map and the same integer
// type.

// The complexity guarantees and iterator invalidation rules are the same as
// boost::adjacency_list with vector storage selectors for both vertex and edge
// lists.

175 176 177 178 179 180 181 182
namespace detail
{
template <class Vertex>
struct adj_edge_descriptor
{
    adj_edge_descriptor()
        : s(std::numeric_limits<Vertex>::max()),
          t(std::numeric_limits<Vertex>::max()),
183 184 185
          idx(std::numeric_limits<Vertex>::max()) {};
    adj_edge_descriptor(Vertex s, Vertex t, Vertex idx)
        : s(s), t(t), idx(idx) {}
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203

    bool operator==(const adj_edge_descriptor& other) const
    {
        return idx == other.idx;
    }
    bool operator!=(const adj_edge_descriptor& other) const
    {
        return idx != other.idx;
    }
    bool operator<(const adj_edge_descriptor& other) const
    {
        return idx < other.idx;
    }

    Vertex s, t, idx;
};
} // namespace detail

204 205 206 207 208 209
template <class Vertex = size_t>
class adj_list
{
public:
    struct graph_tag {};
    typedef Vertex vertex_t;
210

211
    typedef detail::adj_edge_descriptor<Vertex> edge_descriptor;
212

213
    typedef std::vector<std::pair<vertex_t, vertex_t> > edge_list_t;
214
    typedef std::vector<std::pair<size_t, edge_list_t>> vertex_list_t;
215 216
    typedef typename integer_range<Vertex>::iterator vertex_iterator;

217
    adj_list(): _n_edges(0), _edge_index_range(0), _keep_epos(false) {}
218

219 220 221 222
    struct get_vertex
    {
        get_vertex() {}
        typedef Vertex result_type;
223
        [[gnu::always_inline]]
224 225 226 227
        Vertex operator()(const std::pair<vertex_t, vertex_t>& v) const
        { return v.first; }
    };

228 229
    typedef transform_random_access_iterator<get_vertex,
                                             typename edge_list_t::const_iterator>
230 231
        adjacency_iterator;

232
    typedef adjacency_iterator in_adjacency_iterator;
233

234 235 236
    template <class Base>
    struct edge_iter_facade:
        public boost::iterator_facade<Base,
237 238 239
                                      edge_descriptor,
                                      std::random_access_iterator_tag,
                                      edge_descriptor>
240 241 242 243 244
    {};

    template <class Dereference>
    struct base_edge_iterator:
        public edge_iter_facade<base_edge_iterator<Dereference>>
245 246
    {
        base_edge_iterator() {}
247
        [[gnu::always_inline]]
248 249 250 251 252 253
        base_edge_iterator(vertex_t v, typename edge_list_t::const_iterator&& iter)
            : _v(v), _iter(std::forward<typename edge_list_t::const_iterator>(iter))
        {}

    private:
        friend class boost::iterator_core_access;
254
        [[gnu::always_inline]] [[gnu::flatten]]
255
        void increment() { ++_iter; }
256 257

        [[gnu::always_inline]] [[gnu::flatten]]
258
        void decrement() { --_iter; }
259

Tiago Peixoto's avatar
Tiago Peixoto committed
260
        template <class Distance>
261
        [[gnu::always_inline]] [[gnu::flatten]]
Tiago Peixoto's avatar
Tiago Peixoto committed
262
        void advance(Distance n) { _iter += n; }
263 264

        [[gnu::always_inline]] [[gnu::flatten]]
265 266 267 268 269
        auto distance_to(base_edge_iterator const& other) const
        {
            return other._iter - _iter;
        }

270
        [[gnu::always_inline]] [[gnu::flatten]]
271 272 273 274 275
        bool equal(base_edge_iterator const& other) const
        {
            return _iter == other._iter;
        }

276
        [[gnu::always_inline]] [[gnu::flatten]]
277 278
        edge_descriptor dereference() const
        {
279 280 281 282 283 284 285 286
            return Dereference::def(_v, *_iter, *this);
        }

    public:
        [[gnu::always_inline]] [[gnu::flatten]]
        edge_descriptor operator*() const
        {
            return edge_iter_facade<base_edge_iterator>::operator*();
287 288
        }

289
    protected:
290 291 292 293
        vertex_t _v;
        typename edge_list_t::const_iterator _iter;
    };

294 295
    struct make_out_edge
    {
296
        template <class Iter>
297
        static edge_descriptor def(vertex_t src,
298 299
                                   const std::pair<vertex_t, vertex_t>& v,
                                   Iter&&)
300
        { return edge_descriptor(src, v.first, v.second); }
301 302 303 304

        static edge_descriptor def(vertex_t src,
                                   const std::pair<vertex_t, vertex_t>& v)
        { return def(src, v, nullptr); }
305 306 307 308
    };

    struct make_in_edge
    {
309
        template <class Iter>
310
        static edge_descriptor def(vertex_t tgt,
311 312
                                   const std::pair<vertex_t, vertex_t>& v,
                                   Iter&&)
313
        { return edge_descriptor(v.first, tgt, v.second); }
314 315 316 317

        static edge_descriptor def(vertex_t tgt,
                                   const std::pair<vertex_t, vertex_t>& v)
        { return def(tgt, v, nullptr); }
318 319
    };

320 321
    typedef base_edge_iterator<make_out_edge> out_edge_iterator;
    typedef base_edge_iterator<make_in_edge> in_edge_iterator;
322

323 324 325 326 327

    template <class Iter, bool reversed>
    struct make_in_or_out_edge
    {
        template <class I>
328
        [[gnu::always_inline]] [[gnu::flatten]]
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
        static edge_descriptor def(vertex_t u,
                                   const std::pair<vertex_t, vertex_t>& v,
                                   const I& i)
        {
            const Iter& iter = reinterpret_cast<const Iter&>(i);
            if ((iter._iter < iter._pos) != reversed)
                return edge_descriptor(u, v.first, v.second);
            else
                return edge_descriptor(v.first, u, v.second);
        }
    };

    template <bool reversed>
    struct all_edge_iterator_base:
        public base_edge_iterator<make_in_or_out_edge<all_edge_iterator_base<reversed>,
                                                      reversed>>
    {
        all_edge_iterator_base() {}
347
        [[gnu::always_inline]]
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
        all_edge_iterator_base(vertex_t v,
                               typename edge_list_t::const_iterator&& iter,
                               const typename edge_list_t::const_iterator& pos)
            : base_edge_iterator<make_in_or_out_edge<all_edge_iterator_base,
                                                     reversed>>
                  (v, std::forward<typename edge_list_t::const_iterator>(iter)),
              _pos(pos)
        {}

    private:
        friend struct make_in_or_out_edge<all_edge_iterator_base<reversed>,
                                          reversed>;
        typename edge_list_t::const_iterator _pos;
    };

    typedef all_edge_iterator_base<false> all_edge_iterator;
    typedef all_edge_iterator_base<true>  all_edge_iterator_reversed;

366 367 368 369 370 371 372 373
    class edge_iterator:
        public boost::iterator_facade<edge_iterator,
                                      edge_descriptor,
                                      boost::forward_traversal_tag,
                                      edge_descriptor>
    {
    public:
        edge_iterator() {}
374
        [[gnu::always_inline]]
375 376 377
        explicit edge_iterator(const typename vertex_list_t::const_iterator& vi_begin,
                               const typename vertex_list_t::const_iterator& vi_end,
                               const typename vertex_list_t::const_iterator& vi,
378 379 380 381 382 383 384 385 386 387
                               const typename edge_list_t::const_iterator& ei)
            : _vi_begin(vi_begin), _vi_end(vi_end), _vi(vi), _ei(ei)
        {
            // move position to first edge
            skip();
        }

    private:
        friend class boost::iterator_core_access;

388
        [[gnu::always_inline]] [[gnu::flatten]]
389 390 391
        void skip()
        {
            //skip empty vertices
392 393
            while (_vi != _vi_end &&
                   _ei == _vi->second.begin() + _vi->first)
394 395 396
            {
                ++_vi;
                if (_vi != _vi_end)
397
                    _ei = _vi->second.begin();
398 399 400
            }
        }

401
        [[gnu::always_inline]] [[gnu::flatten]]
402 403 404 405 406 407
        void increment()
        {
            ++_ei;
            skip();
        }

408
        [[gnu::always_inline]] [[gnu::flatten]]
409 410 411 412 413 414 415
        bool equal(edge_iterator const& other) const
        {
            if (_vi_begin == _vi_end)
                return _vi == other._vi;
            return _vi == other._vi && _ei == other._ei;
        }

416
        [[gnu::always_inline]] [[gnu::flatten]]
417 418
        edge_descriptor dereference() const
        {
419
            return edge_descriptor(vertex_t(_vi - _vi_begin),
420
                                   _ei->first, _ei->second);
421 422
        }

423 424 425
        typename vertex_list_t::const_iterator _vi_begin;
        typename vertex_list_t::const_iterator _vi_end;
        typename vertex_list_t::const_iterator _vi;
426 427 428 429 430 431
        typename edge_list_t::const_iterator _ei;
    };

    void reindex_edges()
    {
        _free_indexes.clear();
432
        _edge_index_range = 0;
433 434 435
        for (auto& es : _edges)
            es.second.resize(es.first);
        for (size_t i = 0; i < _edges.size(); ++i)
436
        {
437 438 439
            auto pos = _edges[i].first;
            auto& es = _edges[i].second;
            for (size_t j = 0; j < pos; ++j)
440
            {
441
                auto& oe = es[j];
442
                Vertex v = oe.first;
443
                oe.second = _edge_index_range;
444
                _edges[v].second.emplace_back(i, _edge_index_range);
445
                _edge_index_range++;
446
            }
447
        }
448 449 450 451 452 453 454 455 456

        if (_keep_epos)
            rebuild_epos();
    }

    void set_keep_epos(bool keep)
    {
        if (keep)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
457
            if (!_keep_epos)
458 459 460 461 462 463 464 465 466 467 468 469
                rebuild_epos();
        }
        else
        {
            _epos.clear();
        }
        _keep_epos = keep;
    }

    bool get_keep_epos()
    {
        return _keep_epos;
470 471
    }

472
    size_t get_edge_index_range() const { return _edge_index_range; }
473

474 475
    static Vertex null_vertex() { return std::numeric_limits<Vertex>::max(); }

476 477
    void shrink_to_fit()
    {
478 479 480
        _edges.shrink_to_fit();
        std::for_each(_edges.begin(), _edges.end(),
                      [](auto &es){es.second.shrink_to_fit();});
481
        auto erange = boost::edges(*this);
482 483 484 485 486 487 488 489 490 491 492 493

// Clang 8.0 fails to correctly recognize these as ForwardIterators,
// triggering a static_assert in std::max_element(). See #576.
#ifndef __clang__
        auto iter = std::max_element(
#else
        auto iter = boost::first_max_element(
#endif
            erange.first, erange.second,
            [](const auto &a, const auto& b) -> bool
            {return a.idx < b.idx;});

494
        if (iter == erange.second)
495
            _edge_index_range = 0;
496
        else
497
            _edge_index_range = iter->idx + 1;
498 499 500
        auto iter_idx = std::remove_if(_free_indexes.begin(),
                                       _free_indexes.end(),
                                       [&](auto idx) -> bool
501
                                       {return idx >= _edge_index_range;});
502 503 504
        _free_indexes.erase(iter_idx, _free_indexes.end());
        _free_indexes.shrink_to_fit();
        if (_keep_epos)
505
            _epos.resize(_edge_index_range);
506 507 508
        _epos.shrink_to_fit();
    }

509
    [[gnu::always_inline]] [[gnu::flatten]]
510 511 512 513 514 515 516 517
    void reverse_edge(edge_descriptor& e) const
    {
        auto& elist = _edges[e.s];
        auto pos = elist.first;
        auto& es = elist.second;
        if (_keep_epos)
        {
            auto& epos = _epos[e.idx];
518
            if (epos.first >= pos || es[epos.first].second != e.idx)
519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
                std::swap(e.s, e.t);
        }
        else
        {
            bool found = false;
            for (size_t i = 0; i < pos; ++i)
            {
                if (es[i].second == e.idx)
                {
                    found = true;
                    break;
                }
            }
            if (!found)
                std::swap(e.s, e.t);
        }
    }

537
private:
538
    vertex_list_t _edges;
539
    size_t _n_edges;
540
    size_t _edge_index_range;
541 542 543 544
    std::deque<size_t> _free_indexes; // indexes of deleted edges to be used up
                                      // for new edges to avoid very large
                                      // indexes, and unnecessary property map
                                      // memory use
545
    bool _keep_epos;
546
    std::vector<std::pair<uint32_t, uint32_t>> _epos; // out, in
547 548 549

    void rebuild_epos()
    {
550
        _epos.resize(_edge_index_range);
551
        for (auto& pes : _edges)
552
        {
553 554 555
            auto pos = pes.first;
            auto& es = pes.second;
            for (size_t j = 0; j < es.size(); ++j)
556
            {
557 558 559 560 561
                size_t idx = es[j].second;
                if (j < pos)
                    _epos[idx].first = j;
                else
                    _epos[idx].second = j;
562
            }
563 564 565
        }
        //check_epos();
    }
566

567 568 569 570 571 572 573 574
    void check_epos()
    {
#ifndef NDEBUG
        for (auto& pes : _edges)
        {
            auto pos = pes.first;
            auto& es = pes.second;
            for (size_t j = 0; j < es.size(); ++j)
575
            {
576 577 578 579 580
                assert(es[j].second < _epos.size());
                if (j < pos)
                    assert(_epos[es[j].second].first == j);
                else
                    assert(_epos[es[j].second].second == j);
581 582
            }
        }
583
#endif
584
    }
585 586 587 588 589 590 591 592

    // manipulation functions
    friend std::pair<vertex_iterator, vertex_iterator>
    vertices<>(const adj_list<Vertex>& g);

    friend std::pair<edge_iterator, edge_iterator>
    edges<>(const adj_list<Vertex>& g);

593
    friend std::pair<edge_descriptor, bool>
594 595 596 597 598 599
    edge<>(Vertex s, Vertex t, const adj_list<Vertex>& g);

    friend size_t out_degree<>(Vertex v, const adj_list<Vertex>& g);

    friend size_t in_degree<>(Vertex v, const adj_list<Vertex>& g);

600 601
    friend size_t degree<>(Vertex v, const adj_list<Vertex>& g);

602 603 604 605 606 607
    friend std::pair<out_edge_iterator, out_edge_iterator>
    out_edges<>(Vertex v, const adj_list<Vertex>& g);

    friend std::pair<in_edge_iterator, in_edge_iterator>
    in_edges<>(Vertex v, const adj_list<Vertex>& g);

608 609 610 611 612 613
    friend std::pair<out_edge_iterator, out_edge_iterator>
    _all_edges_out<>(Vertex v, const adj_list<Vertex>& g);

    friend std::pair<in_edge_iterator, in_edge_iterator>
    _all_edges_in<>(Vertex v, const adj_list<Vertex>& g);

614 615 616 617 618 619
    friend std::pair<all_edge_iterator, all_edge_iterator>
    all_edges<>(Vertex v, const adj_list<Vertex>& g);

    friend std::pair<all_edge_iterator_reversed, all_edge_iterator_reversed>
    _all_edges_reversed<>(Vertex v, const adj_list<Vertex>& g);

620 621 622
    friend std::pair<adjacency_iterator, adjacency_iterator>
    adjacent_vertices<>(Vertex v, const adj_list<Vertex>& g);

623
    friend std::pair<adjacency_iterator, adjacency_iterator>
624
    out_neighbors<>(Vertex v, const adj_list<Vertex>& g);
625 626

    friend std::pair<adjacency_iterator, adjacency_iterator>
627
    in_neighbors<>(Vertex v, const adj_list<Vertex>& g);
628

629
    friend std::pair<adjacency_iterator, adjacency_iterator>
630
    all_neighbors<>(Vertex v, const adj_list<Vertex>& g);
631

632 633 634 635 636 637
    friend size_t num_vertices<>(const adj_list<Vertex>& g);

    friend size_t num_edges<>(const adj_list<Vertex>& g);

    friend Vertex add_vertex<>(adj_list<Vertex>& g);

638 639
    template <class V, class Pred>
    friend void clear_vertex(V v, adj_list<V>& g, Pred&& pred);
640 641 642

    friend void remove_vertex<>(Vertex v, adj_list<Vertex>& g);

643 644
    friend void remove_vertex_fast<>(Vertex v, adj_list<Vertex>& g);

645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
    friend std::pair<edge_descriptor, bool>
    add_edge<>(Vertex s, Vertex t, adj_list<Vertex>& g);

    friend void remove_edge<>(Vertex s, Vertex t, adj_list<Vertex>& g);

    friend void remove_edge<>(const edge_descriptor& e, adj_list<Vertex>& g);
};

//========================================================================
// Graph traits and BGL scaffolding
//========================================================================

struct adj_list_traversal_tag
    : public vertex_list_graph_tag,
      public edge_list_graph_tag,
      public adjacency_graph_tag,
661 662
      public bidirectional_graph_tag,
      public adjacency_matrix_tag {};
663 664 665 666 667 668 669 670

template <class Vertex>
struct graph_traits<adj_list<Vertex> >
{
    typedef Vertex vertex_descriptor;
    typedef typename adj_list<Vertex>::edge_descriptor edge_descriptor;
    typedef typename adj_list<Vertex>::edge_iterator edge_iterator;
    typedef typename adj_list<Vertex>::adjacency_iterator adjacency_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
671
    typedef typename adj_list<Vertex>::in_adjacency_iterator in_adjacency_iterator;
672 673 674 675 676 677 678 679 680 681 682 683 684 685

    typedef typename adj_list<Vertex>::out_edge_iterator out_edge_iterator;
    typedef typename adj_list<Vertex>::in_edge_iterator in_edge_iterator;

    typedef typename adj_list<Vertex>::vertex_iterator vertex_iterator;

    typedef bidirectional_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category;
    typedef adj_list_traversal_tag traversal_category;

    typedef Vertex vertices_size_type;
    typedef Vertex edges_size_type;
    typedef size_t degree_size_type;

686
    static Vertex null_vertex() { return adj_list<Vertex>::null_vertex(); }
687

688 689 690 691 692 693 694
private:
    BOOST_STATIC_ASSERT((is_convertible<typename std::iterator_traits<out_edge_iterator>::iterator_category,
                                        std::random_access_iterator_tag>::value));
    BOOST_STATIC_ASSERT((is_convertible<typename std::iterator_traits<in_edge_iterator>::iterator_category,
                                        std::random_access_iterator_tag>::value));
    BOOST_STATIC_ASSERT((is_convertible<typename std::iterator_traits<adjacency_iterator>::iterator_category,
                                        std::random_access_iterator_tag>::value));
695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726
};

template <class Vertex>
struct graph_traits<const adj_list<Vertex> >
    : public graph_traits<adj_list<Vertex> >
{
};


template <class Vertex>
struct edge_property_type<adj_list<Vertex> >
{
    typedef void type;
};

template <class Vertex>
struct vertex_property_type<adj_list<Vertex> >
{
    typedef void type;
};

template <class Vertex>
struct graph_property_type<adj_list<Vertex> >
{
    typedef void type;
};

//========================================================================
// Graph access and manipulation functions
//========================================================================

template <class Vertex>
727
[[gnu::always_inline]] [[gnu::flatten]] inline
728 729
std::pair<typename adj_list<Vertex>::vertex_iterator,
          typename adj_list<Vertex>::vertex_iterator>
730 731 732
vertices(const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::vertex_iterator vi_t;
733
    return {vi_t(0), vi_t(g._edges.size())};
734 735 736 737
}


template <class Vertex>
738
[[gnu::always_inline]] [[gnu::flatten]] inline
739 740
std::pair<typename adj_list<Vertex>::edge_iterator,
          typename adj_list<Vertex>::edge_iterator>
741 742 743 744
edges(const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::edge_list_t::const_iterator ei_t;
    typedef typename adj_list<Vertex>::vertex_list_t::const_iterator vi_t;
745 746
    ei_t ei_begin, ei_end;
    vi_t last_vi;
747
    if (g._edges.empty())
748
    {
749
        last_vi = g._edges.end();
750 751 752
    }
    else
    {
753 754 755
        ei_begin = g._edges[0].second.begin();
        last_vi = g._edges.end() - 1;
        ei_end = last_vi->second.begin() + last_vi->first;
756
    }
757 758 759
    typename adj_list<Vertex>::edge_iterator ebegin(g._edges.begin(),
                                                    g._edges.end(),
                                                    g._edges.begin(),
760
                                                    ei_begin);
761 762
    typename adj_list<Vertex>::edge_iterator eend(g._edges.begin(),
                                                  g._edges.end(),
763 764
                                                  last_vi,
                                                  ei_end);
Tiago Peixoto's avatar
Tiago Peixoto committed
765
    return {ebegin, eend};
766 767 768
}

template <class Vertex>
769
[[gnu::always_inline]] inline
770
Vertex vertex(size_t i, const adj_list<Vertex>&)
771 772 773 774 775
{
    return i;
}

template <class Vertex>
776
inline
777
std::pair<typename adj_list<Vertex>::edge_descriptor, bool>
778 779
edge(Vertex s, Vertex t, const adj_list<Vertex>& g)
{
780
    typedef typename adj_list<Vertex>::edge_descriptor edge_descriptor;
781 782 783 784 785
    const auto& pes = g._edges[s];
    auto pos = pes.first;
    const auto& es = pes.second;
    auto end = es.begin() + pos;
    auto iter = std::find_if(es.begin(), end,
786
                             [&](const auto& e) -> bool {return e.first == t;});
787 788 789
    if (iter != end)
        return {edge_descriptor(s, t, iter->second), true};
    return {edge_descriptor(), false};
790 791 792
}

template <class Vertex>
793
[[gnu::always_inline]] inline
794
size_t out_degree(Vertex v, const adj_list<Vertex>& g)
795
{
796 797
    const auto& pes = g._edges[v];
    return pes.first;
798 799 800
}

template <class Vertex>
801
[[gnu::always_inline]] inline
802
size_t in_degree(Vertex v, const adj_list<Vertex>& g)
803
{
804 805 806 807
    const auto& pes = g._edges[v];
    auto pos = pes.first;
    auto& es = pes.second;
    return es.size() - pos;
808 809 810
}

template <class Vertex>
811
[[gnu::always_inline]] inline
812
size_t degree(Vertex v, const adj_list<Vertex>& g)
813
{
814
    return g._edges[v].second.size();
815 816 817
}

template <class Vertex>
818
[[gnu::always_inline]] [[gnu::flatten]] inline
819 820
std::pair<typename adj_list<Vertex>::out_edge_iterator,
          typename adj_list<Vertex>::out_edge_iterator>
821 822 823
out_edges(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::out_edge_iterator ei_t;
824 825 826 827
    const auto& pes = g._edges[v];
    auto pos = pes.first;
    auto& es = pes.second;
    return {ei_t(v, es.begin()), ei_t(v, es.begin() + pos)};
828 829 830
}

template <class Vertex>
831
[[gnu::always_inline]] [[gnu::flatten]] inline
832 833
std::pair<typename adj_list<Vertex>::in_edge_iterator,
          typename adj_list<Vertex>::in_edge_iterator>
834 835 836
in_edges(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::in_edge_iterator ei_t;
837 838 839 840 841 842 843
    const auto& pes = g._edges[v];
    auto pos = pes.first;
    auto& es = pes.second;
    return {ei_t(v, es.begin() + pos), ei_t(v, es.end())};
}

template <class Vertex>
844
[[gnu::always_inline]] [[gnu::flatten]] inline
845 846 847 848 849 850 851 852 853 854 855
std::pair<typename adj_list<Vertex>::out_edge_iterator,
          typename adj_list<Vertex>::out_edge_iterator>
_all_edges_out(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::out_edge_iterator ei_t;
    const auto& pes = g._edges[v];
    auto& es = pes.second;
    return {ei_t(v, es.begin()), ei_t(v, es.end())};
}

template <class Vertex>
856
[[gnu::always_inline]] [[gnu::flatten]] inline
857 858 859 860 861 862 863 864
std::pair<typename adj_list<Vertex>::in_edge_iterator,
          typename adj_list<Vertex>::in_edge_iterator>
_all_edges_in(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::in_edge_iterator ei_t;
    const auto& pes = g._edges[v];
    auto& es = pes.second;
    return {ei_t(v, es.begin()), ei_t(v, es.end())};
865 866
}

867
template <class Vertex>
868
[[gnu::always_inline]] [[gnu::flatten]] inline
869 870 871 872 873 874 875 876 877 878 879 880
std::pair<typename adj_list<Vertex>::all_edge_iterator,
          typename adj_list<Vertex>::all_edge_iterator>
all_edges(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::all_edge_iterator ei_t;
    const auto& pes = g._edges[v];
    auto& es = pes.second;
    auto pos = es.begin() + pes.first;
    return {ei_t(v, es.begin(), pos), ei_t(v, es.end(), pos)};
}

template <class Vertex>
881
[[gnu::always_inline]] [[gnu::flatten]] inline
882 883 884 885 886 887 888 889 890 891 892
std::pair<typename adj_list<Vertex>::all_edge_iterator_reversed,
          typename adj_list<Vertex>::all_edge_iterator_reversed>
_all_edges_reversed(Vertex v, const adj_list<Vertex>& g)
{
    typedef typename adj_list<Vertex>::all_edge_iterator_reversed ei_t;
    const auto& pes = g._edges[v];
    auto& es = pes.second;
    auto pos = es.begin() + pes.first;
    return {ei_t(v, es.begin(), pos), ei_t(v, es.end(), pos)};
}

893
template <class Vertex>
894
[[gnu::always_inline]] [[gnu::flatten]] inline
895 896
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
897
out_neighbors(Vertex v, const adj_list<Vertex>& g)
898 899
{
    typedef typename adj_list<Vertex>::adjacency_iterator ai_t;
900 901 902 903
    const auto& pes = g._edges[v];
    auto pos = pes.first;
    auto& es = pes.second;
    return {ai_t(es.begin()), ai_t(es.begin() + pos)};
904 905
}

906
template <class Vertex>
907
[[gnu::always_inline]] [[gnu::flatten]] inline
908 909
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
910
in_neighbors(Vertex v, const adj_list<Vertex>& g)
911 912
{
    typedef typename adj_list<Vertex>::adjacency_iterator ai_t;
913 914 915 916 917 918 919
    const auto& pes = g._edges[v];
    auto pos = pes.first;
    auto& es = pes.second;
    return {ai_t(es.begin() + pos), ai_t(es.end())};
}

template <class Vertex>
920
[[gnu::always_inline]] [[gnu::flatten]] inline
921 922
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
923
all_neighbors(Vertex v, const adj_list<Vertex>& g)
924 925 926 927 928
{
    typedef typename adj_list<Vertex>::adjacency_iterator ai_t;
    const auto& pes = g._edges[v];
    auto& es = pes.second;
    return {ai_t(es.begin()), ai_t(es.end())};
929 930 931
}

template <class Vertex>
932
[[gnu::always_inline]] [[gnu::flatten]] inline
933 934 935 936
std::pair<typename adj_list<Vertex>::adjacency_iterator,
          typename adj_list<Vertex>::adjacency_iterator>
adjacent_vertices(Vertex v, const adj_list<Vertex>& g)
{
937
    return out_neighbors(v, g);
938 939 940
}


941
template <class Vertex>
942
[[gnu::always_inline]] inline
943
size_t num_vertices(const adj_list<Vertex>& g)
944
{
945
    return g._edges.size();
946 947 948
}

template <class Vertex>
949
[[gnu::always_inline]] inline
950
size_t num_edges(const adj_list<Vertex>& g)
951 952 953 954 955 956
{
    return g._n_edges;
}


template <class Vertex>
957
typename std::pair<typename adj_list<Vertex>::edge_descriptor, bool>
958 959
add_edge(Vertex s, Vertex t, adj_list<Vertex>& g)
{
960
    // get index from free list, if available
961 962 963
    Vertex idx;
    if (g._free_indexes.empty())
    {
964
        idx = g._edge_index_range++;
965 966 967 968 969 970 971
    }
    else
    {
        idx = g._free_indexes.front();
        g._free_indexes.pop_front();
    }

972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994
    // put target on back of source's out-list (middle of total list)
    auto& s_pes = g._edges[s];
    auto& s_pos = s_pes.first;
    auto& s_es = s_pes.second;

    if (s_pos < s_es.size())
    {
        //in-list is not empty: push first element to the back
        s_es.push_back(s_es[s_pos]);
        s_es[s_pos] = {t, idx};
        if (g._keep_epos)
            g._epos[s_es.back().second].second = s_es.size() - 1;
    }
    else
    {
        s_es.emplace_back(t, idx);
    }
    s_pos++;

    // put source on back of target's in-list
    auto& t_es = g._edges[t].second;
    t_es.emplace_back(s, idx);

995 996
    g._n_edges++;

997 998 999 1000
    if (g._keep_epos)
    {
        if (idx >= g._epos.size())
            g._epos.resize(idx + 1);
1001
        auto& ei = g._epos[idx];
1002 1003 1004 1005 1006 1007
        ei.first = s_pos - 1;         // out
        ei.second = t_es.size() - 1;  // in

        assert(g._edges[s].second[ei.first].first == t);
        assert(g._edges[t].second[ei.second].first == s);
        //g.check_epos();
1008 1009
    }

1010
    typedef typename adj_list<Vertex>::edge_descriptor edge_descriptor;
1011
    return {edge_descriptor(s, t, idx), true};
1012 1013 1014
}

template <class Vertex>
Tiago Peixoto's avatar
Tiago Peixoto committed
1015
void remove_edge(Vertex s, Vertex t, adj_list<Vertex>& g)
1016
{
1017
    remove_edge(edge(s, t, g).first, g);
1018 1019 1020
}

template <class Vertex>
Tiago Peixoto's avatar
Tiago Peixoto committed
1021 1022
void remove_edge(const typename adj_list<Vertex>::edge_descriptor& e,
                 adj_list<Vertex>& g)
1023
{
1024 1025 1026 1027 1028 1029 1030 1031 1032
    auto s = e.s;
    auto t = e.t;
    auto idx = e.idx;
    auto& s_pes = g._edges[s];
    auto& s_pos = s_pes.first;
    auto& s_es  = s_pes.second;
    auto& t_pes = g._edges[t];
    auto& t_pos = t_pes.first;
    auto& t_es  = t_pes.second;
1033 1034

    if (!g._keep_epos) // O(k_s + k_t)
1035
    {
1036 1037
        // remove and shift
        auto remove_e = [&] (auto& elist, auto&& begin, auto&& end, auto v)
1038
            {
1039
                auto iter = std::find_if(begin, end,
1040
                                         [&] (const auto& ei) -> bool
1041 1042
                                         { return v == ei.first &&
                                                  idx == ei.second; });
1043 1044
                assert(iter != end);
                elist.erase(iter);
1045
            };
1046

1047
        remove_e(s_es, s_es.begin(), s_es.begin() + s_pos, t);
1048
        s_pos--;
1049
        remove_e(t_es, t_es.begin() + t_pos, t_es.end(), s);
1050
    }
1051 1052
    else // O(1)
    {
1053
        //g.check_epos();
1054
        assert (idx < g._epos.size());
1055 1056 1057 1058

        // swap with back, and pop back
        auto remove_e = [&] (auto& elist, auto&& begin, auto&& end,
                             auto&& get_pos, bool swap_back)
1059
        {
1060 1061 1062 1063
            auto back_iter = begin + ((end - begin) - 1);
            auto& back = *back_iter;
            auto j = get_pos(idx);
            assert(j < elist.size());
1064
            assert(elist[j].second == idx);
1065 1066 1067
            elist[j] = back;
            get_pos(back.second) = j;
            if (swap_back && end != elist.end())
1068
            {
1069 1070 1071 1072 1073 1074
                // in-edge list; swap middle with very back
                back = elist.back();
                g._epos[back.second].second = back_iter - elist.begin();
            }
            elist.pop_back();
        };
1075

1076 1077 1078 1079 1080
        remove_e(s_es, s_es.begin(), s_es.begin() + s_pos,
                 [&](size_t i) -> auto& {return g._epos[i].first;}, true);
        s_pos--;
        remove_e(t_es, t_es.begin() + t_pos, t_es.end(),
                 [&](size_t i) -> auto& {return g._epos[i].second;}, false);
1081