0
\$\begingroup\$

I have the below code for finding the shortest path between a source node and destination node in a BiDirectional graph.It is working alright. However, when I am running Static Code Analysis (VS2017), it is giving poor score (42) on Maintainability Index. My questions are:

  1. How to improve the overall code quality?
  2. How can I make it more extendable or maintainable?
  3. Will employing some specific Design Pattern here would have mad more sense?If yes, which one and how, can you please guide?

Here is the code below:

interface IRouter
  {
    void AddNode(string name, Dictionary<string, int> node);
    List<string> GetShortestPath(string source, string destination);
  }
public  class BaggageRouter: IRouter
  {
    Dictionary<string, Dictionary<string, int>> vertices = new Dictionary<string, Dictionary<string, int>>();

    public void AddNode(string name, Dictionary<string, int> node)
    {
      vertices[name] = node;
    }

    public List<string> GetShortestPath(string start, string finish)
    {
      #region SettingUp
      var previous = new Dictionary<string, string>();
      var distances = new Dictionary<string, int>();
      var queue = new List<string>();// the set of all nodes in Graph   - all nodes in the graph are unoptimized - thus are in Q

      List<string> path = null;

      foreach (var vertex in vertices)
      {
        if (vertex.Key == start)
        {
          distances[vertex.Key] = 0;//setting Source Node Distance=0
        }
        else
        {
          distances[vertex.Key] = int.MaxValue;//remaining all nodes are set at max distance
        }
        queue.Add(vertex.Key);
      }
      #endregion

      while (queue.Count != 0)
      {
        queue.Sort((x, y) => distances[x] - distances[y]);

        var smallest = queue[0];
        queue.Remove(smallest);//Removing the optimized Node at every Iteration

        if (smallest == finish)//Meaning we have calculated the shortest path upto destination node, so no need to calculate shortest path for remaining nodes like in original Dijkstra
        {
          path = new List<string>();
          while (previous.ContainsKey(smallest))
          {
            path.Add(smallest);
            smallest = previous[smallest];
          }
          path.Add(start);
          path.Reverse();
          path.Add(": " + distances[finish].ToString());//Adding the shortest path distance as last element
          break;
        }

        if (distances[smallest] == int.MaxValue)
        {
          break;//This corner-case scenario can happen if the remaining nodes are Un-reachable.
        }

        foreach (var neighbor in vertices[smallest])
        {
          var alt = distances[smallest] + neighbor.Value;
          if (distances.ContainsKey(neighbor.Key))
          {
            if (alt < distances[neighbor.Key])
            {
              distances[neighbor.Key] = alt;
              previous[neighbor.Key] = smallest;
            }
          }
        }
      }

      return path;
    }
  }
\$\endgroup\$
  • \$\begingroup\$ Can you tell us what is the Maintainability Index measuring? Is it, for example, cyclomatic complexity, method length, etc.? I don't have VS2017 and couldn't find the definition easily with Google. You should understand concretely what the meaning is before you attempt to improve your code. \$\endgroup\$ – Fuhrmanator Oct 14 '17 at 13:43
  • \$\begingroup\$ If you're considering true maintainability, you should cite in the comments the source of the algorithm you're coding to. Someone who has to debug/improve this code later will thank you for it. \$\endgroup\$ – Fuhrmanator Oct 14 '17 at 13:49
  • \$\begingroup\$ Another consideration is the variants of the algorithms to find a shortest path. Some algorithms might yield code that is easier to maintain, simply because they're more straightforward (although they might have drawbacks in terms of time and memory). You could also take an existing solution that someone else maintains (that's more a project-management decision than a code-review one). \$\endgroup\$ – Fuhrmanator Oct 14 '17 at 14:54
0
\$\begingroup\$

In my opinion, there are a few improvements that can be made. I'll address only some readability issues here, not the performance or algorithmic ones.

Remove regions

There are a lot of discussions on this, just google it and you'll find a ton of discussions.

The methods are too long

Try to reduce them by using already existing object or methods.

For example:

    var queue = new List<string>();// the set of all nodes in Graph   - all nodes in the graph are unoptimized - thus are in Q

    foreach (var vertex in vertices)
    {
        if (vertex.Key == start)
        {
            distances[vertex.Key] = 0;//setting Source Node Distance=0
        }
        else
        {
            distances[vertex.Key] = int.MaxValue;//remaining all nodes are set at max distance
        }
        queue.Add(vertex.Key);
    }

can be written like:

    var queue = vertices.Select(vertex => vertex.Key == start ? 0 : int.MaxValue).ToList();// the set of all nodes in Graph   - all nodes in the graph are unoptimized - thus are in Q

Also, path seems like it should be a Stack<string> data type. In this case, instead of:

            while (previous.ContainsKey(smallest))
            {
                path.Add(smallest);
                smallest = previous[smallest];
            }
            path.Add(start);
            path.Reverse();
            path.Add(": " + distances[finish].ToString());//Adding the shortest path distance as last element

and

    return path;

you'd have:

            while (previous.ContainsKey(smallest))
            {
                path.Push(smallest);
                smallest = previous[smallest];
            }
            path.Push(start);
            path.Push(": " + distances[finish].ToString());//Adding the shortest path distance as last element

and

    return path.ToList();

Cycle conditions

The main while cycle has two internal paths that cause it to interrupt through the break instruction. It could be better to refactor the code in order to include these conditions in the cycle's one.

