API Reference

A note on Node and Edge types

The following types are used throughout the docs

  • Nodes are integers

Node: TypeAlias = int

  • Collections of nodes are tuples of Node

Nodes: TypeAlias = tuple[Node, ...]

  • Edges are 2-tuples of Node.

Edge: TypeAlias = tuple[Node, Node]

  • Hyperedges are 2-tuples of Nodes:

HyperEdge: TypeAlias = tuple[Nodes, Nodes]

Examples:

  • (0, 1) is an edge from node 0 to node 1.

  • ((0,), (1, 2)) is a hyperedge from node 0 to nodes 1 and 2 (i.e. a split).

  • ((0, 1), 2) is a not a valid edge.

  • All attributes in a graph (for both Node``s and ``(Hyper)Edge``s) are dictionaries mapping string attribute names to values. For example, a node's attributes might be ``{ "x": 0.5, "y": 0.5, "t": 0 }

    Attributes: TypeAlias = Mapping[str, Any]

Track Graph

class motile.TrackGraph(nx_graph=None, frame_attribute='t')

A graph of nodes in time & space, with edges connecting them across time.

This wraps a networkx.DiGraph object.

Both nodes and edges are represented by a dictionary of properties.

Provides a few convenience methods for time series graphs in addition to all the methods inherited from networkx.DiGraph.

Parameters:

  • nx_graph (DiGraph | None) – A directed networkx graph representing the TrackGraph to be created. Hyperedges are represented by networkx nodes that do not have the frame_attribute and are connected to nodes that do have this attribute.

  • frame_attribute (str) – The name of the node attribute that corresponds to the frame (i.e., the time dimension) of the object. Defaults to 't'.

add_edge(edge_id, data)

Adds an edge to this TrackGraph.

Parameters:
Return type:

None

add_from_nx_graph(nx_graph)

Add nodes/edges from nx_graph to this TrackGraph.

Hyperedges are represented by nodes in the nx_graph that do not have the frame_attribute property. All ‘regular’ nodes connected to such a hyperedge node will be added as a hyperedge.

Parameters:

nx_graph (DiGraph) –

A directed networkx graph representing a TrackGraph to be added. Hyperedges are represented by networkx nodes that do not have the frame_attribute and are connected to nodes that do have this attribute.

Duplicate nodes and edges will not be added again but new attributes associated to nodes and edges added. If attributes of existing nodes or edges do already exist, the values set in the given nx_graph will be updating the previously set values.

Return type:

None

add_node(node_id, data)

Adds a new node to this TrackGraph.

Parameters:

  • node_id (int) – the node to be added.

  • data (Mapping[str, Any]) – all properties associated to the added node.

Return type:

None

get_frames()

Return tuple with first and last (exclusive) frame this graph has nodes for.

Returns (t_begin, t_end) where t_end is exclusive. Returns (0, 0) for empty graph.

Return type:

tuple[int, int]

is_hyperedge(edge)

Test if the given edge is a hyperedge in this track graph.

Return type:

TypeGuard[tuple[tuple[int, ...], tuple[int, ...]]]

nodes_by_frame(t)

Get all nodes in frame t.

Return type:

list[Hashable]

nodes_of(edge)

Returns an Iterator of node id’s that are incident to the given edge.

Parameters:

edge (Union[tuple[int, int], tuple[tuple[int, ...], tuple[int, ...]], tuple[int, ...], int]) – an edge of this TrackGraph.

Yields:

all nodes incident to the given edge.

Return type:

Iterator[int]

Solver

class motile.Solver(track_graph)

Create a solver for a given track graph.

Parameters:

track_graph (TrackGraph) – The TrackGraph of objects to track over time.

add_constraint(constraint)

Add linear constraints to the solver.

Parameters:

constraint (Constraint) – The Constraint to add.

Return type:

None

add_cost(cost, name=None)

Add linear cost to the value of variables in this solver.

Parameters:

  • cost (Cost) – The cost to add. An instance of Cost.

  • name (str | None) – An optional name of the , used to refer to weights of cost in an unambiguous manner. Defaults to the name of the cost class, if not given.

Return type:

None

add_variable_cost(index, value, weight)

Add cost for an individual variable.

To be used within implementations of motile.costs.Cost.

Return type:

None

property costs: ndarray

Returns the costs as a numpy.ndarray.

fit_weights(gt_attribute, regularizer_weight=0.1, max_iterations=1000, eps=1e-06)

Fit weights of ILP costs to ground truth with structured SVM.

Updates the weights in the solver object to the found solution.

See https://github.com/funkelab/structsvm for details.

