3
\$\begingroup\$

Another recreational implementation for review! As a side comment, for some reason I just feel like if (visited.Contains(vertex)) { .. } isn't necessary, as this example doesn't break from not including it in either algorithm. Any feedback is welcome!

Graph.cs

using System;
using System.Collections.Generic;

namespace CodeReview
{
    public class Graph<T>
    {
        public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

        public Graph() { }

        public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
        {
            foreach (var vertex in vertices)
            {
                AddVertex(vertex);
            }

            foreach (var edge in edges)
            {
                AddEdge(edge);
            }
        }

        public void AddVertex(T vertex)
        {
            AdjacencyList[vertex] = new HashSet<T>();
        }

        public void AddEdge(Tuple<T, T> edge)
        {
            if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2))
            {
                AdjacencyList[edge.Item1].Add(edge.Item2);
                AdjacencyList[edge.Item2].Add(edge.Item1);
            }
        }
    }
}

Program.cs

using System;
using System.Collections.Generic;

namespace CodeReview
{
    class Program
    {
        public static void Main(string[] args)
        {
            var vertices = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            var edges = new[] {
                Tuple.Create(1, 2),
                Tuple.Create(1, 3),
                Tuple.Create(2, 4),
                Tuple.Create(3, 5),
                Tuple.Create(3, 6),
                Tuple.Create(4, 7),
                Tuple.Create(5, 7),
                Tuple.Create(5, 8),
                Tuple.Create(5, 6),
                Tuple.Create(8, 9),
                Tuple.Create(9, 10)
            };

            var graph = new Graph<int>(vertices, edges);

            Console.WriteLine(string.Join(", ", BFS(graph, 1)));
            // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

            Console.WriteLine(string.Join(", ", DFS(graph, 1)));
            // 1, 3, 6, 5, 8, 9, 10, 7, 4, 2

            Console.ReadKey();
        }

        // using HashSet for O(1) access and loop operations
        public static HashSet<T> BFS<T>(Graph<T> graph, T start)
        {
            var visited = new HashSet<T>();

            if (!graph.AdjacencyList.ContainsKey(start))
            {
                return visited;
            }

            var queue = new Queue<T>();
            queue.Enqueue(start);

            while (queue.Count > 0)
            {
                var vertex = queue.Dequeue();

                if (visited.Contains(vertex))
                {
                    continue;
                }

                visited.Add(vertex);

                foreach (var neighbor in graph.AdjacencyList[vertex])
                {
                    if (!visited.Contains(neighbor))
                    {
                        queue.Enqueue(neighbor);
                    }
                }
            }

            return visited;
        }

