# Path: graph_theory/spfa.py
# def spfa(source, num_nodes, weights, neighbor_list, epsilon=10E-5):
#     """Shortest Paths Fastests Algorithm - think optimized Bellman-Ford,
# 
#         Assumes nodes have numbers from 0 to num_nodes (inclusive).
#         Returns two variables:
#             success - true if no negative cycle
#             distances - shortest distance from the source to each node
#                         or None if negative cycle
#         """
#     # None is Infinity
#     distance = [None] * num_nodes
#     currently_in_queue = [False for i in range(num_nodes)]
#     times_in_queue = [0 for _ in range(num_nodes)]
#     predecessor = [None for _ in range(num_nodes)]
#     q = deque()
# 
#     distance[source] = 0
#     currently_in_queue[source] = True
#     times_in_queue[source] = 1
#     q.append(0)
# 
#     negative_cycle_exists = False
# 
#     while len(q) > 0 and not negative_cycle_exists:
#         node = q.popleft()
#         currently_in_queue[node] = False
#         for neighbor in neighbor_list[node]:
# 
#             if (distance[neighbor] is None or
#                         distance[neighbor] > distance[node] + weights[(node, neighbor)] + epsilon):
#                 predecessor[neighbor] = node
# 
#                 distance[neighbor] = distance[node] + weights[(node, neighbor)]
#                 if not currently_in_queue[neighbor]:
#                     currently_in_queue[neighbor] = True
#                     times_in_queue[neighbor] += 1
#                     if times_in_queue[neighbor] > num_nodes:
#                         negative_cycle_exists = True
#                         break
#                     q.append(neighbor)
# 
#     if negative_cycle_exists:
#         visited = [False for _ in range(num_nodes)]
#         negative_cycle = None
# 
#         for node in range(num_nodes):
#             if not visited[node]:
#                 # Here we are extracting cycle in predecessor graph.
#                 # If we find any cycle it is necessarily negative cycle
#                 # because predecessor graph cannot be cyclic otherwise.
#                 potential_cycle_node = node
#                 potential_cycle = []
#                 while predecessor[potential_cycle_node] is not None and not visited[predecessor[potential_cycle_node]]:
#                     # print(str(predecessor[potential_cycle_node]) + '->' + str(potential_cycle_node) + ':' + str(weights[(predecessor[potential_cycle_node], potential_cycle_node)]))
#                     potential_cycle_node = predecessor[potential_cycle_node]
#                     potential_cycle.append(potential_cycle_node)
#                     visited[potential_cycle_node] = True
#                 # If the predecessor of the last node was already visited in this run we have our cycle.
#                 # it is not necessary spanning the entire array (we could have "entered" on cycle through
#                 # simple path.
#                 if predecessor[potential_cycle_node] in potential_cycle:
#                     # print(str(predecessor[potential_cycle_node]) + '->' + str(potential_cycle_node) + ':' + str(weights[(predecessor[potential_cycle_node], potential_cycle_node)]))
#                     cycle_start_index = potential_cycle.index(predecessor[potential_cycle_node])
#                     negative_cycle = list(reversed(potential_cycle[cycle_start_index:]))
#                     break
#                 visited[node] = True
# 
#         assert negative_cycle is not None
#         # print("NCycle size: " + str(len(negative_cycle)))
#         return distance, negative_cycle
#     else:
#         return distance, None
# 
# Path: controllability/distance_graph_edge.py
# class EdgeType(object):
#     SIMPLE = 1
#     LOWER_CASE = 2
#     UPPER_CASE = 3
# 
# class DistanceGraphEdge(object):
#     def __init__(self, fro, to, value, edge_type, maybe_letter=None, renaming=None):
#         self.fro = fro
#         self.to = to
#         self.value = value
#         self.edge_type = edge_type
#         self.maybe_letter = maybe_letter
#         self.renaming = renaming
# 
#     def hash(self):
#         return hash((self.fro, self.to, self.value, self.edge_type, self.maybe_letter))
# 
#     def _printit(self, fro, to, maybe_letter):
#         type_str = ''
#         if self.edge_type == EdgeType.UPPER_CASE:
#             type_str = 'UC(%s):' % maybe_letter
#         elif self.edge_type == EdgeType.LOWER_CASE:
#             type_str = 'LC(%s):' % maybe_letter
#         return '%s\t\t---[%s%.1f]---> \t\t%s' % (fro,
#                                     type_str,
#                                     self.value,
#                                     to)
# 
#     def __unicode__(self):
#         if self.renaming is None:
#             return self._printit(self.fro, self.to, self.maybe_letter)
#         else:
#             return self._printit(self.renaming[self.fro],
#                           self.renaming[self.to],
#                           self.renaming[self.maybe_letter]
#                           if self.maybe_letter is not None else None)
# 
# 
#     def __str__(self):
#         return self.__unicode__()
# 
# Path: controllability/temporal_consistency.py
# class EdgeSupport(object):
#     BASE = 1
#     DERIVED = 2
#     UPPER = 1
#     LOWER = 2
# 
#     @staticmethod
#     def base(expression):
#         es = EdgeSupport()
#         es.type = EdgeSupport.BASE
#         es.expression = expression
#         return es
# 
#     @staticmethod
#     def derived(parent1, parent2):
#         es = EdgeSupport()
#         es.type = EdgeSupport.DERIVED
#         es.parents = [parent1, parent2]
#         return es


