<commit_before><?php

namespace Fhaculty\Graph\Algorithm\Search;

use Fhaculty\Graph\Vertex;
use Fhaculty\Graph\Graph;

class BreadthFirst extends Base{
    /**
     *
     * @return Vertex[]
     */
    public function getVertices(){
        $queue = array($this->startVertex);
        $mark = array($this->startVertex->getId() => true);                            //to not add vertices twice in array visited
        $visited = array();                                                        //visited vertices
        
        do{
            $t = array_shift($queue);                                                // get first from queue
            $visited[$t->getId()]= $t;                                                //save as visited

            $vertices = $this->getVerticesAdjacent($t);                                //get next vertices
            foreach($vertices as $id=>$vertex){
                if(!isset($mark[$id])){                                                    //if not "toughed" before
                    $queue[] = $vertex;                                                        //add to queue
                    $mark[$id] = true;                                                        //and mark
                }
            }

        }while($queue);                                                            //untill queue is empty

        return $visited;
    }

    /**
     * Get a path from algorithms $startVertex to given $destination vertex
     *
     * @param Vertex $destinationVertex
     * @return Graph with lowest vertex count between start and destination OR NUll if no path exists
     */
    public function getGraphPathTo(Vertex $destinationVertex){
        $queue = array($this->startVertex);                                         //Start vertex
        $mark = array($this->startVertex->getId() => true);                            //to not add vertices twice in array visited
         
        $deepSearchThree = $this->startVertex->getGraph()->createGraphCloneEdgeless();   //create copy of graph without edges
        $visited = array();                                                        //visited vertices

        $pathToDestinationVertexFound = false;

        do{
            $t = array_shift($queue);                                            //get first from queue
            $visited[$t->getId()]= $t;                                            //save as visited

            $vertices = $this->getVerticesAdjacent($t);                                //get next vertices
            foreach($vertices as $id=>$vertex){
                if(!isset($mark[$id])){                                            //if not "toughed" before
                    $queue[] = $vertex;                                            //add to queue
                    $mark[$id] = true;                                            //and mark
                     
                    $oldEdgeArray=$t->getEdgesTo($vertex);
                    $oldEdge=array_shift($oldEdgeArray);

                    $newEdge=$deepSearchThree->createEdgeClone($oldEdge);

                }
            }

            if(isset($mark[$destinationVertex->getId()])){                               //stop if destination node is reached
                $queue=null;
                $pathToDestinationVertexFound = true;
            }

        } while($queue);                                                            //untill queue is empty
         
        if(!$pathToDestinationVertexFound){
            return NULL;
        }

        //remove not used edges
        $destinationVertexInNewGraph = $deepSearchThree->getVertex($destinationVertex->getId());
         
         
        // create path
        $path = new Graph();
        $path->createVertexClone($destinationVertex);                 //add clone of destination vertex to path
        $currentVertex=$destinationVertexInNewGraph;

        //run over the tree
        do{                                                                     // run from the buttom to top to the tree and add the predecessor until the startvertex is reached
            $edge=$currentVertex->getEdgesIn();                            // can only one because of the deepsearch tree

            $upperVertex=$edge[0]->getVertexFromTo($currentVertex);
            $path->createVertexClone($upperVertex);                             // clone upper vertex to graph
            $path->createEdgeClone($edge[0]);                                   // clone connecting edge
             
            $currentVertex=$upperVertex;

        } while($currentVertex->getId()!==$this->startVertex->getId());
        
        return $path;
    }
}<commit_msg>Remove now-obsolete search for shortest path (see ShortestPath)<commit_after><?php

namespace Fhaculty\Graph\Algorithm\Search;

use Fhaculty\Graph\Vertex;
use Fhaculty\Graph\Graph;

class BreadthFirst extends Base{
    /**
     *
     * @return Vertex[]
     */
    public function getVertices(){
        $queue = array($this->startVertex);
        $mark = array($this->startVertex->getId() => true);                            //to not add vertices twice in array visited
        $visited = array();                                                        //visited vertices
        
        do{
            $t = array_shift($queue);                                                // get first from queue
            $visited[$t->getId()]= $t;                                                //save as visited

            $vertices = $this->getVerticesAdjacent($t);                                //get next vertices
            foreach($vertices as $id=>$vertex){
                if(!isset($mark[$id])){                                                    //if not "toughed" before
                    $queue[] = $vertex;                                                        //add to queue
                    $mark[$id] = true;                                                        //and mark
                }
            }

        }while($queue);                                                            //untill queue is empty

        return $visited;
    }
}
{'fraction_non_alphanumeric': 0.09691985163683277, 'fraction_numerical': 0.0003225286244154169, 'mean_word_length': 1.0221715030974894, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 49, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5102453', 'n_tokens_mistral': 1294, 'n_tokens_neox': 1261, 'n_words': 339}