Yield the shortest path in state transistions

Question

I am trying to come up with an algorithm for a tree traversal, but I am getting stuck.

This is a fairly hard question (compared to others I have asked) so I may need to keep figuring on my own. But I thought I would throw it out here.

I have the following class structure:

public class Transition
{
    // The state we are moving from.
    public String From { get; set; }
    // All the To states for this from
    public List<String>To { get; set; }
}

List<Transition> currentTransistions;

When currentTransistions is fully filled out it looks like this (for me):

<?xml version="1.0" encoding="utf-8"?>
<ArrayOfTransition xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"&gt;
  <Transition>
    <From />
    <To>
      <string>Not Done</string>
    </To>
  </Transition>
  <Transition>
    <From>Not Done</From>
    <To>
      <string>In Progress</string>
      <string>Deleted</string>
    </To>
  </Transition>
  <Transition>
    <From>Deleted</From>
    <To>
      <string>Not Done</string>
    </To>
  </Transition>
  <Transition>
    <From>In Progress</From>
    <To>
      <string>Done</string>
      <string>Ready For Test</string>
      <string>Deleted</string>
    </To>
  </Transition>
  <Transition>
    <From>Done</From>
    <To>
      <string>In Progress</string>
    </To>
  </Transition>
  <Transition>
    <From>Ready For Test</From>
    <To>
      <string>In Progress</string>
      <string>Done</string>
      <string>Deleted</string>
    </To>
  </Transition>
</ArrayOfTransition>

The idea here is that I have mapped the state transitions for TFS Work items. What I need now is a way to say "Given a current state, how do I get to another state".

Ideally it would look like this:

 foreach (string state in GetToFinalState(finalState, currentState, currentTransistions)
 {
     // Save the workitem at the state so we can get to the final state.
 }

GetToFinalState, would have to have a way to caclulate the shortest path and use the yield feature of C# to offer them up one at a time for the foreach statement.

I have used yield one before, so I think I can figure that out. But I am not sure how to do that at the same time as finding the shortest path (with out recalculating on each time in the func)?

If you have read this far, thanks. If you offer an answer then double thanks.

Answer 1

You can't do that efficiently without calculating the shortest path and yielding each path segment after the whole process is completed. The nature of shortest path problem doesn't lend itself to algorithms that efficiently compute such partial solutions.

Since the transition graph is not weighted, you can simply run a BFS on it to compute the shortest path. You need to do something like this (I'm not sure of the properties of the TFS object so this is just a pseudocode):

IEnumerable<string> ShortestPath(string fromState, string toState, Transition[] currentTransitions) {
    var map = new Dictionary<string, string>();
    var edges = currentTransitions.ToDictionary(i => i.From, i => i.To);
    var q = new Queue<string>(); 
    map.Add(fromState, null);
    q.Enqueue(fromState);
    while (q.Count > 0) {
        var current = q.Dequeue();
        foreach (var s in edges[current]) {
            if (!map.ContainsKey(s)) {
                map.Add(s, current);
                if (s == toState) {
                    var result = new Stack<string>();
                    var thisNode = s;
                    do {
                        result.Push(thisNode);
                        thisNode = map[thisNode];
                    } while (thisNode != fromState);
                    while (result.Count > 0)
                        yield return result.Pop();
                    yield break;
                }
                q.Enqueue(s);
            }
        }
    }
    // no path exists
}

Answer 2

If you need to find the shortest path from a node to a descendent node in an acyclic tree, then Mehrdad's solution is a good one. That is, first do a breadth-first-search until you find the destination node, and then work out the path from the start node to the destination.

If your graph is not an (acyclic) tree, but rather an arbitrary weighted graph, then naive breadth-first-search does not work. Either it goes into infinite loops (if you're not clever about keeping track of when you've seen a node already), or it is not guaranteed to find the least-weight path.

If you're in that situation then a good algorithm to use is the famous "A*" algorithm. I've got some notes on how to implement A* in C# here:

http://blogs.msdn.com/ericlippert/archive/tags/AStar/default.aspx

This is particularly useful if you have an "estimating function" that can make guesses about what the most likely next node on the shortest path is.