forked from cfrasinaru/Graph4J
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtodo.txt
184 lines (128 loc) · 5.07 KB
/
todo.txt
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
https://github.com/jgrapht/jgrapht
https://github.com/kevin-wayne/algs4
https://github.com/jrtom/jung
https://github.com/google/guava/tree/master/guava/src/com/google/common/graph
https://github.com/google/guava/wiki/GraphsExplained
https://gephi.org/users/supported-graph-formats/
NetworkX
https://networkx.org/
https://github.com/networkx/networkx/tree/main/networkx/algorithms
NetworKit
https://networkit.github.io/index.html
C++
BGL https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/index.html
.NET
https://github.com/YaccConstructor/QuickGraph/tree/master/src/QuickGraph/Algorithms
iGraph
https://igraph.org/c/doc/
teexGraph (diameter)
https://github.com/franktakes/teexgraph
R Plots
https://sites.harding.edu/fmccown/r/
FastUtils
https://github.com/vigna/fastutil
Linear regression
https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/LinearRegression.java.html
Stanford Large Network Dataset Collection
https://snap.stanford.edu/data/
Comparatii legate de modul de rulare / performanta:
- crearea de grafuri (empty,random,complete)
- dfs, bfs
- conectivitate
- cicluri
Implementare de noi algoritmi
Package .ordering
vertex orderings: lex-bfs, maximum cardinality search (?), maximal neighborhood search (?), degeneracy (?)
Package .col
Chordal Ggraph coloring
https://en.wikipedia.org/wiki/Chordal_graph
https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/color/ChordalGraphColoring.java
3-coloring
Wigderson’S Algorithm https://iq.opengenus.org/wigderson-algorithm/
JCOL
https://github.com/shah314/graphcoloring
ColPack (C++)
https://github.com/CSCsw/ColPack
Min cutset
Karger's Algorithm
https://en.wikipedia.org/wiki/Karger%27s_algorithm
Shortest Paths:
Johnson's algorithm
https://en.wikipedia.org/wiki/Johnson%27s_algorithm
Finding the k-shortest path between two nodes
https://cs.stackexchange.com/questions/18849/finding-the-k-shortest-path-between-two-nodes
https://en.wikipedia.org/wiki/K_shortest_path_routing
Chordal Graphs
generation: Linear-Time Generation of Random Chordal Graphs
recognition: LexBFS
coloring, maximum clique
For the Assignment Problem
Succesive shortest path algorithm
https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/AssignmentProblem.java
Hungarian algorithm ( Kuhn Munkres Minimal Weight Bipartite Perfect Matching)
https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/matching/KuhnMunkresMinimalWeightBipartitePerfectMatching.java
https://en.wikipedia.org/wiki/Hungarian_algorithm
https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/optimization/HungarianAlgorithm.java
Jonker-Volgenant Algorithm for Linear Assignment Problem
R. Jonker and A. Volgenant, "A shortest augmenting path algorithm for dense and spare linear assignment problems"
https://link.springer.com/article/10.1007/bf02278710
https://github.com/yongyanghz/LAPJV-algorithm-c/blob/master/LAPJV/lap.cpp
https://www.mathworks.com/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v3-0
PageRank
https://en.wikipedia.org/wiki/PageRank
http://infolab.stanford.edu/~backrub/google.html
https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/scoring/PageRank.html
Scoring algorithms
https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/scoring/package-summary.html
MST
Boruvka Algorithm
https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
Randomized minimum spanning tree algorithm ?
Parallel Prim
https://en.wikipedia.org/wiki/Prim%27s_algorithm
Metrici si masuri specifice relatiilor sociale
Generaratoare de grafuri
OK k-regulate
https://math.stackexchange.com/questions/142112/how-to-construct-a-k-regular-graph
https://mediatum.ub.tum.de/doc/1315533/1315533.pdf
- care au o anumita secventa (di)grafica
folosind fluxuri
Planarity
Breadth First Search
Depth First Search
Uniform Cost Search
Dijkstra's Shortest Paths
Bellman-Ford Shortest Paths
Johnson's All-Pairs Shortest Paths
Kruskal's Minimum Spanning Tree
Prim's Minimum Spanning Tree
Connected Components
Strongly Connected Components
Dynamic Connected Components (using Disjoint Sets)
Topological Sort
Transpose
Reverse Cuthill Mckee Ordering
Smallest Last Vertex Ordering
Sequential Vertex Coloring
//graph
//vertices=4n, degree=4n, adjList=4n+2*4m, adjPos=4n+2*4m
//vertexWeight=8n, edgeWeight=4n+2*8m
//vertexLabel=4n, edgeLabel=4n+2*4m
//
//vertexIndex=4n
//adjSet=n^2/64 ~ m
//labelVertexMap=4n + 16n
//labelEdgeMap=16m + 16m
//
//simple graph: 16n + 16m (adjPos true, adjSet false) OK
//simple with fast adjacency test: 16n + 17m OK
//edge weighted graph: 20n + 32/33m OK
//edge labeled graph: 20n + 24/25m OK
//vertex labeled graph:24n + 16m OK
//
//digraph
//vertices=4n, degree=4n, indegree=4n, adjList = 4n+4m, predList=4n+4m, predPos=4n + 4m
//vertexWeight=8n, edgeWeight=4n+8m
//vertexLabel=4n, edgeLabel=4n+4m
//simple digraph=24n + 12/13m OK
//simple weighted digraph=28n + 20/21m OK