﻿// Traversal.cs
// Graph traversal algorithm implementations for GraphsLib.
//
// Licensed 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.


using System.Collections.Generic;

namespace GraphsLib
{
    public class Traversal
    {
        public static Node[] BreadthFirst(Node start)
        {
            Queue<Node> q = new Queue<Node>(), result = new Queue<Node>();
            start.visited = true;
            q.Enqueue(start);
            result.Enqueue(start);

            while (q.Count > 0)
            {
                Node current = q.Dequeue();
                foreach (NodeLink link in current.neighbors)
                {
                    Node node = link.to;
                    if (!node.visited)
                    {
                        node.visited = true;
                        q.Enqueue(node);
                        result.Enqueue(node);
                    }
                }
            }

            Node[] r = new Node[result.Count];

            for (int i = 0, l = result.Count; i < l; ++i)
            {
                r[i] = result.Dequeue();
            }

            return r;
        }

        public static Node[] DepthFirst(Node start)
        {
            Stack<Node> q = new Stack<Node>(), result = new Stack<Node>();
            start.visited = true;
            q.Push(start);
            result.Push(start);

            while (q.Count > 0)
            {
                Node current = q.Pop();
                foreach (NodeLink link in current.neighbors)
                {
                    Node node = link.to;
                    if (!node.visited)
                    {
                        node.visited = true;
                        q.Push(node);
                        result.Push(node);
                    }
                }
            }

            Node[] r = new Node[result.Count];

            for (int i = 0, l = result.Count; i < l; ++i)
            {
                r[i] = result.Pop();
            }

            return r;
        }
    }
}
