3v4l.org

run code in 300+ PHP versions simultaneously
<?php class Graph { private $graph = []; private $nodes = []; public function __construct(array $edges) { foreach ($edges as $edge => $weight) { $start = $edge[0]; $end = $edge[1]; $this->graph[$start][$end] = $weight; $this->graph[$end][$start] = $weight; $this->nodes[$start] = [ 'L' => INF, 'Q' => null, 'final' => false, ]; $this->nodes[$end] = [ 'L' => INF, 'Q' => null, 'final' => false, ]; } } public function find($start, $end, $initStartNode = true) { if ($initStartNode) { $this->initStartNode($start); } $nodes = $this->getNextNodes($start); $startLength = $this->getLength($start); foreach($nodes as $node => $weight) { $currentLength = $this->getLength($node); if ($startLength + $weight < $currentLength) { $this->setLength($node, $startLength + $weight); $this->setFromNode($node, $start); } } $nextNode = $this->getNextMinimumNode(); if (is_null($nextNode)) { return $this->getNodes(); } $this->setFinal($nextNode); $this->find($nextNode, $end, false); // var_dump($this->getGraph()); var_dump($this->getNodes()); // die(); } protected function getNextMinimumNode() { $nodes = $this->getNodes(); $min = INF; $minNode = null; foreach ($nodes as $node => $data) { if ($data['final']) { continue; } $nodeLength = $this->getLength($node); if ($nodeLength < $min) { $min = $nodeLength; $minNode = $node; } } return $minNode; } protected function initStartNode($node) { $this->setLength($node, 0); $this->setFromNode($node, '-'); $this->setFinal($node); } protected function getNextNodes($node) { return $this->graph[$node]; } protected function setLength($node, $value) { $this->nodes[$node]['L'] = $value; } protected function getLength($node) { return $this->nodes[$node]['L']; } protected function setFromNode($node, $value) { $this->nodes[$node]['Q'] = $value; } protected function setFinal($node) { $this->nodes[$node]['final'] = true; } public function getGraph() { return $this->graph; } public function getNodes() { return $this->nodes; } } $g = new Graph([ 'AB' => 5, 'AC' => 2, 'CB' => 2, 'CD' => 8, 'BE' => 7, 'DE' => 1, ]); $result = $g->find('A', 'E'); var_dump($result); // var_dump($g->getGraph()); // var_dump($g->getNodes());
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  (null)
number of ops:  13
compiled vars:  !0 = $g, !1 = $result
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  124     0  E >   NEW                                              $2      'Graph'
  125     1        SEND_VAL_EX                                              <array>
          2        DO_FCALL                                      0          
  124     3        ASSIGN                                                   !0, $2
  133     4        INIT_METHOD_CALL                                         !0, 'find'
          5        SEND_VAL_EX                                              'A'
          6        SEND_VAL_EX                                              'E'
          7        DO_FCALL                                      0  $5      
          8        ASSIGN                                                   !1, $5
  134     9        INIT_FCALL                                               'var_dump'
         10        SEND_VAR                                                 !1
         11        DO_ICALL                                                 
  136    12      > RETURN                                                   1

Class Graph:
Function __construct:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 77) Position 1 = 2, Position 2 = 23
Branch analysis from position: 2
2 jumps found. (Code = 78) Position 1 = 3, Position 2 = 23
Branch analysis from position: 3
1 jumps found. (Code = 42) Position 1 = 2
Branch analysis from position: 2
Branch analysis from position: 23
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 23
filename:       /in/36R1K
function name:  __construct
number of ops:  25
compiled vars:  !0 = $edges, !1 = $weight, !2 = $edge, !3 = $start, !4 = $end
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
    7     0  E >   RECV                                             !0      
    9     1      > FE_RESET_R                                       $5      !0, ->23
          2    > > FE_FETCH_R                                       ~6      $5, !1, ->23
          3    >   ASSIGN                                                   !2, ~6
   10     4        FETCH_DIM_R                                      ~8      !2, 0
          5        ASSIGN                                                   !3, ~8
   11     6        FETCH_DIM_R                                      ~10     !2, 1
          7        ASSIGN                                                   !4, ~10
   12     8        FETCH_OBJ_W                                      $12     'graph'
          9        FETCH_DIM_W                                      $13     $12, !3
         10        ASSIGN_DIM                                               $13, !4
         11        OP_DATA                                                  !1
   13    12        FETCH_OBJ_W                                      $15     'graph'
         13        FETCH_DIM_W                                      $16     $15, !4
         14        ASSIGN_DIM                                               $16, !3
         15        OP_DATA                                                  !1
   15    16        FETCH_OBJ_W                                      $18     'nodes'
         17        ASSIGN_DIM                                               $18, !3
   16    18        OP_DATA                                                  <array>
   20    19        FETCH_OBJ_W                                      $20     'nodes'
         20        ASSIGN_DIM                                               $20, !4
   21    21        OP_DATA                                                  <array>
    9    22      > JMP                                                      ->2
         23    >   FE_FREE                                                  $5
   26    24      > RETURN                                                   null

End of function __construct

Function find:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 4, Position 2 = 7
Branch analysis from position: 4
2 jumps found. (Code = 77) Position 1 = 16, Position 2 = 35
Branch analysis from position: 16
2 jumps found. (Code = 78) Position 1 = 17, Position 2 = 35
Branch analysis from position: 17
2 jumps found. (Code = 43) Position 1 = 25, Position 2 = 34
Branch analysis from position: 25
1 jumps found. (Code = 42) Position 1 = 16
Branch analysis from position: 16
Branch analysis from position: 34
Branch analysis from position: 35
2 jumps found. (Code = 43) Position 1 = 41, Position 2 = 44
Branch analysis from position: 41
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 44
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 35
Branch analysis from position: 7
filename:       /in/36R1K
function name:  find
number of ops:  58
compiled vars:  !0 = $start, !1 = $end, !2 = $initStartNode, !3 = $nodes, !4 = $startLength, !5 = $weight, !6 = $node, !7 = $currentLength, !8 = $nextNode
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   28     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV_INIT                                        !2      <true>
   30     3      > JMPZ                                                     !2, ->7
   31     4    >   INIT_METHOD_CALL                                         'initStartNode'
          5        SEND_VAR_EX                                              !0
          6        DO_FCALL                                      0          
   34     7    >   INIT_METHOD_CALL                                         'getNextNodes'
          8        SEND_VAR_EX                                              !0
          9        DO_FCALL                                      0  $10     
         10        ASSIGN                                                   !3, $10
   36    11        INIT_METHOD_CALL                                         'getLength'
         12        SEND_VAR_EX                                              !0
         13        DO_FCALL                                      0  $12     
         14        ASSIGN                                                   !4, $12
   37    15      > FE_RESET_R                                       $14     !3, ->35
         16    > > FE_FETCH_R                                       ~15     $14, !5, ->35
         17    >   ASSIGN                                                   !6, ~15
   39    18        INIT_METHOD_CALL                                         'getLength'
         19        SEND_VAR_EX                                              !6
         20        DO_FCALL                                      0  $17     
         21        ASSIGN                                                   !7, $17
   40    22        ADD                                              ~19     !4, !5
         23        IS_SMALLER                                               ~19, !7
         24      > JMPZ                                                     ~20, ->34
   41    25    >   INIT_METHOD_CALL                                         'setLength'
         26        SEND_VAR_EX                                              !6
         27        ADD                                              ~21     !4, !5
         28        SEND_VAL_EX                                              ~21
         29        DO_FCALL                                      0          
   42    30        INIT_METHOD_CALL                                         'setFromNode'
         31        SEND_VAR_EX                                              !6
         32        SEND_VAR_EX                                              !0
         33        DO_FCALL                                      0          
   37    34    > > JMP                                                      ->16
         35    >   FE_FREE                                                  $14
   46    36        INIT_METHOD_CALL                                         'getNextMinimumNode'
         37        DO_FCALL                                      0  $24     
         38        ASSIGN                                                   !8, $24
   48    39        TYPE_CHECK                                    2          !8
         40      > JMPZ                                                     ~26, ->44
   49    41    >   INIT_METHOD_CALL                                         'getNodes'
         42        DO_FCALL                                      0  $27     
         43      > RETURN                                                   $27
   52    44    >   INIT_METHOD_CALL                                         'setFinal'
         45        SEND_VAR_EX                                              !8
         46        DO_FCALL                                      0          
   54    47        INIT_METHOD_CALL                                         'find'
         48        SEND_VAR_EX                                              !8
         49        SEND_VAR_EX                                              !1
         50        SEND_VAL_EX                                              <false>
         51        DO_FCALL                                      0          
   57    52        INIT_FCALL                                               'var_dump'
         53        INIT_METHOD_CALL                                         'getNodes'
         54        DO_FCALL                                      0  $30     
         55        SEND_VAR                                                 $30
         56        DO_ICALL                                                 
   59    57      > RETURN                                                   null

End of function find

Function getnextminimumnode:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 77) Position 1 = 6, Position 2 = 20
Branch analysis from position: 6
2 jumps found. (Code = 78) Position 1 = 7, Position 2 = 20
Branch analysis from position: 7
2 jumps found. (Code = 43) Position 1 = 10, Position 2 = 11
Branch analysis from position: 10
1 jumps found. (Code = 42) Position 1 = 6
Branch analysis from position: 6
Branch analysis from position: 11
2 jumps found. (Code = 43) Position 1 = 17, Position 2 = 19
Branch analysis from position: 17
1 jumps found. (Code = 42) Position 1 = 6
Branch analysis from position: 6
Branch analysis from position: 19
Branch analysis from position: 20
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 20
filename:       /in/36R1K
function name:  getNextMinimumNode
number of ops:  23
compiled vars:  !0 = $nodes, !1 = $min, !2 = $minNode, !3 = $data, !4 = $node, !5 = $nodeLength
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   63     0  E >   INIT_METHOD_CALL                                         'getNodes'
          1        DO_FCALL                                      0  $6      
          2        ASSIGN                                                   !0, $6
   65     3        ASSIGN                                                   !1, INF
   66     4        ASSIGN                                                   !2, null
   67     5      > FE_RESET_R                                       $10     !0, ->20
          6    > > FE_FETCH_R                                       ~11     $10, !3, ->20
          7    >   ASSIGN                                                   !4, ~11
   68     8        FETCH_DIM_R                                      ~13     !3, 'final'
          9      > JMPZ                                                     ~13, ->11
   69    10    > > JMP                                                      ->6
   72    11    >   INIT_METHOD_CALL                                         'getLength'
         12        SEND_VAR_EX                                              !4
         13        DO_FCALL                                      0  $14     
         14        ASSIGN                                                   !5, $14
   73    15        IS_SMALLER                                               !5, !1
         16      > JMPZ                                                     ~16, ->19
   74    17    >   ASSIGN                                                   !1, !5
   75    18        ASSIGN                                                   !2, !4
   67    19    > > JMP                                                      ->6
         20    >   FE_FREE                                                  $10
   79    21      > RETURN                                                   !2
   80    22*     > RETURN                                                   null

