bmichotte / dijkstra

example/index.php

Indentation +1 added lines, -1 removed lines

@@ -18,7 +18,7 @@
 // we add "$nodes" dynamic nodes
 $positions = [];
 foreach (range(0, $nodes) as $value) {
-    $positions[] = new Point(rand(0, $max), rand(0, $max));
+	$positions[] = new Point(rand(0, $max), rand(0, $max));
 }
 
 // add random links

src/Dijkstra.php

Indentation +123 added lines, -123 removed lines

@@ -4,116 +4,116 @@ 
 
 class Dijkstra
 {
-    private $positions;
-    private $from;
-    private $to;
-    private $weights;
-    private $predecessors;
-
-    public function __construct(array $positions, Point $from, Point $to)
-    {
-        $this->positions = $positions;
-        $this->from = $from;
-        $this->to = $to;
-    }
-
-    public function findShortestPath(): array
-    {
-        $this->weights = [];
-        $this->predecessors = [];
-
-        foreach ($this->positions as $position) {
-            $weight = -1;
-            $passed = false;
-
-            if ($position->equals($this->from)) {
-                $weight = 0;
-                $passed = true;
-            }
-
-            // init weights array
-            $this->weights[$position->ref] = [
-                'position' => $position,
-                'weight' => $weight,
-                'passed' => $passed,
-            ];
-
-            // init predecessors array
-            $this->predecessors[$position->ref] = [
-                'position' => $position,
-                'previous' => null,
-            ];
-        }
-
-        return $this->run($this->from)->getPath();
-    }
-
-    protected function run(Point $parent): Dijkstra
-    {
-        // we reached the final point !
-        if ($parent->equals($this->to)) {
-            return $this;
-        }
-
-        // we can set this node has been passed by
-        $this->weights[$parent->ref]['passed'] = true;
-
-        // search for weight between $parent and its children
-        foreach ($parent->points as $child) {
-            $this->calculateWeight($parent, $child);
-        }
-
-        // search for the next parent (smallest weight)
-        // we have to find the smallest weight for a node we didn't passed by atm
-        $smallest = INF;
-        $nextParent = null;
-        foreach ($this->weights as $weight) {
-            if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) {
-                $smallest = $weight['weight'];
-                $nextParent = $weight['position'];
-            }
-        }
-        if (! is_null($nextParent)) {
-            return $this->run($nextParent);
-        }
-
-        return $this;
-    }
-
-    protected function getPath(): array
-    {
-        $path = [$this->to];
-
-        $point = $this->to;
-        while (true) {
-            foreach ($this->predecessors as $predecessor) {
-                if ($predecessor['position']->equals($point)) {
-                    $point = $predecessor['previous'];
-                    $path[] = $point;
-
-                    break;
-                }
-            }
-
-            // $point is null -> path impossible
-            if (is_null($point)) {
-                unset($path[count($path) - 1]);
-                break;
-            }
-
-            if ($point->equals($this->from)) {
-                break;
-            }
-        }
-
-        $path = array_reverse($path);
-
-        return $path;
-    }
-
-    protected function calculateWeight(Point $parent, Point $child): void
-    {
-        /*
+	private $positions;
+	private $from;
+	private $to;
+	private $weights;
+	private $predecessors;
+
+	public function __construct(array $positions, Point $from, Point $to)
+	{
+		$this->positions = $positions;
+		$this->from = $from;
+		$this->to = $to;
+	}
+
+	public function findShortestPath(): array
+	{
+		$this->weights = [];
+		$this->predecessors = [];
+
+		foreach ($this->positions as $position) {
+			$weight = -1;
+			$passed = false;
+
+			if ($position->equals($this->from)) {
+				$weight = 0;
+				$passed = true;
+			}
+
+			// init weights array
+			$this->weights[$position->ref] = [
+				'position' => $position,
+				'weight' => $weight,
+				'passed' => $passed,
+			];
+
+			// init predecessors array
+			$this->predecessors[$position->ref] = [
+				'position' => $position,
+				'previous' => null,
+			];
+		}
+
+		return $this->run($this->from)->getPath();
+	}
+
+	protected function run(Point $parent): Dijkstra
+	{
+		// we reached the final point !
+		if ($parent->equals($this->to)) {
+			return $this;
+		}
+
+		// we can set this node has been passed by
+		$this->weights[$parent->ref]['passed'] = true;
+
+		// search for weight between $parent and its children
+		foreach ($parent->points as $child) {
+			$this->calculateWeight($parent, $child);
+		}
+
+		// search for the next parent (smallest weight)
+		// we have to find the smallest weight for a node we didn't passed by atm
+		$smallest = INF;
+		$nextParent = null;
+		foreach ($this->weights as $weight) {
+			if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) {
+				$smallest = $weight['weight'];
+				$nextParent = $weight['position'];
+			}
+		}
+		if (! is_null($nextParent)) {
+			return $this->run($nextParent);
+		}
+
+		return $this;
+	}
+
+	protected function getPath(): array
+	{
+		$path = [$this->to];
+
+		$point = $this->to;
+		while (true) {
+			foreach ($this->predecessors as $predecessor) {
+				if ($predecessor['position']->equals($point)) {
+					$point = $predecessor['previous'];
+					$path[] = $point;
+
+					break;
+				}
+			}
+
+			// $point is null -> path impossible
+			if (is_null($point)) {
+				unset($path[count($path) - 1]);
+				break;
+			}
+
+			if ($point->equals($this->from)) {
+				break;
+			}
+		}
+
+		$path = array_reverse($path);
+
+		return $path;
+	}
+
+	protected function calculateWeight(Point $parent, Point $child): void
+	{
+		/*
          * Dijkstra algo says :
          *
          * IF (child-node is not traversed yet) AND
@@ -123,17 +123,17 @@ 
          *  PREDECESSOR(child-node) = parent-node
          * ENDIF
          */
-        if (! $this->weights[$child->ref]['passed']
-            && ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight']
-                || $this->weights[$child->ref]['weight'] === -1)) {
-            $this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child);
-            $this->predecessors[$child->ref]['previous'] = $parent;
-        }
-    }
-
-    public static function distance(Point $p1, Point $p2): float
-    {
-        // distance = square root of ((x2 - x1)^2 + (y2 - y1)^2)
-        return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2));
-    }
+		if (! $this->weights[$child->ref]['passed']
+			&& ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight']
+				|| $this->weights[$child->ref]['weight'] === -1)) {
+			$this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child);
+			$this->predecessors[$child->ref]['previous'] = $parent;
+		}
+	}
+
+	public static function distance(Point $p1, Point $p2): float
+	{
+		// distance = square root of ((x2 - x1)^2 + (y2 - y1)^2)
+		return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2));
+	}
 }

