-
Notifications
You must be signed in to change notification settings - Fork 0
/
digraph.h
238 lines (216 loc) · 8.77 KB
/
digraph.h
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
/***************************************************
* digraph.h
* by M.Weller
**************************************************/
#ifndef digraph_h
#define digraph_h
#include "stdlib.h"
#include "string.h"
#include <set>
#include <map>
#include <string>
#include <vector>
#define DEBUG 0
#define dbgcout if(DEBUG) cout
#define MY_INFINITY (uint)-2
#define MRK_NONE 0
#define MRK_FORBIDDEN 1
#define MRK_PERMANENT 2
using namespace std;
typedef unsigned int uint;
typedef string t_vertex;
typedef pair<t_vertex, t_vertex> t_arc;
typedef pair<t_arc, uint> t_labeled_arc; // 0 = no label, 1 = forbidden, 2 = permanent
typedef set<t_vertex> t_adjlist;
typedef map<t_vertex, t_adjlist> t_adjtable;
typedef pair<t_arc, t_arc> t_3path;
typedef t_arc t_diamond; // only the first and the last vertex of a diamond
// are saved, the belt can be calced in O(n)
typedef t_3path* p_3path;
typedef t_diamond* p_diamond;
#include <iostream>
#include <fstream>
#include <algorithm>
inline set<t_arc> get_irreflexive(const set<t_arc>& s){
set<t_arc> result;
for(set<t_arc>::const_iterator i = s.begin(); i != s.end(); i++)
if(i->first != i->second) result.insert(*i);
return result;
}
inline set<t_vertex> set_unite(const set<t_vertex>& s1, const set<t_vertex>& s2){
set<t_vertex> result(s1);
// set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), result.begin());
// for(set<t_vertex>::const_iterator i = s2.begin(); i != s2.end(); i++) result.insert(*i);
result.insert(s2.begin(), s2.end());
return result;
}
inline set<t_vertex> set_intersect(const set<t_vertex>& s1, const set<t_vertex>& s2){
set<t_vertex> result;
// for(set<t_vertex>::const_iterator i = s1.begin(); i != s1.end(); i++)
// if(s2.find(*i) != s2.end()) result.insert(*i);
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result,result.begin()));
return result;
}
inline set<t_vertex> set_substract(const set<t_vertex>& s1, const set<t_vertex>& s2){
// set<t_vertex> result(s1);
// for(set<t_vertex>::const_iterator i = s2.begin(); i != s2.end(); i++) result.erase(*i);
set<t_vertex> result;
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result,result.begin()));
return result;
}
inline set<t_vertex> set_symm_diff(const set<t_vertex>& s1, const set<t_vertex>& s2){
// set<t_vertex> result(s1);
// for(set<t_vertex>::const_iterator i = s2.begin(); i != s2.end(); i++)
// if(s2.find(*i) != s2.end()) result.erase(*i); else result.insert(*i);
set<t_vertex> result;
set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result,result.begin()));
return result;
}
inline set<t_arc> set_multiply(const set<t_vertex>& s1, const set<t_vertex>& s2){
set<t_arc> result;
for(set<t_vertex>::const_iterator i = s1.begin(); i != s1.end(); i++)
for(set<t_vertex>::const_iterator j = s2.begin(); j != s2.end(); j++)
result.insert(t_arc(*i,*j));
return get_irreflexive(result);
}
inline set<t_arc> set_substract(const set<t_arc>& s1, const set<t_arc>& s2){
// set<t_arc> result(s1);
// for(set<t_arc>::const_iterator i = s2.begin(); i != s2.end(); i++) result.erase(*i);
set<t_arc> result;
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result,result.begin()));
return result;
}
/*
set<t_vertex> set_unite(const set<t_vertex>& s1, const set<t_vertex>& s2);
set<t_vertex> set_intersect(const set<t_vertex>& s1, const set<t_vertex>& s2);
set<t_vertex> set_substract(const set<t_vertex>& s1, const set<t_vertex>& s2);
set<t_vertex> set_symm_diff(const set<t_vertex>& s1, const set<t_vertex>& s2);
set<t_arc> set_multiply(const set<t_vertex>& s1, const set<t_vertex>& s2);
set<t_arc> set_substract(const set<t_arc>& s1, const set<t_arc>& s2);
set<t_arc> get_irreflexive(const set<t_arc>& s);
*/
inline t_arc reverse_arc(const t_arc a){
return t_arc(a.second, a.first);
}
set<t_vertex> get_maximal_matching(const set<t_vertex>& vertices, const set<t_arc>& arcs);
ostream& operator<<(ostream& os, const set<t_vertex>& s);
ostream& operator<<(ostream& os, const set<t_arc>& a);
ostream& operator<<(ostream& os, const t_arc& a);
class t_dir_graph {
private:
t_adjtable successors;
t_adjtable predecessors;
set<t_arc> forbidden_arcs;
set<t_arc> permanent_arcs;
set<t_3path> p3_set;
map<t_diamond, uint> diamond_set; // map diamonds to belt sizes
public:
// ============ construction / destruction =============
// constructor
t_dir_graph();
// copy constructor
t_dir_graph(const t_dir_graph& d);
// destructor
~t_dir_graph();
// ============== operators ==================
t_dir_graph operator=(const t_dir_graph& d);
// ============== information providing ==============
// return whether the digraph is empty [contains no arcs]
bool has_no_arcs() const;
// return whether the digraph is empty [contains no vertices]
bool is_empty() const;
// return whether the digraph is completely connected
bool is_complete() const;
// return whether the given vertex is in the digraph
bool contains_vertex(const t_vertex& v) const;
// return whether the given arc is in the digraph
bool contains_arc(const t_arc& a) const;
// return whether the given arc is forbidden
bool is_forbidden(const t_arc& a) const;
// return whether the given arc is permanent
bool is_permanent(const t_arc& a) const;
// return whether v is a sink of the digraph
bool is_sink(const t_vertex& v) const;
// return whether v is a source of the digraph
bool is_source(const t_vertex& v) const;
// return all sinks
set<t_vertex> get_sinks() const;
// return all sources
set<t_vertex> get_sources() const;
// get all vertices
set<t_vertex> get_vertices() const;
// get all arcs
set<t_arc> get_arcs() const;
// get all successor-vertices of a given vertex
set<t_vertex> get_successors(const t_vertex& v) const;
// get all predecessor-vertices of a given vertex
set<t_vertex> get_predecessors(const t_vertex& v) const;
// get all neighbors of v, that is successors and predecessors
set<t_vertex> get_neighbors(const t_vertex& v) const;
// get the number of vertices in the graph
uint get_vertex_number() const;
// get the number of arcs in the graph
uint get_arc_number() const;
// get the subgraph induced by the given vertex-set
t_dir_graph* get_induced_subgraph(const set<t_vertex>& vertices) const;
// calculate the reachability of v in D
// if undirected is true, all vertices can reach their predecessors
set<t_vertex> get_reachable(const t_vertex& v, bool undirected = false) const;
// ========== P3 information providing ==============
// return all p3 in p3_set with (v,*,*)
set<t_3path> get_p3_by_first(const t_vertex& v) const;
// return all p3 in p3_set with (*,v,*)
set<t_3path> get_p3_by_middle(const t_vertex& v) const;
// return all p3 in p3_set with (*,*,v)
set<t_3path> get_p3_by_third(const t_vertex& v) const;
// get the set of P3 that involve a given vertex v
set<t_3path> get_p3_involving(const t_vertex& v) const;
// get some p3 in the digraph
p_3path get_a_p3() const;
// get some diamond in the digraph
p_diamond get_a_diamond() const;
// get all p3 in the digraph
set<t_3path> get_p3() const;
// get all diamonds in the digraph
map<t_diamond,uint> get_diamonds() const;
// get all vertices that are the first(second,third) vertex of some P3
set<t_vertex> get_p3_first() const;
set<t_vertex> get_p3_second() const;
set<t_vertex> get_p3_third() const;
// ========== graph modifications ===================
// increase the belt size of the given diamond
void increase_diamond(const t_diamond& diam);
// decrease the belt size of the given diamond
void decrease_diamond(const t_diamond& diam);
// insert a vertex
bool insert_vertex(const t_vertex& v);
// delete a vertex
bool delete_vertex(const t_vertex& v);
// delete multiple vertices
bool delete_vertices(const set<t_vertex>& V);
// insert an arc
bool insert_arc(const t_arc& a, const bool permanent = false);
// delete an arc
bool delete_arc(const t_arc& a, const bool forbidden = false);
// mark an arc forbidden/permanent
bool mark_arc(const t_arc& a, const uint mark);
// delete all vertices that are not in the given vertex set from the graph
void induced_subgraph(const set<t_vertex>& vertices);
// split a weakly connected component from the digraph
t_dir_graph* split_component();
// ============= IO ====================
// read a graph from the given file, return success
bool read_from_stream(istream& input);
// read a graph from the given file, return success
bool read_from_file(const char* filename);
// print the digraph to a stream
void print(ostream& output) const;
// streaming IO
friend ostream& operator<<(ostream& os, const t_dir_graph& d);
friend istream& operator>>(istream& is, t_dir_graph& d);
private:
bool read_format1(istream& input, const string first_line);
bool read_format2(istream& input, const string first_line);
};
t_dir_graph* generate_random_digraph(const uint vertices, const double arc_probability = 0.5);
#endif