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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.