I mean, changing this:

    while (queue.Count != 0)
    {
        queue.Sort((x, y) => distances[x] - distances[y]);

        var smallest = queue[0];
        queue.Remove(smallest);//Removing the optimized Node at every Iteration

        if (smallest == finish)//Meaning we have calculated the shortest path upto destination node, so no need to calculate shortest path for remaining nodes like in original Dijkstra
        {
            path = new Stack<string>();
            while (previous.ContainsKey(smallest))
            {
                path.Push(smallest);
                smallest = previous[smallest];
            }
            path.Push(start);
            path.Push(": " + distances[finish].ToString());//Adding the shortest path distance as last element
            break;
        }

        if (distances[smallest] == int.MaxValue)
        {
            break;//This corner-case scenario can happen if the remaining nodes are Un-reachable.
        }

        foreach (var neighbor in vertices[smallest])
        {
            var alt = distances[smallest] + neighbor.Value;
            if (distances.ContainsKey(neighbor.Key))
            {
                if (alt < distances[neighbor.Key])
                {
                    distances[neighbor.Key] = alt;
                    previous[neighbor.Key] = smallest;
                }
            }
        }
    }

into this:

    int smallest = 0;
    while (queue.Count != 0 && smallest != finish && distances[smallest] != int.MaxValue)
    {
        queue.Sort((x, y) => distances[x] - distances[y]);
        smallest = queue[0];
        queue.Remove(smallest);//Removing the optimized Node at every Iteration

        foreach (var neighbor in vertices[smallest])
        {
            var alt = distances[smallest] + neighbor.Value;
            if (distances.ContainsKey(neighbor.Key) && alt < distances[neighbor.Key])
            {
                distances[neighbor.Key] = alt;
                previous[neighbor.Key] = smallest;
            }
        }
    }

    if (smallest == finish)//Meaning we have calculated the shortest path upto destination node, so no need to calculate shortest path for remaining nodes like in original Dijkstra
    {
        path = new Stack<string>();
        while (previous.ContainsKey(smallest))
        {
            path.Push(smallest);
            smallest = previous[smallest];
        }
        path.Push(start);
        path.Push(": " + distances[finish].ToString());//Adding the shortest path distance as last element
    }

Comments

The last thing is about comments. Inline comments can get really long. Some (me included) like them in this way:

// Comment regarding the following instruction
var a = something;

instead of:

var a = something; // Comment regarding the instruction on the left

The resulting code should become something like the following:

interface IRouter
{
    void AddNode(string name, Dictionary<string, int> node);
    List<string> GetShortestPath(string source, string destination);
}

public class BaggageRouter: IRouter
{
    Dictionary<string, Dictionary<string, int>> vertices = new Dictionary<string, Dictionary<string, int>>();

    public void AddNode(string name, Dictionary<string, int> node)
    {
        vertices[name] = node;
    }

    public List<string> GetShortestPath(string start, string finish)
    {
        var previous = new Dictionary<string, string>();
        var distances = new Dictionary<string, int>();
        // The set of all nodes in Graph - all nodes in the graph are unoptimized - thus are in Q
        var queue = vertices.Select(vertex => vertex.Key == start ? 0 : int.MaxValue).ToList();

        var path = new Stack<string>();

        int smallest = 0;
        while (queue.Count != 0 && smallest != finish && distances[smallest] != int.MaxValue)
        {
            queue.Sort((x, y) => distances[x] - distances[y]);
            smallest = queue[0];
            // Removing the optimized Node at every Iteration
            queue.Remove(smallest);

            foreach (var neighbor in vertices[smallest])
            {
                var alt = distances[smallest] + neighbor.Value;
                if (distances.ContainsKey(neighbor.Key) && alt < distances[neighbor.Key])
                {
                    distances[neighbor.Key] = alt;
                    previous[neighbor.Key] = smallest;
                }
            }
        }

        // Meaning we have calculated the shortest path upto destination node, so no need to 
        // calculate shortest path for remaining nodes like in original Dijkstra.
        if (smallest == finish)
        {
            while (previous.ContainsKey(smallest))
            {
                path.Push(smallest);
                smallest = previous[smallest];
            }
            path.Push(start);
            // Adding the shortest path distance as last element.
            // I've used string interpolation here also.
            path.Push(": {distances[finish]}");
        }

        return path.ToList();
    }
}
\$\endgroup\$
1
\$\begingroup\$

How to improve the overall code quality?

I don't know much about C#, but I guess your analyzer is complaining mainly about the length of your method and its cyclomatic complexity. Try to split it in multiple well named methods and use guard conditions to reduce the nesting level of your ifs.

Maybe you could also use the ternary operator instead of the if in your first foreach to extract the common part of the if branches. But this is an highly discussed topic.

How can I make it more extendable or maintainable?

There is no real use in making something extensible, that you never plan to extend. So if you don't know possible (useful) extension points, you shouldn't desperately try to find some. You can refactor it later when you need it.

Maintainable is in general achieved by readable code and a good test base. If you are not afraid of breaking something, you can do everything with your code easily.

Will employing some specific Design Pattern here would have mad more sense?

Actually I would say, you applied the Strategy pattern here already. This is more or less the default use case, having an interface and change the path finding algorithm. (Maybe building the graph should be splitt from traversing)

\$\endgroup\$
  • \$\begingroup\$ Strategy may or may not require the managing of nodes (i.e., AddNode). I could see separating the nodes from the GetShortestPath function, so that those strategies all work on the same graph. \$\endgroup\$ – Fuhrmanator Oct 14 '17 at 14:44

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.