Looking for an algorithm to find a shortest path in a special graph

Question

I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special extensions:

1. A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path[1..i-1] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.

2. Two adjacent edges in a path are not required to be linked. I.e. $path[j].end$ is not necessary equal to $path[j+1].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path[j]$ edge equals to the $A$ and $path[j+1]$ edge corresponds to the $B$. Still, $path[j+1].start$ should be equal to at least one of $path[1..j+1].end$ vertices.

The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.

My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawbacks:

1. For each combination of property values a new vertex should be created. If property has an integer value, the number of vertices is going to be really large.

2. Because of the extension number two, the vertex can have a large number of edges connected. We need to represent an each edge which can be visited from this state, and when path is long the number of edges becomes big too.

3. If I need to find a path to several vertices, it's necessary to start a search several times and combine received paths. In some cases it is possible to make a shorter path if the algorithm will be aware that I actually need to reach several vertices, not the single one only.

My questions are:

1. Are there an existing name for such graphs? I've learned about dynamic graphs and they don't fully correspond to my description because they don't usually have a state (a state is the main feature of my graph).

2. Are there any better (faster, with less computational complexity, more functional) algorithms to find the shortest path in such graphs? To be more specific, are there an algorithm which solves at least some of the issues mentioned before?

3. If such algorithms exist, are there any libraries that implement it?

P.S. $f$, $g$ functions are simple logical predicates or integer arithmetic expressions. For example, to require some edge to repeat 100 times in the path I may set transition function for this edge as $i_{new} = i_{old} + 1$ and place another edge after it with $g$ equal to $i > 100$. SMT solver may be a helpful tool for this task, but I don't know how to encode the problem itself in a solver format. Also I'm not sure that applying SMT is the best approach.

Answer 1

The "state" of a traversal (after visiting $k$ edges) is the set of $k$ edges that you've traversed so far, in the order they were traversed. You can now use any method for exploring this state space: e.g., BFS; or A*, if you have a suitable heuristic.

In other words, we define a new graph $G'$ where each vertex of $G'$ is a possible state of a traversal (after visiting some number of edges), and where there is an edge $u \to v$ if starting from state $u$ it is possible to add one edge to the end to reach state $v$. Then you do BFS in $G'$. You don't need to build up $G'$ explicitly before doing BFS; the graph can be represented implicitly (where each time you reach a state $u$, you can compute all possible next-states reachable from $u$ in a single step).

If BFS takes too much memory, you can use techniques from explicit-state model checking. This will reduce the space consumption but not the memory usage.

None of this avoids the fact that, for arbitrary functions $f,g$, the running time of these algorithms might all be exponential in the worst case, because you might need to explore an exponentially-sized state space. I suspect the only hope to do better is to take advantage of knowledge of some particular structure in $f,g$.