Graphs Iteration 2.1 Directed Graphs
#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;
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) {}
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; }
};
template<class T> for_iter_t<T> for_iter(T& t) { return for_iter_t<T>(t); };
template<typename T, typename Context = void> class slice_iter {
typedef vector<T> VT;
VT& v;
slice s;
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) {}
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_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;
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_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 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);
bool edge(size_t v, size_t w);
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;
}
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();
}
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>;
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];
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));
}
}
}
bool edge(int v, int w) {
AdjList& l = _adj[v];
return binary_search(l.begin(), l.end(), w);
}
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>;
template <class G, class Method>
void traverse(G& g, Method& m) {
vector<bool> c(g.size());
for( size_t v = 0; v < g.size(); v++ ) {
if( !c[v] ) if(!m(v, c)) break;
}
}
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); }
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); }
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;
}
};
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;
}
};
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); }
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 ) {
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) {
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
|
|
|