Run Code  | API  | Code Wall  | Misc  | Feedback  | Login  | Theme  | Privacy  | Patreon 

Graphs Iteration1 Undirected.

//clang 3.7.0

#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <cassert>
#include <initializer_list>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>

using namespace std;

// Универсальный итератор, который преобразовывает любой random-access-iterable класс в sequence-iterable-class
// Для использования в range-based for
// Для использования T должен поддерживать [size_t] и size()
// А также тип reference как ссылка на хранимый тип.
// Через контекст можно специализировать итератор для специальных целей (напр в матрице смежности графа).
template <class T, class Context = void> class for_iter_t {
    T& t;
    size_t pos;
public:
    for_iter_t(T& t) : t(t), pos(0) {}
//    for_iter_t& begin() { pos = 0; return *this;}
//    for_iter_t& end() {return *this;}
    typename T::reference operator*() { return t[pos]; }
    bool operator != (const for_iter_t& f) const { assert(&f.t == &t); return pos != t.size(); }
    void operator++() { ++pos; }
};
// Функция для инстанциирования for_iter_t чтобы параметр шаблона вывелся компилятором.
template<class T> for_iter_t<T> for_iter(T& t) { return for_iter_t<T>(t); };


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// А-ля Страуструп: http://www.stroustrup.com/matrix.c
template<typename T, typename Context = void> class slice_iter {
    typedef vector<T> VT;
    VT& v;
    slice s;
    // Вместо T& используем typename vector<T>::reference для совместимости с vector<bool>
    typename VT::reference ref(size_t i) const { return (v)[s.start() + i * s.stride()]; }
public:
    typedef T value_type;
    typedef typename VT::reference reference;
    typedef typename VT::const_reference const_reference;
    slice_iter( VT& v, slice s ) : v(v), s(s) {}
    
    // Заменитель конструктора для константных экземпляров. Обычный конструктор "возвратил бы" не const итератор.
    static const slice_iter ct(const VT& v, slice s) { return slice_iter( const_cast<VT&>(v), s ); }
    
    size_t size() const { return s.size(); }
    const_reference operator[](size_t i) const { return ref(i); }
    reference operator[](size_t i) { return ref(i); }
    
    // Для for(:)
    for_iter_t<slice_iter, Context> begin() { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<slice_iter, Context> end() { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<const slice_iter, Context> begin() const { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<const slice_iter, Context> end() const { return for_iter_t<slice_iter, Context>(*this); }
};

template <typename T, typename Context = void>
class matrix {
    size_t _w;
    size_t _h;
    vector<T> _m;
    
public:
    using vec = slice_iter<T, Context>;
    using value_type = vec;
    using reference = vec; // vec это и value_type и reference.
    using const_reference = const vec;
    
    matrix(size_t w, size_t h) : _w(w), _h(h), _m(w * h) {}
    
    explicit matrix(const matrix&) = default;
    
    matrix(initializer_list<initializer_list<T>> l) {
        _h = l.size();
        _w = _h > 0 ? l.begin()->size() : 0;
        _m.resize( _w * _h );
        size_t pos = 0;
        for( initializer_list<T> const& rowList : l ) {
            assert(rowList.size() == _w);
            for( const T& value : rowList) {
                _m[pos] = value;
                pos++;
            }
        }
    }
    
    size_t w() const { return _w; }
    size_t h() const { return _h; }
    
    typename vec::reference operator () (size_t x, size_t y) { return _m[ _w * y + x ]; }
    
    vec col(size_t x) { return vec( _m, slice(x, _h, _w) ); }
    const vec col(size_t x) const { return vec::ct( _m, slice(x, _h, _w) ); }
    
    vec row(size_t y) { return vec( _m, slice( y * _w, _w, 1) ); }
    const vec row(size_t y) const { return vec::ct( _m, slice( y * _w, _w, 1) ); }
    
    vec operator[] (size_t y) { return row(y); }
    const vec operator[] (size_t y) const { return row(y); }
        
    size_t size() const { return _h; }
    
    // Для for(:)
    for_iter_t<matrix> begin() { return for_iter(*this); }
    for_iter_t<matrix> end() { return for_iter(*this); }
    for_iter_t<const matrix> begin() const { return for_iter(*this); }
    for_iter_t<const matrix> end() const { return for_iter(*this); }
};

template <typename T, typename F>
std::ostream& operator << (std::ostream& os, const matrix<T, F>& m) {
    for( auto row : m ) {
        for (auto x : row ) {
            cout << setw(2) << x << ", ";
        }
        cout << endl;
    }
    cout << "\n\n";
    return os;
}

////////////////////////////////////////////////////////////////////////////////////////
    // Ребро графа.
    struct Edge {
        size_t v;
        size_t w;
        Edge(size_t v = -1, size_t w = -1):v(v),w(w){}
    };
    
    // АТД графа
    class Graph {
    public:
        
        Graph(size_t vertices, bool isDirected);
        // Кол-во вершин
        size_t size() const;
        
        // Кол-во ребер
        size_t edges() const;
        
        // Ориентирован ли граф
        bool directed() const;
        
        // Вставить ребро
        void insert(Edge);
        
        // Удалить ребро
        void removeEdge(Edge);
        
        // Еть ли ребро {v, w}
        bool edge(size_t v, size_t w);
        
        // Итератор по смежным вершинам графа. Для for(:)
        class AdjIter;

        AdjIter adjacent(size_t v) const;
        
        // Приготовит граф к работе после добавления в него ребер.
        void prepare();
    };
    
    // Вставляет в граф список ребер.
    template <class G>
    void insertEdges( G& g, initializer_list<Edge>&& es) {
        for( auto&& e : es ) {
            g.insert(e);
        }
        g.prepare();
    }

    // Вывод графа в виде списка смежности.
    template <class G>
    void show(const G& g) {
        cout << "v: " << g.size() << endl;
        cout << "e: " << g.edges() << endl;
        for( size_t y = 0; y < g.size(); y++ ) {
            cout << setw(2) << y << ":";
            for( size_t x : g.adjacent(y) ) {
                cout << setw(2) << x << " ";
            }
            cout << endl;
        }
        cout << endl;
    }

/////////////////////////////////////////////////////////////////////////////////////////////////////////

class DenseGraph;

    // Специализация for_iter_t для итерации по смежным вершинам.
    // Для контекстов, производных от GraphTraits.
template <class T> class for_iter_t <T, DenseGraph> {
        T& t;
        size_t pos;
    public:
        for_iter_t(T& t) : t(t), pos(0) { if(!t[pos]) ++*this; }
        size_t operator*() { return pos; }
        bool operator != (const for_iter_t& f) const { assert(&f.t == &t); return pos != t.size(); }
        void operator++() { while(++pos < t.size() && t[pos] == false); }
    };
    
    class DenseGraph {
        using AdjMatrix = matrix<bool, DenseGraph>;
        AdjMatrix _adj;
        bool _directed;
        size_t _edges = 0;
        
        bool _testEmpty() {
            for(auto row : _adj) for(auto x : row) assert(x == 0);
            return true;
        }
    public:
        DenseGraph(size_t v, bool digrected = false) : _adj(v, v), _directed(digrected) {
            assert(_testEmpty());
        }
        
        size_t size() const { return _adj.h(); }
        size_t edges() const { return _edges; }
        
        bool directed() const { return _directed; }
        
        void insert(const Edge& e) {
            size_t v(e.v), w(e.w);
            if(!directed() && v == w) return;
            auto x = _adj[v][w];
            if (!x) _edges++;
            x = true;
            assert(edge(v,w));
            if( !directed() ) _adj[w][v] = true;
        }
        
        void remove(Edge e) {
            size_t v(e.v), w(e.w);
            auto x = _adj[v][w];
            if (x) _edges--;
            x = false;
            assert(!edge(v,w));
            if( !directed() ) _adj[w][v] = false;
        }
        
        bool edge(size_t v, size_t w) const { return _adj[v][w]; }
        
        using VIter = for_iter_t<const AdjMatrix>;
        VIter vertices() const { return VIter(_adj); }
        
        class AdjIter;
        friend class AdjIter;
        
        AdjIter adjacent(size_t v) const;
        
        void prepare() {}
        
        void show() const {
            cout << _adj;
        }
    };

    class DenseGraph::AdjIter {
        const AdjMatrix::vec a;
        
        struct InnerIter {
            const AdjMatrix::vec& a;
            size_t i;
            size_t width;
            
            InnerIter( const AdjMatrix::vec& a ) : a(a), i(0), width(a.size()) {}
            
            // for(:) support
            size_t operator*() { return i; }
            void operator++() { while(++i < width && !a[i]); }
            
            bool operator!=(const InnerIter&) {return i < width;}
        };
        
    public:
        AdjIter( const DenseGraph& g, size_t v) : a(g._adj[v]){}
        
        InnerIter begin() {
            InnerIter it(a);
            if(!a[0]) ++it;
            return it;
        }
        InnerIter end() { return {a}; }
    };
    
    DenseGraph::AdjIter DenseGraph::adjacent(size_t v) const
    {
        return DenseGraph::AdjIter(*this, v);
    }

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    
    // Представление графа массивом списков смежности.
    class SparseGraph {
        using AdjList = vector<size_t>;
        using AdjLists = vector<AdjList>;
        AdjLists _adj;
        bool _directed;
        size_t _edges = 0;
    public:
        
        SparseGraph(size_t vertices, bool isDirected = false) : _adj(vertices), _directed(isDirected) {}
        
        // Кол-во вершин
        size_t size() const { return _adj.size(); }
        
        // Кол-во ребер
        size_t edges() const { return _edges; }
        
        bool directed() const { return _directed; }
        
        // Вставка.
        void insert(Edge e) {
            size_t v(e.v), w(e.w);
            if ( !directed() && v == w ) return;
            _adj[v].push_back(w);
            if(!directed()) _adj[w].push_back(v);
        }
        
        // Удаление.
        void remove(Edge e) {
            size_t v(e.v), w(e.w);
            AdjList& lv = _adj[v];
            // lower_bound это binary_search на векторах.
            auto pos = lower_bound(lv.begin(), lv.end(), w );
            if( pos != lv.end() ) {
                lv.erase(pos);
                _edges--;
                if( !directed() ) {
                    AdjList& lw = _adj[w];
                    lw.erase(lower_bound(lw.begin(), lw.end(), v));
                }
            }
        }
        
        // Еть ли ребро {v, w}?
        bool edge(int v, int w) {
            AdjList& l = _adj[v];
            return binary_search(l.begin(), l.end(), w); // На векторах O(log(N))
        }
        
        // Итератор по смежным вершинам графа.
        using AdjIter = AdjList;
        AdjIter adjacent(size_t v) const { return _adj[v]; }
        
        // Сортирует списки смежности и удаляет дубликаты. Вычисляет количество ребер.
        void prepare() {
            _edges = 0;
            for( size_t v = 0; v < _adj.size(); v++ ) {
                AdjList& l = _adj[v];
                set<size_t> s(l.begin(), l.end());
                l.resize(s.size());
                l.clear();
                for( size_t w : s ) {
                    l.push_back(w);
                    if( v < w ) _edges++;
                    else if (directed()) _edges++;
                }
            }
        }
    };

//////////////////////////////////////////////////////////////////////////////

    // Визуализатор поиска.
    class SearchTrace {
        vector<size_t> p; // родители вершин в остовном лесе. -1 - корень дерева.
    public:
        SearchTrace( size_t size ) : p(size, -1) {}
        void visit(Edge e) {
            size_t v(e.v), w(e.w);
            if ( p[w] == -1 ) p[w] = v;
            for( size_t vp = p[v]; vp != -1; vp = p[vp] ) cout << string(3, ' ');
            cout << "[" << v << ", " << w << "]" << endl;
        }
    };
    
    // Обход графа. Параметризуется методом из нижеприведенных классов:
    template <class G, class Method>
    void traverse(G& g, Method& m) {
        vector<bool> c(g.size()); // цвет вершины. 0 - не посещали, 1 - посещали.
        for( size_t v = 0; v < g.size(); v++ ) {
            if( !c[v] ) if(!m(v, c)) break;
        }
    }
    
    ///////////////////////////////////////////////////////////////////////////
    // BFS Method for traverse. Обход в ширину.
    template <class G, class Inspector> class BFS_T {
        const G& g;
        Inspector& i;
        deque<size_t> _q; // очередь просмотра вершин.
    public:
        BFS_T( const G& g, Inspector& i ) : g(g), i(i), _q(g.size()) {}
        
        bool operator() (size_t v, vector<bool>& c ) {
            auto q = queue<size_t>(_q);
            q.push(v);
            while( !q.empty() ) {
                c[v] = true;
                v = q.back(); q.pop();
                for( auto w : g.adjacent(v) ) {
                    if(c[w] == false) {
                        c[w] = true;
                        q.push(w);
                        i.visit( Edge(v, w) );
                    }
                }
            }
            return true;
        }
    };
    
    // Ускоритель вызова.
    template <class G, class Inspector>
    BFS_T<G, Inspector> BFS( const G& g, Inspector& i) { return BFS_T<G, Inspector>(g, i); }

    
    ////////////////////////////////////////////////////////////////
    // DFS Method for traverse. Обход в глубину.
    template <class G, class Inspector> class DFS_T {
        const G& g;
        Inspector& i;
    public:
        DFS_T( const G& g, Inspector& i ) : g(g), i(i) {}
        
        bool operator() (size_t v, vector<bool>& c ) {
            c[v] = true;
            for( size_t w : g.adjacent(v)) {
                if(c[w] == false) {
                    i.visit( Edge(v, w) );
                    (*this)(w, c);
                }
            }
            return true;
        }
    };
    
    // Ускоритель вызова.
    template <class G, class Inspector>
    DFS_T<G, Inspector> DFS( const G& g, Inspector& i ) { return DFS_T<G, Inspector>(g, i); }
    
    /////////////////////////////////////////////////////////////////
    // Connected Components Method for traverse. Связность.
    template <class G> class CC_T {
        const G& g;
        size_t ccnt;
        vector<size_t> ids;
    public:
        CC_T( const G& g) : g(g), ccnt(0) { ids.reserve(g.size()); }
        
        void ccR(size_t v,  vector<bool>& c) {
            c[v] = true;
            ids[v] = ccnt;
            for( size_t w : g.adjacent(v) ) {
                if(c[w] == false) {
                    ccR(w, c);
                }
            }
        }
        
        bool operator() (size_t v, vector<bool>& c ) {
            ccR(v , c);
            ccnt++;
            return true;
        }
        
        size_t count() const { return ccnt; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };

    // Ускоритель вызова.
    template <class G>
    CC_T<G> CC(const G& g) { return CC_T<G>(g); }
    
    /////////////////////////////////////////////////////////////////
    // Bipartite graph. Method for traverse. - Двудольность.
    template <class G> class BI_T {
        const G& g;
        bool ok;
        vector<bool> vc;
    public:
        BI_T( const G& g) : g(g), ok(false), vc(g.size()) {}
        
        bool bipR(size_t v, vector<bool>& c, bool color) {
            c[v] = true;
            vc[v] = !color;
            for( size_t w : g.adjacent(v)) {
                if(c[w] == false) {
                    if( !bipR(w, c, !color) ) return false;
                } else if ( vc[w] != color ) return false;
            }
            return true;
        }
        
        bool operator() (size_t v, vector<bool>& c ) {
            ok = bipR(v , c, false);
            return ok;
        }
        
        bool bipartite() const { return ok; }
        bool color(size_t v) const { return vc[v]; }
    };

    // Ускоритель вызова.
    template <class G>
    BI_T<G> BI(const G& g) { return BI_T<G>(g); }

//////////////////////////////////////////////////////////////////////////////
using namespace std;

template <class G> void buildGraph(G& g) {
        insertEdges(g, {
            {0, 2}, {0, 5}, {0, 7},
            {1, 7},
            {2, 6},
            {3, 4}, {3, 5},
            {4, 5}, {4, 6}, {4, 7}
        });
}

template <class G> void buildBiGraph(G& g) {
    insertEdges(g, {
        {0, 1}, {0, 3}, {0, 5},
        {1, 0}, {1, 2},
        {2, 1}, {2, 9},
        {3, 0}, {3, 4},
        {4, 3}, {4, 5}, {4, 11},
        {5, 0}, {5, 4},
        {6, 7}, {6, 9},
        {7, 6}, {7, 8},
        {8, 7}, {8, 9},
        {9, 2}, {9, 6}, {9, 8}, {9, 10}, {9, 12},
        {10, 9},
        {11, 4}, {11, 12},
        {12, 9}, {12, 11},
    });
}

template <class G> void testGraph(G& g) {
    buildGraph(g);
    show(g);
    cout << "BFS:\n";
    SearchTrace sb(g.size());
    auto bfs = BFS(g, sb);
    traverse(g, bfs);
    
    cout << "\nDFS:\n";
    SearchTrace sd(g.size());
    auto dfs = DFS(g, sd);
    traverse(g, dfs);
    
    auto cc = CC(g);
    traverse(g, cc);
    cout << endl << cc.count() << " connected components\n";
    
    auto bi = BI(g);
    traverse(g, bi);
    cout << endl << bi.bipartite() << " bipartite status\n\n";
}

void testDenseGraph() {
    cout << "Dense graph:\n";
    DenseGraph dg(8);
    testGraph(dg);
}

void testSparseGraph() {
    cout << "Sparse graph:\n";
    SparseGraph sg(8);
    testGraph(sg);
}

void testGraphs() {
    testDenseGraph();
    testSparseGraph();
}

int main(int argc, const char * argv[]) {
    testGraphs();
    
    return 0;
}
 run  | edit  | history  | help 0