        // using HashSet for O(1) access and loop operations
        public static HashSet<T> DFS<T>(Graph<T> graph, T start)
        {
            var visited = new HashSet<T>();

            if (!graph.AdjacencyList.ContainsKey(start))
            {
                return visited;
            }

            var stack = new Stack<T>();
            stack.Push(start);

            while (stack.Count > 0)
            {
                var vertex = stack.Pop();

                if (visited.Contains(vertex))
                {
                    continue;
                }

                visited.Add(vertex);

                foreach (var neighbor in graph.AdjacencyList[vertex])
                {
                    if (!visited.Contains(neighbor))
                    {
                        stack.Push(neighbor);
                    }
                }
            }

            return visited;
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

First off, I think the static search methods should not be static but rather methods in the Graph class. Both methods look very similar, other than the fact that one uses a Queue and the other a Stack. In the interest of being DRY this can be modified using an interface.

I also find it needless to pass in the vertices along with edges. By virtue of passing in an edge, you know your vertices.

Since AdjacencyList is public, I suggest making it an IDictionary.

An interface for a searcher is simple:

interface IEdgeSearcher<T>
{
    void Add(T item);
    int Count { get; }
    T GetNext();
}

The 2 different search classes implementing the interface could be private to Graph:

private class SearchQueue<TSearch> : IEdgeSearcher<TSearch>
{
    private Queue<TSearch> _queue;
    private SearchQueue() { _queue = new Queue<TSearch>(); }
    public static SearchQueue<T> Create() => new SearchQueue<T>();
    public void Add(TSearch item) { _queue.Enqueue(item); }
    public int Count => _queue.Count;
    public TSearch GetNext() => _queue.Dequeue();
}

private class SearchStack<TSearch> : IEdgeSearcher<TSearch>
{
    private Stack<TSearch> _stack;
    private SearchStack() { _stack = new Stack<TSearch>(); }
    public static SearchStack<TSearch> Create() => new SearchStack<TSearch>();
    public void Add(TSearch item) { _stack.Push(item); }
    public int Count => _stack.Count;
    public TSearch GetNext() => _stack.Pop();
}

Back in Graph you would call a respective searcher with one line:

public HashSet<T> BreadthFirstSearch(T start) => Search(SearchQueue<T>.Create(), start);
public HashSet<T> DepthFirstSearch(T start) => Search(SearchStack<T>.Create(), start);

Those are public, but call a new private method that expects the interface:

private HashSet<T> Search(IEdgeSearcher<T> searcher, T start)
{
    var visited = new HashSet<T>();

    if (!AdjacencyList.ContainsKey(start))
    {
        return visited;
    }

    searcher.Add(start);

    while (searcher.Count > 0)
    {
        var vertex = searcher.GetNext();

        visited.Add(vertex);

        foreach (var neighbor in AdjacencyList[vertex])
        {
            if (!visited.Contains(neighbor))
            {
                searcher.Add(neighbor);
            }
        }
    }

    return visited;
}

Bringing it all together, the modified Graph would look like:

public class Graph<T>
{
    public IDictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

    public Graph() { }

    public Graph(IEnumerable<Tuple<T, T>> edges)
    {
        foreach (var edge in edges)
        {
            AddEdge(edge);
        }
    }

    public void AddVertex(T vertex)
    {
        AdjacencyList[vertex] = new HashSet<T>();
    }

    public void AddEdge(Tuple<T, T> edge)
    {
        if (!AdjacencyList.ContainsKey(edge.Item1)) { AddVertex(edge.Item1); }
        if (!AdjacencyList.ContainsKey(edge.Item2)) { AddVertex(edge.Item2); }
        if (!AdjacencyList[edge.Item1].Contains(edge.Item2)) { AdjacencyList[edge.Item1].Add(edge.Item2);  }
        if (!AdjacencyList[edge.Item2].Contains(edge.Item1)) { AdjacencyList[edge.Item2].Add(edge.Item1); }
    }

    public HashSet<T> BreadthFirstSearch(T start) => Search(SearchQueue<T>.Create(), start);
    public HashSet<T> DepthFirstSearch(T start) => Search(SearchStack<T>.Create(), start);

    private HashSet<T> Search(IEdgeSearcher<T> searcher, T start)
    {
        var visited = new HashSet<T>();

        if (!AdjacencyList.ContainsKey(start))
        {
            return visited;
        }

        searcher.Add(start);

        while (searcher.Count > 0)
        {
            var vertex = searcher.GetNext();

            visited.Add(vertex);

            foreach (var neighbor in AdjacencyList[vertex])
            {
                if (!visited.Contains(neighbor))
                {
                    searcher.Add(neighbor);
                }
            }
        }

        return visited;
    }

    private class SearchQueue<TSearch> : IEdgeSearcher<TSearch>
    {
        private Queue<TSearch> _queue;
        private SearchQueue() { _queue = new Queue<TSearch>(); }
        public static SearchQueue<T> Create() => new SearchQueue<T>();
        public void Add(TSearch item) { _queue.Enqueue(item); }
        public int Count => _queue.Count;
        public TSearch GetNext() => _queue.Dequeue();
    }

    private class SearchStack<TSearch> : IEdgeSearcher<TSearch>
    {
        private Stack<TSearch> _stack;
        private SearchStack() { _stack = new Stack<TSearch>(); }
        public static SearchStack<TSearch> Create() => new SearchStack<TSearch>();
        public void Add(TSearch item) { _stack.Push(item); }
        public int Count => _stack.Count;
        public TSearch GetNext() => _stack.Pop();
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.