<commit_before>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Graphs.Library
{
    /// <summary>
    /// These problems don't care whether the graph is directed or not.
    /// </summary>
    public class GeneralGraphProblems
    {
        public static void PerformDfsItertatively(Graph g, Action<Node> processNode, int startingNode = 0)
        {
            if (g.Count == 0)
            {
                throw new ArgumentException("Graph is empty.");
            }
            Node root = g[startingNode];
            Stack<Node> stack = new Stack<Node>();

            root.Visited = true;
            stack.Push(root);
            Node temp;
            while (stack.Count > 0)
            {
                temp = stack.Pop();
                processNode(temp);

                foreach (Edge e in temp.Edges)
                {
                    if (!g[e.ToIndex].Visited)
                    {
                        g[e.ToIndex].Visited = true;
                        stack.Push(g[e.ToIndex]);
                    }
                }
            }
        }

        public static void PerformDfsRecursively(Graph g, Action<Node> processNode, int startingNode = 0)
        {
            if (g.Count == 0)
            {
                throw new ArgumentException("Graph is empty.");
            }

            Node n = g[startingNode];
            n.Visited = true;
            processNode(n);

            foreach (Edge e in n.Edges)
            {
                if (!g[e.ToIndex].Visited)
                {
                    PerformDfsRecursively(g, processNode, e.ToIndex);
                }
            }
        }
    }
}<commit_msg>added BFS which also returns shortest paths from starting node.<commit_after>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Graphs.Library
{
    /// <summary>
    /// These problems don't care whether the graph is directed or not.
    /// </summary>
    public class GeneralGraphProblems
    {
        public static void PerformDfsItertatively(Graph g, Action<Node> processNode, int startingNode = 0)
        {
            if (g.Count == 0)
            {
                throw new ArgumentException("Graph is empty.");
            }
            Node root = g[startingNode];
            Stack<Node> stack = new Stack<Node>();

            root.Visited = true;
            stack.Push(root);
            Node temp;
            while (stack.Count > 0)
            {
                temp = stack.Pop();
                processNode(temp);

                foreach (Edge e in temp.Edges)
                {
                    if (!g[e.ToIndex].Visited)
                    {
                        g[e.ToIndex].Visited = true;
                        stack.Push(g[e.ToIndex]);
                    }
                }
            }
        }

        public static void PerformDfsRecursively(Graph g, Action<Node> processNode, int startingNode = 0)
        {
            if (g.Count == 0)
            {
                throw new ArgumentException("Graph is empty.");
            }

            Node n = g[startingNode];
            n.Visited = true;
            processNode(n);

            foreach (Edge e in n.Edges)
            {
                if (!g[e.ToIndex].Visited)
                {
                    PerformDfsRecursively(g, processNode, e.ToIndex);
                }
            }
        }

        public static int[] PerformBfsAndReturnShortestPaths(Graph g, Action<Node> processNode, int startingNode = 0)
        {
            if (g.Count == 0)
            {
                throw new ArgumentException("Graph is empty.");
            }

            int[] paths = new int[g.Capacity];
            foreach (int p in paths)
            {
                paths[p] = -1;
            }
            Queue<Node> q = new Queue<Node>();
            Node n = g[startingNode];
            n.Visited = true;
            q.Enqueue(n);
            paths[startingNode] = startingNode;

            while (q.Count > 0)
            {
                n = q.Dequeue();
                processNode(n);
                foreach (Edge e in n.Edges)
                {
                    if (!g[e.ToIndex].Visited)
                    {
                        g[e.ToIndex].Visited = true;
                        q.Enqueue(g[e.ToIndex]);
                        paths[e.ToIndex] = n.Index;
                    }
                }
            }

            return paths;
        }
    }
}
{'fraction_non_alphanumeric': 0.09878154917319408, 'fraction_numerical': 0.0030461270670147957, 'mean_word_length': 1.1351602415234556, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 21, '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': '7139016', 'n_tokens_mistral': 1254, 'n_tokens_neox': 1170, 'n_words': 286}