-
Notifications
You must be signed in to change notification settings - Fork 1
/
TODO
196 lines (170 loc) · 4.94 KB
/
TODO
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
TODO LIST
=========
[] 23/01/2018 ->
The value of epsilon used for floating point value comparison in the
weighted path-finding algorithms should a user's choice.
[] 20/10/2018 ->
Implement reading/writing from/to graph6, sparse6, digraph6 formats.
[v] 20/10/2018 -> 23/09/2018
graph6
[] 20/10/2018 ->
sparse6
[] 20/10/2018 ->
digraph6
[] 23/09/2018 ->
Implement function to obtain induced subgraph:
- given a list of vertices.
- given a list of edges.
[] 11/09/2018 ->
Implement algorithm to find max-flow min-cut of a weighted graph.
[] 11/09/2018 ->
Implement algorithm to find the topological order of the
nodes of a graph
[] 26/02/2018 ->
Implement an algorithm to find all connected components of a graph.
[] 23/08/2018 ->
Directed graphs
[v] 23/08/2018 -> 01/10/2018
Undirected graphs
[] 21/01/2019 ->
Finish the tests for all currently implemented algorithms (as of 21/01/2019)
[v] 21/01/2019 -> 25/01/2019
Distances in
- (v) unweighted undirected
- (v) unweighted directed
- (v) weighted undirected
- (v) weighted directed
[v] 21/01/2019 -> 25/01/2019
Paths in
- (v) unweighted undirected
- (v) unweighted directed
- (v) weighted undirected
- (v) weighted directed
[] 26/01/2019 ->
Input and output of
- graph6
- digraph6
- sparse6
[] 26/01/2019 ->
Connected components of
- directed graphs
- undirected graphs
[] 26/01/2019 ->
Centrality metrics
- Degree
* (v) unweighted undirected
* unweighted directed
* (v) weighted undirected
* weighted directed
- Closeness
* (v) unweighted undirected
* unweighted directed
* (v) weighted undirected
* weighted directed
- Mean Closeness
* (v) unweighted undirected
* unweighted directed
* (v) weighted undirected
* weighted directed
- Betweenness
* (v) unweighted undirected
* unweighted directed
* (v) weighted undirected
* weighted directed
[] 26/01/2019 ->
Clustering metrics
- Global Clustering Coefficient
* (v) unweighted undirected
* (v) weighted undirected
- Mean Local Clustering Coefficient
* (v) unweighted undirected
* (v) weighted undirected
[] 26/01/2019 ->
Distance metrics
- Maximum distance
* unweighted undirected
* unweighted directed
* weighted undirected
* weighted directed
- Mean distance
* unweighted undirected
* unweighted directed
* weighted undirected
* weighted directed
[v] 23/08/2018 -> 24/08/2018
Refactor code for generating graphs. Make a directory called
generate/ with subdirectories for social graphs, classic graphs.
Each directory should have another subdirectory called random_graphs.
Example:
generate/switching.hpp
generate/switching.cpp
generate/classic/{...}
generate/social/{...}
[v] 22/08/2018 -> 23/08/2018
Implement Erdos-Renyi model
[v] 06/03/2018 -> 19/08/2018
Implement SIS and SIR with node immunity
[v] 26/02/2018 -> 15/08/2018
Use class 'svector' to implement the adjacency list of the graph data
structure.
[v] 24/03/2018 -> 28/05/2018
Add documentation with Doxygen
[v] 31/03/2018 -> 22/04/2018
Refactor code in traversal.hpp
[v] 16/02/2018 -> 22/04/2018
Implement distance and path-finding methods using Dijkstra
[v] 16/02/2018 -> 31/03/2018 (actually, before that date)
Implement generic Dijkstra
[v] 25/03/2018 -> 31/03/2018 (actually, before that date)
Adapt functions in traversal namespace to admit abstract graphs.
[v] 16/03/2018 -> 25/03/2018
Implement undirected weighted graph
[v] 16/02/2018 -> 07/03/2018
Implement generic DFS
[v] 16/02/2018 -> 05/03/2018
Implement the boolean path using actual bitsets (not vector<bool>)
[v] 16/02/2018 -> 26/02/2018
Implement betweennes centrality metric (that uses a boolean path)
[v] 16/02/2018 -> 26/02/2018
For a single vertex
[v] 16/02/2018 -> 26/02/2018
For all vertices of a graph
[v] 20/02/2018 -> 25/02/2018
Implement algorithm to enumerate all shortest paths:
[v] 20/02/2018 -> 25/02/2018
As boolean paths
[v] 20/02/2018 -> 25/02/2018
Between two nodes
[v] 20/02/2018 -> 25/02/2018
From a node to the rest
[v] 20/02/2018 -> 25/02/2018
From a any node to any other node
[v] 20/02/2018 -> 20/02/2018
As node paths
[v] 20/02/2018 -> 20/02/2018
Between two nodes
[v] 20/02/2018 -> 20/02/2018
From a node to the rest
[v] 20/02/2018 -> 20/02/2018
From a any node to any other node
[v] 16/02/2018 -> 18/02/2018
Implement algorithm to count the number of shortest pahts:
[v] 16/02/2018 -> 18/02/2018
Between two nodes
[v] 16/02/2018 -> 17/02/2018
From a node to the rest
[v] 16/02/2018 -> 17/02/2018
From a any node to any other node
[v] 13/02/2018 -> 16/02/2018
Implement two classes that implement paths as
[v] 16/02/2018 -> 16/02/2018
List of vertices
[v] 16/02/2018 -> 16/02/2018
Bitsets (a vertex is in the path if the corresponding bit
is set to 1)
[v] 13/02/2018 -> 16/02/2018
Debug path-finding with BFS
[v] 13/02/2018 -> 16/02/2018
Implement all-to-all path finding
[v] 13/02/2018 -> 13/02/2018
Add option to read graphs in edge list format in main file