3
\$\begingroup\$

I am implementing fundamental data structures in C#. I have written a weighted graph in Java so my main motivation here is to sharpen my skills in C#. I have tested with various cases and there seems to be no logical issues, but I know the language could be better utilized.

The Pathfinder method is not absolutely necessary, because the only difference with A* and Dijkstra is the Heuristic. The reason I have it is two-fold. There are various optimizations of A* that I would like to implement in the future. Thus I want it to be isolated. I also want to master delegates, hence the use of Func.

As always, I am open to any general or specific advice.

WeightedGraph

class WeightedGraph<T>
{
    List<WeightedEdge<T>> edges;
    List<Vertex<T>> vertices;
    public List<WeightedEdge<T>> Edges { get { return edges; } }

    public WeightedGraph(List<Vertex<T>> vertices, List<WeightedEdge<T>> edges)
    {
        this.vertices = vertices;
        this.edges = edges;
    }
    public void AddEdge(WeightedEdge<T> newEdge)
    {
        edges.Add(newEdge);
    }
    public void RemoveEdge(WeightedEdge<T> edge)
    {
        edges.Remove(edge);
    }

    /// <summary>
    /// Pathfinding algorithms available: Dijkstra and AStar
    /// </summary>
    public List<Vertex<T>> Pathfinder(Vertex<T> start, Vertex<T> end, string algorithm)
    {
        Func<Vertex<T>, Vertex<T>, List<Vertex<T>>> pathfinder;

        if (algorithm == "Dijkstra")
        {
            pathfinder = DijkstraSearch;
        }
        else if (algorithm == "AStar")
        {
            pathfinder = AStarSearch;
        }
        else
        {
            throw new ArgumentException("Pathfinding algorithm not available.");
        }
        return pathfinder(start, end);
    }


    public List<Vertex<T>> DijkstraSearch(Vertex<T> start, Vertex<T> end)
    {
        Dictionary<Vertex<T>, Vertex<T>> parentMap = new Dictionary<Vertex<T>, Vertex<T>>();
        PriorityQueue<Vertex<T>> priorityQueue = new PriorityQueue<Vertex<T>>();

        InitializeCosts(start);
        priorityQueue.Enqueue(start, start.Cost);

        Vertex<T> current;

        while (priorityQueue.Count > 0)
        {
            current = priorityQueue.Dequeue();

            if (!current.IsVisited)
            {
                current.IsVisited = true;

                if (current.Equals(end))
                {
                    break;
                }

                foreach (WeightedEdge<T> edge in current.Edges)
                {
                    Vertex<T> neighbor = edge.End;

                    double newCost = current.Cost + edge.Weight;
                    double neighborCost = neighbor.Cost;

                    if (newCost < neighborCost)
                    {
                        neighbor.Cost = newCost;
                        parentMap.Add(neighbor, current);
                        double priority = newCost;
                        priorityQueue.Enqueue(neighbor, priority);
                    }
                }
            }
        }
        List<Vertex<T>> path = ReconstructPath(parentMap, start, end);
        return path;
    }

    public List<Vertex<T>> AStarSearch(Vertex<T> start, Vertex<T> end)
    {
        Dictionary<Vertex<T>, Vertex<T>> parentMap = new Dictionary<Vertex<T>, Vertex<T>>();
        PriorityQueue<Vertex<T>> priorityQueue = new PriorityQueue<Vertex<T>>();

        InitializeCosts(start);
        priorityQueue.Enqueue(start, start.Cost);

        Vertex<T> current;

        while (priorityQueue.Count > 0)
        {
            current = priorityQueue.Dequeue();

            if (!current.IsVisited)
            {
                current.IsVisited = true;

                if (current.Equals(end))
                {
                    break;
                }

                foreach (WeightedEdge<T> edge in current.Edges)
                {
                    Vertex<T> neighbor = edge.End;

                    double newCost = current.Cost + edge.Weight;
                    double neighborCost = neighbor.Cost;

                    if (newCost < neighborCost)
                    {
                        neighbor.Cost = newCost;
                        parentMap.Add(neighbor, current);
                        double priority = newCost + Heuristic(neighbor, end);
                        priorityQueue.Enqueue(neighbor, priority);
                    }
                }
            }
        }
        List<Vertex<T>> path = ReconstructPath(parentMap, start, end);
        return path;
    }

    public double Heuristic(Vertex<T> vertexA, Vertex<T> vertexB)
    {
        return vertexA.Location.DistanceTo(vertexB.Location);
    }

    public void InitializeCosts(Vertex<T> start)
    {
        foreach (Vertex<T> vertex in vertices)
        {
            vertex.Cost = int.MaxValue;
        }

        start.Cost = 0;
    }

    public List<Vertex<T>> ReconstructPath(Dictionary<Vertex<T>, Vertex<T>> parentMap, Vertex<T> start, Vertex<T> end)
    {
        List<Vertex<T>> path = new List<Vertex<T>>();
        Vertex<T> current = end;

        while (current != start)
        {
            path.Add(current);
            current = parentMap[current];
        }

        path.Add(start);

        path.Reverse();
        return path;
    }

}

Vertex

class Vertex<T>
{
    List<Vertex<T>> neighbors;
    List<WeightedEdge<T>> edges;
    T value;

