<commit_before>﻿using System;
using System.Collections.Generic;
using Basics.Structures;
using Basics.Structures.Graphs;

namespace Basics.Algorithms.Graphs
{
    public static class DepthFirstSearch
    {
        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex) where T : IEquatable<T>
        {
            return graph.DFS(startVertex, v => { /* Do nothing */ });
        }

        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex, Action<T> lastVertexAction) where T : IEquatable<T>
        {
            var visited = new HashSet<T>();
            var stack = new StackOnList<T>();
            stack.Push(startVertex);
            T previous = startVertex;
            while (!stack.IsEmpty)
            {
                var current = stack.Pop();
                if (!visited.Contains(current))
                {
                    visited.Add(current);
                    // preserve edges order
                    var edges = new List<Edge<T>>(graph.EdgesOf(current));
                    for (int i = edges.Count - 1; i >= 0; i--)
                    {
                        stack.Push(edges[i].Target);
                    }
                    if (edges.Count == 0)
                    {
                        lastVertexAction(current);
                    }
                    yield return current;
                }
                else
                {
                    lastVertexAction(previous);
                }
                previous = current;
            }
        }
    }
}<commit_msg>Extend DFS with control over visited vertices collection<commit_after>﻿using System;
using System.Collections.Generic;
using Basics.Structures;
using Basics.Structures.Graphs;

namespace Basics.Algorithms.Graphs
{
    public static class DepthFirstSearch
    {
        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex) where T : IEquatable<T>
        {
            return graph.DFS(startVertex, v => { /* Do nothing */ });
        }

        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex, HashSet<T> visitedVertices) where T : IEquatable<T>
        {
            return graph.DFS(startVertex, v => { /* Do nothing */ }, visitedVertices);
        }

        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex, Action<T> lastVertexAction) where T : IEquatable<T>
        {
            return graph.DFS(startVertex, lastVertexAction, new HashSet<T>());
        }

        public static IEnumerable<T> DFS<T>(this IGraph<T> graph, T startVertex, Action<T> lastVertexAction, HashSet<T> visitedVertices) where T : IEquatable<T>
        {
            var stack = new StackOnList<T>();
            stack.Push(startVertex);
            T previous = startVertex;
            while (!stack.IsEmpty)
            {
                var current = stack.Pop();
                if (!visitedVertices.Contains(current))
                {
                    visitedVertices.Add(current);
                    // preserve edges order
                    var edges = new List<Edge<T>>(graph.EdgesOf(current));
                    for (int i = edges.Count - 1; i >= 0; i--)
                    {
                        stack.Push(edges[i].Target);
                    }
                    if (edges.Count == 0)
                    {
                        lastVertexAction(current);
                    }
                    yield return current;
                }
                else
                {
                    lastVertexAction(previous);
                }
                previous = current;
            }
        }
    }
}
{'fraction_non_alphanumeric': 0.09980858627290129, 'fraction_numerical': 0.0016406890894175555, 'mean_word_length': 1.39554682383759, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4894430', 'n_tokens_mistral': 976, 'n_tokens_neox': 926, 'n_words': 222}