<commit_before>package org.apache.commons.graph.visit;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import static org.apache.commons.graph.utils.Edges.getConnectedVertex;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.graph.DirectedGraph;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;

/**
 * Contains different implementations of Graph visitor algorithms.
 */
public final class Visit
{

    /**
     * Breadth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @return the breadth first search tree
     */
    public final <V extends Vertex, E extends Edge<V>> Graph<V, E> breadthFirstSearch( Graph<V, E> graph, V source )
    {
        breadthFirstSearch( graph, source, null );
        return null;
    }

    /**
     * Breadth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @param handler the handler intercepts visit actions
     */
    public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source,
                                                                                GraphVisitHandler<V, E> handler )
    {
        if ( graph == null )
        {
            throw new IllegalArgumentException( "Graph has to be visited can not be null." );
        }
        if ( source == null )
        {
            throw new IllegalArgumentException( "Root node the search begins from can not be null." );
        }

        if ( handler != null )
        {
            handler.discoverGraph( graph );
        }

        LinkedList<V> vertexQueue = new LinkedList<V>();
        vertexQueue.add( source );

        Set<V> visitedVetices = new HashSet<V>();
        visitedVetices.add( source );

        while ( !vertexQueue.isEmpty() )
        {
            V v = vertexQueue.remove();

            if ( handler != null )
            {
                handler.discoverVertex( v );
            }

            Set<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
                                                              : graph.getEdges( v );
            for ( E e : edges )
            {
                V w = getConnectedVertex( v, e );

                if ( visitedVetices.add( w ) )
                {
                    if ( handler != null )
                    {
                        handler.discoverEdge( e );
                    }

                    vertexQueue.addFirst( v );

                    if ( handler != null )
                    {
                        handler.finishEdge( e );
                    }
                }
            }

            if ( handler != null )
            {
                handler.finishVertex( v );
            }
        }

        if ( handler != null )
        {
            handler.finishGraph( graph );
        }
    }

    /**
     * Depth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @return the depth first search tree
     */
    public final <V extends Vertex, E extends Edge<V>> Graph<V, E> depthFirstSearch( Graph<V, E> graph, V source )
    {
        depthFirstSearch( graph, source, null );
        return null;
    }

    /**
     * Depth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @param handler the handler intercepts visit actions
     */
    public final <V extends Vertex, E extends Edge<V>> void depthFirstSearch( Graph<V, E> graph, V source,
                                                                              GraphVisitHandler<V, E> handler )
    {
        if ( graph == null )
        {
            throw new IllegalArgumentException( "Graph has to be visited can not be null." );
        }
        if ( source == null )
        {
            throw new IllegalArgumentException( "Root node the search begins from can not be null." );
        }

        if ( handler != null )
        {
            handler.discoverGraph( graph );
        }

        Stack<V> vertexStack = new Stack<V>();
        vertexStack.push( source );

        Set<V> visitedVetices = new HashSet<V>();
        visitedVetices.add( source );

        while ( !vertexStack.isEmpty() )
        {
            V v = vertexStack.pop();

            if ( handler != null )
            {
                handler.discoverVertex( v );
            }

            Set<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
                                                              : graph.getEdges( v );
            for ( E e : edges )
            {
                V w = getConnectedVertex( v, e );

                if ( visitedVetices.add( w ) )
                {
                    if ( handler != null )
                    {
                        handler.discoverEdge( e );
                    }

                    vertexStack.push( w );

                    if ( handler != null )
                    {
                        handler.finishEdge( e );
                    }
                }
            }

            if ( handler != null )
            {
                handler.finishVertex( v );
            }
        }

        if ( handler != null )
        {
            handler.finishGraph( graph );
        }
    }

    /**
     * Hidden constructor, this class can't be instantiated
     */
    private Visit()
    {
        // do nothing
    }

}
<commit_msg>default (breadth|depht)firstSearch algoritms produce now, as output, the search tree<commit_after>package org.apache.commons.graph.visit;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import static org.apache.commons.graph.utils.Edges.getConnectedVertex;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.graph.DirectedGraph;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;

/**
 * Contains different implementations of Graph visitor algorithms.
 */
public final class Visit
{

