current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

I was asked to implement a graph and BFS and DFS.

Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations? 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class Graph
    {
        public List<Node> list;
        public Graph()
        {
            list = new List<Node>();
        }
    }

    public class Node
    {
        public int Index { get; set; }
        public List<Node> neighbors;
        public Node(int index)
        {
            Index = index;
            neighbors = new List<Node>();
        }
        public void AddNeighbor(int index)
        {
            neighbors.Add(new Node(index));
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class BFS
    {
        public BFS()
        {
              Graph graph = new Graph();
              graph.list.Add(new Node(0));
              graph.list.ElementAt<Node>(0).AddNeighbor(1);
              graph.list.ElementAt<Node>(0).AddNeighbor(2);
              graph.list.ElementAt<Node>(0).neighbors.ElementAt<Node>(0).AddNeighbor(3);
              GraphTraverseBFS(graph);
        }
        public void GraphTraverseBFS(Graph graph)
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(graph.list[0]);
            while(queue.Count > 0)
            {
                Node tempNode = queue.Dequeue();
                Console.WriteLine("Node number: " +tempNode.Index);
                foreach (var item in tempNode.neighbors)
                {
                    queue.Enqueue(item);
                }
            }
        }
    }    
}



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class DFS
    {

        public Graph graph { get; set; }
        public DFS()
        {
              graph = new Graph();

              graph.list.Add(new Node(0));
              graph.list.ElementAt<Node>(0).AddNeighbor(1);
              graph.list.ElementAt<Node>(0).AddNeighbor(2);
              graph.list.ElementAt<Node>(0).neighbors.ElementAt<Node>(0).AddNeighbor(3);
              GraphTraverseDFS(graph);
        }

        public void GraphTraverseDFS(Graph graph)
        {
            Stack<Node> stack = new Stack<Node>();
            stack.Push(graph.list[0]);
            while (stack.Count != 0)
            {
                Node tempNode = stack.Pop();
                Console.WriteLine("Node number: " + tempNode.Index);
                var negibours = tempNode.neighbors;
                foreach (var item in negibours)
                {
                    stack.Push(item);
                }
            }
        }
    }
}
share|improve this question

1 Answer 1

up vote 4 down vote accepted

Let's take a step back and consider the API.

Suppose I want to test the BFS traversal on different graphs.

To call GraphTraverseBFS I need to first create a BFS object. But the BFS constructor creates its own graph and runs GraphTraverseBFS on that. There is no clean way for me to just test it on my own graph.

So let's say that's fixed. Now I want to write some unit tests for GraphTraverseBFS. I can't currently do this without redirecting where the output messages are written to, and then parsing the output. This is more work than I want to do. Ideally I would be able to write something like

CollectionAssert.AreEqual(new[] { 0, 1, 2, 3 }, BFS.Traverse(graph));

The same comments hold for DFS.

List<T> is (generally) an implementation detail.

Graph has a public field List<Node> list. The fact that you're storing nodes in a List is an implementation detail, and should not be exposed to users of this code.

  • The user now has full access to the methods of List, and can manipulate the list however they want. This is more power than they should have.

  • The user can reassign the field, e.g. graph.list = null.

  • It locks you in to your choice of graph representation, as the user may write code that depends on list being a List.

Similar comments hold for Node.neighbors.

One pattern I like for letting the user iterate over a collection, without exposing the choice of implementation is to

  • Have a private readonly field with your choice of collection type (List, HashSet, etc)

  • Have a public IEnumerable<T> read-only property that exposes the collection for iteration

In code, it looks like this

public class Graph
{
    private readonly List<Node> nodes = new List<Node>();

    public IEnumerable<Node> Nodes
    {
        get { return this.nodes; }
    }

    ...
}

This might not be entirely suitable for you needs, but this is the sort of API I would suggest

public class Graph
{
    // Creates a new graph with `count` vertices.
    public Graph(int count)

    public IEnumerable<int> GetNeighbors(int node);

    public void AddEdge(int n, int m);
}

public static class BFS
{
    public static IEnumerable<int> Traverse(Graph graph, int startNode = 0);
}

public static class DFS
{
    public static IEnumerable<int> Traverse(Graph graph, int startNode = 0);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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