aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--.vscode/launch.json26
-rw-r--r--graphs/celegansneural.graph297
-rw-r--r--graphs/florida-bay.graph128
-rw-r--r--graphs/karateWeighted.graph34
-rw-r--r--graphs/polbooksWeighted.graph105
-rw-r--r--src/NetworkFlow/Graph.cs109
-rw-r--r--src/Program/Analysis.cs78
-rw-r--r--src/Program/Program.cs95
8 files changed, 763 insertions, 109 deletions
diff --git a/.vscode/launch.json b/.vscode/launch.json
index 7f48531..0f7ced4 100644
--- a/.vscode/launch.json
+++ b/.vscode/launch.json
@@ -5,39 +5,17 @@
"version": "0.2.0",
"configurations": [
{
- "name": ".NET Core Launch (console)",
+ "name": "lots-o-graphs",
"type": "coreclr",
"request": "launch",
"preLaunchTask": "build",
"program": "${workspaceFolder}/src/Program/bin/Debug/net5.0/Program.dll",
"args": [
- "../../graphs/Project4Graph2.txt",
- "0",
- "6"
+ "../../graphs"
],
"cwd": "${workspaceFolder}/src/Program",
"console": "integratedTerminal",
"stopAtEntry": false
},
- {
- "name": "smol graff",
- "type": "coreclr",
- "request": "launch",
- "preLaunchTask": "build",
- "program": "${workspaceFolder}/src/Program/bin/Debug/net5.0/Program.dll",
- "args": [
- "../../graphs/Project4Graph1.txt",
- "0",
- "5"
- ],
- "cwd": "${workspaceFolder}/src/Program",
- "console": "integratedTerminal",
- "stopAtEntry": false
- },
- {
- "name": ".NET Core Attach",
- "type": "coreclr",
- "request": "attach"
- }
]
} \ No newline at end of file
diff --git a/graphs/celegansneural.graph b/graphs/celegansneural.graph
new file mode 100644
index 0000000..961595d
--- /dev/null
+++ b/graphs/celegansneural.graph
@@ -0,0 +1,297 @@
+0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1
+1 10 1 115 1 12 1 84 1 129 1 7 1 130 1 131 1 72 1 74 1
+2 67 1 151 1 152 1 153 1 154 1 155 1 156 1 157 1 158 1 12 1 86 1 118 1 4 1 159 1 160 1 161 1 162 1 163 1 164 1 165 1 166 1 167 1 168 1 169 1 184 1 185 1 125 1 8 1 173 1 186 1 175 1 176 1 177 1 178 1 179 1 180 1 181 1 182 1 183 1
+3 151 1 154 1 155 1 12 1 117 1 159 1 160 1 161 1 162 1 168 1 195 1 125 1 173 1 186 1 196 1 178 1 179 1 180 1 182 1 197 1 189 1
+4 151 1 154 1 155 1 2 1 118 1 159 1 160 1 161 1 162 1 168 1 195 1 172 1 173 1 174 1 196 1 178 1 179 1 180 1 182 1 197 1 189 1
+5 10 1 11 1 12 1 3 1 13 1 14 1 8 1
+6 27 1 50 1 34 1 23 1 35 1 47 1 48 1 43 1 46 1 72 1 88 1 94 1 25 1 73 1 74 1 77 1 75 1
+7 1 1 2 1 3 1 6 1 59 1 73 1
+8 102 1 108 1 235 1 3 1 4 1 213 1 5 1 193 1 14 1 103 1 214 1 36 1
+9 108 1 236 1 4 1 213 1 218 1 5 1 7 1 103 1 24 1
+10 102 1 208 1 138 1 124 1 142 1 13 1 14 1
+11 12 1 118 1 3 1 13 1 14 1
+12 16 1 151 1 152 1 153 1 154 1 155 1 156 1 157 1 158 1 2 1 84 1 117 1 3 1 159 1 160 1 161 1 162 1 163 1 164 1 165 1 166 1 167 1 168 1 168 1 169 1 170 1 171 1 172 1 173 1 174 1 175 1 176 1 177 1 178 1 179 1 180 1 181 1 182 1 183 1
+13 6 1 34 1 209 1 23 1 35 1 47 1 48 1 43 1 46 1 88 1 73 1 74 1 77 1 75 1
+14 114 1 11 1 12 1 86 1 118 1 3 1 4 1 13 1 75 1
+15 16 1 4 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1
+16 113 1 1 1 114 1 92 1 115 1 116 1 12 1 2 1 84 1 117 1 118 1 119 1 98 1 120 1 19 1 22 1 73 1
+17 41 1 22 1 23 1 53 1 44 1
+18 4 1 71 1 15 1 17 1 14 1 23 1 35 1 47 1 43 1 51 1 72 1 73 1 74 1 75 1 76 1
+19 17 1 70 1 20 1 59 1 22 1 46 1 80 1
+20 12 1 2 1 132 1 130 1 209 1 210 1 89 1 73 1 74 1 75 1
+21 106 1 12 1 2 1 85 1 73 1 74 1 77 1 75 1
+22 55 1
+23 46 1 44 1
+24 48 1 44 1
+25 190 1
+26 22 1 51 1 49 1 64 1 44 1
+27 28 1 3 1 29 1 30 1 31 1 32 1 20 1 21 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1
+28 122 1 114 1
+29 50 1 30 1 33 1 35 1 44 1
+30 29 1 32 1 6 1 59 1 33 1 51 1 49 1 64 1 38 1 52 1
+31 3 1 4 1 58 1 27 1 45 1 29 1 66 1 7 1 35 1 47 1 48 1 46 1 49 1 73 1 74 1 77 1 75 1
+32 29 1 30 1 21 1 59 1 33 1 43 1 49 1 81 1
+33 68 1
+34 13 1 6 1 47 1 43 1 72 1 37 1 112 1 74 1 44 1
+35 43 1 44 1
+36 49 1 93 1 44 1
+37 190 1
+38 50 1 33 1 43 1 49 1 64 1 44 1
+39
+40 41 1 42 1 22 1 43 1 44 1
+41 4 1 40 1 23 1 47 1 48 1 43 1 46 1 49 1 44 1
+42 84 1 86 1 119 1 98 1 218 1 167 1 232 1 168 1 137 1 40 1 45 1 17 1 29 1 185 1 172 1 22 1 33 1 173 1
+43 6 1 23 1 35 1 44 1
+44
+45 33 1 46 1 44 1
+46 23 1 79 1 44 1
+47 31 1 13 1 6 1 35 1 48 1 214 1 44 1
+48 213 1 13 1 6 1 23 1 47 1 44 1
+49 44 1
+50 3 1 45 1 23 1 35 1 47 1 48 1 43 1 46 1 51 1 52 1 44 1
+51 44 1
+52 99 1 84 1 86 1 4 1 32 1 6 1 21 1 9 1 33 1 48 1 37 1
+53 86 1 4 1 17 1 13 1 14 1 59 1 90 1 23 1 46 1 78 1 75 1
+54 11 1 40 1 55 1 14 1 22 1 51 1 49 1 56 1
+55 21 1 35 1 78 1
+56 40 1 22 1 35 1 51 1 44 1
+57 58 1 45 1 21 1 59 1 33 1 60 1 51 1 49 1 61 1
+58 3 1 95 1 45 1 50 1 31 1 68 1 7 1 20 1 21 1 23 1 46 1 87 1 24 1 88 1 85 1 61 1 69 1 82 1
+59 105 1 102 1 108 1 99 1 5 1 71 1 58 1 15 1 27 1 66 1 55 1 68 1 19 1 32 1 13 1 6 1 14 1 7 1 22 1 33 1 49 1 64 1 91 1 39 1
+60 14 1 7 1 44 1
+61 33 1 46 1 60 1 49 1 82 1 44 1
+62 63 1 3 1 41 1 55 1 19 1 20 1 59 1 47 1 48 1 49 1 64 1 65 1
+63 101 1 12 1 2 1 3 1 225 1 71 1 129 1 41 1 62 1 18 1 13 1 215 1 8 1 9 1 59 1 34 1 209 1 47 1 93 1 24 1 94 1 81 1 85 1 83 1
+64 74 1 44 1
+65 11 1 84 1 3 1 98 1 13 1 20 1 8 1
+66 67 1 50 1 31 1 68 1 32 1 59 1 47 1 51 1 64 1 38 1 69 1
+67 106 1 63 1 12 1 2 1 118 1 4 1 98 1 218 1 58 1 129 1 224 1 31 1 8 1 9 1 59 1 48 1 87 1 212 1
+68 20 1 21 1 23 1 36 1 79 1
+69 86 1 58 1 50 1 66 1 21 1 47 1 48 1 87 1 88 1 37 1 89 1 52 1
+70 5 1 17 1 19 1 13 1 59 1 22 1 51 1 49 1 64 1 26 1
+71 4 1 40 1 41 1 18 1 55 1 14 1 20 1 21 1 22 1 90 1 43 1 93 1 36 1 94 1 89 1 56 1 83 1 76 1
+72 114 1 2 1 18 1 132 1 130 1 214 1 93 1
+73 13 1 6 1 75 1 44 1
+74 13 1 6 1 44 1
+75 13 1 6 1 209 1 23 1 73 1 44 1
+76 4 1 14 1 35 1 43 1 73 1 74 1
+77 42 1 13 1 6 1 34 1 35 1 74 1 44 1
+78 190 1
+79 190 1
+80 190 1
+81 190 1
+82 3 1 4 1 7 1 23 1 46 1 73 1 74 1
+83 84 1 71 1 41 1 21 1 35 1 25 1 85 1 65 1
+84 151 1 152 1 155 1 156 1 157 1 158 1 2 1 86 1 118 1 4 1 187 1 163 1 142 1 175 1 180 1 188 1 189 1 190 1
+85 12 1 60 1 211 1 44 1
+86 151 1 152 1 155 1 156 1 157 1 158 1 12 1 84 1 117 1 3 1 187 1 163 1 191 1 175 1 180 1 188 1 189 1 190 1
+87 106 1 236 1 109 1 2 1 86 1 117 1 4 1 119 1 103 1 47 1 48 1 43 1 46 1 52 1 44 1
+88 190 1
+89 2 1 60 1 212 1 44 1
+90 3 1 4 1 213 1 218 1 187 1 71 1 58 1 15 1 27 1 31 1 14 1 7 1 132 1 130 1 23 1 47 1 48 1 73 1 74 1 77 1 75 1 91 1
+91 12 1 3 1 29 1 6 1 7 1 23 1 35 1 43 1 78 1 79 1 77 1
+92 3 1 4 1 48 1 39 1 39 1
+93 101 1 114 1 216 1 235 1 141 1 12 1 86 1 3 1 71 1 47 1 48 1 43 1 36 1 25 1 78 1 104 1 65 1 44 1
+94 190 1
+95 63 1 67 1 240 1 12 1 198 1 119 1 142 1 125 1 172 1 207 1 204 1 72 1 241 1 61 1
+96 97 1 60 1 44 1
+97 166 1 227 1 221 1 44 1
+98 2 1 84 1 86 1 118 1 3 1 202 1 198 1 119 1 206 1 191 1 125 1 172 1 207 1 145 1 186 1
+99 107 1 2 1 4 1 6 1 7 1 52 1
+100 101 1 102 1 11 1 19 1 13 1 103 1 104 1
+101 1 1 114 1 2 1 84 1 86 1 3 1 98 1 224 1 132 1 22 1 22 1 77 1
+102 100 1 113 1 1 1 114 1 135 1 136 1 4 1 137 1 13 1 59 1 132 1 89 1 104 1
+103 102 1 108 1 201 1 11 1 5 1 137 1 191 1 13 1 6 1 65 1 52 1
+104 222 1 64 1 131 1 44 1
+105 106 1 107 1 108 1 109 1 99 1 110 1 111 1 6 1 9 1 103 1 89 1 112 1 52 1
+106 84 1 86 1 3 1 119 1 130 1 33 1 209 1 75 1
+107 105 1 108 1 139 1 191 1 6 1 7 1
+108 122 1 1 1 114 1 3 1 4 1 137 1 6 1 130 1 85 1 112 1
+109 106 1 105 1 122 1 114 1 2 1 86 1 117 1 118 1 4 1 142 1 111 1 6 1 87 1
+110 105 1 108 1 28 1 86 1 6 1 103 1 112 1
+111 105 1 201 1 12 1 2 1 84 1 86 1 3 1 198 1 187 1 233 1 193 1 125 1 172 1 145 1 6 1 9 1 130 1 190 1
+112 223 1 64 1 72 1 44 1
+113 101 1 1 1 149 1 102 1 115 1 140 1 141 1 124 1 191 1 215 1
+114 2 1 86 1 3 1 13 1 14 1 132 1 130 1 131 1 73 1 133 1
+115 126 1 128 1 113 1 122 1 1 1 114 1 10 1 107 1 139 1 138 1 124 1
+116 100 1 113 1 1 1 141 1 12 1 84 1 117 1 118 1 13 1 132 1 22 1 103 1
+117 151 1 152 1 153 1 156 1 157 1 12 1 84 1 118 1 159 1 160 1 161 1 162 1 163 1 166 1 167 1 192 1 193 1 170 1 194 1 125 1 173 1 186 1 176 1 178 1 179 1 181 1 182 1
+118 151 1 152 1 153 1 156 1 157 1 2 1 86 1 117 1 159 1 160 1 161 1 162 1 163 1 166 1 167 1 192 1 193 1 184 1 194 1 172 1 173 1 174 1 176 1 178 1 179 1 181 1 182 1
+119 12 1 84 1 86 1 117 1 4 1 199 1 123 1 142 1 125 1 172 1 204 1 148 1 205 1 90 1 174 1
+120 100 1 114 1 102 1 84 1 13 1 85 1
+121 122 1 114 1 115 1 109 1 2 1 84 1 86 1 117 1 118 1 123 1 98 1 124 1 31 1 125 1 20 1 21 1
+122 106 1 121 1 114 1 108 1 115 1 139 1 124 1 205 1
+123 121 1 201 1 84 1 118 1 202 1 198 1 119 1 98 1 203 1 145 1 8 1 103 1 89 1 104 1 200 1
+124 121 1 122 1 1 1 114 1 10 1 107 1 138 1
+125 151 1 154 1 12 1 2 1 84 1 86 1 117 1 118 1 3 1 4 1 119 1 187 1 160 1 232 1 168 1 192 1 169 1 253 1 137 1 184 1 171 1 172 1 42 1 256 1 96 1 90 1 78 1 254 1 262 1 263 1 264 1 265 1 266 1 267 1
+126 127 1 10 1
+127 126 1 113 1 1 1 115 1 5 1 14 1 96 1 39 1
+128 107 1 115 1
+129 63 1 67 1 1 1 114 1 12 1 2 1 84 1 86 1 117 1 118 1 137 1 224 1
+130 106 1 1 1 12 1 84 1 86 1 119 1 213 1 7 1 90 1 47 1 48 1 210 1 211 1 212 1 73 1 74 1 44 1
+131 1 1 12 1 132 1 130 1 93 1
+132 12 1 84 1 86 1 14 1 90 1 47 1 48 1 210 1 72 1 211 1 212 1 74 1 77 1 44 1
+133 114 1 219 1 132 1 214 1 131 1 72 1 173 1 196 1 178 1 179 1 200 1 197 1 44 1
+134 128 1 135 1 28 1 99 1 0 1 14 1 7 1 39 1
+135 105 1 113 1 1 1 114 1 10 1 107 1 138 1 124 1 6 1
+136 1 1 10 1 102 1 135 1 115 1 141 1 138 1 124 1
+137 102 1 201 1 11 1 99 1 12 1 84 1 3 1 4 1 232 1 168 1 192 1 169 1 253 1 185 1 125 1 42 1 13 1 6 1 130 1 103 1 72 1 211 1 212 1 89 1 85 1 104 1 112 1 177 1 133 1 254 1
+138 113 1 122 1 1 1 114 1 10 1 12 1 13 1
+139 105 1 128 1 107 1 108 1 135 1 115 1 110 1 205 1 103 1
+140 113 1 1 1 127 1 141 1
+141 113 1 1 1 149 1 144 1
+142 1 1 114 1 102 1 108 1 157 1 116 1 117 1 202 1 119 1 120 1 95 1 163 1 164 1 169 1 191 1 204 1 148 1 205 1 130 1 87 1 173 1 186 1 181 1 182 1 238 1 245 1 244 1 44 1 44 1
+143 122 1 135 1 109 1 138 1 124 1
+144 141 1 145 1
+145 113 1 144 1 141 1 187 1 219 1 195 1 193 1 191 1 93 1 200 1 39 1
+146 147 1 142 1 148 1
+147 122 1 114 1 150 1 139 1
+148 122 1 147 1 199 1 187 1 219 1 195 1 193 1 142 1 205 1 200 1 39 1
+149 113 1 216 1 140 1 141 1 86 1 117 1 118 1 4 1 202 1 199 1 198 1 123 1 119 1 145 1 215 1 104 1 39 1 39 1
+150 122 1 28 1 146 1 147 1 118 1 202 1 199 1 98 1 191 1 142 1 205 1 87 1 39 1
+151 159 1 200 1 44 1
+152 165 1 249 1 268 1 44 1
+153 161 1 166 1 167 1 249 1 227 1 44 1
+154 160 1 197 1 44 1
+155 161 1 197 1 189 1 44 1
+156 189 1 231 1 44 1
+157 162 1 231 1 234 1 44 1
+158 163 1 234 1 269 1 44 1
+159 200 1 197 1 44 1
+160 219 1 200 1 197 1 189 1 44 1
+161 162 1 233 1 189 1 231 1 44 1
+162 163 1 275 1 231 1 234 1 269 1 44 1
+163 164 1 276 1 269 1 271 1 44 1
+164 165 1 276 1 273 1 268 1 44 1
+165 166 1 97 1 249 1 227 1 44 1
+166 167 1 97 1 227 1 221 1 44 1
+167 97 1 227 1 221 1 44 1
+168 156 1 233 1 275 1 189 1 231 1 234 1 269 1 44 1
+169 270 1 272 1 276 1 277 1 234 1 269 1 271 1 273 1 44 1
+170 12 1 2 1 117 1 118 1 119 1 255 1 207 1 256 1
+171 213 1 137 1 185 1 125 1 217 1 42 1 246 1 190 1
+172 201 1 151 1 154 1 12 1 2 1 84 1 86 1 117 1 118 1 3 1 4 1 187 1 160 1 232 1 168 1 192 1 169 1 253 1 137 1 129 1 170 1 185 1 125 1 42 1 220 1 96 1 79 1 254 1 262 1 263 1 264 1 265 1 266 1 267 1
+173 178 1
+174 190 1
+175 277 1 176 1 44 1
+176 97 1 177 1 249 1 227 1 44 1
+177 153 1 166 1 167 1 253 1 97 1 170 1 125 1 172 1 176 1 221 1 183 1 44 1
+178 219 1 179 1 200 1 197 1 44 1
+179 219 1 233 1 180 1 197 1 189 1 44 1
+180 233 1 181 1 231 1 44 1
+181 275 1 182 1 231 1 234 1 44 1
+182 275 1 188 1 44 1
+183 177 1 44 1
+184 12 1 2 1 117 1 118 1 98 1 194 1 172 1 42 1 256 1
+185 218 1 137 1 171 1 172 1 217 1 42 1 246 1 190 1
+186 190 1
+187 151 1 4 1 199 1 160 1 219 1 97 1 111 1 220 1 173 1 174 1 221 1 44 1
+188 276 1 279 1 269 1 271 1 44 1
+189 155 1 237 1 44 1
+190
+191 113 1 102 1 108 1 157 1 116 1 109 1 146 1 141 1 117 1 202 1 119 1 120 1 110 1 163 1 142 1 215 1 132 1 173 1 186 1 182 1 238 1 244 1 44 1 44 1
+192 157 1 158 1 275 1 276 1 231 1 234 1 269 1 271 1 44 1
+193 1 1 114 1 12 1 2 1 84 1 213 1 218 1 195 1 14 1 8 1 9 1 214 1 210 1
+194 12 1 2 1 118 1 226 1 170 1 204 1
+195 1 1 114 1 213 1 218 1 187 1 166 1 97 1 97 1 193 1 250 1 111 1 8 1 9 1 59 1 64 1 214 1 210 1 85 1 44 1 190 1
+196 219 1 178 1 133 1 200 1 44 1
+197 155 1 237 1 44 1
+198 105 1 86 1 117 1 199 1 123 1 119 1 98 1 110 1 111 1 148 1 130 1 103 1 85 1 112 1 200 1
+199 84 1 86 1 202 1 226 1 123 1 119 1 187 1 142 1 185 1 145 1 227 1 44 1
+200 219 1 196 1 44 1
+201 12 1 2 1 84 1 86 1 117 1 118 1 119 1 0 1 5 1 137 1 125 1 172 1 203 1 13 1 6 1 65 1
+202 84 1 199 1 226 1 123 1 98 1 187 1 191 1 171 1 145 1 133 1 227 1 44 1
+203 101 1 201 1 12 1 2 1 84 1 86 1 118 1 4 1 123 1 187 1 233 1 193 1 172 1 148 1 8 1 190 1
+204 2 1 86 1 118 1 4 1 199 1 226 1 119 1 98 1 187 1 225 1 95 1 219 1 233 1 194 1 172 1 207 1 252 1 220 1 205 1 238 1 245 1 221 1 189 1 231 1 44 1 190 1
+205 109 1 84 1 86 1 202 1 198 1 119 1 98 1 142 1 125 1 172 1 111 1 130 1 33 1
+206 67 1 84 1 86 1 98 1 225 1 95 1 159 1 159 1 125 1 172 1 42 1 96 1 78 1
+207 2 1 86 1 118 1 4 1 199 1 226 1 119 1 98 1 187 1 95 1 219 1 233 1 194 1 172 1 204 1 252 1 256 1 205 1 238 1 245 1 221 1 189 1 231 1 44 1 190 1
+208 101 1 126 1 10 1 102 1 135 1 140 1 120 1
+209 13 1 6 1 23 1 48 1 46 1 64 1 131 1 25 1 73 1 75 1 44 1
+210 114 1 213 1 218 1 48 1 44 1
+211 12 1 31 1 132 1 130 1 210 1 74 1
+212 2 1 132 1 130 1 73 1
+213 84 1 3 1 4 1 206 1 137 1 185 1 217 1 148 1 132 1 130 1 72 1 37 1 190 1
+214 1 1 213 1 218 1 47 1 48 1 87 1 44 1
+215 216 1 84 1 86 1 123 1 98 1 203 1 132 1 130 1
+216 118 1 3 1 225 1 71 1 15 1 125 1 172 1 35 1 93 1 239 1
+217 213 1 206 1 137 1 171 1 125 1 42 1 190 1
+218 137 1 171 1 217 1 203 1 145 1 132 1 130 1 131 1 85 1 73 1 74 1 75 1 190 1
+219 159 1 200 1 197 1 44 1
+220 2 1 118 1 119 1 172 1 252 1 256 1 177 1
+221 177 1 44 1
+222 72 1 112 1
+223 131 1 104 1
+224 67 1 114 1 12 1 2 1 84 1 86 1 117 1 118 1 3 1 4 1 137 1 129 1 125 1 133 1 190 1
+225 63 1 2 1 198 1 98 1 191 1 125 1 207 1 204 1 131 1 56 1 39 1
+226 12 1 2 1 84 1 117 1 118 1 4 1 202 1 98 1 166 1 166 1 195 1 228 1 229 1 125 1 172 1 207 1 204 1 203 1 111 1 145 1 148 1 176 1 176 1 190 1 190 1
+227 44 1
+228 118 1 202 1 226 1 198 1 123 1 166 1 137 1 229 1 255 1 257 1 145 1
+229 226 1 123 1 137 1 228 1 255 1 257 1 145 1
+230 151 1 154 1 219 1 200 1 197 1 189 1 231 1 44 1
+231 44 1
+232 155 1 219 1 233 1 197 1 189 1 231 1 234 1 44 1
+233 161 1 189 1 231 1 44 1
+234 44 1
+235 211 1 85 1 77 1
+236 36 1 212 1 89 1 74 1 77 1
+237 219 1 233 1 178 1 238 1 197 1 189 1 44 1
+238 233 1 142 1 200 1 231 1 44 1 44 1
+239 114 1 216 1 12 1 2 1 3 1 129 1 21 1 90 1 214 1
+240 95 1 58 1 27 1 172 1 23 1 88 1
+241 16 1 1 1 12 1 84 1 86 1 137 1 24 1 36 1
+242 190 1
+243 190 1
+244 202 1 199 1 195 1 193 1 245 1 283 1 44 1
+245 187 1 219 1 233 1 275 1 276 1 142 1 148 1 252 1 282 1 238 1 283 1 200 1 197 1 189 1 231 1 234 1 269 1 271 1 44 1
+246 277 1 175 1 273 1 268 1 44 1
+247 12 1 137 1 172 1 248 1 190 1
+248 2 1 137 1 125 1 247 1 190 1
+249 44 1
+250 167 1 97 1 204 1 44 1
+251 97 1 44 1
+252 190 1
+253 152 1 153 1 97 1 249 1 227 1 273 1 268 1 44 1
+254 97 1 177 1 44 1
+255 12 1 2 1 117 1 257 1 125 1 177 1
+256 12 1 117 1 98 1 125 1 252 1 220 1 177 1
+257 12 1 2 1 117 1 118 1 255 1 125 1 172 1 177 1
+258 12 1 137 1 170 1 125 1 177 1
+259 123 1 167 1 137 1 184 1 258 1 172 1 177 1
+260 191 1
+261 12 1 117 1 137 1 142 1 185 1 172 1
+262 233 1 44 1
+263 233 1 275 1 44 1
+264 275 1 44 1
+265 275 1 276 1 44 1
+266 276 1 44 1
+267 276 1 277 1 44 1
+268 44 1
+269 44 1
+270 269 1 271 1 44 1
+271 44 1
+272 164 1 271 1 273 1 44 1
+273 44 1
+274 273 1 268 1 44 1
+275 162 1 234 1 269 1 44 1
+276 164 1 271 1 273 1 44 1
+277 165 1 249 1 268 1 44 1
+278 274 1 277 1 97 1 269 1 271 1 273 1 268 1 44 1
+279 276 1 246 1 44 1
+280 277 1 97 1 44 1
+281 277 1 44 1
+282 219 1 142 1 238 1 200 1 44 1 44 1
+283 202 1 199 1 276 1 195 1 193 1 244 1 44 1
+284 187 1 233 1 275 1 276 1 277 1 142 1 145 1 244 1 249 1 227 1 221 1 183 1 271 1 273 1 268 1 44 1 44 1
+285 44 1
+286 44 1
+287 44 1
+288 44 1
+289 44 1
+290 44 1
+291 44 1
+292 44 1
+293 44 1
+294 44 1
+295 190 1
+296 190 1
diff --git a/graphs/florida-bay.graph b/graphs/florida-bay.graph
new file mode 100644
index 0000000..05545f1
--- /dev/null
+++ b/graphs/florida-bay.graph
@@ -0,0 +1,128 @@
+0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 24 1 62 1 18 1 15 1
+1 17 1 19 1 20 1 21 1 22 1 23 1 25 1 30 1 44 1 45 1 54 1 40 1 70 1 93 1 15 1
+2 17 1 19 1 20 1 21 1 22 1 23 1 25 1 30 1 44 1 45 1 46 1 52 1 54 1 55 1 33 1 34 1 57 1 59 1 93 1 73 1 84 1 74 1 15 1
+3 20 1 21 1 22 1 25 1 44 1 93 1 73 1 84 1 74 1 15 1
+4 17 1 19 1 20 1 21 1 22 1 23 1 25 1 30 1 31 1 45 1 54 1 15 1
+5 19 1 20 1 21 1 22 1 25 1 30 1 31 1 45 1 54 1 57 1 40 1 70 1 93 1 15 1
+6 19 1 20 1 21 1 22 1 24 1 25 1 30 1 45 1 54 1 40 1 70 1 93 1 15 1
+7 19 1 20 1 21 1 22 1 25 1 30 1 44 1 45 1 54 1 40 1 70 1 93 1 15 1
+8 26 1 28 1 29 1 44 1 46 1 52 1 53 1 55 1 33 1 34 1 35 1 37 1 57 1 59 1 93 1 75 1 27 1
+9 35 1 36 1 38 1 57 1 56 1 90 1 73 1 75 1 112 1 113 1 122 1 125 1 18 1 27 1 15 1 126 1
+10 35 1 36 1 38 1 57 1 56 1 90 1 73 1 75 1 112 1 113 1 125 1 18 1 27 1 15 1 126 1
+11 35 1 36 1 38 1 57 1 56 1 90 1 73 1 75 1 112 1 113 1 125 1 18 1 27 1 15 1 126 1
+12 27 1
+13 93 1 73 1 84 1 74 1 75 1 18 1 27 1 15 1 126 1
+14 44 1 47 1 35 1 36 1 37 1 38 1 57 1 39 1 56 1 90 1 93 1 82 1 73 1 84 1 74 1 75 1 112 1 113 1 122 1 125 1 18 1 27 1 15 1
+15 16 1
+16 17 1 19 1 20 1 21 1 22 1 23 1 25 1 30 1 45 1 18 1 127 1
+17 19 1 20 1 21 1 22 1 23 1 25 1 30 1 45 1 54 1 18 1 127 1
+18 17 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 30 1 45 1 54 1 27 1 127 1
+19 20 1 21 1 22 1 25 1 30 1 45 1 54 1 18 1 127 1
+20 24 1 31 1 32 1 44 1 57 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 50 1 78 1 79 1 80 1 95 1 96 1 71 1 72 1 83 1 98 1 88 1 43 1 51 1 86 1 18 1 127 1
+21 24 1 31 1 32 1 44 1 57 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 50 1 78 1 79 1 80 1 95 1 96 1 71 1 72 1 83 1 98 1 88 1 43 1 51 1 86 1 18 1 127 1
+22 24 1 31 1 32 1 44 1 57 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 50 1 78 1 79 1 80 1 95 1 96 1 71 1 72 1 83 1 98 1 88 1 43 1 51 1 86 1 18 1 127 1
+23 24 1 31 1 32 1 44 1 57 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 50 1 78 1 79 1 80 1 95 1 96 1 71 1 72 1 83 1 98 1 88 1 43 1 51 1 86 1 18 1 127 1
+24 32 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 92 1 50 1 51 1 18 1 127 1
+25 24 1 31 1 32 1 44 1 54 1 57 1 64 1 65 1 66 1 90 1 40 1 41 1 70 1 50 1 78 1 79 1 80 1 51 1 18 1 127 1
+26 28 1 29 1 46 1 52 1 53 1 54 1 55 1 33 1 34 1 74 1 27 1 127 1
+27 26 1 28 1 29 1 44 1 46 1 52 1 53 1 55 1 33 1 34 1 35 1 38 1 57 1 59 1 56 1 60 1 61 1 49 1 74 1 127 1
+28 29 1 46 1 52 1 53 1 54 1 55 1 33 1 34 1 74 1 27 1 127 1
+29 44 1 46 1 53 1 55 1 38 1 57 1 58 1 59 1 65 1 72 1 83 1 84 1 74 1 51 1 75 1 27 1 127 1
+30 44 1 64 1 71 1 82 1 73 1 84 1 85 1 75 1 121 1 123 1 125 1 18 1 127 1
+31 100 1 84 1 85 1 27 1 127 1
+32 44 1 71 1 73 1 100 1 85 1 121 1 123 1 27 1 127 1
+33 32 1 44 1 53 1 57 1 58 1 56 1 76 1 87 1 64 1 65 1 49 1 40 1 41 1 70 1 92 1 78 1 79 1 80 1 96 1 71 1 72 1 82 1 73 1 83 1 99 1 100 1 74 1 42 1 88 1 43 1 51 1 102 1 75 1 27 1 127 1
+34 32 1 44 1 53 1 38 1 58 1 56 1 62 1 64 1 65 1 66 1 67 1 91 1 40 1 41 1 70 1 92 1 50 1 78 1 79 1 80 1 71 1 72 1 82 1 73 1 83 1 98 1 99 1 100 1 74 1 42 1 88 1 43 1 51 1 102 1 75 1 125 1 27 1 127 1
+35 32 1 44 1 53 1 38 1 58 1 56 1 64 1 65 1 66 1 67 1 91 1 40 1 41 1 70 1 92 1 50 1 78 1 79 1 80 1 71 1 72 1 82 1 73 1 83 1 98 1 99 1 100 1 74 1 42 1 88 1 43 1 51 1 102 1 75 1 125 1 27 1 127 1
+36 32 1 44 1 53 1 58 1 87 1 64 1 65 1 66 1 40 1 70 1 92 1 50 1 78 1 79 1 80 1 96 1 81 1 71 1 72 1 82 1 73 1 83 1 99 1 100 1 74 1 42 1 51 1 75 1 125 1 27 1 127 1
+37 32 1 38 1 60 1 61 1 87 1 64 1 65 1 66 1 89 1 49 1 67 1 68 1 69 1 91 1 40 1 41 1 70 1 92 1 50 1 78 1 79 1 80 1 94 1 95 1 96 1 81 1 97 1 71 1 72 1 82 1 73 1 83 1 98 1 99 1 100 1 42 1 51 1 102 1 86 1 75 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 120 1 121 1 123 1 124 1 125 1 18 1 127 1
+38 32 1 60 1 61 1 63 1 76 1 87 1 64 1 65 1 66 1 89 1 49 1 67 1 68 1 69 1 40 1 41 1 70 1 92 1 50 1 78 1 79 1 80 1 94 1 95 1 96 1 81 1 97 1 71 1 72 1 82 1 73 1 83 1 98 1 99 1 100 1 42 1 51 1 102 1 86 1 75 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 120 1 121 1 123 1 124 1 125 1 27 1 127 1
+39 32 1 87 1 64 1 65 1 66 1 89 1 68 1 69 1 40 1 41 1 70 1 92 1 50 1 78 1 79 1 80 1 81 1 97 1 71 1 72 1 83 1 98 1 99 1 100 1 42 1 51 1 18 1 127 1
+40 32 1 63 1 77 1 91 1 81 1 97 1 98 1 99 1 103 1 109 1 18 1 127 1
+41 32 1 63 1 77 1 89 1 67 1 68 1 69 1 91 1 94 1 95 1 96 1 81 1 97 1 83 1 98 1 99 1 101 1 103 1 86 1 75 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 121 1 124 1 18 1 127 1
+42 32 1 63 1 87 1 89 1 68 1 69 1 94 1 96 1 83 1 103 1 51 1 75 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+43 32 1 87 1 89 1 67 1 68 1 69 1 92 1 94 1 96 1 81 1 97 1 83 1 98 1 99 1 103 1 51 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 18 1 27 1 127 1
+44 53 1 58 1 49 1 84 1 85 1 102 1 75 1 105 1 121 1 123 1 125 1 27 1 127 1
+45 44 1 48 1 53 1 38 1 56 1 60 1 61 1 62 1 63 1 76 1 87 1 64 1 65 1 49 1 40 1 41 1 70 1 96 1 71 1 72 1 82 1 73 1 83 1 99 1 84 1 85 1 102 1 75 1 105 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 121 1 123 1 124 1 125 1 27 1 127 1
+46 44 1 48 1 38 1 58 1 62 1 63 1 76 1 87 1 64 1 65 1 49 1 40 1 41 1 70 1 79 1 96 1 71 1 72 1 82 1 73 1 99 1 85 1 102 1 75 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 121 1 123 1 125 1 27 1 127 1
+47 62 1 63 1 76 1 87 1 64 1 65 1 49 1 41 1 71 1 72 1 82 1 73 1 99 1 85 1 102 1 75 1 110 1 112 1 113 1 116 1 117 1 118 1 121 1 27 1 127 1
+48 62 1 63 1 76 1 87 1 64 1 65 1 49 1 96 1 71 1 72 1 82 1 73 1 99 1 85 1 102 1 75 1 112 1 113 1 116 1 117 1 118 1 121 1 27 1 127 1
+49 48 1 63 1 77 1 99 1 108 1 115 1 120 1 124 1 18 1 126 1 127 1
+50 48 1 77 1 91 1 94 1 95 1 96 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+51 48 1 77 1 89 1 94 1 75 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 27 1 126 1 127 1
+52 53 1 38 1 56 1 76 1 87 1 49 1 67 1 41 1 96 1 71 1 72 1 82 1 73 1 83 1 84 1 88 1 43 1 51 1 85 1 102 1 75 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 121 1 123 1 125 1 27 1 127 1
+53 38 1 56 1 76 1 87 1 49 1 67 1 41 1 96 1 71 1 72 1 82 1 73 1 83 1 84 1 88 1 43 1 51 1 85 1 102 1 75 1 105 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 121 1 123 1 125 1 27 1 127 1
+54 53 1 56 1 76 1 87 1 49 1 67 1 41 1 70 1 96 1 71 1 72 1 82 1 73 1 83 1 84 1 88 1 43 1 51 1 85 1 102 1 75 1 105 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 121 1 123 1 125 1 27 1 127 1
+55 53 1 57 1 58 1 76 1 87 1 64 1 65 1 49 1 40 1 41 1 70 1 96 1 71 1 72 1 73 1 83 1 100 1 84 1 74 1 51 1 102 1 75 1 108 1 109 1 110 1 111 1 116 1 117 1 118 1 125 1 27 1 127 1
+56 38 1 60 1 61 1 62 1 63 1 76 1 77 1 87 1 89 1 49 1 67 1 68 1 69 1 41 1 70 1 92 1 94 1 96 1 72 1 82 1 73 1 83 1 100 1 42 1 51 1 85 1 102 1 75 1 104 1 105 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 120 1 121 1 123 1 125 1 27 1 127 1
+57 63 1 76 1 87 1 64 1 65 1 66 1 89 1 49 1 67 1 68 1 69 1 41 1 92 1 50 1 78 1 79 1 80 1 94 1 95 1 96 1 81 1 97 1 71 1 72 1 82 1 73 1 83 1 98 1 99 1 100 1 42 1 51 1 86 1 75 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 120 1 121 1 123 1 124 1 125 1 27 1 126 1 127 1
+58 62 1 63 1 76 1 77 1 87 1 49 1 94 1 83 1 100 1 102 1 104 1 105 1 110 1 111 1 116 1 117 1 118 1 120 1 121 1 123 1 27 1 126 1 127 1
+59 60 1 61 1 63 1 76 1 77 1 87 1 89 1 49 1 67 1 68 1 69 1 41 1 70 1 92 1 94 1 96 1 73 1 100 1 42 1 85 1 102 1 110 1 112 1 113 1 116 1 117 1 118 1 120 1 121 1 123 1 27 1 127 1
+60 63 1 76 1 77 1 89 1 49 1 67 1 68 1 69 1 92 1 94 1 96 1 100 1 85 1 102 1 117 1 27 1 127 1
+61 63 1 76 1 77 1 87 1 89 1 49 1 67 1 68 1 69 1 92 1 94 1 96 1 100 1 85 1 102 1 104 1 105 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 120 1 121 1 123 1 27 1 126 1 127 1
+62 63 1 77 1 49 1 94 1 100 1 102 1 27 1 126 1 127 1
+63 18 1 126 1 127 1
+64 63 1 77 1 91 1 92 1 94 1 95 1 96 1 81 1 97 1 98 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+65 63 1 77 1 91 1 92 1 95 1 96 1 81 1 97 1 98 1 101 1 103 1 86 1 18 1 127 1
+66 63 1 77 1 89 1 67 1 91 1 92 1 94 1 95 1 96 1 81 1 97 1 83 1 98 1 99 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+67 63 1 87 1 89 1 68 1 69 1 94 1 96 1 104 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 27 1 127 1
+68 63 1 87 1 89 1 49 1 94 1 81 1 97 1 98 1 99 1 51 1 75 1 104 1 105 1 106 1 107 1 109 1 111 1 114 1 115 1 120 1 124 1 27 1 126 1 127 1
+69 63 1 87 1 49 1 94 1 99 1 51 1 75 1 115 1 120 1 27 1 127 1
+70 63 1 77 1 67 1 91 1 94 1 95 1 96 1 81 1 97 1 83 1 98 1 99 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 121 1 124 1 18 1 127 1
+71 63 1 77 1 94 1 95 1 96 1 81 1 97 1 72 1 83 1 98 1 99 1 103 1 75 1 104 1 105 1 108 1 109 1 110 1 111 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 120 1 121 1 124 1 18 1 27 1 126 1 127 1
+72 63 1 77 1 94 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+73 63 1 77 1 67 1 94 1 95 1 96 1 81 1 97 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 109 1 111 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+74 63 1 77 1 94 1 72 1 83 1 103 1 115 1 120 1 124 1 18 1 27 1 126 1 127 1
+75 63 1 77 1 89 1 67 1 92 1 94 1 96 1 81 1 97 1 83 1 98 1 99 1 103 1 51 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 115 1 116 1 117 1 118 1 119 1 120 1 124 1 18 1 27 1 126 1 127 1
+76 115 1 18 1 27 1 126 1 127 1
+77 103 1 115 1 120 1 18 1 126 1 127 1
+78 77 1 94 1 81 1 97 1 83 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+79 77 1 94 1 81 1 97 1 83 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 113 1 114 1 116 1 117 1 118 1 119 1 124 1 18 1 127 1
+80 77 1 94 1 81 1 97 1 83 1 104 1 105 1 107 1 109 1 110 1 111 1 114 1 116 1 117 1 118 1 119 1 18 1 127 1
+81 77 1 103 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+82 77 1 18 1 126 1 127 1
+83 77 1 103 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+84 77 1 103 1 86 1 104 1 105 1 106 1 107 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+85 77 1 67 1 83 1 99 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+86 77 1 91 1 95 1 101 1 103 1 106 1 108 1 120 1 124 1 18 1 126 1 127 1
+87 103 1 18 1 126 1 127 1
+88 87 1 89 1 67 1 68 1 69 1 92 1 94 1 96 1 81 1 97 1 83 1 98 1 99 1 103 1 51 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 116 1 117 1 118 1 119 1 121 1 124 1 18 1 27 1 127 1
+89 67 1 98 1 104 1 105 1 106 1 107 1 114 1 115 1 120 1 18 1 126 1 127 1
+90 91 1 95 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 114 1 115 1 120 1 18 1 126 1 127 1
+91 95 1 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+92 120 1 124 1 18 1 126 1 127 1
+93 94 1 81 1 97 1 72 1 83 1 103 1 105 1 109 1 110 1 111 1 119 1 18 1 127 1
+94 18 1 126 1 127 1
+95 115 1 120 1 124 1 18 1 126 1 127 1
+96 120 1 18 1 126 1 127 1
+97 115 1 120 1 18 1 126 1 127 1
+98 103 1 104 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+99 115 1 120 1 18 1 126 1 127 1
+100 115 1 120 1 124 1 18 1 126 1 127 1
+101 18 1 126 1 127 1
+102 101 1 103 1 86 1 104 1 105 1 106 1 107 1 108 1 114 1 115 1 120 1 124 1 18 1 126 1 127 1
+103 115 1 120 1 124 1 18 1 126 1 127 1
+104 18 1 127 1
+105 18 1 127 1
+106 115 1 18 1 127 1
+107 115 1 18 1 127 1
+108 115 1 120 1 18 1 127 1
+109 115 1 120 1 18 1 127 1
+110 115 1 18 1 127 1
+111 115 1 18 1 127 1
+112 115 1 18 1 127 1
+113 115 1 18 1 127 1
+114 18 1 127 1
+115 18 1 127 1
+116 115 1 18 1 127 1
+117 115 1 18 1 127 1
+118 115 1 18 1 127 1
+119 18 1 127 1
+120 18 1 127 1
+121 120 1 18 1 127 1
+122 120 1 18 1 127 1
+123 18 1 127 1
+124 18 1 127 1
+125 18 1 127 1
+126
+127
diff --git a/graphs/karateWeighted.graph b/graphs/karateWeighted.graph
new file mode 100644
index 0000000..72a6161
--- /dev/null
+++ b/graphs/karateWeighted.graph
@@ -0,0 +1,34 @@
+0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 10 1 11 1 12 1 13 1 17 1 19 1 21 1 31 1
+1 0 1 2 1 3 1 7 1 13 1 17 1 19 1 21 1 30 1
+2 0 1 1 1 3 1 7 1 8 1 9 1 13 1 27 1 28 1 32 1
+3 0 1 1 1 2 1 7 1 12 1 13 1
+4 0 1 6 1 10 1
+5 0 1 6 1 10 1 16 1
+6 0 1 4 1 5 1 16 1
+7 0 1 1 1 2 1 3 1
+8 0 1 2 1 30 1 32 1 33 1
+9 2 1 33 1
+10 0 1 4 1 5 1
+11 0 1
+12 0 1 3 1
+13 0 1 1 1 2 1 3 1 33 1
+14 32 1 33 1
+15 32 1 33 1
+16 5 1 6 1
+17 0 1 1 1
+18 32 1 33 1
+19 0 1 1 1 33 1
+20 32 1 33 1
+21 0 1 1 1
+22 32 1 33 1
+23 25 1 27 1 29 1 32 1 33 1
+24 25 1 27 1 31 1
+25 23 1 24 1 31 1
+26 29 1 33 1
+27 2 1 23 1 24 1 33 1
+28 2 1 31 1 33 1
+29 23 1 26 1 32 1 33 1
+30 1 1 8 1 32 1 33 1
+31 0 1 24 1 25 1 28 1 32 1 33 1
+32 2 1 8 1 14 1 15 1 18 1 20 1 22 1 23 1 29 1 30 1 31 1 33 1
+33 8 1 9 1 13 1 14 1 15 1 18 1 19 1 20 1 22 1 23 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1
diff --git a/graphs/polbooksWeighted.graph b/graphs/polbooksWeighted.graph
new file mode 100644
index 0000000..d3a32ed
--- /dev/null
+++ b/graphs/polbooksWeighted.graph
@@ -0,0 +1,105 @@
+0 1 1 2 1 3 1 4 1 5 1 6 1
+1 0 1 3 1 5 1 6 1
+2 0 1 4 1 5 1 7 1
+3 0 1 1 1 5 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1
+4 0 1 2 1 5 1 6 1 28 1 29 1 30 1 31 1
+5 0 1 1 1 2 1 3 1 4 1 6 1 7 1
+6 0 1 1 1 4 1 5 1 7 1 10 1 12 1 18 1 22 1 25 1 29 1
+7 2 1 5 1 6 1 14 1 30 1 58 1 71 1 85 1
+8 3 1 9 1 10 1 11 1 12 1 13 1 14 1 20 1 21 1 22 1 23 1 24 1 26 1 27 1 32 1 33 1 35 1 37 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1
+9 3 1 8 1 11 1 12 1 14 1 20 1 24 1 27 1 41 1 45 1 47 1 48 1 49 1 50 1 51 1 52 1
+10 3 1 6 1 8 1 11 1 12 1 15 1 16 1 19 1 21 1 33 1 35 1 37 1 38 1 39 1 55 1
+11 3 1 8 1 9 1 10 1 12 1 13 1 14 1 17 1 20 1 21 1 22 1 26 1 27 1 29 1 45 1 47 1 50 1 56 1
+12 3 1 6 1 8 1 9 1 10 1 11 1 13 1 14 1 15 1 17 1 18 1 23 1 24 1 32 1 33 1 36 1 38 1 39 1 40 1 41 1 44 1 46 1 47 1 54 1 55 1
+13 3 1 8 1 11 1 12 1 17 1 29 1 32 1 40 1 42 1 43 1 44 1 47 1 57 1
+14 3 1 8 1 9 1 11 1 12 1 7 1 25 1 26 1 58 1
+15 3 1 10 1 12 1 16 1 55 1
+16 3 1 10 1 15 1
+17 3 1 11 1 12 1 13 1 47 1
+18 3 1 6 1 12 1
+19 3 1 10 1 55 1 56 1 77 1
+20 3 1 8 1 9 1 11 1 24 1 40 1 48 1 49 1 53 1 57 1
+21 3 1 8 1 10 1 11 1 23 1
+22 3 1 6 1 8 1 11 1 25 1 40 1 52 1
+23 3 1 8 1 12 1 21 1 27 1 32 1 33 1 47 1 54 1
+24 3 1 8 1 9 1 12 1 20 1 26 1 40 1 47 1 53 1
+25 3 1 6 1 14 1 22 1 40 1
+26 3 1 8 1 11 1 14 1 24 1 40 1 45 1 47 1 53 1
+27 3 1 8 1 9 1 11 1 23 1 40 1 41 1 47 1 54 1
+28 4 1 66 1 72 1
+29 4 1 6 1 11 1 13 1
+30 4 1 7 1 31 1 58 1 66 1 67 1 70 1 73 1 74 1 75 1 76 1 77 1 79 1 80 1 82 1 83 1 84 1 86 1 93 1 99 1
+31 4 1 30 1 49 1 73 1 74 1 75 1 76 1 77 1 78 1 82 1 91 1
+32 8 1 12 1 13 1 23 1 33 1
+33 32 1 8 1 10 1 12 1 23 1 37 1 38 1 39 1 47 1
+34 35 1 36 1 37 1 38 1 39 1
+35 34 1 8 1 10 1 36 1 37 1 38 1 39 1 40 1 43 1 44 1
+36 34 1 35 1 12 1 41 1 47 1
+37 34 1 8 1 10 1 35 1 33 1 38 1 47 1
+38 34 1 10 1 35 1 12 1 37 1 33 1 39 1
+39 34 1 10 1 35 1 12 1 38 1 33 1 40 1 42 1
+40 8 1 35 1 12 1 13 1 20 1 22 1 39 1 24 1 25 1 26 1 27 1 41 1 42 1 44 1 45 1 47 1 53 1 54 1
+41 8 1 9 1 40 1 12 1 36 1 27 1 47 1 54 1
+42 8 1 40 1 13 1 39 1 43 1 47 1
+43 8 1 35 1 13 1 42 1 56 1
+44 8 1 40 1 35 1 12 1 13 1
+45 8 1 9 1 40 1 11 1 26 1 47 1
+46 8 1 12 1 47 1 102 1
+47 9 1 40 1 41 1 11 1 12 1 13 1 42 1 36 1 37 1 17 1 33 1 45 1 46 1 23 1 24 1 26 1 27 1 54 1
+48 9 1 20 1 49 1 57 1
+49 9 1 20 1 31 1 48 1 57 1 58 1 72 1 76 1
+50 9 1 11 1 58 1
+51 9 1 52 1 58 1 64 1 65 1 69 1
+52 9 1 22 1 51 1 58 1 64 1
+53 40 1 20 1 24 1 26 1 76 1
+54 40 1 41 1 12 1 47 1 23 1 27 1
+55 10 1 12 1 15 1 19 1
+56 11 1 19 1 43 1 57 1
+57 13 1 56 1 20 1 48 1 49 1
+58 14 1 7 1 30 1 49 1 50 1 51 1 52 1 64 1 65 1 68 1 69 1 77 1 85 1
+59 60 1 61 1 62 1 63 1 99 1
+60 59 1 62 1 63 1 84 1 86 1 99 1
+61 59 1 86 1 95 1 101 1
+62 59 1 60 1 63 1 84 1 99 1 100 1
+63 59 1 60 1 62 1 99 1
+64 58 1 51 1 52 1 65 1 66 1 67 1 68 1 69 1 70 1
+65 64 1 58 1 51 1 67 1 68 1 69 1 85 1
+66 64 1 28 1 30 1 67 1 70 1 72 1 73 1 74 1 76 1 80 1 84 1 85 1 86 1 88 1 89 1 90 1 93 1 96 1 97 1 99 1 100 1
+67 64 1 65 1 66 1 30 1 103 1 104 1
+68 64 1 58 1 65 1 71 1
+69 64 1 58 1 65 1 51 1 104 1
+70 64 1 66 1 30 1 71 1 72 1 75 1 90 1
+71 7 1 68 1 70 1 72 1 73 1 74 1 75 1 76 1 77 1 78 1 79 1 80 1 81 1 82 1 83 1
+72 71 1 28 1 66 1 49 1 70 1 73 1 74 1 75 1 76 1 78 1 79 1 80 1 82 1 84 1 85 1 86 1 87 1 88 1 89 1 90 1 91 1 92 1
+73 71 1 72 1 66 1 30 1 31 1 74 1 75 1 82 1 83 1 84 1 86 1 89 1 92 1 93 1 94 1 95 1 96 1 97 1 98 1 99 1 100 1
+74 71 1 72 1 73 1 66 1 30 1 31 1 75 1 78 1 79 1 82 1 84 1 87 1 88 1 91 1 98 1 99 1
+75 71 1 72 1 73 1 74 1 30 1 31 1 70 1 76 1 77 1 78 1 79 1 82 1 83 1 84 1 91 1 92 1
+76 71 1 72 1 75 1 66 1 30 1 31 1 49 1 53 1 77 1 82 1 83 1 84 1 86 1
+77 71 1 75 1 58 1 30 1 19 1 31 1 76 1
+78 71 1 72 1 74 1 75 1 31 1
+79 71 1 72 1 74 1 75 1 30 1 84 1 91 1 100 1
+80 71 1 72 1 66 1 30 1
+81 71 1 84 1 86 1 97 1
+82 71 1 72 1 73 1 74 1 75 1 30 1 31 1 76 1 84 1
+83 71 1 73 1 75 1 30 1 76 1 84 1 87 1 100 1
+84 72 1 74 1 75 1 66 1 73 1 60 1 30 1 62 1 76 1 79 1 81 1 82 1 83 1 86 1 87 1 88 1 89 1 94 1 96 1 97 1 99 1 100 1 101 1
+85 72 1 7 1 58 1 65 1 66 1
+86 72 1 73 1 66 1 84 1 60 1 30 1 61 1 76 1 81 1 89 1 93 1 97 1 100 1 101 1
+87 72 1 74 1 84 1 83 1 98 1
+88 72 1 74 1 66 1 84 1 89 1
+89 72 1 73 1 66 1 84 1 86 1 88 1
+90 72 1 66 1 70 1 91 1 99 1
+91 72 1 74 1 75 1 31 1 90 1 79 1 98 1 100 1
+92 72 1 73 1 75 1
+93 73 1 66 1 86 1 30 1 94 1 99 1 102 1
+94 73 1 84 1 93 1 95 1 96 1 101 1 102 1
+95 73 1 94 1 61 1 102 1
+96 73 1 66 1 84 1 94 1 97 1 100 1
+97 73 1 66 1 84 1 86 1 96 1 81 1
+98 73 1 74 1 87 1 91 1 100 1
+99 73 1 74 1 66 1 84 1 93 1 60 1 59 1 30 1 62 1 63 1 90 1 100 1
+100 73 1 66 1 84 1 86 1 96 1 98 1 99 1 62 1 79 1 91 1 83 1 101 1
+101 84 1 86 1 94 1 100 1 61 1
+102 93 1 94 1 95 1 46 1
+103 67 1 104 1
+104 67 1 69 1 103 1
diff --git a/src/NetworkFlow/Graph.cs b/src/NetworkFlow/Graph.cs
index a66732d..3b0d879 100644
--- a/src/NetworkFlow/Graph.cs
+++ b/src/NetworkFlow/Graph.cs
@@ -1,22 +1,36 @@
using System;
using System.Collections.Generic;
+using System.Linq;
namespace NetworkFlow
{
using Nodes = Dictionary<int, Node>;
using Path = List<int>;
- public class Graph
+ public class Graph : ICloneable
{
Dictionary<int, Node> _nodes;
+ public bool Undirected;
public Nodes Nodes { get => _nodes; set => _nodes = value; }
- public Graph()
+ public Graph(bool undirected = false)
{
+ Undirected = undirected;
Nodes = new Nodes();
}
+ public Graph(Graph o)
+ {
+ Undirected = o.Undirected;
+ Nodes = o.Nodes.ToDictionary(entry => entry.Key,
+ entry => (Node)entry.Value.Clone());
+ }
+
+ public Graph ShallowCopy() => (Graph)this.MemberwiseClone();
+ public object Clone() => new Graph(this);
+ // public object Clone() => new Graph(this._nodes, Undirected);
+
/// <summary>
/// Indexer; Retrieves the node with node.Id of <c>id</c>
/// </summary>
@@ -31,8 +45,14 @@ namespace NetworkFlow
/// </summary>
public void AddNode(int id)
{
- if (!this.Nodes.ContainsKey(id))
- this.Nodes.Add(id, new(id));
+ this.Nodes.TryAdd(id, new(id));
+ }
+
+ public void RemoveNode(int id)
+ {
+ if (this[id].Edges.Count > 1)
+ throw new Exception("Removing this node would leave orphaned edges");
+ this.Nodes.Remove(id);
}
/// <summary>
@@ -41,7 +61,20 @@ namespace NetworkFlow
public void AddEdge(int u, int v, double capacity)
{
AddNode(u);
- this[u].Edges.Add(v, capacity);
+ AddNode(v);
+
+ if (!Nodes[u].Edges.TryAdd(v, capacity))
+ Nodes[u].Edges[v] += capacity;
+
+ if (Undirected && !Nodes[v].Edges.TryAdd(u, capacity))
+ Nodes[v].Edges[u] += capacity;
+ }
+
+ public void RemoveEdge(int u, int v)
+ {
+ Nodes[u].Edges.Remove(v);
+ if (Undirected && Nodes[v].Edges.ContainsKey(u))
+ Nodes[v].Edges.Remove(u);
}
/// <summary>
@@ -50,6 +83,24 @@ namespace NetworkFlow
public void ChangeEdge(int u, int v, double capacity)
=> this[u].Edges[v] -= capacity;
+
+ public Graph ToUndirected()
+ {
+ Graph graph = new Graph(undirected: true);
+
+ foreach (var node in Nodes.Values)
+ foreach (var edge in node.Edges)
+ {
+ graph.AddNode(node.Id);
+
+ // if child node does not have an edge pointing back to parent
+ if (!this[edge.Key].Edges.ContainsKey(node.Id))
+ graph.AddEdge(edge.Key, node.Id, edge.Value);
+ }
+
+ return graph;
+ }
+
/// <summary>
/// Finds the maximum flow possible from the <c>source</c>
/// node to the <c>terminal</c> node.
@@ -129,9 +180,46 @@ namespace NetworkFlow
// return an empty path if a path to terminal node was not found
return new();
}
+
+
+ public double Contraction()
+ {
+
+ Random random = new Random();
+
+ // while nodes > 2
+ while (Nodes.Count > 2)
+ {
+ // pick a random edge
+ Node node = Nodes.Values.ElementAt(random.Next(0, Nodes.Count));
+
+ int u = node.Id;
+ int v = node.Edges.Keys.ElementAt(random.Next(0, node.Edges.Count));
+
+ // redirect edges of one node (v) to other node (u)
+ // this includes changing the edges that point to v for each node that v has in its edges
+ foreach (var edge in Nodes[v].Edges)
+ if (edge.Key != u)
+ {
+ AddEdge(u, edge.Key, edge.Value);
+ RemoveEdge(v, edge.Key);
+ }
+
+ // remove the edge from both sides (u and v)
+ RemoveEdge(u, v);
+
+ // delete node whose edges were redirected (v)
+ RemoveNode(v);
+ }
+
+ // return the sum of the remaining edges' weights
+ return Nodes.ElementAt(0).Value.Edges.ElementAt(0).Value;
+ }
+
+
}
- public struct Node
+ public struct Node : ICloneable
{
public int Id { get; set; }
public Dictionary<int, double> Edges { get; set; }
@@ -141,5 +229,14 @@ namespace NetworkFlow
Id = id;
Edges = new();
}
+
+ public Node(Node o)
+ {
+ Id = o.Id;
+ Edges = o.Edges.ToDictionary(entry => entry.Key,
+ entry => entry.Value);
+ }
+
+ public object Clone() => new Node(this);
}
} \ No newline at end of file
diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs
new file mode 100644
index 0000000..d0a49cb
--- /dev/null
+++ b/src/Program/Analysis.cs
@@ -0,0 +1,78 @@
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using NetworkFlow;
+
+namespace Program
+{
+ public struct Result
+ {
+ public double MinCut;
+ public TimeSpan Runtime;
+
+ public Result(double minCut, TimeSpan runtime)
+ {
+ MinCut = minCut;
+ Runtime = runtime;
+ }
+ }
+
+ class Analysis
+ {
+ Result ExactResult;
+ Dictionary<int, List<Result>> ApproxResults = new();
+ Func<int, int>[] IterFuncs = new Func<int, int>[] { n => 10, n => n, n => (int)(Math.Pow(n, 2) * Math.Log(n, Math.E)) };
+ Graph _graph;
+
+ public Analysis(Graph graph)
+ {
+ _graph = graph;
+ }
+
+ public void Analize()
+ {
+ Stopwatch stopwatch = new();
+ double result = CalculateExact((Graph)_graph.Clone());
+ ExactResult = new(result, stopwatch.Elapsed);
+
+ foreach (var iterFunc in IterFuncs)
+ {
+ int iterations = iterFunc(_graph.Nodes.Count);
+ ApproxResults.Add(iterations, new());
+
+ for (int i = 0; i < 5; i++)
+ {
+ stopwatch.Restart();
+ result = CalculateApprox(_graph, iterations);
+ ApproxResults[iterations].Add(new(result, stopwatch.Elapsed));
+ }
+ }
+ }
+
+ double CalculateExact(Graph graph) => graph.MaxFlow(0, graph.Nodes.Count - 1);
+
+ double CalculateApprox(Graph graph, int iterations)
+ {
+ double result = double.MaxValue;
+
+ for (int j = 0; j < iterations; j++){
+ var graphClone = (Graph)_graph.Clone();
+ result = Math.Min(result, graphClone.Contraction());
+ }
+
+ return result;
+ }
+
+ public override string ToString()
+ {
+ string outString = $"Exact Value: {ExactResult.MinCut}, Exact Runtime: {ExactResult.Runtime}\n";
+
+ foreach (var results in ApproxResults)
+ foreach (var result in results.Value)
+ outString += $"Approx Value: {result.MinCut}, Approx Runtime: {result.Runtime}";
+
+ return outString;
+ }
+ }
+} \ No newline at end of file
diff --git a/src/Program/Program.cs b/src/Program/Program.cs
index 90e80bd..6aab0a3 100644
--- a/src/Program/Program.cs
+++ b/src/Program/Program.cs
@@ -1,104 +1,40 @@
using System;
using System.Collections.Generic;
+using System.Diagnostics;
using System.IO;
using System.Linq;
using Graph = NetworkFlow.Graph;
namespace Program
{
+
class Program
{
static void Main(string[] args)
{
- // attempt to read file from command line args, otherwise asks for a file
- FileInfo inputFile = (args.Length > 0) ? new FileInfo(args[0]) : ReadFileName();
-
- // attempt to get source and terminal nodes from command line args
- string source = (args.Length >= 2) ? args[1] : default(string);
- string terminal = (args.Length >= 3) ? args[2] : default(string);
+ List<Analysis> Analysii = new();
+ DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs");
-
- if (!inputFile.Exists)
+ if (!graphDir.Exists)
{
- Console.WriteLine($"Failed to open {inputFile}: File does not exist.");
- return;
+ Console.WriteLine($"Failed to open {graphDir}: Graph does not exist.");
+ System.Environment.Exit(1);
}
-
- // read file into graph
- Graph graph = ReadFile(inputFile.FullName);
-
- // verify command line source and terminal values or gets new values from the user
- (int s, int t) = ReadSourceAndTerminal(graph, source, terminal);
-
- // call maxFlow
- double maxFlow = graph.MaxFlow(s, t);
- Console.WriteLine($"The max flow is {maxFlow}");
- }
-
- public static (int s, int t) ReadSourceAndTerminal(Graph graph, string source, string terminal)
- {
- int s, t;
- // retries until it succeeds
- while (true)
+
+ foreach (var file in graphDir.EnumerateFiles())
{
- // try to parse supplied values
- bool isSetSource = int.TryParse(source, out s);
- bool isSetTerminal = int.TryParse(terminal, out t);
-
- // validates the values are ints and the graph contains the corresponding node
- if (!(isSetSource && graph.Nodes.ContainsKey(s)))
- {
- if (source != default(string))
- Console.WriteLine($"Invalid Source Node: {source}");
- Console.Write($"Enter the Source Node: ");
- // asks for a new value
- source = Console.ReadLine();
- }
- // validates the values are ints and the graph contains the corresponding node
- if (!(isSetTerminal && graph.Nodes.ContainsKey(t)))
- {
- if (terminal != default(string))
- Console.WriteLine($"Invalid Terminal Node: {terminal}");
- Console.Write($"Enter the Terminal Node: ");
- // asks for a new value
- terminal = Console.ReadLine();
- }
- // if everything is correct then we can return
- if (isSetSource && isSetTerminal && graph.Nodes.ContainsKey(s) && graph.Nodes.ContainsKey(t))
- break;
- }
-
-
- return (s, t);
- }
-
- public static FileInfo ReadFileName()
- {
- string filePath;
-
- // continues to ask for a valid filepath until obtained
- while (true)
- {
- Console.Write("Enter a path to a points file: ");
- filePath = Console.ReadLine();
-
- if (String.IsNullOrEmpty(filePath))
- Console.WriteLine("File path cannot be empty!");
- else if (!System.IO.File.Exists(filePath))
- Console.WriteLine($"{filePath} does not exist.");
- else
- break;
+ Graph graph = ReadFile(file.FullName);
+ Analysis analysis = new(graph);
+ analysis.Analize();
+ Analysii.Add(analysis);
+ Console.WriteLine(analysis.ToString());
}
-
- FileInfo file = new FileInfo(filePath);
-
- return file;
}
public static Graph ReadFile(string file)
{
// create default Graph object
- Graph graph = new Graph();
+ Graph graph = new Graph(undirected: true);
// Read in graph file
foreach (string line in File.ReadLines(file))
@@ -122,5 +58,6 @@ namespace Program
// return object when done
return graph;
}
+
}
}