CODEWITHSUNDEEP
phpgraphnodesdepth-first-search
user1114864
user1114864

Reputation: 1764

Find All Paths Between Two Nodes with DFS

For the past few days, I have been trying to find a way to count all of the non-cyclic paths between two nodes. I've been working with a breadth-first search and a depth-first search. I'm fairly sure either can accomplish this task. However, I've been struggling with how to adapt the DFS code below to find all possible paths between two nodes. I've tried a few different things (remembering nodes in array, recursion), but I haven't implemented them correctly and haven't been able to output the possible paths.

Ultimately, I would like return an array of arrays that contain all possible paths between two selected nodes. Is there any simple modification I could make to accomplish this? The code below is what I'm currently working with.

function init(&$visited, &$graph){
  foreach ($graph as $key => $vertex) {
    $visited[$key] = 0;
  }
}

/* DFS args
$graph = Node x Node sociomatrix
$start = starting node
$end = target node (currently not used)
$visited = list of visited nodes
$list = hold keys' corresponding node values, for printing path;
*/

function depth_first(&$graph, $start, $end, $visited, $list){

  // create an empty stack
  $s = array();

  // put the starting node on the stack
  array_push($s, $start);

  // note that we visited the start node
  $visited[$start] = 1;

  // do the following while there are items on the stack
  while (count($s)) {

    // remove the last item from the stack
    $t = array_pop($s);

    // move through all connections
    foreach ($graph[$t] as $key => $vertex) {

      // if node hasn't been visited and there's a connection
      if (!$visited[$key] && $vertex == 1) {

        // note that we visited this node
        $visited[$key] = 1;

        // push key onto stack
        array_push($s, $key);

        // print the node we're at              
        echo $list[$key];                   
      }             
    }           
  }
}

// example usage
$visited = array();
$visited = init($visited, $sym_sociomatrix);
breadth_first($sym_sociomatrix, 1, 3, $visited, $list);

Upvotes: 1

Views: 2895

Answers (1)

TemplateRex
TemplateRex

Reputation: 70526

Assuming you have a framework / library to create a graph data structure and to traverse it, you could do a backtracking depth-first search with an early return if you get a cycle. Cycle detection is easy if you store the path from the starting node. In C-style pseudo-code (sorry don't know PHP, or if it is capable of recursion):

void DFS(Vertex current, Vertex goal, List<Vertex> path) {
  // avoid cycles
  if (contains(path, current)
     return;

  // got it!
  if (current == goal)) {
     print(path);
     return;
  }

  // keep looking
  children = successors(current); // optionally sorted from low to high cost
  for(child: children)          
      DFS(child, add_path(path, child));      
}

and you can then call it as DFS(start, goal, List<Vertex>(empty))

Upvotes: 0

Related Questions