From 3af85a294bbecd92e2a412bf1904dc4f833c3082 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Thu, 2 Dec 2021 01:26:58 -0600 Subject: Working state but it takes 6 lifetimes to run Co-authored-by: Neil Kollack --- .vscode/launch.json | 26 +--- graphs/celegansneural.graph | 297 ++++++++++++++++++++++++++++++++++++++++++ graphs/florida-bay.graph | 128 ++++++++++++++++++ graphs/karateWeighted.graph | 34 +++++ graphs/polbooksWeighted.graph | 105 +++++++++++++++ src/NetworkFlow/Graph.cs | 109 +++++++++++++++- src/Program/Analysis.cs | 78 +++++++++++ src/Program/Program.cs | 95 +++----------- 8 files changed, 763 insertions(+), 109 deletions(-) create mode 100644 graphs/celegansneural.graph create mode 100644 graphs/florida-bay.graph create mode 100644 graphs/karateWeighted.graph create mode 100644 graphs/polbooksWeighted.graph create mode 100644 src/Program/Analysis.cs 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; using Path = List; - public class Graph + public class Graph : ICloneable { Dictionary _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); + /// /// Indexer; Retrieves the node with node.Id of id /// @@ -31,8 +45,14 @@ namespace NetworkFlow /// 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); } /// @@ -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); } /// @@ -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; + } + /// /// Finds the maximum flow possible from the source /// node to the terminal 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 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> ApproxResults = new(); + Func[] IterFuncs = new Func[] { 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 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; } + } } -- cgit v1.2.3-70-g09d2 From 5035be4d28a238bfea8564a1f20eebe1a9193df0 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Thu, 2 Dec 2021 16:47:26 -0600 Subject: fixed the issues to graph creation Co-authored-by: Neil Kollack --- .gitignore | 2 ++ src/NetworkFlow/Graph.cs | 22 ++------------ src/Program/Analysis.cs | 76 +++++++++++++++++++++++++++++++++++++----------- src/Program/Program.cs | 21 +++++++------ 4 files changed, 75 insertions(+), 46 deletions(-) diff --git a/.gitignore b/.gitignore index 01b4c2f..ed38931 100644 --- a/.gitignore +++ b/.gitignore @@ -414,3 +414,5 @@ obj/ !.vscode/*.code-snippets # End of https://www.toptal.com/developers/gitignore/api/csharp,dotnetcore,visualstudiocode + +output.csv \ No newline at end of file diff --git a/src/NetworkFlow/Graph.cs b/src/NetworkFlow/Graph.cs index 3b0d879..54c2b29 100644 --- a/src/NetworkFlow/Graph.cs +++ b/src/NetworkFlow/Graph.cs @@ -51,7 +51,7 @@ namespace NetworkFlow public void RemoveNode(int id) { if (this[id].Edges.Count > 1) - throw new Exception("Removing this node would leave orphaned edges"); + throw new Exception("Removing this node would leave orphaned batma... edges, I mean edges."); this.Nodes.Remove(id); } @@ -83,24 +83,6 @@ 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; - } - /// /// Finds the maximum flow possible from the source /// node to the terminal node. @@ -132,7 +114,7 @@ namespace NetworkFlow maxFlow += capacity; // output the current progress - Console.WriteLine($"The augmenting path is {String.Join(",", path)} capacity = {capacity}"); + // Console.WriteLine($"The augmenting path is {String.Join(",", path)} capacity = {capacity}"); } // output when completed diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs index d0a49cb..d6c6082 100644 --- a/src/Program/Analysis.cs +++ b/src/Program/Analysis.cs @@ -2,20 +2,32 @@ using System; using System.Collections.Generic; using System.Diagnostics; +using System.Linq; +using System.Threading.Tasks; using NetworkFlow; namespace Program { public struct Result { + string Filename; + string ResultType; + int Iterations; public double MinCut; public TimeSpan Runtime; - public Result(double minCut, TimeSpan runtime) + public Result(string filename, String type, int interations, double minCut, TimeSpan runtime) { + Filename = filename; + ResultType = type; + Iterations = interations; MinCut = minCut; Runtime = runtime; } + + public string ToCSV() => $"{Filename},{ResultType},{Iterations},{MinCut},{Runtime}"; + public override string ToString() => $"{ResultType} Value: {MinCut}, Runtime: {Runtime} (i: {Iterations})"; + } class Analysis @@ -24,17 +36,22 @@ namespace Program Dictionary> ApproxResults = new(); Func[] IterFuncs = new Func[] { n => 10, n => n, n => (int)(Math.Pow(n, 2) * Math.Log(n, Math.E)) }; Graph _graph; + public string Filename; - public Analysis(Graph graph) + public Analysis(Graph graph, string filename) { _graph = graph; + Filename = filename; } public void Analize() { + Console.WriteLine($"\nFilename: {Filename}"); Stopwatch stopwatch = new(); - double result = CalculateExact((Graph)_graph.Clone()); - ExactResult = new(result, stopwatch.Elapsed); + double result = CalculateExact(); + ExactResult = new(Filename, "Exact", 1, result, stopwatch.Elapsed); + + Console.WriteLine(ExactResult); foreach (var iterFunc in IterFuncs) { @@ -44,34 +61,59 @@ namespace Program for (int i = 0; i < 5; i++) { stopwatch.Restart(); - result = CalculateApprox(_graph, iterations); - ApproxResults[iterations].Add(new(result, stopwatch.Elapsed)); + result = CalculateApprox(iterations); + Result approxResult = new(Filename, "Apprx", iterations, result, stopwatch.Elapsed); + ApproxResults[iterations].Add(approxResult); + Console.WriteLine(approxResult); } } } - double CalculateExact(Graph graph) => graph.MaxFlow(0, graph.Nodes.Count - 1); + double CalculateExact() + { + double result = double.MaxValue; + // loop t for all nodes + foreach (var node in _graph.Nodes.Keys.ToList().Skip(1)) + { + var graphClone = (Graph)_graph.Clone(); + // take min of current result and new result + double currentResult = graphClone.MaxFlow(0, node); + if (currentResult != 0) + result = Math.Min(result, currentResult); + } + Console.WriteLine(); + return result; + } - double CalculateApprox(Graph graph, int iterations) + double CalculateApprox(int iterations) { double result = double.MaxValue; - for (int j = 0; j < iterations; j++){ + #region Parallel_Loop + Parallel.For(0, iterations, j => + { var graphClone = (Graph)_graph.Clone(); - result = Math.Min(result, graphClone.Contraction()); - } + double currentResult = graphClone.Contraction(); + if (currentResult != 0) + result = Math.Min(result, currentResult); + }); + #endregion return result; } - public override string ToString() + public List ToCSV() { - 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}"; + List lines = new(); + lines.Add(ExactResult.ToCSV()); + ApproxResults.Values.ToList().ForEach(approx => approx.ForEach(r => lines.Add(r.ToCSV()))); + return lines; + } + public override string ToString() + { + string outString = ExactResult.ToString(); + ApproxResults.Values.ToList().ForEach(r => outString += String.Join("", r)); return outString; } } diff --git a/src/Program/Program.cs b/src/Program/Program.cs index 6aab0a3..c27369a 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -1,6 +1,5 @@ using System; using System.Collections.Generic; -using System.Diagnostics; using System.IO; using System.Linq; using Graph = NetworkFlow.Graph; @@ -15,29 +14,32 @@ namespace Program List Analysii = new(); DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs"); + FileInfo outfile = new("../../output.csv"); + File.WriteAllText(outfile.FullName, $"Filename,ResultType,Iterations,MinCut,Runtime\n"); + if (!graphDir.Exists) { Console.WriteLine($"Failed to open {graphDir}: Graph does not exist."); System.Environment.Exit(1); } - + foreach (var file in graphDir.EnumerateFiles()) { - Graph graph = ReadFile(file.FullName); - Analysis analysis = new(graph); + Graph graph = ReadFile(file); + Analysis analysis = new(graph, file.Name); analysis.Analize(); Analysii.Add(analysis); - Console.WriteLine(analysis.ToString()); + File.AppendAllLines(outfile.FullName, analysis.ToCSV()); } } - public static Graph ReadFile(string file) + public static Graph ReadFile(FileInfo file) { // create default Graph object Graph graph = new Graph(undirected: true); // Read in graph file - foreach (string line in File.ReadLines(file)) + foreach (string line in File.ReadLines(file.FullName)) { // each file line is a Node with optional edges // line format: @@ -52,12 +54,13 @@ namespace Program // AddEdge(int u, int v, double weight) int.TryParse(vals[i], out v); double.TryParse(vals[i + 1], out weight); - graph.AddEdge(u, v, weight); + if (!graph[u].Edges.ContainsKey(v)) + graph.AddEdge(u, v, weight); } } // return object when done return graph; } - + } } -- cgit v1.2.3-70-g09d2 From c28168978b2f64162171e8a51d6330ae48784234 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sun, 5 Dec 2021 20:02:33 -0600 Subject: fixed csv output format and bug in stopwatch Co-authored-by: Neil Kollack --- .gitignore | 443 +++++++++++++++++++++++++++++++++++++++++++- README.md | 2 +- output/constant_cuts.csv | 7 + output/constant_times.csv | 7 + output/linear_cuts.csv | 7 + output/linear_times.csv | 7 + output/polynomial_cuts.csv | 7 + output/polynomial_times.csv | 7 + src/Program/Analysis.cs | 81 +++----- src/Program/Program.cs | 47 ++++- 10 files changed, 546 insertions(+), 69 deletions(-) create mode 100644 output/constant_cuts.csv create mode 100644 output/constant_times.csv create mode 100644 output/linear_cuts.csv create mode 100644 output/linear_times.csv create mode 100644 output/polynomial_cuts.csv create mode 100644 output/polynomial_times.csv diff --git a/.gitignore b/.gitignore index ed38931..35861e5 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,6 @@ -# Created by https://www.toptal.com/developers/gitignore/api/csharp,dotnetcore,visualstudiocode -# Edit at https://www.toptal.com/developers/gitignore?templates=csharp,dotnetcore,visualstudiocode +# Created by https://www.toptal.com/developers/gitignore/api/csharp,dotnetcore,visualstudiocode,tex,latex +# Edit at https://www.toptal.com/developers/gitignore?templates=csharp,dotnetcore,visualstudiocode,tex,latex ### Csharp ### ## Ignore Visual Studio temporary files, build results, and @@ -401,6 +401,441 @@ obj/ /node_modules /wwwroot/node_modules +### LaTeX ### +## Core latex/pdflatex auxiliary files: +*.aux +*.lof +*.lot +*.fls +*.out +*.toc +*.fmt +*.fot +*.cb +*.cb2 +.*.lb + +## Intermediate documents: +*.dvi +*.xdv +*-converted-to.* +# these rules might exclude image files for figures etc. +# *.ps +# *.eps +# *.pdf + +## Generated if empty string is given at "Please type another file name for output:" +.pdf + +## Bibliography auxiliary files (bibtex/biblatex/biber): +*.bbl +*.bcf +*.blg +*-blx.aux +*-blx.bib +*.run.xml + +## Build tool auxiliary files: +*.fdb_latexmk +*.synctex +*.synctex(busy) +*.synctex.gz +*.synctex.gz(busy) +*.pdfsync + +## Build tool directories for auxiliary files +# latexrun +latex.out/ + +## Auxiliary and intermediate files from other packages: +# algorithms +*.alg +*.loa + +# achemso +acs-*.bib + +# amsthm +*.thm + +# beamer +*.nav +*.pre +*.snm +*.vrb + +# changes +*.soc + +# comment +*.cut + +# cprotect +*.cpt + +# elsarticle (documentclass of Elsevier journals) +*.spl + +# endnotes +*.ent + +# fixme +*.lox + +# feynmf/feynmp +*.mf +*.mp +*.t[1-9] +*.t[1-9][0-9] +*.tfm + +#(r)(e)ledmac/(r)(e)ledpar +*.end +*.?end +*.[1-9] +*.[1-9][0-9] +*.[1-9][0-9][0-9] +*.[1-9]R +*.[1-9][0-9]R +*.[1-9][0-9][0-9]R +*.eledsec[1-9] +*.eledsec[1-9]R +*.eledsec[1-9][0-9] +*.eledsec[1-9][0-9]R +*.eledsec[1-9][0-9][0-9] +*.eledsec[1-9][0-9][0-9]R + +# glossaries +*.acn +*.acr +*.glg +*.glo +*.gls +*.glsdefs +*.lzo +*.lzs + +# uncomment this for glossaries-extra (will ignore makeindex's style files!) +# *.ist + +# gnuplottex +*-gnuplottex-* + +# gregoriotex +*.gaux +*.glog +*.gtex + +# htlatex +*.4ct +*.4tc +*.idv +*.lg +*.trc +*.xref + +# hyperref +*.brf + +# knitr +*-concordance.tex +# TODO Uncomment the next line if you use knitr and want to ignore its generated tikz files +# *.tikz +*-tikzDictionary + +# listings +*.lol + +# luatexja-ruby +*.ltjruby + +# makeidx +*.idx +*.ilg +*.ind + +# minitoc +*.maf +*.mlf +*.mlt +*.mtc[0-9]* +*.slf[0-9]* +*.slt[0-9]* +*.stc[0-9]* + +# minted +_minted* +*.pyg + +# morewrites +*.mw + +# newpax +*.newpax + +# nomencl +*.nlg +*.nlo +*.nls + +# pax +*.pax + +# pdfpcnotes +*.pdfpc + +# sagetex +*.sagetex.sage +*.sagetex.py +*.sagetex.scmd + +# scrwfile +*.wrt + +# sympy +*.sout +*.sympy +sympy-plots-for-*.tex/ + +# pdfcomment +*.upa +*.upb + +# pythontex +*.pytxcode +pythontex-files-*/ + +# tcolorbox +*.listing + +# thmtools +*.loe + +# TikZ & PGF +*.dpth +*.md5 +*.auxlock + +# todonotes +*.tdo + +# vhistory +*.hst +*.ver + +# easy-todo +*.lod + +# xcolor +*.xcp + +# xmpincl +*.xmpi + +# xindy +*.xdy + +# xypic precompiled matrices and outlines +*.xyc +*.xyd + +# endfloat +*.ttt +*.fff + +# Latexian +TSWLatexianTemp* + +## Editors: +# WinEdt +*.bak +*.sav + +# Texpad +.texpadtmp + +# LyX +*.lyx~ + +# Kile +*.backup + +# gummi +.*.swp + +# KBibTeX +*~[0-9]* + +# TeXnicCenter +*.tps + +# auto folder when using emacs and auctex +./auto/* +*.el + +# expex forward references with \gathertags +*-tags.tex + +# standalone packages +*.sta + +# Makeindex log files +*.lpz + +# xwatermark package +*.xwm + +# REVTeX puts footnotes in the bibliography by default, unless the nofootinbib +# option is specified. Footnotes are the stored in a file with suffix Notes.bib. +# Uncomment the next line to have this generated file ignored. +#*Notes.bib + +### LaTeX Patch ### +# LIPIcs / OASIcs +*.vtc + +# glossaries +*.glstex + +### TeX ### + +# these rules might exclude image files for figures etc. +# *.ps +# *.eps +# *.pdf + + + + +# latexrun + +# algorithms + +# achemso + +# amsthm + +# beamer + +# changes + +# comment + +# cprotect + +# elsarticle (documentclass of Elsevier journals) + +# endnotes + +# fixme + +# feynmf/feynmp + + +# glossaries + +# uncomment this for glossaries-extra (will ignore makeindex's style files!) +# *.ist + +# gnuplottex + +# gregoriotex + +# htlatex + +# hyperref + +# knitr +# TODO Uncomment the next line if you use knitr and want to ignore its generated tikz files +# *.tikz + +# listings + +# luatexja-ruby + +# makeidx + +# minitoc + +# minted + +# morewrites + +# newpax + +# nomencl + +# pax + +# pdfpcnotes + +# sagetex + +# scrwfile + +# sympy + +# pdfcomment + +# pythontex + +# tcolorbox + +# thmtools + +# TikZ & PGF + +# todonotes + +# vhistory + +# easy-todo + +# xcolor + +# xmpincl + +# xindy + +# xypic precompiled matrices and outlines + +# endfloat + +# Latexian + +# WinEdt + +# Texpad + +# LyX + +# Kile + +# gummi + +# KBibTeX + +# TeXnicCenter + +# auto folder when using emacs and auctex + +# expex forward references with \gathertags + +# standalone packages + +# Makeindex log files + +# xwatermark package + +# REVTeX puts footnotes in the bibliography by default, unless the nofootinbib +# option is specified. Footnotes are the stored in a file with suffix Notes.bib. +# Uncomment the next line to have this generated file ignored. + +### TeX Patch ### +# LIPIcs / OASIcs + +# glossaries + ### VisualStudioCode ### # Local History for Visual Studio Code @@ -413,6 +848,4 @@ obj/ # Support for Project snippet scope !.vscode/*.code-snippets -# End of https://www.toptal.com/developers/gitignore/api/csharp,dotnetcore,visualstudiocode - -output.csv \ No newline at end of file +# End of https://www.toptal.com/developers/gitignore/api/csharp,dotnetcore,visualstudiocode,tex,latex diff --git a/README.md b/README.md index a0abc2b..048ea7a 100644 --- a/README.md +++ b/README.md @@ -1,5 +1,5 @@ # NetworkFlow -CS 456: Project4 - Network Flow +CS 456: Project5 - Global Min Cut Professor: Dr. John Matta diff --git a/output/constant_cuts.csv b/output/constant_cuts.csv new file mode 100644 index 0000000..9fbdcbd --- /dev/null +++ b/output/constant_cuts.csv @@ -0,0 +1,7 @@ +Graph,Exact Cuts,Contract1 Cuts,Contract2 Cuts,Contract3 Cuts,Contract4 Cuts,Contract5 Cuts +celegansneural.graph,1,1,9,4,1,12 +Project4Graph2.txt,10,10,10,10,11,11 +Project4Graph1.txt,5,5,5,5,5,11 +polbooksWeighted.graph,2,5,3,4,7,4 +karateWeighted.graph,1,1,2,2,2,2 +florida-bay.graph,2,16,204,13,288,12 diff --git a/output/constant_times.csv b/output/constant_times.csv new file mode 100644 index 0000000..53ff7d6 --- /dev/null +++ b/output/constant_times.csv @@ -0,0 +1,7 @@ +Graph,Exact (ms),Contract1 (ms),Contract2 (ms),Contract3 (ms),Contract4 (ms),Contract5 (ms) +celegansneural.graph,1750.2084,81.0912,18.408,18.5579,17.5412,17.3655 +Project4Graph2.txt,0.0775,0.5155,0.4025,0.4386,0.1804,0.4783 +Project4Graph1.txt,0.0502,0.4511,0.4779,0.3802,0.4031,0.4454 +polbooksWeighted.graph,102.1129,44.3344,21.2961,21.3725,22.2797,21.3039 +karateWeighted.graph,3.1357,20.9576,1.2417,0.6967,0.7071,20.8144 +florida-bay.graph,513.2117,25.1122,49.1835,24.0553,24.487,24.4457 diff --git a/output/linear_cuts.csv b/output/linear_cuts.csv new file mode 100644 index 0000000..50780b3 --- /dev/null +++ b/output/linear_cuts.csv @@ -0,0 +1,7 @@ +Graph,Exact Cuts,Contract1 Cuts,Contract2 Cuts,Contract3 Cuts,Contract4 Cuts,Contract5 Cuts +celegansneural.graph,1,1,1,1,1,1 +Project4Graph2.txt,10,11,11,10,11,17 +Project4Graph1.txt,5,13,11,5,5,5 +polbooksWeighted.graph,2,4,2,3,3,2 +karateWeighted.graph,1,1,1,1,1,1 +florida-bay.graph,2,2,13,2,2,13 diff --git a/output/linear_times.csv b/output/linear_times.csv new file mode 100644 index 0000000..2416aa9 --- /dev/null +++ b/output/linear_times.csv @@ -0,0 +1,7 @@ +Graph,Exact (ms),Contract1 (ms),Contract2 (ms),Contract3 (ms),Contract4 (ms),Contract5 (ms) +celegansneural.graph,1750.2084,557.0621,503.0906,399.7002,413.8505,406.6934 +Project4Graph2.txt,0.0775,0.3823,0.4282,0.4109,0.1151,0.4346 +Project4Graph1.txt,0.0502,0.3987,0.369,0.341,0.3666,0.3754 +polbooksWeighted.graph,102.1129,73.3894,54.0188,34.3985,53.5005,32.6633 +karateWeighted.graph,3.1357,21.8032,21.3198,43.1202,21.163,0.8361 +florida-bay.graph,513.2117,87.747,88.7737,84.243,127.649,88.0672 diff --git a/output/polynomial_cuts.csv b/output/polynomial_cuts.csv new file mode 100644 index 0000000..b7f40fa --- /dev/null +++ b/output/polynomial_cuts.csv @@ -0,0 +1,7 @@ +Graph,Exact Cuts,Contract1 Cuts,Contract2 Cuts,Contract3 Cuts,Contract4 Cuts,Contract5 Cuts +celegansneural.graph,1,1,1,1,1,1 +Project4Graph2.txt,10,10,10,10,10,10 +Project4Graph1.txt,5,5,5,5,5,5 +polbooksWeighted.graph,2,2,2,2,2,2 +karateWeighted.graph,1,1,1,1,1,1 +florida-bay.graph,2,2,2,2,2,2 diff --git a/output/polynomial_times.csv b/output/polynomial_times.csv new file mode 100644 index 0000000..3d70aa4 --- /dev/null +++ b/output/polynomial_times.csv @@ -0,0 +1,7 @@ +Graph,Exact (ms),Contract1 (ms),Contract2 (ms),Contract3 (ms),Contract4 (ms),Contract5 (ms) +celegansneural.graph,1750.2084,774759.5932,703439.1859,687873.8018,716489.0127,689531.893 +Project4Graph2.txt,0.0775,0.9838,1.9534,0.7784,0.7699,0.3623 +Project4Graph1.txt,0.0502,0.6279,0.2741,0.6162,0.3017,0.5493 +polbooksWeighted.graph,102.1129,6181.3018,6342.346,6557.8713,6485.526,6532.7274 +karateWeighted.graph,3.1357,134.6114,110.5004,129.3092,110.1674,130.8909 +florida-bay.graph,513.2117,41388.8641,42039.0769,43972.4187,43956.6237,43784.628 diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs index d6c6082..f817200 100644 --- a/src/Program/Analysis.cs +++ b/src/Program/Analysis.cs @@ -10,83 +10,67 @@ namespace Program { public struct Result { - string Filename; - string ResultType; - int Iterations; public double MinCut; public TimeSpan Runtime; - public Result(string filename, String type, int interations, double minCut, TimeSpan runtime) + public Result(double minCut, TimeSpan runtime) { - Filename = filename; - ResultType = type; - Iterations = interations; MinCut = minCut; Runtime = runtime; } - public string ToCSV() => $"{Filename},{ResultType},{Iterations},{MinCut},{Runtime}"; - public override string ToString() => $"{ResultType} Value: {MinCut}, Runtime: {Runtime} (i: {Iterations})"; - + public override string ToString() => $"{MinCut} @ {Runtime.TotalMilliseconds}"; } class Analysis { - Result ExactResult; - Dictionary> ApproxResults = new(); - Func[] IterFuncs = new Func[] { n => 10, n => n, n => (int)(Math.Pow(n, 2) * Math.Log(n, Math.E)) }; Graph _graph; - public string Filename; + Result _exact = new(); + Result Exact { get => _exact.Equals(default(Result)) ? (_exact = CalculateExact()) : _exact; } + int Repetitions; - public Analysis(Graph graph, string filename) + public Analysis(Graph graph, int repetitions) { _graph = graph; - Filename = filename; + Repetitions = repetitions; } - public void Analize() + public List Analize(int iterations) { - Console.WriteLine($"\nFilename: {Filename}"); - Stopwatch stopwatch = new(); - double result = CalculateExact(); - ExactResult = new(Filename, "Exact", 1, result, stopwatch.Elapsed); - - Console.WriteLine(ExactResult); - - foreach (var iterFunc in IterFuncs) + List results = new(); + results.Add(Exact); + Console.WriteLine($"Exact {Exact}"); + for (int i = 0; i < Repetitions; i++) { - int iterations = iterFunc(_graph.Nodes.Count); - ApproxResults.Add(iterations, new()); - - for (int i = 0; i < 5; i++) - { - stopwatch.Restart(); - result = CalculateApprox(iterations); - Result approxResult = new(Filename, "Apprx", iterations, result, stopwatch.Elapsed); - ApproxResults[iterations].Add(approxResult); - Console.WriteLine(approxResult); - } + results.Add(CalculateApprox(iterations)); + Console.WriteLine($"Contract_{i + 1} {results.Last()}"); } + + return results; } - double CalculateExact() + Result CalculateExact() { + Stopwatch stopwatch = Stopwatch.StartNew(); double result = double.MaxValue; + // loop t for all nodes foreach (var node in _graph.Nodes.Keys.ToList().Skip(1)) { var graphClone = (Graph)_graph.Clone(); + // take min of current result and new result double currentResult = graphClone.MaxFlow(0, node); if (currentResult != 0) result = Math.Min(result, currentResult); } - Console.WriteLine(); - return result; + + return new(result, stopwatch.Elapsed); } - double CalculateApprox(int iterations) + Result CalculateApprox(int iterations) { + Stopwatch stopwatch = Stopwatch.StartNew(); double result = double.MaxValue; #region Parallel_Loop @@ -99,22 +83,7 @@ namespace Program }); #endregion - return result; - } - - public List ToCSV() - { - List lines = new(); - lines.Add(ExactResult.ToCSV()); - ApproxResults.Values.ToList().ForEach(approx => approx.ForEach(r => lines.Add(r.ToCSV()))); - return lines; - } - - public override string ToString() - { - string outString = ExactResult.ToString(); - ApproxResults.Values.ToList().ForEach(r => outString += String.Join("", r)); - return outString; + return new(result, stopwatch.Elapsed); } } } \ No newline at end of file diff --git a/src/Program/Program.cs b/src/Program/Program.cs index c27369a..05a91dc 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -13,9 +13,8 @@ namespace Program { List Analysii = new(); DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs"); - - FileInfo outfile = new("../../output.csv"); - File.WriteAllText(outfile.FullName, $"Filename,ResultType,Iterations,MinCut,Runtime\n"); + DirectoryInfo outDir = new("../../output"); + outDir.Create(); if (!graphDir.Exists) { @@ -23,14 +22,48 @@ namespace Program System.Environment.Exit(1); } + string cuts_header = $"Graph,Exact Cuts,Contract1 Cuts,Contract2 Cuts,Contract3 Cuts,Contract4 Cuts,Contract5 Cuts"; + string times_header = $"Graph,Exact (ms),Contract1 (ms),Contract2 (ms),Contract3 (ms),Contract4 (ms),Contract5 (ms)"; + List constant_cuts = new() { cuts_header }; + List constant_times = new() { times_header }; + List linear_cuts = new() { cuts_header }; + List linear_times = new() { times_header }; + List polynomial_cuts = new() { cuts_header }; + List polynomial_times = new() { times_header }; + foreach (var file in graphDir.EnumerateFiles()) { Graph graph = ReadFile(file); - Analysis analysis = new(graph, file.Name); - analysis.Analize(); - Analysii.Add(analysis); - File.AppendAllLines(outfile.FullName, analysis.ToCSV()); + Analysis analysis = new(graph, 5); + List results; + int iter; + Console.WriteLine(file.Name); + + iter = 10; + Console.WriteLine($"\nconstant ({iter}):"); + results = analysis.Analize(iter); + constant_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + constant_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); + + iter = graph.Nodes.Count; + Console.WriteLine($"\nlinier ({iter}):"); + results = analysis.Analize(iter); + linear_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + linear_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); + + iter = (int)(Math.Pow(graph.Nodes.Count, 2) * Math.Log(graph.Nodes.Count, Math.E)); + Console.WriteLine($"\npolynomial ({iter}):"); + results = analysis.Analize(iter); + polynomial_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + polynomial_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); } + + File.WriteAllLines($"{outDir.FullName}/constant_cuts.csv", constant_cuts); + File.WriteAllLines($"{outDir.FullName}/constant_times.csv", constant_times); + File.WriteAllLines($"{outDir.FullName}/linear_cuts.csv", linear_cuts); + File.WriteAllLines($"{outDir.FullName}/linear_times.csv", linear_times); + File.WriteAllLines($"{outDir.FullName}/polynomial_cuts.csv", polynomial_cuts); + File.WriteAllLines($"{outDir.FullName}/polynomial_times.csv", polynomial_times); } public static Graph ReadFile(FileInfo file) -- cgit v1.2.3-70-g09d2 From 5cb64e38c38655ae322643ce379738bca8fa97d1 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sun, 5 Dec 2021 20:03:00 -0600 Subject: wrote report Co-authored-by: Neil Kollack --- docs/report/report.pdf | Bin 0 -> 112770 bytes docs/report/report.tex | 65 ++++++++++++++++++++++++++++++++++++++++ docs/report/styles/header.sty | 35 ++++++++++++++++++++++ docs/report/styles/packages.sty | 12 ++++++++ docs/report/styles/section.sty | 35 ++++++++++++++++++++++ docs/report/styles/title.sty | 29 ++++++++++++++++++ 6 files changed, 176 insertions(+) create mode 100644 docs/report/report.pdf create mode 100644 docs/report/report.tex create mode 100644 docs/report/styles/header.sty create mode 100644 docs/report/styles/packages.sty create mode 100644 docs/report/styles/section.sty create mode 100644 docs/report/styles/title.sty diff --git a/docs/report/report.pdf b/docs/report/report.pdf new file mode 100644 index 0000000..5092c22 Binary files /dev/null and b/docs/report/report.pdf differ diff --git a/docs/report/report.tex b/docs/report/report.tex new file mode 100644 index 0000000..02472ac --- /dev/null +++ b/docs/report/report.tex @@ -0,0 +1,65 @@ +\documentclass[11pt]{scrartcl} + +% Metadata +\title{Global Min Cut} +\subtitle{CS 456: Project 5} +\author{Neil Kollack and Toby Vincent} + +% Packages +\usepackage{styles/packages} +\usepackage{styles/header} +\usepackage{styles/title} +\usepackage{styles/section} +\usepackage{csvsimple} +\usepackage{graphicx} +\usepackage{amsmath} + +\begin{document} +\maketitle + +\section{Introduction} + +The goal of this project was to analyze and compare the Edmonds-Karp algorithm with Karger's approximation algorithm for finding the global minimum cut of a graph. The global minimum cut problem consists of finding the lowest capacity cut through a graph. Being a NP Hard problem, the runtime of finding the exact solution using the Edmonds–Karp algorithm is $O(\vert V \vert ^ 2 \vert E \vert ^ 2)$, and as such, we aim to experiment with Karger's approximation algorithm to discover its viability, and what trade-offs are made compared to the Edmonds–Karp algorithm. + +\section{Results} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/constant_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/constant_times.csv}} + \caption{\label{tab:constant} Minimum cut and associated runtimes for $10$ iterations} +\end{table} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/linear_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/linear_times.csv}} + \caption{\label{tab:linier} Minimum cut and associated runtimes for $n$ iterations} +\end{table} + +\begin{table}[h] + \centering + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/polynomial_cuts.csv}} + \resizebox{\textwidth}{!}{% + \csvautotabular{../../output/polynomial_times.csv}} + \caption{\label{tab:polynomial} Minimum cut and associated runtimes for $n^2\ln n$ iterations} +\end{table} + +\section{Analysis} + +When looking at the probability of not finding the minimum cut we know that when repeating the contraction algorithm $n^2 ln(n)$ times that the probability of not finding the minimum cut is $1/n^2$. However, when running the algorithm only n times there is a rather noticeable change in the probability. Simplifying the probability equation down from $P_n = 1-[ 1- \binom{n}{2}^{-1}]^n$ to $P_n = 1-[ 1-\frac{2}{n^2-n} ]^n$ it becomes apparent that while running the algorithm n times is moving toward a low probability of not finding the minimum cut, it is nowhere near as effective as $n^2 ln(n)$ times. Where running n times the failure rate never really reaches a sufficiently small probability, whereas $n^2 ln(n)$ would reach a point of failure that is sufficient on graphs with very small n values. + +When also taking into account that we performed 5 repetitions, the probability of failure for $n^2 ln(n)$ drops immediately to almost zero, even at n = 2. Where n still has at least a 1\% overall failure rate. This is reflected in our data, where $n^2 ln(n)$ did not fail on any repetitions and n failed a majority of the time but at least one of the five repetitions came up with the correct answer. + +As for the runtimes, as expected with the Contraction Algorithm being $O(\vert V \vert ^2* \vert E \vert *log(V))$, which is at least a factor less than the Edmonds-Karp method, the approximation method is much faster even when ran $n^2 ln(n)$ times. Therefore, with the accuracy of the $n^2 ln(n)$ iteration Contraction Algorithm matching that of the exact method, and its runtime proving to be better, this experiment would seem to conclude that the $n^2 ln(n)$ iteration approximation is the preferable choice of all options examined + +\section{Conclusion} + +Due to the insurmountable runtimes of the algorithm on a larger graph for $n^2\ln n$ iterations, it is unfeasible to run the number of repetitions needed for a dataset large enough to conclusively show the probability of not finding the minimum cut converges to zero. Even with parallelization of the main iteration loop the runtime of larger graphs was still excessive. That being said, even five repetitions of the algorithm illustrates the disparity between the different iteration counts that where chosen for this experiment. The level of experimentation was a successfully demonstrated the viability of using Karger's algorithm as a solution to an otherwise difficult problem. + +\end{document} \ No newline at end of file diff --git a/docs/report/styles/header.sty b/docs/report/styles/header.sty new file mode 100644 index 0000000..b86e98e --- /dev/null +++ b/docs/report/styles/header.sty @@ -0,0 +1,35 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/header}[2021/09/29 Header style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ [Header] +% │ Author │ ──┘ +% │ Title │ ──┬─ Title +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ Sections +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\pagestyle{myheadings} + +\newsavebox{\headingbox} +\sbox{\headingbox}{% + \begin{minipage}[b]{0.5\textwidth} + \begin{flushright} + \@title \\ + \@subtitle \\ + \@author \\ + \end{flushright} + \end{minipage}} +\markright{\hfill\usebox{\headingbox}} diff --git a/docs/report/styles/packages.sty b/docs/report/styles/packages.sty new file mode 100644 index 0000000..262b9d1 --- /dev/null +++ b/docs/report/styles/packages.sty @@ -0,0 +1,12 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/packages}[2021/09/29 Package imports] + +\RequirePackage[english]{babel} +\RequirePackage[letterpaper,top=2.54cm,bottom=2.54cm,left=2.54cm,right=2.54cm,marginparwidth=1.75cm]{geometry} +\RequirePackage{lipsum} +\RequirePackage{array} +\RequirePackage[colorlinks=true, allcolors=blue]{hyperref} +\RequirePackage[autostyle, english = american]{csquotes} + +% Styles +\MakeOuterQuote{"} \ No newline at end of file diff --git a/docs/report/styles/section.sty b/docs/report/styles/section.sty new file mode 100644 index 0000000..ed4d606 --- /dev/null +++ b/docs/report/styles/section.sty @@ -0,0 +1,35 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/section}[2021/09/29 Section style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ Header +% │ Author │ ──┘ +% │ Title │ ──┬─ Title +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ [Sections] +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\RequirePackage{indentfirst} +% \RequirePackage{titlesec} +% \titlespacing*{\section}{0pt}{1.1\baselineskip}{\baselineskip} + +% Paragraph spacing +\setlength{\parskip}{1em} + +\RedeclareSectionCommand[ + afterindent=false, + beforeskip=.5\baselineskip, + afterskip=.5\baselineskip +]{section} \ No newline at end of file diff --git a/docs/report/styles/title.sty b/docs/report/styles/title.sty new file mode 100644 index 0000000..fdeabbe --- /dev/null +++ b/docs/report/styles/title.sty @@ -0,0 +1,29 @@ +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{styles/title}[2021/09/29 Title style] + +% ┌───────────────────────────────────┐ +% │ Title: Subtitle │ ──┬─ Header +% │ Author │ ──┘ +% │ Title │ ──┬─ [Title] +% │ Subtitle │ ──┘ +% │ │ +% │ A Section │ ──┬─ Sections +% │ ... │ │ +% │ 1.1 A Subsection │ ──┤ +% │ ... │ │ +% │ Another Section │ ──┤ +% │ ... │ │ +% │ 2.1 A Subsection │ ──┤ +% │ ... │ │ +% │ 2.2 Another Subsection │ ──┘ +% │ ... │ +% │ │ +% │ │ +% └───────────────────────────────────┘ + +\renewcommand{\maketitle}{ + \begin{flushleft} + {\Huge \bfseries \sffamily \@title }\\[2ex] + {\Large \sffamily \@subtitle }\\[4ex] + \end{flushleft} +} -- cgit v1.2.3-70-g09d2