End of function getnextminimumnode

Function initstartnode:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  initStartNode
number of ops:  13
compiled vars:  !0 = $node
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   82     0  E >   RECV                                             !0      
   84     1        INIT_METHOD_CALL                                         'setLength'
          2        SEND_VAR_EX                                              !0
          3        SEND_VAL_EX                                              0
          4        DO_FCALL                                      0          
   85     5        INIT_METHOD_CALL                                         'setFromNode'
          6        SEND_VAR_EX                                              !0
          7        SEND_VAL_EX                                              '-'
          8        DO_FCALL                                      0          
   86     9        INIT_METHOD_CALL                                         'setFinal'
         10        SEND_VAR_EX                                              !0
         11        DO_FCALL                                      0          
   87    12      > RETURN                                                   null

End of function initstartnode

Function getnextnodes:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  getNextNodes
number of ops:  5
compiled vars:  !0 = $node
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   89     0  E >   RECV                                             !0      
   91     1        FETCH_OBJ_R                                      ~1      'graph'
          2        FETCH_DIM_R                                      ~2      ~1, !0
          3      > RETURN                                                   ~2
   92     4*     > RETURN                                                   null

End of function getnextnodes

Function setlength:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  setLength
number of ops:  7
compiled vars:  !0 = $node, !1 = $value
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   94     0  E >   RECV                                             !0      
          1        RECV                                             !1      
   96     2        FETCH_OBJ_W                                      $2      'nodes'
          3        FETCH_DIM_W                                      $3      $2, !0
          4        ASSIGN_DIM                                               $3, 'L'
          5        OP_DATA                                                  !1
   97     6      > RETURN                                                   null

