Compute list of edges that start in a given node.

Compute list of edges that target a given node.

Note: expensive for unidirectional graph representations.

Set.foldl does not exist in legacy versions of the containers package.

Floyd-Warshall algorithm.

Test for negativity, used to detect negative cycles.

Going from Lt to Le is pred, going from Le to Lt is succ.

X --(R,n)--> Y means X (R) Y + n. [ ... if n positive and X + (-n) (R) Y if n negative. ]

Convert a label to a weight, decrementing in case of Lt.

A graph forest.

Split a list of graphs gs into those that mention node n and those that do not. If n is zero or infinity, we regard it as "not mentioned".

Add an edge to a graph forest. Graphs that share a node with the edge are joined.

Reflexive closure. Add edges 0 -> n -> n -> oo for all nodes n.

h implies g if any edge in g between rigids and constants is implied by a corresponding edge in h, which means that the edge in g carries at most the information of the one in h.

Application: Constraint implication: Constraints are compatible with hypotheses.

Build a graph from list of simplified constraints.

Build a graph from list of simplified constraints.

If we have an edge X + n <= X (with n >= 0), we must set X = oo.

Lower or upper bound for a flexible variable

Compute a lower bound for a flexible from an edge.

Compute an upper bound for a flexible from an edge.

Compute the lower bounds for all flexibles in a graph.

Compute the upper bounds for all flexibles in a graph.

Compute the bounds for all flexibles in a graph.

Compute the relative minima in a set of nodes (those that do not have a predecessor in the set).

Compute the relative maxima in a set of nodes (those that do not have a successor in the set).

Given source nodes n1,n2,... find all target nodes m1,m2, such that for all j, there are edges n_i --l_ij--> m_j for all i. Return these edges as a map from target notes to a list of edges. We assume the graph is reflexive-transitive.

Given target nodes m1,m2,... find all source nodes n1,n2, such that for all j, there are edges n_i --l_ij--> m_j for all i. Return these edges as a map from target notes to a list of edges. We assume the graph is reflexive-transitive.

Compute the sup of two different rigids or a rigid and a constant.

Compute the inf of two different rigids or a rigid and a constant.

Compute the least upper bound (sup).

Compute the greatest lower bound (inf) of size expressions relative to a hypotheses graph.

Solve a forest of constraint graphs relative to a hypotheses graph. Concatenate individual solutions.

Check that after substitution of the solution, constraints are implied by hypotheses.

Iterate solver until no more metas can be solved.

This might trigger a (wanted) error on the second iteration (see Issue 2096) which would otherwise go unnoticed.