How to handle "composed nodes" in a graph traversed via Dijkstra's algorithm?

Question

I'm dealing with a state machine that is currently traversed via Dijkstra's algorithm. However, now I need to enhance that state machine to be "smarter" in how it figures out routes to account for some side-effects. Basically some paths are not traversable if certain requirements aren't met, even if you're in the correct starting state for that path. These requirements can be satisfied by traversing other paths first. A simplified example of what I'm trying to address is traveling between cities:

• You can travel domestically without your passport (just a basic ID) (i.e. Philly -> NYC)
• As soon as you need to travel internationally, you need your passport (NYC -> Paris)
• If you already have your passport, you can travel internationally (NYC -> Paris)
• If you don't, you need to travel home first to take it (NYC -> Philly -> NYC -> Paris)

An alternative example (that I'm actually dealing with) is website states and the concept of being logged in and logged out).

There are 2 approaches I'm thinking of:

• Composing states (i.e. having passport is itself a secondary state that can be combined with "location" states), this sounds like it would add a whole other dimension to my state machine and I'm not sure whether it would make the algorithm a mess.
• Conditional paths that are only available if certain property is set while being in a state (a somewhat Bayesian approach), this would effectively make my states "impure", where transition taken would depend on internal state properties, so I prefer the composing states approach instead.

Is there a clean way to represent this via graph theory? Is there a general case algorithm that can deal with this preliminary requirement for being able to traverse a path? This problem is basically a 2-stage Dijkstra's search where you must visit a certain node first, but that node doesn't need to be visited if you already satisfy the "has passport" condition.

Answer 1

Given these facts

connection(philly,nyc,no).
connection(nyc,philly,no).
connection(philly,harrisburg,no).
connection(harrisburg,philly,no).
connection(paris,nyc,yes).
connection(nyc,paris,yes).
passport(harrisburg).

where a connection has arguments from, to, passport needed

and these test cases

:- begin_tests(travel).

travel_test_case_generator( harrisburg ,harrisburg ,no  ,[harrisburg]                                                        ).
travel_test_case_generator( harrisburg ,harrisburg ,yes ,[harrisburg]                                                        ).
travel_test_case_generator( harrisburg ,philly     ,no  ,[harrisburg,philly]                                                 ).
travel_test_case_generator( harrisburg ,philly     ,yes ,[harrisburg,philly]                                                 ).
travel_test_case_generator( harrisburg ,nyc        ,no  ,[harrisburg,philly,nyc]                                             ).
travel_test_case_generator( harrisburg ,nyc        ,yes ,[harrisburg,philly,nyc]                                             ).
travel_test_case_generator( harrisburg ,paris      ,yes ,[harrisburg,philly,nyc,paris]                                       ).
travel_test_case_generator( harrisburg ,paris      ,no  ,[harrisburg,philly,nyc,philly,harrisburg,passport,philly,nyc,paris] ).
travel_test_case_generator( philly     ,philly     ,no  ,[philly]                                                            ).
travel_test_case_generator( philly     ,philly     ,yes ,[philly]                                                            ).
travel_test_case_generator( philly     ,nyc        ,no  ,[philly,nyc]                                                        ).
travel_test_case_generator( philly     ,nyc        ,yes ,[philly,nyc]                                                        ).
travel_test_case_generator( philly     ,paris      ,yes ,[philly,nyc,paris]                                                  ).
travel_test_case_generator( philly     ,paris      ,no  ,[philly,nyc,philly,harrisburg,passport,philly,nyc,paris]            ).
travel_test_case_generator( nyc        ,paris      ,yes ,[nyc,paris]                                                         ).
travel_test_case_generator( nyc        ,paris      ,no  ,[nyc,philly,harrisburg,passport,philly,nyc,paris]                   ).

test(001,[forall(travel_test_case_generator(Start,End,Passport,Expected_route))]) :-
    route(Start,End,Passport,Route),

    assertion( Route == Expected_route ).

:- end_tests(travel).

Here is the solution using prolog. This code was written as a proof of concept to see how to answer the question. It was not written to the specs of the question so if you know Prolog you will find the obvious places where it can be improved or doesn't implement an algorithm as expected.

route(Start,End,Passport,Route) :-
    route(Start,End,Passport,[],Route_reversed),
    reverse(Route_reversed,Route), !.

route(City,City,_,Route0,Route) :-
    visit(City,Route0,Route).

route(A,C,yes,Route0,Route) :-
    connection(A,B,_),
    \+ member(B,Route0),
    visit(A,Route0,Route1),
    route(B,C,yes,Route1,Route).

route(A,C,no,Route0,Route) :-
    connection(A,B,Need_passport),
    \+ member(B,Route0),
    (
        (
            Need_passport == yes,
            \+ member(passport,Route0)
        )
    ->
        (
            get_passport_shortest(A,Route1),
            route(B,C,yes,[],Route2),
            reverse(Route0,Route0_reversed),
            append([Route0_reversed,[A],Route1,Route2],Route_reversed),
            reverse(Route_reversed,Route)
        )
    ;
        (
            visit(A,Route0,Route1),
            route(B,C,no,Route1,Route)
        )
    ).

route_no(A,A,no,Route,Route).
route_no(A,C,no,Route0,Route) :-
    connection(A,B,no),
    \+ member(B,Route0),
    visit(B,Route0,Route1),
    route_no(B,C,no,Route1,Route).

get_passport(A,Route) :-
    passport(B),
    route_no(A,B,no,[],Route1),
    route_no(B,A,no,[],Route2),
    reverse(Route1,Route1_reversed),
    reverse(Route2,Route2_reversed),
    append([Route1_reversed,[passport],Route2_reversed],Route).

visit(City,Route0,Route) :-
    (
        Route0 = [City|_]
    ->
        Route = Route0
    ;
        Route = [City|Route0]
    ).

get_passport_shortest(A,Shortest_route) :-
    findall(Route,get_passport(A,Route),Routes),
    select_shortest(Routes,Shortest_route).

select_shortest([H|T],Result) :-
    length(H,Length),
    select_shortest(T,Length,H,Result).

select_shortest([],_Current_length,Result,Result).
select_shortest([Item|T],Current_length0,Current_shortest0,Result) :-
    length(Item,Item_length),
    (
        Item_length < Current_length0
    ->
        (
            Current_length = Item_length,
            Current_shortest = Item
        )
    ;
        (
            Current_length = Current_length0,
            Current_shortest = Current_shortest0
        )
    ),
    select_shortest(T,Current_length,Current_shortest,Result).

When the test case are run

?- make.
% c:/so_question_159 (posted) compiled 0.00 sec, 0 clauses
% PL-Unit: travel ................ done
% All 16 tests passed
true.

All the test pass.

---

The reason the passport is in Harrisburg instead of Philly is that in testing the code, the code worked when the passport was in Philly. Then by adding Harrisburg and testing again a problem was uncovered in the code and fixed. If one changes passport(harrisburg). to passport(philly). the code will work but requires additional test cases.

---

Further questions posted in comments and moved here.

---

From grodzi

In your tests, the line (third from the end) philly, paris, no, why do philly,nyc,philly, harrisbug... when you can just do philly,harrisburg,philly... to get the passport? Is it intended or some minor bug?

Nice to see someone is paying attention. That is no bug and that was one of the test that exposed the bug when the passport was in Harrisburg. The way I interpret the problem as stated by the OP, the travel case is just an easier to understand version of his real problem related to an dynamic FSA with login and logout. So knowing that you need the passport is not known until you try to do the travel from nyc to paris. At this point you need the passport if it is not in hand and so need travel back to harrisbug to get it.

So yes that does look odd from a normal trip solver problem and we as humans can easily see the optimization, either because of experience, or superior reason ability, or peeking ahead and knowing that we need a passport to get to paris, but the system does not know it needs a passport until it is needed. I can add more rules and more conditions to this, but at present there is only the passport. If however the OP adds more conditions then I will ask for a new question because this question should have been more specific.

---

From OP

Regarding conditions being several layers deep, how does your example show that?

It doesn't at the moment because there were no rules needing to do that. It was posed as a question for others who have or plan to answer this as it will be a choice they would have to make when writing the code.

---

From OP

Does your example with the password window attempt to see how FSM handles user error?

No, I only looked at your basic ideas in the question posted.

This question is referring to the OPs code posted at GitHub

---

References of value

Attribute Grammars (Wikipedia)
Automated planning and scheduling (Wikipedia) (Prolog example)
RosettaCode Dijkstra's algorithm
SLD Resolution
Tabled execution (SLG resolution)
Declarative Programming - 3: logic programming and Prolog

Answer 2

One can solve it with Astar by indeed "dupplicating" cities in a seemingly 2^n fashion (in practice this is less since not all the states will be explored).

A node is now a tuple <city, ...flags> where in this case, flags is the simple boolean to represent whether we are in possession of the passport or not.

Instead of basically considering the neighbours of some city C, we now consider the neighbours of the tuple T, which are the neighbours of T.city restricted to some rule:

If the neighbouring city requires a pass, T must have the pass in its flags

Below Astar, copy pasted from wiki. The only adaptation, is:

while generating the neighbours from some node, if node has pass, so have the neighbours.

Notice in tests (copied more or less from Guy Coder), two tests commented (which fail).

• The first one, because harrisburg having the passport overrides in my case the absence of password specified as argument
• The second one, because as commented, I am not expecting to come "back & forth" if not needed.

Note that the edges are not weighted d(a,b) = 1 forall existing (a,b) but they could/should be.

function h (node) { return 0 }
function d (a, b) { return 1 } // no weight but could be
const M = {
    harrisburg: [
      { c: 'philly', passRequired: false }
    ],
    nyc: [
      { c: 'philly', passRequired: false },
      { c: 'paris', passRequired: true }
    ],
    paris: [
      { c: 'nyc', passRequired: true }
    ],
    philly: [
      { c: 'harrisburg', passRequired: false },
      { c: 'nyc', passRequired: false }
    ]
}

const neighbours = node => {
    if (node.c === 'harrisburg') {
        return M[node.c].map(x => {
            return { c: x.c, hasPass: true }
        })
    }
    if (node.hasPass) {
        return M[node.c].map(x => Object.assign({ hasPass: true }, x))
    }
    return M[node.c].filter(x => !x.passRequired)
}
function id (node) { return node.c + !!node.hasPass }

//https://en.wikipedia.org/wiki/A*_search_algorithm
function reconstruct_path (cameFrom, current) {
  const total_path = [current]
  while(cameFrom.has(id(current))) {
    current = cameFrom.get(id(current))
    total_path.unshift(current)
  }
  return total_path
}


// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h) {
  // The set of discovered nodes that may need to be (re-)expanded.
  // Initially, only the start node is known.
  const openSet = new Map([[id(start), start]])

  // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
  const cameFrom = new Map()

  // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
  const gScore = new Map()
  gScore.set(id(start), 0)

  // For node n, fScore[n] := gScore[n] + h(n).
  const fScore = new Map()
  fScore.set(id(start), h(start))

  while (openSet.size) {
    //current := the node in openSet having the lowest fScore[] value
    let current
    let bestScore = Number.MAX_SAFE_INTEGER
    for (let [nodeId, node] of openSet) {
      const score = fScore.get(nodeId)
      if (score < bestScore) {
        bestScore = score
        current = node
      }
    }
    
    if (current.c == goal.c) {
      return reconstruct_path(cameFrom, current)
    }
    openSet.delete(id(current))
    neighbours(current).forEach(neighbor => {
      const neighborId = id(neighbor)
      // d(current,neighbor) is the weight of the edge from current to neighbor
      // tentative_gScore is the distance from start to the neighbor through current
      const tentative_gScore = gScore.get(id(current)) + d(current, neighbor)
      if (!gScore.has(neighborId) || tentative_gScore < gScore.get(neighborId)) {
        // This path to neighbor is better than any previous one. Record it!
        cameFrom.set(neighborId, current)
        gScore.set(neighborId, tentative_gScore)
        fScore.set(neighborId, gScore.get(neighborId) + h(neighbor))
        if (!openSet.has(neighborId)){
          openSet.set(neighborId, neighbor)
        }
      }
    })
  }
  // Open set is empty but goal was never reached
  return false
}

