jayljohnson/critical-path-finder

Calculate the critical (longest) path within a network of task dependencies

critical-path-finder

Calculate the critical (longest) path within a network (graph) of weighted task dependencies.

Returns the tasks with dependencies and their weights, and the sum of the weights from those tasks. Also saves a visualization of the graph with the critical path highlighted.

Used for understanding and optimizing any physical or virtual systems.

Quick Start

1. Run from the CLI by:
   1. Using the provided sample inputs with python critical_path_finder.py
   2. Or, pass in paths to your own input and output locations using python critical_path_finder.py -g input/sample_graph.dot -w input/sample_weights.csv -i ../target
2. Or, import this package into another module and pass the graph and node weights inputs into a new CriticalPath object. See CriticalPath.main() for examples.

Important! The node weights must be int's. Handle any unit conversions outside of this module. For example if your weights are measured in fractional hours like 2.25 and you want to keep the values precise, convert them to minutes (2.25 * 60), or seconds (2.25 * 60 * 60). Then the output units will be based on the input units.

CLI Arguments

• -g, --graph: path to the graph .dot file
• -w, --weights: path to the node weight mapping in csv format
• -i, --image-target: path to where the graph image is saved in png format
• --help: view the help menu

Features

1. Read a graph of tasks from one of three sources:
   1. Graphviz digraph file (.dot) by calling CriticalPath.load_graph_from_dot_file()
   2. Networkx DiGraph by passing it into the graph variable during CriticalPath instance creation
   3. Python List of tuples representing graph edges by converting it to a NetworkxDigraph by calling static method CriticalPath._get_digraph_from_tuples(), then passing it into the graph variable during CriticalPath instance creation.
2. Read the weighting of each graph node from one of two sources:
   1. csv file with two columns, the node and the weight
   2. Python dictionary
3. Return the critical path weighted edges as a dictionary of tuples, with the edge weights as the values
4. Save an image of the graph with the critical path highlighted

Examples

Using graphviz .dot files generated by other systems

Save the .dot file to a file, then reference the file path with the Critical Path Finder CLI using the -g flag.

Airflow

Use the Airflow CLI to run: airflow dags show <DAG_ID> –save path/to/file/filename.dot Airflow Docs

Design Assumptions

1. Work is performed as tasks. Task relationships form a graph or network.
2. The graph is directional and does not repeat (acyclic). This graph structure is called a DAG, or DiGraph.
3. Tasks are orchestrated according to the dependencies between tasks
4. The network of task dependencies is managed separately than the orchestration history, and the data structures for each are decoupled. Information about task performance, such as duration or cost, are tracked during task orchestration.
5. The task weight units of measure are varied and could represent time, cost, volume, or something else. The critical path calculation is agnostic to the unit of measure and accepts any integer value. Conversion to or from fractional units happens outside of this module.
6. Don't reinvent the wheel. Focus on ease of use with the inputs and outputs. Use existing and proven graph theory libraries where possible, including networkx and graphviz.

Testing

Run python -m pytest

Credits and References

• For more info on CPM see https://en.wikipedia.org/wiki/Critical_path_method.
• The .dot file sample is based on the example in the Graphviz docs: https://www.graphviz.org/pdf/dotguide.pdf
• Heizer, J and Render. (2004). Operations Management, 7th Ed. Upper Saddle River, NJ: Pearson Education Inc

critical-path-finder's Issues

Add unit tests for file read write operations

Add unit tests for methods where inputs are loaded from files, and where the output image is saved to a file.

Return file object from save_image instead of path

The image generation and storage should be decoupled. Downstream calling applications need the ability to use their own file writing logic

Accept node weights across another dimension such as time

I want the graph visualization to show the critical path as a color gradient, with edges on the critical path across multiple dimension values having a stronger color weighting than edges with fewer dimension values.

For example, for a node weights csv input as:

date, node, weight
20220601, a, 100
20220601, b, 200
20220601, c, 300
20220602, a, 110
20220602, b, 220
20220602, c, 330

And graph as:
(a,b), (b,c), (a,c)

Add setup.py

The requirements.txt currently has the packages to install. This file is used by docker build.

Decide how to keep dependencies for setup.py, add a setup.py, and update setup.cfg

Both docker and pip install to virtualenv should work after the change.

Setup branch protection and PR merge squash as default

Require approval
Require approved PR to merge or commit to main
Default the merge behavior to squash

Improve the output graph .PNG image

Ideas:

• The graph image should render the node and weight labels without overlapping.
• The edge length should be roughly proportional to the edge weight
• The node layout should be rendered in task order from left to right