Parameters:

  • gt_attribute (str) –

    Node/edge attribute that marks the ground truth for fitting. gt_attribute is expected to be set to:

    • 1 for objects labaled as ground truth.

    • 0 for objects explicitly labeled as not part of the ground truth.

    • None or not set for unlabeled objects.

  • regularizer_weight (float) – The weight of the quadratic regularizer.

  • max_iterations (int) – Maximum number of gradient steps in the structured SVM.

  • eps (float) – Convergence threshold.

Return type:

None

get_selected_subgraph(solution=None)

Return TrackGraph with only the selected nodes/edges from the solution.

Parameters:

solution (Solution | None) – The solution to use. If not provided, the last solution is used.

Return type:

TrackGraph

Returns:

A new TrackGraph with only the selected nodes and edges.

Raises:

  • RuntimeError – If no solution is provided and the solver has not been solved

  • yet. –

get_variables(cls)

Get variables by their class name.

If the solver does not yet contain those variables, they will be created.

Parameters:

cls (type of motile.variables.Variable) – A subclass of motile.variables.Variable.

Return type:

TypeVar(V, bound= Variable)

Returns:

A singleton instance of Variable (of whatever type was passed in as cls), mimicking a dictionary that can be used to look up variable indices by their keys. See Variable for details.

solve(timeout=0.0, num_threads=1, verbose=False, backend=<Preference.Any: 0>, on_event=None)

Solve the global optimization problem.

Parameters:

  • timeout (float) – The timeout for the ILP solver, in seconds. Default (0.0) is no timeout. If the solver times out, the best solution encountered so far is returned (if any has been found at all).

  • num_threads (int) – The number of threads the ILP solver uses.

  • verbose (bool) – If true, print more information from ILP solver. Defaults to False.

  • backend (Preference) – The ILP solver backend to use. Defaults to Any.

  • on_event (Optional[Callable[[Mapping], None]]) – A callback function that will be called when the solver emits an event. Should accept an event data dict. (see ilpy.EventData for typing info which may be imported inside of a TYPE_CHECKING block.) Defaults to None.

Return type:

Solution

Returns:

ilpy.Solution, a vector of variable values. Use get_variables() to find the indices of variables in this vector.

Variables

Solver variables are introduced by inheriting from the following abstract base class:

class motile.variables.Variable(solver, index_map)

Base class for solver variables.

New variables can be introduced by inheriting from this base class and overwriting instantiate() and optionally instantiate_constraints().

Variable classes should not be instantiated by a user. Instead, the Solver provides access to concrete variables through the class name. The following example shows how to obtain the variable values after optimization:

solver = Solver(graph)

# add costs, constraints...

solution = solver.solve()

# here `node_selected` is an instance of a Variable subclass
# specifically, it will be an instance of NodeSelected, which
# maps node Ids to variables in the solver.
node_selected = solver.get_variables(NodeSelected)

for node in graph.nodes:
    if solution[node_selected[node]] > 0.5:
        print(f"Node {node} was selected")

This allows variables to be added lazily to the solver. Constraints and motile.costs.Cost can ask for variables.

abstract static instantiate(solver)

Create and return keys for the variables.

For example, to create a variable for each node, this function would return a list of all nodes:

@staticmethod
def instantiate(solver):
    return solver.graph.nodes

The solver will create one variable for each key. The index of that variable can be accessed through a dictionary returned by motile.Solver.get_variables():

solver = Solver(graph)

node_selected = solver.get_variables(NodeSelected)

for node in graph.nodes:
    index = node_selected[node]
    print(f"Selection indicator of node {node} has index {index}")
Parameters:

solver (Solver) – The Solver instance to create variables for.

Return type:

Collection[TypeVar(_KT, bound= Hashable)]

Returns:

A collection of keys (anything that is hashable, e.g., nodes of a graph), one for each variable to create.

static instantiate_constraints(solver)

Add constraints for this variable to the solver.

This ensures that these variables are coupled to other variables of the solver.

Parameters:

solver (Solver) – The Solver instance to create variable constraints for.

Return type:

Iterable[Constraint | Expression]

Returns:

A iterable of ilpy.Constraint or ilpy.expressions.Expression. See motile.constraints.Constraint for how to create linear constraints.

The following lists all variables that are already implemented in motile.

NodeSelected

class motile.variables.NodeSelected(solver, index_map)

Binary variable indicating whether a node is part of the solution or not.

EdgeSelected

class motile.variables.EdgeSelected(solver, index_map)

Binary variable indicates whether an edge is part of the solution or not.

NodeAppear

class motile.variables.NodeAppear(solver, index_map)

Binary variable indicating whether a node is the start of a track.

(i.e., the node is selected and has no selected incoming edges).

This variable is coupled to the node and edge selection variables through the following linear constraints:

