============
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 <#full-code>`_.

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 <../cpalgnodes.graph.html#cpalgnodes.graph.GraphBuilder>`_ instances and then the dependency graph is constructed using the `build_graph <../cpalgnodes.graph.html#cpalgnodes.graph.GraphBuilder.build_graph>`_ method.

.. literalinclude:: ../../examples/basic.py
    :language: python
    :start-after: # [create-graph]
    :end-before: # [end-create-graph]

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

.. image:: ../images/basic_no_order.svg

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 <../cpalgnodes.graph.html#cpalgnodes.graph.GraphBuilder.add_strong_dependency>`_ method or the `add_weak_dependency <../cpalgnodes.graph.html#cpalgnodes.graph.GraphBuilder.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 <../cpalgnodes.graph.html#cpalgnodes.graph.GraphBuilder.order_graph>`_ method.

.. literalinclude:: ../../examples/basic.py
    :language: python
    :start-after: # [order-graph]
    :end-before: # [end-order-graph]

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 <../cpalgnodes.graph.htmll#cpalgnodes.graph.GraphBuilder._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.

.. image:: ../images/basic_order.svg

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.

.. literalinclude:: ../../examples/basic.py
    :language: python
    :start-after: # [reorder-graph]
    :end-before: # [end-reorder-graph]

.. image:: ../images/basic_reorder.svg

Full Code
---------

.. literalinclude:: ../../examples/basic.py
    :language: python