Changeset View
Changeset View
Standalone View
Standalone View
src/utils/AbstractDirectedGraph.php
| Show First 20 Lines • Show All 312 Lines • ▼ Show 20 Lines | /* -( Cycle Detection )---------------------------------------------------- */ | ||||
| * keeping track of where it's been, and returns the first cycle it finds. | * keeping track of where it's been, and returns the first cycle it finds. | ||||
| * | * | ||||
| * @param scalar The node to walk from. | * @param scalar The node to walk from. | ||||
| * @param list Previously visited nodes. | * @param list Previously visited nodes. | ||||
| * @return null|list Null if no cycles are found, or a list of nodes | * @return null|list Null if no cycles are found, or a list of nodes | ||||
| * which cycle. | * which cycle. | ||||
| * @task cycle | * @task cycle | ||||
| */ | */ | ||||
| final private function performCycleDetection($node, array $visited) { | private function performCycleDetection($node, array $visited) { | ||||
| $visited[$node] = true; | $visited[$node] = true; | ||||
| foreach ($this->knownNodes[$node] as $edge) { | foreach ($this->knownNodes[$node] as $edge) { | ||||
| if (isset($visited[$edge])) { | if (isset($visited[$edge])) { | ||||
| $result = array_keys($visited); | $result = array_keys($visited); | ||||
| $result[] = $edge; | $result[] = $edge; | ||||
| return $result; | return $result; | ||||
| } | } | ||||
| $result = $this->performCycleDetection($edge, $visited); | $result = $this->performCycleDetection($edge, $visited); | ||||
| if ($result) { | if ($result) { | ||||
| return $result; | return $result; | ||||
| } | } | ||||
| } | } | ||||
| return null; | return null; | ||||
| } | } | ||||
| } | } | ||||