Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
extensions:polytropes [2020/03/18 11:25] – created joswig | extensions:polytropes [2021/01/12 14:34] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== | + | ====== |
This is the software companion to the article "The tropical geometry of shortest paths" by | This is the software companion to the article "The tropical geometry of shortest paths" by | ||
- | [[https:// | + | [[https:// |
+ | 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. | 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. | ||
Line 8: | Line 9: | ||
===== Download ===== | ===== Download ===== | ||
- | [[http:// | + | [[http:// |
===== Installation ===== | ===== Installation ===== | ||
Line 20: | Line 21: | ||
Suppose this ends up at ''/ | Suppose this ends up at ''/ | ||
< | < | ||
- | import_extension "/ | + | import_extension "/ |
</ | </ | ||
- | 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 '' | + | 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 '' |
===== Examples ===== | ===== Examples ===== | ||
Line 28: | Line 29: | ||
This extension contributes to the application '' | This extension contributes to the application '' | ||
- | In the application '' | + | In the application '' |
We construct Example 8 from the paper (see Figure 3, loc. cit.). | We construct Example 8 from the paper (see Figure 3, loc. cit.). | ||
Line 36: | Line 37: | ||
> $G = new GraphAdjacency< | > $G = new GraphAdjacency< | ||
</ | </ | ||
- | The edges are defined along with their weights. | + | [For polymake 4.0 use '' |
< | < | ||
> $Weights = new EdgeMap< | > $Weights = new EdgeMap< | ||
Line 131: | Line 132: | ||
In the first solution, e.g., we see that $c$ and $d$ go through $b$ to reach $a$. | 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 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 " | + | The distance from $a$ to itself is zero; the output " |
The distance from $b$ to $a$ is $x$. | The distance from $b$ to $a$ is $x$. | ||
The distance from $c$ to $a$ is $2+x$. | The distance from $c$ to $a$ is $2+x$. | ||
Line 137: | Line 138: | ||
All these hold under the conditions $3-x \geq 0$ and $1-x \geq 0$ (standard polymake notation for linear inequalities); | All these hold under the conditions $3-x \geq 0$ and $1-x \geq 0$ (standard polymake notation for linear inequalities); | ||
The nonnegativity is always implicit. | 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), | ||
+ |