\[ \begin{align}\begin{aligned}|\text{in_edges}(v)|\cdot x_v - &\sum_{e \in \text{in_edges}(v)} x_e - a_v &\leq&\;\; |\text{in_edges}(v)| - 1\\|\text{in_edges}(v)|\cdot x_v - &\sum_{e \in \text{in_edges}(v)} x_e - a_v\cdot |\text{in_edges}(v)| &\geq&\;\; 0\end{aligned}\end{align} \]

where \(x_v\) and \(x_e\) are selection indicators for node \(v\) and edge \(e\), and \(a_v\) is the appear indicator for node \(v\).

NodeSplit

class motile.variables.NodeSplit(solver, index_map)

Binary variable indicating whether a node has more than one child.

(i.e., the node is selected and has more than one selected outgoing edge).

This variable is coupled to the edge selection variables through the following linear constraints:

\[ \begin{align}\begin{aligned}2 s_v\; - &\sum_{e\in\text{out_edges}(v)} x_e &\leq&\;\; 0\\(|\text{out_edges}(v)| - 1) s_v\; - &\sum_{e\in\text{out_edges}(v)} x_e &\geq&\;\; -1\end{aligned}\end{align} \]

where \(x_e\) are selection indicators for edge \(e\), and \(s_v\) is the split indicator for node \(v\).

Costs

All costs inherit from the following base class:

class motile.costs.Cost

A base class for a cost that can be added to a solver.

abstract apply(solver)

Apply a cost to the given solver.

Use motile.Solver.get_variables() and motile.Solver.add_variable_cost().

Parameters:

solver (Solver) – The Solver to create a cost for.

Return type:

None

The following lists all costs that are already implemented in motile.

Appear

class motile.costs.Appear(weight=1, attribute=None, constant=0, ignore_attribute=None)

Cost for NodeAppear variables.

This is cost is not applied to nodes in the first frame of the graph.

Parameters:

  • weight (float) – The weight to apply to the cost of each starting track.

  • attribute (str | None) – The name of the attribute to use to look up cost. Default is None, which means that a constant cost is used.

  • constant (float) – A constant cost for each node that starts a track.

  • ignore_attribute (str | None) – The name of an optional node attribute that, if it is set and evaluates to True, will not set the appear cost for that node.

EdgeSelection

class motile.costs.EdgeSelection(weight, attribute='cost', constant=0.0)

Cost for EdgeSelected variables.

Parameters:

  • weight (float) – The weight to apply to the cost given by the cost attribute of each edge.

  • attribute (str) – The name of the edge attribute to use to look up cost. Default is 'cost'.

  • constant (float) – A constant cost for each selected edge. Default is 0.0.

NodeSelection

class motile.costs.NodeSelection(weight, attribute='cost', constant=0.0)

Cost for NodeSelected variables.

Parameters:

  • weight (float) – The weight to apply to the cost given by the cost attribute of each node.

  • attribute (str) – The name of the node attribute to use to look up cost. Default is 'cost'.

  • constant (float) – A constant cost for each selected node. Default is 0.0.

Split

class motile.costs.Split(weight=1, attribute=None, constant=0)

Cost for NodeSplit variables.

Parameters:

  • weight (float) – The weight to apply to the cost of each split.

  • attribute (str | None) – The name of the attribute to use to look up the cost. Default is None, which means that a constant cost is used.

  • constant (float) – A constant cost for each node that has more than one selected child.

EdgeDistance

class motile.costs.EdgeDistance(position_attribute, weight=1.0, constant=0.0)

Cost for EdgeSelected variables.

Cost is based on the spatial distance of the incident nodes.

Parameters:

  • position_attribute (str | tuple[str, ...]) – The name of the node attribute that corresponds to the spatial position. Can also be given as a tuple of multiple coordinates, e.g., ('z', 'y', 'x').

  • weight (float) – The weight to apply to the distance to convert it into a cost.

  • constant (float) – A constant cost for each selected node. Default is 0.0.

Features

class motile.costs.Features

Simple container for features with resizeable dimensions.

A Solver has a Features instance.

add_feature(variable_index, feature_index, value)

Add a value to a feature.

Parameters:

  • variable_index (int | Variable) – The index of the variable to add the value to.

  • feature_index (int) – The index of the feature to add the value to.

  • value (float) – The value to add.

Return type:

None

resize(num_variables=None, num_features=None)

Resize the feature matrix.

Parameters:

  • num_variables (int | None) – The number of variables to resize to. If None, the number of variables is not changed.

  • num_features (int | None) – The number of features to resize to. If None, the number of features is not changed.

Return type:

None

to_ndarray()

Export the feature matrix as a numpy array.

Note: you can also use np.asarray(features).

