forked from leo000leo/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdigraph.h
More file actions
80 lines (70 loc) · 2.19 KB
/
Copy pathdigraph.h
File metadata and controls
80 lines (70 loc) · 2.19 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//
// digraph
// Algorithm
//
// Created by dtysky on 2017/2/18.
// Copyright © 2017 [email protected]. All rights reserved.
//
#ifndef ALGORITHM_DIGRAPH_H
#define ALGORITHM_DIGRAPH_H
#include <cstdio>
#include <vector>
#include "graph.h"
namespace data_structures {
template <typename T>
class Digraph: public Graph<T> {
public:
Digraph(): Graph<T>() {};
Digraph(Digraph<T> &graph): Graph<T>(graph) {};
virtual ~Digraph();
Digraph<T>& addEdge(const T& v, const T& w);
Digraph<T>& deleteEdge(const T& v, const T& w);
void reverse(Digraph<T>& res_graph);
friend std::ostream &operator<<(std::ostream &out, Digraph<T> &graph) {
auto nodes = graph._tree.getAllNodes();
for (auto node: nodes) {
out << node->element.key << ": ";
for (auto &v: node->element.value.adjVertex()) {
out << v << " ";
}
out << std::endl;
}
return out;
}
};
template <typename T> inline
Digraph<T>::~Digraph() {}
template <typename T> inline
Digraph<T>& Digraph<T>::addEdge(const T& v, const T& w){
auto vp = this->_tree.getNode(v);
auto wp = this->_tree.getNode(w);
if (vp->element.value.addEdge(wp)) {
this->_edge_count++;
}
return *this;
}
template <typename T> inline
Digraph<T>& Digraph<T>::deleteEdge(const T& v, const T& w){
auto vp = this->_tree.getNode(v);
auto wp = this->_tree.getNode(w);
if (vp->element.value.deleteEdge(wp)) {
this->_edge_count--;
}
return *this;
}
template <typename T> inline
void Digraph<T>::reverse(Digraph<T>& res_graph){
res_graph.clear();
auto nodes = this->_tree.getAllNodes();
for (auto &node: nodes) {
res_graph.addVertex(node->element.key);
}
for (auto &node: nodes) {
auto adj_set = node->element.value.adjVertexNodes();
for (auto &v: adj_set) {
res_graph.addEdge(v->element.key, node->element.key);
}
}
}
}
#endif //ALGORITHM_DIGRAPH_H