# -*- coding: utf-8 -*-
"""
    CPM.py
    ~~~~~~
    Critical path method

    :author: Jiri Spilka, 2019
"""

import networkx as nx
import matplotlib.pyplot as plt


class CPM(nx.DiGraph):
    """
    Graph representation subclassing networkx.DiGraph
    """

    def __init__(self):
        super().__init__()
        self._makespan = -1
        self._critical_path = None

    def _forward(self):
        """
        Step 1: For each job j that has no predecessors Sj = 0 and Cj = pj
        Step 2: Compute inductively for each remaining job j
            Sj = max Ck_{all k - j}
            Cj = Sj + pj
        Step 3: Cmax = max(C1,..., Cn)

        :return:
        """
        raise NotImplemented

        # self._makespan = ...

    def _backward(self):
        """
        Step 1: For each job j that has no successors Cj = Cmax and Sj = Cmax − pj
        Step 2: Compute inductively for each remaining job j
                Cj = min Sk{ j - all k }
                Sj = Cj − pj
        Step 3: Verify that 0 = min(S1, ... ,Sn)

        :return:
        """
        raise NotImplemented

    def _compute_critical_path(self):
        """
        The jobs whose earliest possible starting times are equal to their latest possible starting times are
        critical jobs.
        A critical path is a chain of jobs which begin at time 0 and ends at Cmax.

        :return:
        """
        raise NotImplemented

        # self._critical_path = ...

    @property
    def makespan(self):
        self.compute()
        return self._makespan

    @property
    def critical_path(self):
        self.compute()
        return self._critical_path

    def compute(self):
        self._forward()
        self._backward()
        self._compute_critical_path()

    def draw_graph(self):

        pos = nx.kamada_kawai_layout(self)  # positions for all nodes

        labels = {v: str(v) for v in cpm.nodes}
        nx.draw_networkx_nodes(self, pos, alpha=0.2)
        nx.draw_networkx_edges(self, pos)
        nx.draw_networkx_labels(self, pos, labels, font_size=16)

        plt.draw()
        plt.show()


if __name__ == "__main__":

    cpm = CPM()

    cpm.add_node(1, p=4)
    cpm.add_node(2, p=9)
    cpm.add_node(3, p=3)
    cpm.add_node(4, p=3)
    cpm.add_node(5, p=6)
    cpm.add_node(6, p=8)
    cpm.add_node(7, p=8)
    cpm.add_node(8, p=12)
    cpm.add_node(9, p=6)

    cpm.add_edges_from([(1, 2), (2, 6), (6, 7)])
    cpm.add_edges_from([(3, 4), (4, 5), (5, 6), (5, 8)])
    cpm.add_edges_from([(8, 7), (8, 9)])

    print('nodes in the graph')
    print(cpm.nodes)

    print('Cmax (makespan)')
    print(cpm.makespan)

    print('nodes on the critical path')
    print(cpm.critical_path.nodes())

    cpm.draw_graph()