function tests() {
  const assert = x => {
    if(!x){
      throw new Error(x)
    }
  }
  function travel_test_case_generator(from, to, initialPass, expect) {
    const res = A_Star({ c: from, hasPass: initialPass === 'yes'}, {c: to}, h).map(x => x.c)
    try {
    assert(res.length === expect.length)
    assert(res.every((x, i) => x === expect[i]))
    } catch (e) {
      console.log('failed', from, to, initialPass, res, expect)
      throw e
    }
    console.log('ok', `from ${from} to ${to} ${initialPass==='yes' ? 'with': 'without'} pass:`, res)
  }
  travel_test_case_generator( 'harrisburg' ,'harrisburg' ,'no'  ,['harrisburg'])
  travel_test_case_generator( 'harrisburg' ,'harrisburg' ,'yes' ,['harrisburg'])
  travel_test_case_generator( 'harrisburg' ,'philly'     ,'no'  ,['harrisburg', 'philly'])
  travel_test_case_generator( 'harrisburg' ,'philly'     ,'yes' ,['harrisburg', 'philly'])
  travel_test_case_generator( 'harrisburg' ,'nyc'        ,'no'  ,['harrisburg', 'philly', 'nyc'])
  travel_test_case_generator( 'harrisburg' ,'nyc'        ,'yes' ,['harrisburg', 'philly', 'nyc'])
  travel_test_case_generator( 'harrisburg' ,'paris'      ,'yes' ,['harrisburg', 'philly', 'nyc', 'paris'])
  // travel_test_case_generator( 'harrisburg' ,'paris'      ,'no'  ,['harrisburg', 'philly', 'nyc', 'philly', 'harrisburg', 'passport', 'philly', 'nyc', 'paris'])
  travel_test_case_generator( 'philly'     ,'philly'     ,'no'  ,['philly'])
  travel_test_case_generator( 'philly'     ,'philly'     ,'yes' ,['philly'])
  travel_test_case_generator( 'philly'     ,'nyc'        ,'no'  ,['philly', 'nyc'])
  travel_test_case_generator( 'philly'     ,'nyc'        ,'yes' ,['philly', 'nyc'])
  travel_test_case_generator( 'philly'     ,'paris'      ,'yes' ,['philly', 'nyc', 'paris'])
  // travel_test_case_generator( 'philly'     ,'paris'      ,'no'  ,['philly', 'nyc', 'philly', 'harrisburg', 'philly', 'nyc', 'paris'])
  travel_test_case_generator( 'nyc'        ,'paris'      ,'yes' ,['nyc', 'paris'])
  travel_test_case_generator( 'nyc'        ,'paris'      ,'no'  ,['nyc', 'philly', 'harrisburg', 'philly', 'nyc', 'paris'])
}
tests()

Answer 3

What you call "composing states" is the usual way to do it. Sometimes it's called "graph layering". It's often used to solve "shortest path with constraint" sorts of problems.

The usual description would be like:

Make two copies of your state machine M₁ and M₂, M₁ contains only transitions that you can take without your passport, M₂ contains the transitions you can take with your passport. Then add a transition from M₁ to M₂ for every arc that aquires your passport. Now find the shortest path from the start state in M₁ to the target state in either copy.

It is exactly, as you say, "adding a whole other dimension". If there are N vertices in your original graph and M supplementary states, the resulting graph has N*M vertices, so this is only practical if either N or M is smallish.

Here's a not bad lecture on the technique: https://www.youtube.com/watch?v=OQ5jsbhAv_M&feature=youtu.be&t=47m7s

And here are some other answers I've written using the same technique: https://stackoverflow.com/search?q=user%3A5483526+graph+layering

Note that in implementation, we don't usually make a real copy of the graph. We traverse the implicit graph using tuples to represent the composite states.