bingo-soft /
graphp
| Total Complexity | 43 |
| Total Lines | 331 |
| Duplicated Lines | 0 % |
| Coverage | 0% |
| Changes | 1 | ||
| Bugs | 0 | Features | 1 |
Complex classes like GraphUtils often do a lot of different things. To break such a class down, we need to identify a cohesive component within that class. A common approach to find such a component is to look for fields/methods that share the same prefixes, or suffixes.
Once you have determined the fields that belong together, you can apply the Extract Class refactoring. If the component makes sense as a sub-class, Extract Subclass is also a candidate, and is often faster.
While breaking up the class, it is a good idea to analyze how other classes use GraphUtils, and based on these observations, apply Extract Interface, too.
| 1 | <?php |
||
| 16 | class GraphUtils |
||
| 17 | { |
||
| 18 | /** |
||
| 19 | * Create a new edge and add it to the specified graph |
||
| 20 | * |
||
| 21 | * @param GraphInterface $graph - the graph |
||
| 22 | * @param VertexInterface $sourceVertex - the source vertex |
||
| 23 | * @param VertexInterface $targetVertex - the target vertex |
||
| 24 | * @param float $weight - the weight of the edge being added |
||
| 25 | * |
||
| 26 | * @return EdgeInterface |
||
| 27 | */ |
||
| 28 | public static function addEdge( |
||
| 29 | GraphInterface $graph, |
||
| 30 | VertexInterface $sourceVertex, |
||
| 31 | VertexInterface $targetVertex, |
||
| 32 | ?float $weight = null |
||
| 33 | ): ?EdgeInterface { |
||
| 34 | $edgeSupplier = $graph->getEdgeSupplier(); |
||
| 35 | if (is_null($edgeSupplier)) { |
||
| 36 | throw new Exception("Graph contains no edge supplier"); |
||
|
Bug
introduced
by
|
|||
| 37 | } |
||
| 38 | $edge = $edgeSupplier->get(); |
||
| 39 | |||
| 40 | if ($graph->addEdge($sourceVertex, $targetVertex, $edge)) { |
||
| 41 | if ($graph->getType()->isWeighted()) { |
||
| 42 | $graph->setEdgeWeight($edge, $weight); |
||
| 43 | } |
||
| 44 | return $edge; |
||
| 45 | } |
||
| 46 | return null; |
||
| 47 | } |
||
| 48 | |||
| 49 | /** |
||
| 50 | * Add the speficied source and target vertices to the graph |
||
| 51 | * |
||
| 52 | * @param GraphInterface $graph - the graph |
||
| 53 | * @param VertexInterface $sourceVertex - the source vertex |
||
| 54 | * @param VertexInterface $targetVertex - the target vertex |
||
| 55 | * @param float $weight - the weight of the edge being added |
||
| 56 | * |
||
| 57 | * @return EdgeInterface |
||
| 58 | */ |
||
| 59 | public static function addEdgeWithVertices( |
||
| 60 | GraphInterface $graph, |
||
| 61 | VertexInterface $sourceVertex, |
||
| 62 | VertexInterface $targetVertex, |
||
| 63 | ?float $weight = null |
||
| 64 | ): EdgeInterface { |
||
| 65 | $graph->addVertex($sourceVertex); |
||
| 66 | $graph->addVertex($targetVertex); |
||
| 67 | return self::addEdge($graph, $sourceVertex, $targetVertex, $weight); |
||
| 68 | } |
||
| 69 | |||
| 70 | /** |
||
| 71 | * Add all the vertices and all the edges of the source graph to the target graph. |
||
| 72 | * Return true, if the target graph was changed |
||
| 73 | * |
||
| 74 | * @param GraphInterface $targetGraph - the target graph |
||
| 75 | * @param GraphInterface $sourceGraph - the source graph |
||
| 76 | * |
||
| 77 | * @return bool |
||
| 78 | */ |
||
| 79 | public static function addGraph(GraphInterface $targetGraph, GraphInterface $sourceGraph): bool |
||
| 80 | { |
||
| 81 | $modified = self::addAllVertices($targetGraph, $sourceGraph->vertexSet()); |
||
| 82 | return self::addAllEdges($targetGraph, $sourceGraph, $sourceGraph->edgeSet()) || $modified; |
||
| 83 | } |
||
| 84 | |||
| 85 | /** |
||
| 86 | * Add all vertices to the specified graph. |
||
| 87 | * Return true, if the graph was modified |
||
| 88 | * |
||
| 89 | * @param GraphInterface $graph - the target graph |
||
| 90 | * @param VertexSet $vertices - the vertices |
||
| 91 | * |
||
| 92 | * @return bool |
||
| 93 | */ |
||
| 94 | public static function addAllVertices(GraphInterface $graph, VertexSet $vertices): bool |
||
| 95 | { |
||
| 96 | $modified = false; |
||
| 97 | foreach ($vertices as $vertex) { |
||
| 98 | $modified = $graph->addVertex($vertex) || $modified; |
||
| 99 | } |
||
| 100 | return $modified; |
||
| 101 | } |
||
| 102 | |||
| 103 | /** |
||
| 104 | * Add all edges of the source graph to the target graph. |
||
| 105 | * Return true, if the graph was modified |
||
| 106 | * |
||
| 107 | * @param GraphInterface $targetGraph - the target graph |
||
| 108 | * @param GraphInterface $sourceGraph - the source graph |
||
| 109 | * @param EdgeSet $edges - the edges to add |
||
| 110 | * |
||
| 111 | * @return bool |
||
| 112 | */ |
||
| 113 | public static function addAllEdges( |
||
| 114 | GraphInterface $targetGraph, |
||
| 115 | GraphInterface $sourceGraph, |
||
| 116 | EdgeSet $edges |
||
| 117 | ): bool { |
||
| 118 | $modified = false; |
||
| 119 | foreach ($edges as $edge) { |
||
| 120 | $sourceVertex = $sourceGraph->getEdgeSource($edge); |
||
| 121 | $targetVertex = $sourceGraph->getEdgeTarget($edge); |
||
| 122 | $targetGraph->addVertex($sourceVertex); |
||
| 123 | $targetGraph->addVertex($targetVertex); |
||
| 124 | $modified = $targetGraph->addEdge($sourceVertex, $targetVertex, $edge) || $modified; |
||
| 125 | } |
||
| 126 | return $modified; |
||
| 127 | } |
||
| 128 | |||
| 129 | /** |
||
| 130 | * Add all the vertices and all the edges of the source graph to the target graph in the reversed order |
||
| 131 | * |
||
| 132 | * @param GraphInterface $targetGraph - the target graph |
||
| 133 | * @param GraphInterface $sourceGraph - the source graph |
||
| 134 | */ |
||
| 135 | public static function addGraphReversed(GraphInterface $targetGraph, GraphInterface $sourceGraph): void |
||
| 136 | { |
||
| 137 | if (!$sourceGraph->getType()->isDirected() || !$targetGraph->getType()->isDirected()) { |
||
| 138 | throw new InvalidArgumentException("graph must be directed"); |
||
| 139 | } |
||
| 140 | |||
| 141 | self::addAllVertices($targetGraph, $sourceGraph->vertexSet()); |
||
| 142 | |||
| 143 | $edges = $sourceGraph->edgeSet(); |
||
| 144 | foreach ($edges as $edge) { |
||
| 145 | $targetGraph->addEdge($sourceGraph->getEdgeTarget($edge), $sourceGraph->getEdgeSource($edge)); |
||
| 146 | } |
||
| 147 | } |
||
| 148 | |||
| 149 | /** |
||
| 150 | * Get a list of vertices that are the neighbors of a specified vertex. |
||
| 151 | * |
||
| 152 | * @param GraphInterface $graph - the graph |
||
| 153 | * @param VertexInterface $vertex - the vertex |
||
| 154 | * |
||
| 155 | * @return array |
||
| 156 | */ |
||
| 157 | public static function neighborsOf(GraphInterface $graph, VertexInterface $vertex): array |
||
| 158 | { |
||
| 159 | $neighbors = []; |
||
| 160 | $edges = $graph->edgesOf($vertex); |
||
| 161 | foreach ($edges as $edge) { |
||
| 162 | $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex); |
||
| 163 | } |
||
| 164 | return $neighbors; |
||
| 165 | } |
||
| 166 | |||
| 167 | /** |
||
| 168 | * Get a list of vertices that are the direct predecessors of a specified vertex. |
||
| 169 | * |
||
| 170 | * @param GraphInterface $graph - the graph |
||
| 171 | * @param VertexInterface $vertex - the vertex |
||
| 172 | * |
||
| 173 | * @return array |
||
| 174 | */ |
||
| 175 | public static function predecessorsOf(GraphInterface $graph, VertexInterface $vertex): array |
||
| 176 | { |
||
| 177 | $neighbors = []; |
||
| 178 | $edges = $graph->incomingEdgesOf($vertex); |
||
| 179 | foreach ($edges as $edge) { |
||
| 180 | $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex); |
||
| 181 | } |
||
| 182 | return $neighbors; |
||
| 183 | } |
||
| 184 | |||
| 185 | /** |
||
| 186 | * Get a list of vertices that are the direct successors of a specified vertex. |
||
| 187 | * |
||
| 188 | * @param GraphInterface $graph - the graph |
||
| 189 | * @param VertexInterface $vertex - the vertex |
||
| 190 | * |
||
| 191 | * @return array |
||
| 192 | */ |
||
| 193 | public static function successorsOf(GraphInterface $graph, VertexInterface $vertex): array |
||
| 194 | { |
||
| 195 | $neighbors = []; |
||
| 196 | $edges = $graph->outgoingEdgesOf($vertex); |
||
| 197 | foreach ($edges as $edge) { |
||
| 198 | $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex); |
||
| 199 | } |
||
| 200 | return $neighbors; |
||
| 201 | } |
||
| 202 | |||
| 203 | /** |
||
| 204 | * Test whether an edge is incident to a vertex. |
||
| 205 | * |
||
| 206 | * @param GraphInterface $graph - the graph |
||
| 207 | * @param EdgeInterface $edge - the edge |
||
| 208 | * @param VertexInterface $vertex - the vertex |
||
| 209 | * |
||
| 210 | * @return bool |
||
| 211 | */ |
||
| 212 | public static function testIncidence(GraphInterface $graph, EdgeInterface $edge, VertexInterface $vertex): bool |
||
| 213 | { |
||
| 214 | return $graph->getEdgeSource($edge)->equals($vertex) |
||
| 215 | || $graph->getEdgeTarget($edge)->equals($vertex); |
||
| 216 | } |
||
| 217 | |||
| 218 | /** |
||
| 219 | * Get the vertex opposite another vertex across an edge. |
||
| 220 | * |
||
| 221 | * @param g graph containing e and v |
||
| 222 | * @param e edge in g |
||
| 223 | * @param v vertex in g |
||
| 224 | * @param <V> the graph vertex type |
||
| 225 | * @param <E> the graph edge type |
||
| 226 | * |
||
| 227 | * @return vertex opposite to v across e |
||
| 228 | * |
||
| 229 | * @throws InvalidArgumentException |
||
| 230 | */ |
||
| 231 | public static function getOppositeVertex( |
||
| 232 | GraphInterface $graph, |
||
| 233 | EdgeInterface $edge, |
||
| 234 | VertexInterface $vertex |
||
| 235 | ): VertexInterface { |
||
| 236 | $source = $graph->getEdgeSource($edge); |
||
| 237 | $target = $graph->getEdgeTarget($edge); |
||
| 238 | if ($vertex->equals($source)) { |
||
| 239 | return $target; |
||
| 240 | } elseif ($vertex->equals($target)) { |
||
| 241 | return $source; |
||
| 242 | } else { |
||
| 243 | throw new InvalidArgumentException("no such vertex: " + $vertex); |
||
| 244 | } |
||
| 245 | } |
||
| 246 | |||
| 247 | /** |
||
| 248 | * Remove the given vertices from the given graph. If the vertex to be removed has one or more |
||
| 249 | * predecessors, the predecessors will be connected directly to the successors of the vertex to |
||
| 250 | * be removed. |
||
| 251 | * |
||
| 252 | * @param GraphInterface $graph - the graph |
||
| 253 | * @param VertexInterface $vertex - the vertex to be removed |
||
| 254 | * @param mixed $vertices - the remaining vertices |
||
| 255 | * |
||
| 256 | * @return bool |
||
| 257 | */ |
||
| 258 | public static function removeVertexAndPreserveConnectivity( |
||
| 259 | GraphInterface $graph, |
||
| 260 | VertexInterface $vertex, |
||
| 261 | ...$vertices |
||
| 262 | ): bool { |
||
| 263 | if (!$graph->containsVertex($vertex)) { |
||
| 264 | return false; |
||
| 265 | } |
||
| 266 | |||
| 267 | $vertices[] = $vertex; |
||
| 268 | foreach ($vertices as $vertex) { |
||
| 269 | if (self::vertexHasPredecessors($graph, $vertex)) { |
||
| 270 | $predecessors = self::predecessorsOf($graph, $vertex); |
||
| 271 | $successors = self::successorsOf($graph, $vertex); |
||
| 272 | |||
| 273 | foreach ($predecessors as $predecessor) { |
||
| 274 | self::addOutgoingEdges($graph, $predecessor, ...$successors); |
||
| 275 | } |
||
| 276 | } |
||
| 277 | $graph->removeVertex($vertex); |
||
| 278 | } |
||
| 279 | |||
| 280 | return true; |
||
| 281 | } |
||
| 282 | |||
| 283 | /** |
||
| 284 | * Add edges from one source vertex to multiple target vertices |
||
| 285 | * |
||
| 286 | * @param GraphInterface $graph - the graph |
||
| 287 | * @param VertexInterface $vertex - the source vertex |
||
| 288 | * @param mixed $vertices - the target vertices |
||
| 289 | */ |
||
| 290 | public static function addOutgoingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void |
||
| 300 | } |
||
| 301 | } |
||
| 302 | |||
| 303 | /** |
||
| 304 | * Add edges from multiple source vertices to one target vertex |
||
| 305 | * |
||
| 306 | * @param GraphInterface $graph - the graph |
||
| 307 | * @param VertexInterface $vertex - the target vertex |
||
| 308 | * @param mixed $vertices - the source vertices |
||
| 309 | */ |
||
| 310 | public static function addIncomingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void |
||
| 311 | { |
||
| 312 | if (!$graph->containsVertex($vertex)) { |
||
| 313 | $graph->addVertex($vertex); |
||
| 314 | } |
||
| 315 | foreach ($vertices as $source) { |
||
| 316 | if (!$graph->containsVertex($source)) { |
||
| 317 | $graph->addVertex($source); |
||
| 318 | } |
||
| 319 | $graph->addEdge($source, $vertex); |
||
| 320 | } |
||
| 321 | } |
||
| 322 | |||
| 323 | /** |
||
| 324 | * Check if the vertex has direct successors |
||
| 325 | * |
||
| 326 | * @param GraphInterface $graph - the graph |
||
| 327 | * @param VertexInterface $vertex - the vertex |
||
| 328 | * |
||
| 329 | * @return bool |
||
| 330 | */ |
||
| 331 | public static function vertexHasSuccessors(GraphInterface $graph, VertexInterface $vertex): bool |
||
| 332 | { |
||
| 333 | return count($graph->outgoingEdgesOf($vertex)) > 0; |
||
| 334 | } |
||
| 335 | |||
| 336 | /** |
||
| 337 | * Check if the vertex has direct predecessors |
||
| 338 | * |
||
| 339 | * @param GraphInterface $graph - the graph |
||
| 340 | * @param VertexInterface $vertex - the vertex |
||
| 341 | * |
||
| 342 | * @return bool |
||
| 343 | */ |
||
| 344 | public static function vertexHasPredecessors(GraphInterface $graph, VertexInterface $vertex): bool |
||
| 347 | } |
||
| 348 | } |
||
| 349 |
Loading history...