from collections import defaultdict
from queue import PriorityQueue
from graph_theory import spfa
from controllability.distance_graph_edge import EdgeType, DistanceGraphEdge
from controllability.temporal_consistency import EdgeSupport
import math


class MorrisN4Dc(object):
    """Implementation based on paper "A Structural Characterization of Temporal
    Dynamic Controllability" by Paul Morris"""

    def __init__(self):
        self.edge_support = {}
        self.moat_edges = set()

# Path: graph_theory/spfa.py
# def spfa(source, num_nodes, weights, neighbor_list, epsilon=10E-5):
#     """Shortest Paths Fastests Algorithm - think optimized Bellman-Ford,
# 
#         Assumes nodes have numbers from 0 to num_nodes (inclusive).
#         Returns two variables:
#             success - true if no negative cycle
#             distances - shortest distance from the source to each node
#                         or None if negative cycle
#         """
#     # None is Infinity
#     distance = [None] * num_nodes
#     currently_in_queue = [False for i in range(num_nodes)]
#     times_in_queue = [0 for _ in range(num_nodes)]
#     predecessor = [None for _ in range(num_nodes)]
#     q = deque()
# 
#     distance[source] = 0
#     currently_in_queue[source] = True
#     times_in_queue[source] = 1
#     q.append(0)
# 
#     negative_cycle_exists = False
# 
#     while len(q) > 0 and not negative_cycle_exists:
#         node = q.popleft()
#         currently_in_queue[node] = False
#         for neighbor in neighbor_list[node]:
# 
#             if (distance[neighbor] is None or
#                         distance[neighbor] > distance[node] + weights[(node, neighbor)] + epsilon):
#                 predecessor[neighbor] = node
# 
#                 distance[neighbor] = distance[node] + weights[(node, neighbor)]
#                 if not currently_in_queue[neighbor]:
#                     currently_in_queue[neighbor] = True
#                     times_in_queue[neighbor] += 1
#                     if times_in_queue[neighbor] > num_nodes:
#                         negative_cycle_exists = True
#                         break
#                     q.append(neighbor)
# 
#     if negative_cycle_exists:
#         visited = [False for _ in range(num_nodes)]
#         negative_cycle = None
# 
#         for node in range(num_nodes):
#             if not visited[node]:
#                 # Here we are extracting cycle in predecessor graph.
#                 # If we find any cycle it is necessarily negative cycle
#                 # because predecessor graph cannot be cyclic otherwise.
#                 potential_cycle_node = node
#                 potential_cycle = []
#                 while predecessor[potential_cycle_node] is not None and not visited[predecessor[potential_cycle_node]]:
#                     # print(str(predecessor[potential_cycle_node]) + '->' + str(potential_cycle_node) + ':' + str(weights[(predecessor[potential_cycle_node], potential_cycle_node)]))
#                     potential_cycle_node = predecessor[potential_cycle_node]
#                     potential_cycle.append(potential_cycle_node)
#                     visited[potential_cycle_node] = True
#                 # If the predecessor of the last node was already visited in this run we have our cycle.
#                 # it is not necessary spanning the entire array (we could have "entered" on cycle through
#                 # simple path.
#                 if predecessor[potential_cycle_node] in potential_cycle:
#                     # print(str(predecessor[potential_cycle_node]) + '->' + str(potential_cycle_node) + ':' + str(weights[(predecessor[potential_cycle_node], potential_cycle_node)]))
#                     cycle_start_index = potential_cycle.index(predecessor[potential_cycle_node])
#                     negative_cycle = list(reversed(potential_cycle[cycle_start_index:]))
#                     break
#                 visited[node] = True
# 
#         assert negative_cycle is not None
#         # print("NCycle size: " + str(len(negative_cycle)))
#         return distance, negative_cycle
#     else:
#         return distance, None
# 
# Path: controllability/distance_graph_edge.py
# class EdgeType(object):
#     SIMPLE = 1
#     LOWER_CASE = 2
#     UPPER_CASE = 3
# 
# class DistanceGraphEdge(object):
#     def __init__(self, fro, to, value, edge_type, maybe_letter=None, renaming=None):
#         self.fro = fro
#         self.to = to
#         self.value = value
#         self.edge_type = edge_type
#         self.maybe_letter = maybe_letter
#         self.renaming = renaming
# 
#     def hash(self):
#         return hash((self.fro, self.to, self.value, self.edge_type, self.maybe_letter))
# 
#     def _printit(self, fro, to, maybe_letter):
#         type_str = ''
#         if self.edge_type == EdgeType.UPPER_CASE:
#             type_str = 'UC(%s):' % maybe_letter
#         elif self.edge_type == EdgeType.LOWER_CASE:
#             type_str = 'LC(%s):' % maybe_letter
#         return '%s\t\t---[%s%.1f]---> \t\t%s' % (fro,
#                                     type_str,
#                                     self.value,
#                                     to)
# 
#     def __unicode__(self):
#         if self.renaming is None:
#             return self._printit(self.fro, self.to, self.maybe_letter)
#         else:
#             return self._printit(self.renaming[self.fro],
#                           self.renaming[self.to],
#                           self.renaming[self.maybe_letter]
#                           if self.maybe_letter is not None else None)
# 
# 
#     def __str__(self):
#         return self.__unicode__()
# 
# Path: controllability/temporal_consistency.py
# class EdgeSupport(object):
#     BASE = 1
#     DERIVED = 2
#     UPPER = 1
#     LOWER = 2
# 
#     @staticmethod
#     def base(expression):
#         es = EdgeSupport()
#         es.type = EdgeSupport.BASE
#         es.expression = expression
#         return es
# 
#     @staticmethod
#     def derived(parent1, parent2):
#         es = EdgeSupport()
#         es.type = EdgeSupport.DERIVED
#         es.parents = [parent1, parent2]
#         return es


# Path: controllability/morris_n4_dc.py
from collections import defaultdict
from queue import PriorityQueue
from graph_theory import spfa
from controllability.distance_graph_edge import EdgeType, DistanceGraphEdge
from controllability.temporal_consistency import EdgeSupport
import math



class MorrisN4Dc(object):
    """Implementation based on paper "A Structural Characterization of Temporal
    Dynamic Controllability" by Paul Morris"""

    def __init__(self):
        self.edge_support = {}
        self.moat_edges = set()

        self.includeReductionCycle = True