This is the software companion to the article “The tropical geometry of shortest paths” by Michael Joswig and Benjamin Schröter, arXiv:1904.01082. Ewgenij Gawrilow co-authors the code.
We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include the enumeration of polytropes, i.e., ordinary convex polytopes which are also tropically convex, as well as shortest paths in traffic networks with variable link travel times.
polytropes-0.1.tar.xz [18 Mar 2020], for the upcoming polymake version 4.1 (but mostly usable for 4.0, too).
This requires an installation of polymake, version 4.0. Older versions of polymake are not supported.
After download you first need to extract the code.
tar Jxpf polytropes-0.1.tar.xz
Suppose this ends up at /your/path/polytropes-0.1. Then you start up polymake. Within the polymake shell do:
import_extension "/your/path/polytropes-0.1";
Do not forget to use an absolute path! Afterwards you are good to run the code. This import needs to be performed only once. The reference to the extension is permanently stored in $HOME/.polymake/settings. For more details there is a guide to polymake's extension system.
This extension contributes to the application graph.
In the application graph you can create a directed graph whose weights are allowed to be intervals with nonnegative rational boundaries or $+\infty$. That is, we are in the case of separated variables.
We construct Example 8 from the paper (see Figure 3, loc. cit.). This is a directed graph on four nodes. The node numbers 0,1,2,3 correspond to the labels $a,b,c,d$ in the Figure.
> $G = new GraphAdjacency<Directed>(4);
[For polymake 4.0 use props::Graph instead of GraphAdjacency; the rest stays the same.] The edges are defined along with their weights.
> $Weights = new EdgeMap<Directed, WeightInterval<Rational>>($G); > $Weights->edge(1,0)=new WeightInterval<Rational>(0,0,"inf"); > $Weights->edge(2,0)=new WeightInterval<Rational>(-1,5,5); > $Weights->edge(3,0)=new WeightInterval<Rational>(-1,4,4); > $Weights->edge(2,1)=new WeightInterval<Rational>(-1,2,2); > $Weights->edge(3,1)=new WeightInterval<Rational>(-1,3,3);
The interval is specified as a triplet of an index, the lower and the upper bound. The index indicates the variable, and we use -1 for constant weights. Only the first edge, from $b$ to $a$, has a variable weight (which is not restricted further, i.e., the weight lies in $[0,+\infty)$). The variables are consecutively numbered, starting from 0.
The network is defined by the abstract graph (via its adjacency) and the weights (which are constants or intervals). Additionally, we give labels to the nodes, and we attach the total number of variables.
> $Network = new graph::Graph<Directed>(ADJACENCY=>$G, NODE_LABELS=>"a b c d");
> $Network->attach("WEIGHTS", $Weights, "ADJACENCY");
> $Network->attach("N_VARS",1);
The next step computes all shortest path trees to the target node $a=0$.
> parameterized_shortest_path_trees($Network, 0); #nodes=4 #edges=5 p=0 #vars=1 #solutions=4
In this bare form the output is little impressive. We only see that the digraph has four nodes and five arcs, one variable edge weight, and there are four distinct shortest path trees with the given target. The output “p=0” is irrelevant here.
It is more interesting to specify the verbosity level to a positive number (third optional argument):
> parameterized_shortest_path_trees($Network, 0, 1); solution # 1 shortest paths: 1 -> 0 2 -> 1 3 -> 1 distances to target (constant + linear combination of variables): 0: (2) 1: 0 1 2: 2 1 3: 3 1 inequalities: 3 -1 1 -1 solution # 2 shortest paths: 1 -> 0 2 -> 0 3 -> 1 distances to target (constant + linear combination of variables): 0: (2) 1: 0 1 2: 5 0 3: 3 1 inequalities: -3 1 1 -1 solution # 3 shortest paths: 1 -> 0 2 -> 1 3 -> 0 distances to target (constant + linear combination of variables): 0: (2) 1: 0 1 2: 2 1 3: 4 0 inequalities: 3 -1 -1 1 solution # 4 shortest paths: 1 -> 0 2 -> 0 3 -> 0 distances to target (constant + linear combination of variables): 0: (2) 1: 0 1 2: 5 0 3: 4 0 inequalities: -3 1 -1 1 #nodes=4 #edges=5 p=0 #vars=1 #solutions=4
Each tree is first given combinatorially, i.e., for each node other than the target we see the next node on the directed path to the target. In the first solution, e.g., we see that $c$ and $d$ go through $b$ to reach $a$. The next part of the output for each solution are the distances from each node to the target, written in the form $\alpha + \beta x$, where $x$ is the variable weight of the arc from $b$ to $a$. The distance from $a$ to itself is zero; the output “(2)” is SparseVector notation; it means zero; see below for more details on the sparse notation. The distance from $b$ to $a$ is $x$. The distance from $c$ to $a$ is $2+x$. The distance from $d$ to $a$ is $3+x$. All these hold under the conditions $3-x \geq 0$ and $1-x \geq 0$ (standard polymake notation for linear inequalities); i.e., $0 \leq x \leq 1$, and the other inequality is redundant. The nonnegativity is always implicit.
The actual feasibility of a shortest path tree is not checked here. The second solution (which is the one shown in Figure 3) is subject to the conditions $-3+x\geq 0$ and $1-x\geq 0$, i.e., $x \geq 3$ and $x\leq 1$, which is impossible. The feasibility can be checked via an LP oracle.
The sparse matrix notation works as follows: each row is a sparse vector. Each sparse vector starts with its length (in parantheses), followed by a list of pairs of indices and nonzero coefficients.