    public List<Vertex<T>> Neighbors { get { return neighbors; } }
    public List<WeightedEdge<T>> Edges { get { return edges; } }
    public Location Location { get; set; }
    public T Value { get { return value; } set { this.value = value; } }
    public bool IsVisited { get; set; }
    public int NeighborsCount { get { return neighbors.Count; } }
    public double Cost { get; set; }

    public Vertex(T value)
    {
        this.value = value;
        IsVisited = false;
        neighbors = new List<Vertex<T>>();
        edges = new List<WeightedEdge<T>>();
    }

    public Vertex(T value, List<Vertex<T>> neighbors)
    {
        this.value = value;
        IsVisited = false;
        this.neighbors = neighbors;
    }

    public void AddNeighbor(Vertex<T> vertex)
    {
        neighbors.Add(vertex);
    }
    public void AddEdge(WeightedEdge<T> edge)
    {
        edges.Add(edge);
    }

    public override string ToString()
    {
        StringBuilder allNeighbors = new StringBuilder("");
        allNeighbors.Append(value + ": ");

        foreach (Vertex<T> neighbor in neighbors)
        {
            allNeighbors.Append(neighbor.value + "  ");
        }

        return allNeighbors.ToString();
    }

}

WeightedEdge

class WeightedEdge<T>
{
    int weight;

    Vertex<T> start;
    Vertex<T> end;

    public int Weight { get { return weight; } }

    public Vertex<T> Start { get { return start; } }
    public Vertex<T> End { get { return end; } }

    public WeightedEdge(Vertex<T> start, Vertex<T> end, int weight)
    {
        this.start = start;
        this.end = end;
        this.weight = weight;
        start.AddNeighbor(end);
        start.AddEdge(this);
    }

    public override string ToString()
    {
        return string.Format("{0}--{1}-->{2}", start.Value, weight, end.Value);
    }
}
\$\endgroup\$
2
\$\begingroup\$

WeightedGraph

This class shoudln't implement any search algorithms. They need to be injected. Let's do this...

First you change the signature of the Pathfinder method to accept an interface instead of a magic string:

public List<Vertex<T>> Pathfinder<TSearchAlgorithm>(Vertex<T> start, Vertex<T> end) 
    where TSearchAlgorithm : ISearchAlgorithm, new()
{
    var searchAlgorithm = new TSearchAlgorithm();
    return searchAlgorithm.Search(start, end);      
}

you use the new() constraint to be able to create an instance of the generic argument that at the same time must implement the interface below that requires one method for searching:

interface ISearchAlgorithm
{ 
    List<Vertex<T>> Search<T>(Vertex<T> start, Vertex<T> end);
}

you implement this interface in two classes, one for each search algorithm (here only one):

class DijkstraSearchAlgorithm : ISearchAlgorithm
{
    public List<Vertex<T>> Search<T>(Vertex<T> start, Vertex<T> end)
    {
        ...
    }
}

now if you call it like this:

weightedGraph.Pathfinder<DijkstraSearchAlgorithm>(..., ...);

instead of magic strings real magic happens ;-)


Access modifiers

Although not requried for private fields, it's a good habit to use them anyway to avoid any confusion.

Edges property

List<WeightedEdge<T>> edges;
public List<WeightedEdge<T>> Edges { get { return edges; } }

You provide additional methods for adding and removing edges... but currently the user is free to modify the list anyway becasue you expose it to him. Either remove the add/remove-edge methods or make the property IReadOnlyCollection<WeightedEdge<T>> so that he cannot change it.


Search algorithms

I see that your search algorithms share one method: ReconstructPath.

If you don't want to repeat it in each algorithm you can as well create an abstract class that already implements it and derive the search algorithms from it:

interface ISearchAlgorithm
{ 
    List<Vertex<T>> Search<T>(Vertex<T> start, Vertex<T> end);
}

abstract class SearchAlgorithm : ISearchAlgorithm
{
    public abstract List<Vertex<T>> Search<T>(Vertex<T> start, Vertex<T> end);

    protected List<Vertex<T>> ReconstructPath<T>(Dictionary<Vertex<T>, Vertex<T>> parentMap, Vertex<T> start, Vertex<T> end)
    {
        ...
    }
}

class DijkstraSearchAlgorithm : SearchAlgorithm
{
    public override List<Vertex<T>> Search<T>(Vertex<T> start, Vertex<T> end)
    {
        ...
    }       
}
\$\endgroup\$
  • \$\begingroup\$ Wow the interface is a fantastic idea. Thank you so much! \$\endgroup\$ – Vardominator Aug 12 '16 at 4:47
  • 1
    \$\begingroup\$ @Vardominator I've added one more edit about the ReconstructPath method ;-) \$\endgroup\$ – t3chb0t Aug 12 '16 at 5:05
  • \$\begingroup\$ These are some great things things to consider. Off to editing. Thanks! \$\endgroup\$ – Vardominator Aug 12 '16 at 5:07
  • \$\begingroup\$ Actually this does not work because the SearchAlgorithm class does not know what 'T' is. \$\endgroup\$ – Vardominator Aug 12 '16 at 5:44
  • \$\begingroup\$ @Vardominator do you think that or did you try it out because before I posted the code I've tested it in LINQPad and everything was fine so I'm pretty sure it's correct... could you post your code as an answer to this question? \$\endgroup\$ – t3chb0t Aug 12 '16 at 5:52

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.