Module convex 

Convexity checking for portgraphs.

This is based on a ConvexChecker object that is expensive to create (linear in the size of the graph), but can be reused to check multiple subgraphs for convexity quickly.

There are currently two implementations of the ConvexChecker trait:

• TopoConvexChecker uses a pre-computed topological node order to speed up convexity checks. This is a good default choice for most graphs.
• LineConvexChecker uses a pre-computed line partition, i.e. a partition of the graph into edge disjoint paths. Convexity checks can then be performed based on the indices of the nodes in the paths. This will be faster than TopoConvexChecker for convexity checking of small subgraphs (say, up to ~100 nodes), in graphs for which most nodes have few incoming and outgoing ports. Note that initializing the LineConvexChecker is up to 4x slower than initializing the TopoConvexChecker, so must be amortized over many convexity checks.

Structs

LineConvexChecker

Convexity checking using a pre-computed line partition of the graph.

LineIndex

Index of a line in a LineConvexChecker’ s line partition.

LineInterval

Interval of positions on a line, [min, max] inclusive.

LineIntervals

Intervals of positions on each line that are occupied by a subgraph.

Position

Position of a node on a line in a LineConvexChecker’ s line partition.

TopoConvexChecker

Convexity checking using a pre-computed topological node order.

Traits

ConvexChecker

Pre-computed data for fast subgraph convexity checking on a given graph.

CreateConvexChecker

Trait to create a ConvexChecker for a given graph.