Graphs Iteration 2.1 Directed Graphs, C++ (clang)

Graphs Iteration 2.1 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>
#include <string>

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;
		
		// Ориентирован ли граф
		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 ) {
			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