How to elegantly define shortest happy path between start and end state in a State Pattern design implementation?

Question

When using state pattern, one is delegating behaviour of the Entity to the current State. I have prepared SSCCE that I pasted below. We have an Entity which can transition between states : StartState, StateA, StateB, EndState. The happy path is simply the shortest path between StartState and EndState.

In this particual example the shortest happy path is: StartState->StateA->StateB->EndState

I find it hard to express what is the happy path, so I can return the order to the frontend but also be able to navigate myself through. State pattern uses methods not dicitonaries to store nodes end edges, right? I want to avoid just List<string>. I'm looking for an elegant solution.

I want to be able to know upfront what is the order of the states in the happy path.

1. Dynamically calculate the shortest path for that class structure? XOR
2. Because dynamic calculation is probably hard or very hacky, what is the most elastic/convienient to use way to describe statically the shortest happy path in this state graph?

---

namespace States
{
    public class Entity
    {
        public int Id { get; private set; }
        public State CurrentState { get; private set; }
        public void Action1() => CurrentState = CurrentState.Action1() ?? CurrentState;
        public void Action2() => CurrentState = CurrentState.Action2() ?? CurrentState;
        public void Action3() => CurrentState = CurrentState.Action3() ?? CurrentState;
    }

    public abstract class State
    {
        protected Entity _entity;

        public State(Entity entity)
        {
            _entity = entity;
        }
        //They return new state or null if transition is illegal
        public abstract State Action1();
        public abstract State Action2();
        public abstract State Action3();
    }

    public class StartState : State
    {
        public StartState(Entity entity) : base(entity) { }
        public override State Action1() => new StateA(_entity); //moves workflow forward
        public override State Action2() => null;
        public override State Action3() => null;
    }

    public class StateA : State
    {
        public StateA(Entity entity) : base(entity) { }
        public override State Action1() => null;
        public override State Action2() => new StateB(_entity); //moves workflow forward
        public override State Action3() => new StartState(_entity); // goes back to StartState
    }

    public class StateB : State
    {
        public StateB(Entity entity) : base(entity) { }
        public override State Action1() => new EndState(_entity); //moves workflow forward to EndState
        public override State Action2() => null;
        public override State Action3() => new StartState(_entity); // goes back to StartState
    }

    public class EndState : State
    {
        public EndState(Entity entity) : base(entity) { }
        public override State Action1() => null;
        public override State Action2() => null;
        public override State Action3() => null;
    }
}

Answer 1

One of the possible approaches here is to go beyond the canonical State implementation and just add an extra information to each state that defines a list of possible transitions.

The motivation here is to have the transition information available as data so that it can possibly be used by an extra algorithm that would compute the path you want to present to the user.

An approach without this extra information is risky as the only way State keeps the information about transitions is the code - each of the Action methods just returns a possible new state. Note however that in cases where there are more possible transitions from a given state (and the actual transition is hidden behind a runtime condition), getting this information in runtime could be tricky.

Consider this

public class StartState : State
  public override State Action1() {
     if ( (DateTime.Now.Ticks % 2) == 0 ) {
        return new StateA(_entity); 
     } else {
        return new StateB(_entity); 
     }
  }

In this example the start state has two transitions, to A and B, but trying to get this information in runtime could be tricky if not impossible.

Instead, I recommend to just kind of duplicate this knowledge available at runtime and provide an explicit list of states reachable from given state

public abstract class State
{
    protected Entity _entity;

    public State(Entity entity)
    {
        _entity = entity;
    }

    //They return new state or null if transition is illegal
    public abstract State Action1();
    public abstract State Action2();
    public abstract State Action3();

    public abstract IEnumerable<State> Transitions { get; }
}

and a specific state

public class StartState : State
  public override State Action1() {
     if ( (DateTime.Now.Ticks % 2) == 0 ) {
        return new StateA(_entity); 
     } else {
        return new StateB(_entity); 
     }
  }

  public override IEnumerable<State> Transitions { 
     get {
        return new List<State>() { 
           new StateA( this._entity ), new StateB( this._entity )
        }
     }
  }

This newly introduced information can be used to compute paths, together with another extra info about a state being the start state or the end state, you could code a graph traversal algorithm to find a path, all paths, a shortest path, whatever you want.

Depending on how big your graph is and how often it's about to change in future, this approach could be possibly slightly safer than just hardcoding the path into the graph itself (a List<State> in your state machine).

I'd only add a string with a description to your state class so that the description can be used in the user interface as a visible representation of states.

public abstract class State
{
   public virtual string Description { get; }
   ...