Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Graphs Iteration2 Directed Graphs
//clang 3.7.0 #include <iostream> #include <iomanip> #include <valarray> #include <vector> #include <cassert> #include <initializer_list> #include <type_traits> #include <set> #include <deque> #include <queue> using namespace std; //////////////////////////////////////////////////////////////////////////////////////////////////////// // Matrix // Универсальный итератор, который преобразовывает любой random-access-iterable класс в sequence-iterable-class // Для использования в range-based for // Для использования T должен поддерживать [size_t] и size() // А также тип reference как ссылка на хранимый тип. // Через контекст можно специализировать итератор для специальных целей (напр в матрице смежности графа). template <class T, class Context = void, class Enable = 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; } ////////////////////////////////////////////////////////////////////////////////////////// // Graph base struct GraphTraits { static const bool directed = false; }; struct DirectedGraphTraits : public GraphTraits { static const bool directed = true; enum EdgeType { Tree, Back, Forward, Cross }; }; // Ребро графа. struct Edge { size_t v; size_t w; Edge(size_t v = 0, size_t w = 0):v(v),w(w){} }; // АТД графа class Graph { public: using traits = GraphTraits; Graph(size_t vertices, bool isDirected); // Кол-во вершин size_t size() const; // Кол-во ребер size_t edges() const; // Ориентирован ли граф constexpr bool directed() const {return traits::directed; } // Вставить ребро void insert(Edge); // Удалить ребро void remove(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 show(const G& g, ostream& os = cout) { 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; } // Оператор вывода графа в ostream. template<class G, class T = typename G::traits> typename enable_if< is_base_of<GraphTraits, T>::value, ostream& >::type operator << (ostream& os, const G& g) { show(g, os); return os; } // Вставляет в граф список ребер. template <class G> void insertEdges( G& g, initializer_list<Edge>&& es) { for( auto&& e : es ) { g.insert(e); } g.prepare(); } // Вставляет в граф список ребер. template <class G> void insertEdges( G& g, const vector<Edge>& es) { for( auto& e : es ) { g.insert(e); } g.prepare(); } ///////////////////////////////////////////////////////////////////////////////////////////// // Dense Graph // Специализация for_iter_t для итерации по смежным вершинам. // Для контекстов, производных от GraphTraits. template <class T, class C> class for_iter_t <T, C, typename enable_if< is_base_of<GraphTraits, C>::value >::type> { 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); } }; /////////////////////////////////////// // Граф на матрице смежности. template< class Traits = GraphTraits> class DenseGraph_T { using AdjMatrix = matrix<bool, Traits>; AdjMatrix _adj; size_t _edges = 0; bool _testEmpty() { for(auto row : _adj) for(auto x : row) assert(x == 0); return true; } public: using traits = Traits; DenseGraph_T(int v) : _adj(v, v) { assert(_testEmpty()); } size_t size() const { return _adj.h(); } size_t edges() const { return _edges; } constexpr bool directed() const { return traits::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 AdjIter = typename AdjMatrix::vec; AdjIter adjacent(size_t v) const { return _adj[v]; } void prepare() {} void show() const { cout << _adj; } }; using DenseGraph = DenseGraph_T<GraphTraits>; using DenseGraphD = DenseGraph_T<DirectedGraphTraits>; ////////////////////////////////////////////////////////////////////////////////////// // Sparse Graph // Граф на списке смежности вершин. template< class Traits = GraphTraits> class SparseGraph_T { using AdjList = vector<size_t>; using AdjLists = vector<AdjList>; AdjLists _adj; size_t _edges = 0; public: using traits = Traits; SparseGraph_T(size_t vertices) : _adj(vertices) {} // Кол-во вершин size_t size() const { return _adj.size(); } // Кол-во ребер size_t edges() const { return _edges; } constexpr bool directed() const { return traits::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++; } } } }; using SparseGraph = SparseGraph_T<GraphTraits>; using SparseGraphD = SparseGraph_T<DirectedGraphTraits>; //////////////////////////////////////////////////////////////////////////////////////////// // Undirected graphs // Обход графа. Параметризуется методом из нижеприведенных классов: 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 Context = typename G::traits> 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 Context = typename G::traits> 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); } /////////////////////////////////////////////////////////////////////////////////////////// // DirectedGraphs template <class InG, class OutG> void reverse( const InG& inG, OutG& outG ) { for ( size_t v = 0; v < inG.size(); v++ ) { for ( size_t w : inG.adjacent(v) ) { outG.insert(Edge(w, v)); } } outG.prepare(); } // Визуализатор поиска в ориентированном графе. class SearchTraceD { using T = DirectedGraphTraits; const char* etStr(T::EdgeType et) const { switch( et ) { case T::Tree: return " tree"; case T::Back: return " back"; case T::Forward: return " forward"; default: assert(et == T::Cross); break; }; return " cross"; } public: SearchTraceD( size_t size ) {} void visit(Edge e, size_t depth, DirectedGraphTraits::EdgeType et) { size_t v(e.v), w(e.w); cout << string(depth * 3, ' ') << "[" << v << ", " << w << "]" << etStr(et) << endl; } }; //////////////////////////////////////////////////////////////////////////// // Специализация DFS для ориентированных графов. Метод traverse. template <class G, class Inspector> class DFS_T<G, Inspector, DirectedGraphTraits> { const G& g; Inspector& i; vector<size_t> enter; // порядок входов в вершины. vector<size_t> leave; // порядок выходов из вершин. size_t cnt; size_t depth; public: DFS_T( const G& g, Inspector& i ) : g(g), i(i), enter(g.size(), -1), leave(g.size(), -1), cnt(0), depth(0) {} bool operator() (size_t v, vector<bool>& c ) { using T = DirectedGraphTraits; c[v] = true; enter[v] = cnt++; depth++; for ( size_t w : g.adjacent(v) ) { Edge e(v, w); T::EdgeType et = T::Tree; if ( c[w] == false ) { assert(enter[w] == -1); i.visit( e, depth, et ); (*this)(w, c); } else { if ( leave[w] == -1 ) et = T::Back; else if ( enter[v] < enter[w] ) et = T::Forward; else et = T::Cross; i.visit( e, depth, et ); } } leave[v] = cnt++; depth--; return true; } }; ////////////////////////////////////////////////////////////////////////////////// // TransitiveClosure - Транзитивное замыкание - построение множества достижимости. // O(V(V + E)). template <class G> class TC_T { const G& g; // Исходим из предположения, что граф транзитивного замыкания будет очень плотным. // Плюс граф на списках смежности не приспособлен для использования с динамической вставкой ребер. DenseGraph tc; void tcR( size_t v, size_t w ) { tc.insert(Edge(v, w)); for ( size_t t : g.adjacent(w)) { if (!tc.edge(v, t)) tcR(v, t); } } public: TC_T( const G& g) : g(g), tc(g.size()) { for( size_t v = 0; v < g.size(); v++ ) tcR(v, v); } bool reachable( size_t v, size_t w ) const { return tc.edge(v , w); } const DenseGraph& getTC() const { return tc; } }; // Ускоритель вызова. template<class G> TC_T<G> TC(const G& g) { return TC_T<G>(g); } /////////////////////////////////////////////////////////////// // DAG Topoligical Sort. template <class G> class TS_T { const G& g; vector<size_t> enter; // Порядок входов в вершины. vector<size_t> leave; // Обратный вектор переименования. vector<size_t> top; // Обратный топологический порядок. size_t cnt; bool isDag; public: TS_T( const G& g) : g(g), enter(g.size(), -1), leave(g.size(), -1), cnt(0), isDag(true) { top.reserve(g.size()); } bool operator() (size_t v, vector<bool>& c ) { using T = DirectedGraphTraits; c[v] = true; enter[v] = cnt++; for ( size_t w : g.adjacent(v) ) { if ( c[w] == false ) { assert(enter[w] == -1); if(!(*this)(w, c)) return false; } else { if ( leave[w] == -1 ) { // back edge detected. Not a DAG. isDag = false; return false; } } } leave[v] = top.size(); top.push_back(v); return true; } bool isDAG() const { return isDag; } // Возвращаем вектора, обратные топологической сортровке. vector<size_t>& ts(){ return top; } vector<size_t>& relabel() { return leave; } }; // Ускоритель вызова. template<class G> TS_T<G> TS(const G& g) { return TS_T<G>(g); } /////////////////////////////////////////////////////////////////////////////////////////////// template <class G> void buildDirGraph(G& g) { // Рис. 19.1 Седжвик. insertEdges(g, { {4, 2}, {11, 12}, {4, 11}, {5, 4}, {2, 3}, {12, 9}, {4, 3}, {0, 5}, {3, 2}, {9, 10}, {3, 5}, {6, 4}, {0, 6}, {9, 11}, {7, 8}, {6, 9}, {0, 1}, {8, 9}, {8,7}, {7, 6}, {2, 0}, {10, 12} }); } template <class G> void testDirGraph(G& g) { buildDirGraph(g); show(g); cout << "Directed DFS:\n"; SearchTraceD s(g.size()); auto dfs = DFS(g, s); traverse(g, dfs); cout << "Transitive closure:\n" << TC(g).getTC(); } void testDenseDirGraph() { cout << "Dense directed graph:\n"; DenseGraphD g(13); testDirGraph(g); } void testSparseDirGraph() { cout << "Sparse directed graph:\n"; SparseGraphD g(13); testDirGraph(g); } void testDirGraphs() { testDenseDirGraph(); cout << endl; testSparseDirGraph(); } int main() { testDirGraphs(); return 0; }
run
|
edit
|
history
|
help
0
back_inserter example
Variable declarations in while loop conditions are also C++-only.
simple in-memory b-tree
mine
GraphBase
Move Construction
C++ Program to Print Binary
Throttle Example in C++
Combination
selection sort