summaryrefslogtreecommitdiff
path: root/include/graph.hh
diff options
context:
space:
mode:
Diffstat (limited to 'include/graph.hh')
-rw-r--r--include/graph.hh103
1 files changed, 57 insertions, 46 deletions
diff --git a/include/graph.hh b/include/graph.hh
index 211444a..e5885ce 100644
--- a/include/graph.hh
+++ b/include/graph.hh
@@ -37,17 +37,25 @@
struct Empty {
Empty() {};
+
bool operator<(const Empty &) const { return true; };
+
bool operator==(const Empty &) const { return false; };
- friend std::ostream& operator<<(std::ostream &os, const Empty &) { return os; };
+
+ friend std::ostream &operator<<(std::ostream &os, const Empty &) { return os; };
};
namespace {
- enum GraphColorType {WHITE, GREY, BLACK};
+ enum GraphColorType {
+ WHITE, GREY, BLACK
+ };
}
-template<typename VertexType, typename EdgeType> struct Graph;
-template<typename VertexType, typename EdgeType> std::ostream& operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g);
+template<typename VertexType, typename EdgeType>
+struct Graph;
+
+template<typename VertexType, typename EdgeType>
+std::ostream &operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g);
template<typename VertexType = Empty, typename EdgeType = Empty>
struct Graph {
@@ -58,18 +66,27 @@ struct Graph {
bool directed;
Graph(bool directed = true);
-
+
int vertexCount() const;
+
int edgeCount() const;
+
bool isEmpty() const;
+
bool isDirected() const;
+
int insert(const VertexType &v = VertexType());
+
void connect(int v1, int v2, const EdgeType &e = EdgeType());
+
void connect(int v1, int v2, const std::vector<EdgeType> &e);
+
void disconnect(int v1, int v2);
+
bool hasEdge(int v1, int v2) const;
+
std::vector<EdgeType> getEdge(int v1, int v2) const;
-
+
//! Topological sort
/*! This topological sort does handle SCC in graph. */
std::vector<std::set<int> > topoSort() const;
@@ -80,15 +97,16 @@ struct Graph {
void dump() {
std::cout << *this;
}
-
- friend std::ostream& operator<< <>(std::ostream &os, const Graph<VertexType, EdgeType> &g);
+
+ friend std::ostream &operator<<<>(std::ostream &os, const Graph<VertexType, EdgeType> &g);
};
template<typename VertexType, typename EdgeType>
-std::ostream& operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g) {
+std::ostream &operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g) {
for (int i = 0; i < g.vertex.size(); i++)
- for (typename Graph<VertexType,EdgeType>::EdgeList::const_iterator j = g.vertex[i].second.begin(); j != g.vertex[i].second.end(); j++) {
- os << "s" << i << "->" << "s" << j->first << ":";
+ for (typename Graph<VertexType, EdgeType>::EdgeList::const_iterator j = g.vertex[i].second.begin();
+ j != g.vertex[i].second.end(); j++) {
+ os << "s" << i << "->" << "s" << j->first << ":";
for (typename std::vector<EdgeType>::const_iterator k = j->second.begin(); k != j->second.end(); k++)
os << " " << *k;
os << std::endl;
@@ -100,7 +118,7 @@ std::ostream& operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g)
template<typename VertexType, typename EdgeType>
Graph<VertexType, EdgeType>::Graph(bool directed_):
- directed(directed_) {
+ directed(directed_) {
}
template<typename VertexType, typename EdgeType>
@@ -117,8 +135,8 @@ int Graph<VertexType, EdgeType>::edgeCount() const {
result += j->second.size();
if (!directed)
- result = result/2;
-
+ result = result / 2;
+
return result;
}
@@ -133,7 +151,7 @@ bool Graph<VertexType, EdgeType>::isDirected() const {
}
template<typename VertexType, typename EdgeType>
-int Graph<VertexType, EdgeType>::insert(const VertexType & v) {
+int Graph<VertexType, EdgeType>::insert(const VertexType &v) {
for (int i = 0; i < vertex.size(); i++)
if (vertex[i].first == v)
return i;
@@ -141,10 +159,10 @@ int Graph<VertexType, EdgeType>::insert(const VertexType & v) {
vertex.push_back(std::make_pair(v, EdgeList()));
return vertex.size() - 1;
}
-
-
+
+
template<typename VertexType, typename EdgeType>
-void Graph<VertexType, EdgeType>::connect(int v1, int v2, const EdgeType &e) {
+void Graph<VertexType, EdgeType>::connect(int v1, int v2, const EdgeType &e) {
assert(v1 < vertex.size() && v2 < vertex.size());
vertex[v1].second[v2].push_back(e);;
@@ -153,19 +171,19 @@ void Graph<VertexType, EdgeType>::connect(int v1, int v2, const EdgeType &e) {
}
template<typename VertexType, typename EdgeType>
-void Graph<VertexType, EdgeType>::connect(int v1, int v2, const std::vector<EdgeType> &e) {
+void Graph<VertexType, EdgeType>::connect(int v1, int v2, const std::vector<EdgeType> &e) {
assert(v1 < vertex.size() && v2 < vertex.size());
if (e.size() == 0)
return;
-
+
copy(e.begin(), e.end(), back_inserter(vertex[v1].second[v2]));
if (!directed)
copy(e.begin(), e.end(), back_inserter(vertex[v2].second[v1]));
}
template<typename VertexType, typename EdgeType>
-void Graph<VertexType, EdgeType>::disconnect(int v1, int v2) {
+void Graph<VertexType, EdgeType>::disconnect(int v1, int v2) {
assert(v1 < vertex.size() && v2 < vertex.size());
vertex[v1].second.erase(v2);
@@ -174,12 +192,12 @@ void Graph<VertexType, EdgeType>::disconnect(int v1, int v2) {
}
template<typename VertexType, typename EdgeType>
-bool Graph<VertexType,EdgeType>::hasEdge(int v1, int v2) const {
+bool Graph<VertexType, EdgeType>::hasEdge(int v1, int v2) const {
return vertex[v1].second.find(v2) != vertex[v1].second.end();
}
template<typename VertexType, typename EdgeType>
-std::vector<EdgeType> Graph<VertexType,EdgeType>::getEdge(int v1, int v2) const {
+std::vector<EdgeType> Graph<VertexType, EdgeType>::getEdge(int v1, int v2) const {
if (!hasEdge(v1, v2))
return std::vector<EdgeType>();
@@ -194,9 +212,9 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::topoSort() const {
std::vector<int> order(n);
int c = n;
-
+
// first DFS
- for (int i = n-1; i >= 0; i--)
+ for (int i = n - 1; i >= 0; i--)
if (color[i] == WHITE) {
S.push(i);
while (!S.empty()) {
@@ -208,13 +226,11 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::topoSort() const {
S.push(j->first);
color[v] = GREY;
- }
- else if (color[v] == GREY) {
+ } else if (color[v] == GREY) {
color[v] = BLACK;
S.pop();
order[--c] = v;
- }
- else {
+ } else {
S.pop();
}
}
@@ -225,31 +241,29 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::topoSort() const {
for (int i = 0; i < n; i++)
for (typename EdgeList::const_iterator j = vertex[i].second.begin(); j != vertex[i].second.end(); j++)
edgeT[j->first].insert(i);
-
+
// second DFS in transposed graph starting from last finished vertex
fill(color.begin(), color.end(), WHITE);
std::vector<std::set<int> > result;
for (int i = 0; i < n; i++)
if (color[order[i]] == WHITE) {
std::set<int> s;
-
+
S.push(order[i]);
while (!S.empty()) {
int v = S.top();
-
- if(color[v] == WHITE) {
+
+ if (color[v] == WHITE) {
for (std::set<int>::const_iterator j = edgeT[v].begin(); j != edgeT[v].end(); j++)
if (color[*j] == WHITE)
S.push(*j);
color[v] = GREY;
- }
- else if (color[v] == GREY) {
+ } else if (color[v] == GREY) {
color[v] = BLACK;
S.pop();
s.insert(v);
- }
- else {
+ } else {
S.pop();
}
}
@@ -268,9 +282,9 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::packed_topoSort() const
std::vector<bool> is_root(n, false);
std::vector<std::set<int> > edges(n);
-
+
// first DFS
- for (int i = n-1; i >= 0; i--)
+ for (int i = n - 1; i >= 0; i--)
if (color[i] == WHITE) {
S.push(i);
is_root[i] = true;
@@ -282,8 +296,7 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::packed_topoSort() const
if (color[j->first] == WHITE) {
S.push(j->first);
edges[v].insert(j->first);
- }
- else if (color[j->first] == BLACK) {
+ } else if (color[j->first] == BLACK) {
if (is_root[j->first]) {
is_root[j->first] = false;
edges[v].insert(j->first);
@@ -291,12 +304,10 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::packed_topoSort() const
}
color[v] = GREY;
- }
- else if (color[v] == GREY) {
+ } else if (color[v] == GREY) {
color[v] = BLACK;
S.pop();
- }
- else {
+ } else {
S.pop();
}
}
@@ -313,7 +324,7 @@ std::vector<std::set<int> > Graph<VertexType, EdgeType>::packed_topoSort() const
result.push_back(s);
while (true) {
std::set<int> s;
- for (std::set<int>::iterator i = result[result.size()-1].begin(); i != result[result.size()-1].end(); i++)
+ for (std::set<int>::iterator i = result[result.size() - 1].begin(); i != result[result.size() - 1].end(); i++)
s.insert(edges[*i].begin(), edges[*i].end());
if (s.size() != 0)
result.push_back(s);
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-02-02 00:50:16 +0000