    /**
     * Breadth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @return the breadth first search tree
     */
    public final <V extends Vertex, E extends Edge<V>> Graph<V, E> breadthFirstSearch( Graph<V, E> graph, V source )
    {
        VisitGraphBuilder<V, E> visitGraphBuilder = new VisitGraphBuilder<V, E>();
        breadthFirstSearch( graph, source, visitGraphBuilder );
        return visitGraphBuilder.getVisitGraph();
    }

    /**
     * Breadth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @param handler the handler intercepts visit actions
     */
    public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source,
                                                                                GraphVisitHandler<V, E> handler )
    {
        if ( graph == null )
        {
            throw new IllegalArgumentException( "Graph has to be visited can not be null." );
        }
        if ( source == null )
        {
            throw new IllegalArgumentException( "Root node the search begins from can not be null." );
        }

        if ( handler != null )
        {
            handler.discoverGraph( graph );
        }

        LinkedList<V> vertexQueue = new LinkedList<V>();
        vertexQueue.add( source );

        Set<V> visitedVetices = new HashSet<V>();
        visitedVetices.add( source );

        while ( !vertexQueue.isEmpty() )
        {
            V v = vertexQueue.remove();

            if ( handler != null )
            {
                handler.discoverVertex( v );
            }

            Set<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
                                                              : graph.getEdges( v );
            for ( E e : edges )
            {
                V w = getConnectedVertex( v, e );

                if ( visitedVetices.add( w ) )
                {
                    if ( handler != null )
                    {
                        handler.discoverEdge( e );
                    }

                    vertexQueue.addFirst( v );

                    if ( handler != null )
                    {
                        handler.finishEdge( e );
                    }
                }
            }

            if ( handler != null )
            {
                handler.finishVertex( v );
            }
        }

        if ( handler != null )
        {
            handler.finishGraph( graph );
        }
    }

    /**
     * Depth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @return the depth first search tree
     */
    public final <V extends Vertex, E extends Edge<V>> Graph<V, E> depthFirstSearch( Graph<V, E> graph, V source )
    {
        VisitGraphBuilder<V, E> visitGraphBuilder = new VisitGraphBuilder<V, E>();
        depthFirstSearch( graph, source, visitGraphBuilder );
        return visitGraphBuilder.getVisitGraph();
    }

    /**
     * Depth-first search algorithm implementation.
     *
     * @param <V> the Graph vertices type
     * @param <E> the Graph edges type
     * @param graph the Graph instance has to be visited
     * @param source the root node the search begins from
     * @param handler the handler intercepts visit actions
     */
    public final <V extends Vertex, E extends Edge<V>> void depthFirstSearch( Graph<V, E> graph, V source,
                                                                              GraphVisitHandler<V, E> handler )
    {
        if ( graph == null )
        {
            throw new IllegalArgumentException( "Graph has to be visited can not be null." );
        }
        if ( source == null )
        {
            throw new IllegalArgumentException( "Root node the search begins from can not be null." );
        }

        if ( handler != null )
        {
            handler.discoverGraph( graph );
        }

        Stack<V> vertexStack = new Stack<V>();
        vertexStack.push( source );

        Set<V> visitedVetices = new HashSet<V>();
        visitedVetices.add( source );

        while ( !vertexStack.isEmpty() )
        {
            V v = vertexStack.pop();

            if ( handler != null )
            {
                handler.discoverVertex( v );
            }

            Set<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
                                                              : graph.getEdges( v );
            for ( E e : edges )
            {
                V w = getConnectedVertex( v, e );

                if ( visitedVetices.add( w ) )
                {
                    if ( handler != null )
                    {
                        handler.discoverEdge( e );
                    }

                    vertexStack.push( w );

                    if ( handler != null )
                    {
                        handler.finishEdge( e );
                    }
                }
            }

            if ( handler != null )
            {
                handler.finishVertex( v );
            }
        }

        if ( handler != null )
        {
            handler.finishGraph( graph );
        }
    }

    /**
     * Hidden constructor, this class can't be instantiated
     */
    private Visit()
    {
        // do nothing
    }

}

{'fraction_non_alphanumeric': 0.08788830715532286, 'fraction_numerical': 0.0005584642233856893, 'mean_word_length': 1.5328854314002829, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '10658', 'n_tokens_mistral': 3627, 'n_tokens_neox': 3486, 'n_words': 1231}