Basic Graphs

The main idea in this package is to order the execution of the CP algorithms based on their data dependencies. The full implementation contains many extra complications so we will start with a very simple example to demonstrate this approach. The full code for this example is at the end of this page.

Building the Graph

The job can be described by a Directed Acyclic Graph (DAG). Each node declares the data that it produces and the data that it requires. Edges are then added pointing from the producer of the data to any node that requires it, indicating a dependency. Nodes are added into a GraphBuilder instances and then the dependency graph is constructed using the build_graph method.

# Create the builder and add in some simple nodes
builder = GraphBuilder()
builder += [
    BasicNode("A", produces=["a", "b"]),
    BasicNode("B", produces=["c"], requires=["a"]),
    BasicNode("C", produces=["d"], requires=["b"], priority=10),
    BasicNode("D", produces=["e"], requires=["c"], priority=20),
    BasicNode("E", requires=["d", "e"]),
]

# Create the graph
graph = builder.build_graph(ignore_unmet=False)

The example here produces the following graph (data dependencies are labeled by the data item which caused them).

Note that the dependency graph can never contain any cycles as this would make it impossible to determine a valid execution order.

Additional Dependencies

Additional dependencies can also be declared on the builder using either the add_strong_dependency method or the add_weak_dependency method. A strong dependency acts exactly the same as a data dependency and the graph is forced to obey them. A weak dependency acts as hint to the scheduler, it will try to order nodes to respect them but will ignore it if it would introduce a cycle.

Determining the Execution Order

Once the graph has been constructed the order in which to traverse the graph must be determined. This is done using the order_graph method.

# Calculate and annotate the execution order
order = builder.order_graph(graph)
builder.annotate_order(graph, order)

This uses an technique called lexicographical topological sorting which ensures that a node appears before any of its dependencies. Ties after this are resolved through the _make_node_key_func method. The default implementation will first try to obey any weak dependencies and then place higher priority nodes first. Finally any remaining nodes will be placed in the order that they were entered into the builder.

Here, the order of B and C is not determined by their dependencies, but because C has a higher priority it is placed first.

We can add a weak dependency to force these nodes to be ordered differently.

# Use a weak dependency to force the builder to order B before C
builder.add_weak_dependency("B", "C")
reorder = builder.order_graph(graph)
builder.annotate_order(graph, reorder)

Full Code

from operator import attrgetter
from typing import Iterable, Set

import matplotlib.pyplot as plt
import networkx as nx
from cpalgnodes.drawing import GraphDrawer, GraphDrawerConfig, multipartite_layout
from cpalgnodes.graph import BaseNode, GraphBuilder


class BasicNode(BaseNode):
    """Simple node class used for examples"""

    def __init__(
        self,
        name: str,
        produces: Iterable[str] = (),
        requires: Iterable[str] = (),
        priority: int = 0,
    ):
        """Create the node"""
        self._name = name
        self._produces = set(produces)
        self._requires = set(requires)
        self._priority = priority

    @property
    def name(self) -> str:
        return self._name

    def __hash__(self) -> int:
        return hash(self.name)

    def __eq__(self, other: "BasicNode"):
        return (
            self.name == other.name
            and self.produces == other.produces
            and self.requires == other.requires
            and self.priority == other.priority
        )

    @property
    def produces(self) -> Set[str]:
        return self._produces

    @property
    def requires(self) -> Set[str]:
        return self._requires

    @property
    def priority(self) -> int:
        return self._priority


# [create-graph]
# Create the builder and add in some simple nodes
builder = GraphBuilder()
builder += [
    BasicNode("A", produces=["a", "b"]),
    BasicNode("B", produces=["c"], requires=["a"]),
    BasicNode("C", produces=["d"], requires=["b"], priority=10),
    BasicNode("D", produces=["e"], requires=["c"], priority=20),
    BasicNode("E", requires=["d", "e"]),
]

# Create the graph
graph = builder.build_graph(ignore_unmet=False)
# [end-create-graph]

# Create a layout to use in the visualisation
# layout = nx.spring_layout(graph)
layout = multipartite_layout(graph)

# Draw the nodes with their dependency relations
fig, ax = plt.subplots()
GraphDrawer(GraphDrawerConfig(draw_total_order=False)).draw_mpl(
    graph, ax=ax, layout=layout
)
fig.savefig("basic_no_order.svg")

# [order-graph]
# Calculate and annotate the execution order
order = builder.order_graph(graph)
builder.annotate_order(graph, order)
# [end-order-graph]

# Draw the nodes with the calculated execution order
fig, ax = plt.subplots()
GraphDrawer().draw_mpl(graph, ax=ax, layout=layout)
fig.savefig("basic_order.svg")

# [reorder-graph]
# Use a weak dependency to force the builder to order B before C
builder.add_weak_dependency("B", "C")
reorder = builder.order_graph(graph)
builder.annotate_order(graph, reorder)
# [end-reorder-graph]

fig, ax = plt.subplots()
GraphDrawer().draw_mpl(graph, ax=ax, layout=layout)
fig.savefig("basic_reorder.svg")