Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of integers which act as conditions. Consider the graph $G=(V,E)$ where $V= \{v_1,v_2,c\}$ and $E=\{(v_1,v_1,2),(v_1,v_1,-1),(v_1,c,0),(c,v_2,0)\}$ and $c:=\{1,4,5\}$. The conditions are defined as follows. Suppose i start a walk in the graph from node $v_1$ and i arrive at node $c$ with a current weight of $m$. The condition node states that the walk may pass through node $c$ only if there are three separate walks from the start node $v_1$ to $c$ (without going through $c$) of weights $m+1,m+4,m+5$ (i.e the conditions of $c$). All condition nodes in the graph will always only have one incoming edge and one outgoing edge.
Example: Suppose i want to ask the graph if there is a walk from $v_1$ to $v_2$ of weight 0. There is a walk of length 0: $v_1 \rightarrow_0 c \rightarrow_0 v_2$ but this walk is only valid if i can get from $v_1$ to $c$ with weights 0+1,0+4 and 0+5 which i can with the following paths:
- 1: $v_1 \rightarrow_2 v_1 \rightarrow_{-1} v_1 \rightarrow_0 c$
- 4: $v_1 \rightarrow_2 v_1 \rightarrow_{2} v_1 \rightarrow_0 c$
- 5: $v_1 \rightarrow_2 v_1 \rightarrow_{2}v_1 \rightarrow_{2} v_1 \rightarrow_{-1} v_1 \rightarrow_0 c$
Although i can represent this in a graph well (as above) its hard to utilise any existing graph algorithms that can decide this for any walk as the nature of the condition node is unusual for a standard graph. Ideally, it would be good if i could remove all condition nodes from a graph, but it is not obvious how to do this. I did think about using petri nets, but it is difficult to take an unbounded number of tokens (the weights) into account and start a new walk whilst "remembering" the conditions that need to be satisfied.
Is there a better data structure that would be more suitable to represent this problem that existing algorithms could act upon in order to answer the decision question?
Is there a known graph algorithm we can utilise to decide if there exists walks of an exact weight $k$ between 2 simple nodes? I asked a similar question here but this was with a graph of only simple nodes.