End of function setlength

Function getlength:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  getLength
number of ops:  6
compiled vars:  !0 = $node
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   99     0  E >   RECV                                             !0      
  101     1        FETCH_OBJ_R                                      ~1      'nodes'
          2        FETCH_DIM_R                                      ~2      ~1, !0
          3        FETCH_DIM_R                                      ~3      ~2, 'L'
          4      > RETURN                                                   ~3
  102     5*     > RETURN                                                   null

End of function getlength

Function setfromnode:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  setFromNode
number of ops:  7
compiled vars:  !0 = $node, !1 = $value
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  104     0  E >   RECV                                             !0      
          1        RECV                                             !1      
  106     2        FETCH_OBJ_W                                      $2      'nodes'
          3        FETCH_DIM_W                                      $3      $2, !0
          4        ASSIGN_DIM                                               $3, 'Q'
          5        OP_DATA                                                  !1
  107     6      > RETURN                                                   null

End of function setfromnode

Function setfinal:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  setFinal
number of ops:  6
compiled vars:  !0 = $node
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  109     0  E >   RECV                                             !0      
  111     1        FETCH_OBJ_W                                      $1      'nodes'
          2        FETCH_DIM_W                                      $2      $1, !0
          3        ASSIGN_DIM                                               $2, 'final'
          4        OP_DATA                                                  <true>
  112     5      > RETURN                                                   null

End of function setfinal

Function getgraph:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  getGraph
number of ops:  3
compiled vars:  none
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  116     0  E >   FETCH_OBJ_R                                      ~0      'graph'
          1      > RETURN                                                   ~0
  117     2*     > RETURN                                                   null

End of function getgraph

Function getnodes:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/36R1K
function name:  getNodes
number of ops:  3
compiled vars:  none
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  120     0  E >   FETCH_OBJ_R                                      ~0      'nodes'
          1      > RETURN                                                   ~0
  121     2*     > RETURN                                                   null

End of function getnodes

End of class Graph.

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
182.75 ms | 1416 KiB | 15 Q