GraphBase, C++ (clang)

GraphBase

//clang 3.7.0

#include <iostream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <numeric>
#include <cassert>
#include <initializer_list>
#include <forward_list>
#include <algorithm>
#include <set>

using namespace std;

// Универсальный итератор, который преобразовывает любой random-access-iterable класс в sequence-iterable-class
// Для использования в range-based for
// Для использования T должен поддерживать [size_t] и size()
// А также тип reference как ссылка на хранимый тип.
template <class T> 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> 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> begin() { return for_iter(*this); }
	for_iter_t<slice_iter> end() { return for_iter(*this); }
	for_iter_t<const slice_iter> begin() const { return for_iter(*this); }
	for_iter_t<const slice_iter> end() const { return for_iter(*this); }
};

template <typename T>
class matrix {
	size_t _w;
	size_t _h;
	vector<T> _m;
	
public:
	using vec = slice_iter<T>;
	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) {}
	
	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); }
	
	matrix transpond() const {
		auto m = matrix(_h, _w);
		for ( int i = 0; i < _h; i++ ) {
			int j = 0; j < _w; j++;
			m(j, i) = *this(i, j);
		}
		return m;
	}
	
	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>
std::ostream& operator << (std::ostream& os, const matrix<T>& m) {
	for( auto row : m ) {
		for (auto x : row ) {
			cout << setw(2) << x << ", ";
		}
		cout << endl;
	}
	cout << "\n\n";
	return os;
}

////////////////////////////////////////////////////////////////////////////////////////
namespace Graph {

// Ребро графа.
	struct Edge {
		int v;
		int w;
		Edge(int v = -1, int 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(int v, int w);
        
        // Итератор по смежным вершинам графа. Для for(:)
		class AdjIter;

AdjIter adjacent(int v) const;
		
		// Приготовит граф к работе после добавления в него ребер.
		void prepare();
    };
    
    // Вставляет в граф список ребер.
    template <class G>
    void insertEdges( G& g, initializer_list<Edge>&& es, bool doFix = true) {
        for( auto&& e : es ) {
            g.insert(e);
        }
        if (doFix) {
            g.prepare();
        }
    }
    
    // Все ребра графа ввиде vector<Edge> 
    template <class G>
    vector<Edge> edges(const G& g) {
        int e = 0;
        vector<Edge> a(g.e());
        for( int v = 0; v < g.size(); v++ ) {
            for( int w : g.adjacent(v) ) {
                if( g.directed || v < w ) {
                    a[e++] = {v, w};
                }
            }
        }
		
        return a;
    }

// Вывод графа в виде списка смежности.
    template <class G>
    void show(const G& g) {
		
        for( int y = 0; y < g.size(); y++ ) {
            cout << setw(2) << y << ":";
			for( size_t x : g.adjacent(y) ) {
				cout << setw(2) << x << " ";
			}
            cout << endl;
        }
    }
    
    // Ввод графа в виде пар номеров смежных вершин.
    template <class G>
    void scan(G& g) {
        int v, w;
        while( cin >> v >> w ) {
            assert(v >= 0 && w>= 0 && v < g.size() && w < g.size());
            g.insert( v, w );
        }
    }
	
	// Вектор степеней графа.
	template <class G>
	vector<size_t> degree( const G& g) {
		vector<size_t> deg(g.size());
		for( size_t v = 0; v < g.size(); v++ ) {
			for( size_t w : g.adjacent(v) ) {
				deg[v]++; (void)w; // убираем warning.
			}
		}
		return deg;
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////
namespace Graph {

class DenseGraph {
		using AdjMatrix = matrix<bool>;
		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(int 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) {
			int v(e.v), w(e.w);
			auto x = _adj[v][w];
			if (!x) _edges++;
			x = true;
			assert(edge(v,w));
			if( !_directed ) _adj[w][v] = true;
		}
		
		void remove(Edge e) {
			int v(e.w), 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(int v, int w) const { return _adj[v][w]; }
		
		using VIter = for_iter_t<const AdjMatrix>;
		VIter vertices() const { return VIter(_adj); }
		
		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);
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
namespace Graph {
    
    // Представление графа массивом списков смежности.
    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;
            }
            _edges++;
            _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.clear();
                for( size_t w : s ) {
                    l.push_back(w);
                    if( v < w ) _edges++;
                    else if (directed()) _edges++;
                }
			}
		}
    };
}

using namespace std;
using namespace Graph;

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

int main(int argc, const char * argv[]) {
    vector<Edge> a(5);
    a[0] = {0,0};
	cout << "Dense graph:\n";
    testGraph<DenseGraph>();
	cout << "\nSparse graph:\n";
	testGraph<SparseGraph>();
	
    return 0;
}


run \| edit \| history \| help	0