Spacing +3 added lines, -3 removed lines

@@ -68,12 +68,12 @@ 
         $smallest = INF;
         $nextParent = null;
         foreach ($this->weights as $weight) {
-            if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) {
+            if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && !$weight['passed']) {
                 $smallest = $weight['weight'];
                 $nextParent = $weight['position'];
             }
         }
-        if (! is_null($nextParent)) {
+        if (!is_null($nextParent)) {
             return $this->run($nextParent);
         }
 
@@ -123,7 +123,7 @@ 
          *  PREDECESSOR(child-node) = parent-node
          * ENDIF
          */
-        if (! $this->weights[$child->ref]['passed']
+        if (!$this->weights[$child->ref]['passed']
             && ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight']
                 || $this->weights[$child->ref]['weight'] === -1)) {
             $this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child);

src/Point.php

Indentation +26 added lines, -26 removed lines

@@ -4,35 +4,35 @@
 
 class Point
 {
-    public $x;
-    public $y;
-    public $points;
-    public $ref;
+	public $x;
+	public $y;
+	public $points;
+	public $ref;
 
-    public function __construct($x, $y)
-    {
-        $this->x = $x;
-        $this->y = $y;
-        $this->points = [];
-        $this->ref = "{$x}-{$y}";
-    }
+	public function __construct($x, $y)
+	{
+		$this->x = $x;
+		$this->y = $y;
+		$this->points = [];
+		$this->ref = "{$x}-{$y}";
+	}
 
-    public function addPoint(Point $point): Point
-    {
-        if (! in_array($point, $this->points)) {
-            $this->points[] = $point;
-        }
+	public function addPoint(Point $point): Point
+	{
+		if (! in_array($point, $this->points)) {
+			$this->points[] = $point;
+		}
 
-        // add the reverse point
-        if (! in_array($this, $point->points)) {
-            $point->points[] = $this;
-        }
+		// add the reverse point
+		if (! in_array($this, $point->points)) {
+			$point->points[] = $this;
+		}
 
-        return $this;
-    }
+		return $this;
+	}
 
-    public function equals(Point $point): bool
-    {
-        return $this->ref === $point->ref;
-    }
+	public function equals(Point $point): bool
+	{
+		return $this->ref === $point->ref;
+	}
 }

Spacing +2 added lines, -2 removed lines

@@ -19,12 +19,12 @@
 
     public function addPoint(Point $point): Point
     {
-        if (! in_array($point, $this->points)) {
+        if (!in_array($point, $this->points)) {
             $this->points[] = $point;
         }
 
         // add the reverse point
-        if (! in_array($this, $point->points)) {
+        if (!in_array($this, $point->points)) {
             $point->points[] = $this;
         }
 

example/helpers.php

Indentation +89 added lines, -89 removed lines

@@ -4,109 +4,109 @@
 
 function findLink(int $minDistance, array &$positions): void
 {
-    foreach ($positions as $point) {
-        findLinkBetween($minDistance, $point, $positions);
-    }
+	foreach ($positions as $point) {
+		findLinkBetween($minDistance, $point, $positions);
+	}
 }
 
 function findLinkBetween(int $minDistance, Point &$point1, array &$positions): void
 {
-    foreach ($positions as $point2) {
-        if ($point1->equals($point2)) {
-            continue;
-        }
-
-        $distance = Dijkstra::distance($point1, $point2);
-        if ($distance < $minDistance) {
-            $point1->addPoint($point2);
-        }
-    }
-
-    if (0 === count($point1->points)) {
-        findLinkBetween($minDistance * 2, $point1, $positions);
-    }
+	foreach ($positions as $point2) {
+		if ($point1->equals($point2)) {
+			continue;
+		}
+
+		$distance = Dijkstra::distance($point1, $point2);
+		if ($distance < $minDistance) {
+			$point1->addPoint($point2);
+		}
+	}
+
+	if (0 === count($point1->points)) {
+		findLinkBetween($minDistance * 2, $point1, $positions);
+	}
 }
 
 function findFromTo(array $positions): array
 {
-    $from = null;
-    $to = null;
-    foreach ($positions as $point) {
-        $from = $from ?: $point;
-        $to = $to ?: $point;
-
-        if ($point->x < $from->x && $point->y < $from->y) {
-            $from = $point;
-        }
-
-        if ($point->x > $to->x && $point->y > $to->y) {
-            $to = $point;
-        }
-    }
-
-    return [$from, $to];
+	$from = null;
+	$to = null;
+	foreach ($positions as $point) {
+		$from = $from ?: $point;
+		$to = $to ?: $point;
+
+		if ($point->x < $from->x && $point->y < $from->y) {
+			$from = $point;
+		}
+
+		if ($point->x > $to->x && $point->y > $to->y) {
+			$to = $point;
+		}
+	}
+
+	return [$from, $to];
 }
 
 function drawPaths(int $max, array $positions, Point $from, Point $to, array $shortestPath, string $filename): void
 {
-    // open background
-    $image = imagecreatetruecolor($max, $max);
-    $color = imagecolorallocate($image, 255, 255, 255);
-    imagefill($image, 0, 0, $color);
-
-    // first run, draw lines
-    $color = imagecolorallocate($image, 32, 230, 200);
-    foreach ($positions as $point) {
-        foreach ($point->points as $link) {
-            drawLine($image, $point, $link, $color);
-        }
-    }
-
-    // then, draw the points
-    $color = imagecolorallocate($image, 32, 230, 36);
-    foreach ($positions as $point) {
-        imagefilledellipse($image, $point->x, $point->y, 10, 10, $color);
-    }
-
-    // draw the shortest path
-    $color = imagecolorallocate($image, 255, 0, 255);
-    for ($i = 0; $i < count($shortestPath); $i++) {
-        $p = $shortestPath[$i];
-        if (isset($shortestPath[$i + 1])) {
-            $d = $shortestPath[$i + 1];
-            drawLine($image, $p, $d, $color, 3);
-        }
-    }
-
-    // and finally, draw the from and to points
-    $color = imagecolorallocate($image, 255, 0, 255);
-    imagefilledellipse($image, $from->x, $from->y, 10, 10, $color);
-    imagefilledellipse($image, $to->x, $to->y, 10, 10, $color);
-
-    imagepng($image, $filename);
+	// open background
+	$image = imagecreatetruecolor($max, $max);
+	$color = imagecolorallocate($image, 255, 255, 255);
+	imagefill($image, 0, 0, $color);
+
+	// first run, draw lines
+	$color = imagecolorallocate($image, 32, 230, 200);
+	foreach ($positions as $point) {
+		foreach ($point->points as $link) {
+			drawLine($image, $point, $link, $color);
+		}
+	}
+
+	// then, draw the points
+	$color = imagecolorallocate($image, 32, 230, 36);
+	foreach ($positions as $point) {
+		imagefilledellipse($image, $point->x, $point->y, 10, 10, $color);
+	}
+
+	// draw the shortest path
+	$color = imagecolorallocate($image, 255, 0, 255);
+	for ($i = 0; $i < count($shortestPath); $i++) {
+		$p = $shortestPath[$i];
+		if (isset($shortestPath[$i + 1])) {
+			$d = $shortestPath[$i + 1];
+			drawLine($image, $p, $d, $color, 3);
+		}
+	}
+
+	// and finally, draw the from and to points
+	$color = imagecolorallocate($image, 255, 0, 255);
+	imagefilledellipse($image, $from->x, $from->y, 10, 10, $color);
+	imagefilledellipse($image, $to->x, $to->y, 10, 10, $color);
+
+	imagepng($image, $filename);
 }
 
 function drawLine($image, Point $point1, Point $point2, $color, int $thick = 1): void
 {
-    if (null === $point1 || null === $point2) {
-        return;
-    }
-    if (null === $point1->x || null === $point1->y) {
-        return;
-    }
-    if (null === $point2->x || null === $point2->y) {
-        return;
-    }
-
-    if ($point1->x === $point2->x) {
-        $from = $point1->y < $point2->y ? $point1 : $point2;
-        $to = $point1->y > $point2->y ? $point1 : $point2;
-    } else {
-        $from = $point1->x < $point2->x ? $point1 : $point2;
-        $to = $point1->x > $point2->x ? $point1 : $point2;
-    }
-
-    imagesetthickness($image, $thick);
-
-    imageline($image, $from->x, $from->y, $to->x, $to->y, $color);
+	if (null === $point1 || null === $point2) {
+		return;
+	}
+	if (null === $point1->x || null === $point1->y) {
+		return;
+	}
+	if (null === $point2->x || null === $point2->y) {
+		return;
+	}
+
+	if ($point1->x === $point2->x) {
+		$from = $point1->y < $point2->y ? $point1 : $point2;
+		$to = $point1->y > $point2->y ? $point1 : $point2;
+	} else {
+		$from = $point1->x < $point2->x ? $point1 : $point2;
+		$to = $point1->x > $point2->x ? $point1 : $point2;
+	}
+
+	imagesetthickness($image, $thick);
+
+	imageline($image, $from->x, $from->y, $to->x, $to->y, $color);
 }