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