Return type:

ndarray

Weights

Weight

class motile.costs.Weight(initial_value)

A single Weight with observer/callback pattern on update.

See also motile.costs.weights.Weights.

Parameters:

initial_value (float) – The initial value of the weight.

register_modify_callback(callback)

Register a callback to be called when the weight is modified.

Parameters:

callback (Callable[[float, float], Any]) – A function that takes two arguments: the old value and the new value.

Return type:

None

property value: float

Return the value of this weight.

Weights

class motile.costs.Weights

A simple container for weights with observer/callback pattern on update.

A motile.Solver has a Weights instance that is used to store the weights of the model. Changes to the weights can be observed with Solver.weights.register_modify_callback

add_weight(weight, name)

Add a weight to the container.

Parameters:
Return type:

None

from_ndarray(values)

Update weights from an iterable of floats.

Return type:

None

index_of(weight)

Return the index of weight in this container.

Return type:

int

register_modify_callback(callback)

Register callback to be called when a weight is modified.

Parameters:

callback (Callable[[Optional[float], float], Any]) – A function that takes two arguments: the old value (which may be None) and the new value.

Return type:

None

to_ndarray()

Export the weights as a numpy array.

Note: you can also use np.asarray(weights).

Return type:

ndarray

Constraints

All constraints inherit from the following base class:

class motile.constraints.Constraint

A base class for a constraint that can be added to a solver.

abstract instantiate(solver)

Create and return specific linear constraints for the given solver.

Parameters:

solver (Solver) – The Solver instance to create linear constraints for.

Return type:

Iterable[Constraint | Expression]

Returns:

An iterable of ilpy.Constraint.

The following lists all constraints that are already implemented in motile.

MaxChildren

class motile.constraints.MaxChildren(max_children)

Bases: Constraint

Ensures that every selected node has no more than max_children.

Where a “child” is a selected edges to the next frame.

Adds the following linear constraint for each node \(v\):

\[\sum_{e \in \text{out_edges}(v)} x_e \leq \text{max_children}\]
Parameters:

max_children (int) – The maximum number of children allowed.

MaxParents

class motile.constraints.MaxParents(max_parents)

Bases: Constraint

Ensures that every selected node has no more than max_parents.

Where a “parent” is defined as an incoming selected edge from the previous frame.

Adds the following linear constraint for each node \(v\):

\[\sum_{e \in \text{in_edges}(v)} x_e \leq \text{max_parents}\]
Parameters:

max_parents (int) – The maximum number of parents allowed.

ExpressionConstraint

class motile.constraints.ExpressionConstraint(expression, eval_nodes=True, eval_edges=True)

Bases: Constraint

Enforce selection of nodes/edges based on an expression.

The expression string is evaluated with the node/edge dict as a namespace.

This is a powerful general constraint that allows you to select nodes/edges based on any combination of node/edge attributes. The expression string is evaluated for each node/edge (assuming eval_nodes/eval_edges is True) using the actual node object as a namespace to populate any variables names used in the provided expression. If the expression evaluates to True, the node/edge is selected; otherwise, it is excluded.

This takes advantaged of python’s eval function, like this:

my_expression = "some_attribute == True"
eval(my_expression, None, {"some_attribute": True})  # returns True (select)
eval(my_expression, None, {"some_attribute": False})  # returns False (exclude)
eval(my_expression, None, {})  # raises NameError (do nothing)
Parameters:

  • expression (str) – An expression to evaluate for each node/edge. The expression must evaluate to a boolean value. The expression can use any names of node/edge attributes as variables.

  • eval_nodes (bool) – Whether to evaluate the expression for nodes. By default, True.

  • eval_edges (bool) – Whether to evaluate the expression for edges. By default, True.

Example

If the nodes of a graph are:

>>> cells = [
...     {"id": 0, "t": 0, "color": "red", "score": 1.0},
...     {"id": 1, "t": 0, "color": "green", "score": 1.0},
...     {"id": 2, "t": 1, "color": "blue", "score": 1.0},
... ]

Then the following constraint will select node 0:

>>> expr = "t == 0 and color != 'green'"
>>> solver.add_constraints(ExpressionConstraint(expr))

Pin

class motile.constraints.Pin(attribute)

Bases: ExpressionConstraint

Enforces the selection of nodes/edges based on truthiness of a given attribute.

Every node or edge that has the given attribute will be selected if the attribute value is True (and not selected if the attribute value is False). The solver will only determine the selection of nodes and edges that do not have this attribute.

This constraint is useful to complete partial tracking solutions, e.g., when users have already manually selected (or unselected) certain nodes or edges.

Parameters:

attribute (str) – The name of the node/edge attribute to use.