34#ifndef TROPICAL_PATHS_H
35#define TROPICAL_PATHS_H
47 double cost = std::numeric_limits<double>::infinity();
78 for(
const auto &x : v)
83 std::vector<regex_t> best;
84 for(
const auto &x : v)
86 best.push_back(x.paths);
92 std::vector<regex_t> words;
93 for(
const auto &x : v) {
97 words.push_back(x.paths);
105 "The min-cost-paths semiring computes no monus (outer joins, "
106 "EXCEPT and NOT EXISTS need one): on a tie of costs, its monus "
107 "is a difference of languages, which needs automata to "
108 "compute, and it would not register an absence (1 minus a "
109 "positive cost is 1).");
133 "A cycle of negative cost makes the least cost unbounded, with no "
134 "shortest derivation.");
Regular-expression semiring: the derivations of a tuple as a language over the labels of its input tu...
A refusal by design, or a known gap, rather than an error.
Abstract base class for (m-)semirings.
tropical_paths_t value_type
The min-cost-paths semiring over tropical_paths_t.
virtual bool has_star() const override
Every value of nonnegative cost has a star.
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
virtual value_type monus(value_type, value_type) const override
Apply the monus (m-semiring difference) operation.
virtual value_type zero() const override
Return the additive identity .
virtual value_type one() const override
Return the multiplicative identity .
virtual value_type delta(value_type x) const override
Apply the operator.
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
virtual bool exact_equality() const override
Equality of the derivations is syntactic.
virtual bool commutative() const override
Concatenation does not commute.
virtual bool idempotent() const override
A tie keeps the union of the derivations, itself idempotent.
#define PROVSQL_DELIBERATE
What kind of limit a refusal or a freezing is.
static regex_t atom(const std::string &label)
A one-letter language; for an empty label.
static regex_t plus(const std::vector< regex_t > &v)
The union of v.
static regex_t star(const regex_t &a)
The Kleene star of a.
static regex_t times(const std::vector< regex_t > &v)
The concatenation of v, in this order.
A regular expression: an immutable tree, shared between the expressions built from it.
A cost, and the derivations of that cost.
bool operator==(const tropical_paths_t &o) const
Syntactic equality, as for regex_t.
regex_t paths
Its derivations.
bool operator!=(const tropical_paths_t &o) const
Syntactic inequality.