# 数据模型
import math, random
from pprint import pprint

import get_real_data as grd


class Node(object):
  '''节点类'''

  def __init__(self, node_info: list) -> None:
    self.node_info = node_info
    self.id = node_info[0]
    self.label = node_info[1]
    self.is_flag = node_info[2]
    self.vs_coord = node_info[3]
    self.is_must_node = node_info[4]  # 是否必经节点
    if len(node_info) >= 6: # 如果有实际坐标
      self.label = node_info[5][0]
      self.city = node_info[5]  # 所在城市
      self.real_coord = node_info[6]  # 实际坐标

  def __str__(self):
    # 判断
    if hasattr(self, "city"):
      return (f"<Node Obj - NO: {self.id}, Label: {self.label}"
              f"x,y={self.vs_coord} - {self.city}>")
    return (f"<Node Obj - NO: {self.id}, Label: {self.label}"
              f"x,y={self.vs_coord}> ")


class Edge(object):
  '''链接类'''

  def __init__(self, edge_info):
    self.edge_info = edge_info
    self.id = edge_info[0]
    self.node1_id = edge_info[1]
    self.node2_id = edge_info[2]
    self.is_displayed = edge_info[3]  # 是否显示，连接
    self.is_flagged = edge_info[4]  # 是否标记，路径
    self.label = edge_info[5]  # 标签
    self.distance = edge_info[6]  # 距离成本
    self.time = edge_info[7]  # 时间成本
    self.sequence_number = edge_info[8]  # 连接序号（两点多连接时用）

  def __str__(self):
    return f"<Edge {self.id} node-conn {self.node1_id}-{self.node2_id} distance: {self.distance}>"




class CustomPath:
  '''从连接构造路径'''
  def __init__(self):
    self.Path = []  # 路径对象列表
    self.path_distance_count = 0  # 路径距离成本
    self.path_time_count = 0  # 路径时间成本
    self.graph = {}  # 邻接图
    self.Edges = None
    self.Nodes = None
    self.elapsed_time = 0  # 运行时间

  # def create_one_edge(self,id1, id2, ):
  #   connection_id = len(self.Edges) + 1
  #   node1_id = nodes[i].id
  #   node2_id = nodes[j].id
  #   is_displayed = False
  #   is_flagged = False
  #   label = f"Con{connection_id}"
  #   distance = random.randint(10, 1000)  # 你需要设置实际的距离值
  #   time = random.randint(60, 720)  # 你需要设置实际的时间值
  #   sequence_number = 0

  def creat_edge_data(self, nodes):  # 全连接图
    self.Edges = []
    # 构造全部连接
    for i in range(len(nodes)):
      for j in range(i + 1, len(nodes)):
        for n in range(3):  # 两点多连接
          connection_id = len(self.Edges) + 1
          node1_id = nodes[i].id
          node2_id = nodes[j].id
          is_displayed = False
          is_flagged = False
          label = f"C{connection_id}-{n}"
          distance = random.randint(10, 1000)  # 你需要设置实际的距离值
          time = random.randint(60, 720)  # 你需要设置实际的时间值
          sequence_number = n
          edge_info = [connection_id, node1_id, node2_id, is_displayed, is_flagged, label, distance, time,
                       sequence_number]
          edge = Edge(edge_info)
          self.Edges.append(edge)
    return self.Edges

  def creat_real_edge_data(self, nodes):  # 全连接图
    self.Edges = []
    for i in range(len(nodes)):
      for j in range(i + 1, len(nodes)):
        paths = grd.get_route_planning(nodes[i].real_coord, nodes[j].real_coord, nodes[i].city, nodes[j].city)
        for n in range(len(paths)):
          connection_id = len(self.Edges) + 1
          node1_id = nodes[i].id
          node2_id = nodes[j].id
          is_displayed = False
          is_flagged = False
          label = f"C{connection_id}-{paths[n]['seq']}"
          distance = paths[n]['distance']
          time = paths[n]['time']
          sequence_number = n
          edge_info = [connection_id, node1_id, node2_id, is_displayed, is_flagged, label, distance, time,
                       sequence_number]
          edge = Edge(edge_info)
          self.Edges.append(edge)
    return self.Edges


  def creat_node_data(self, data):
    if isinstance(data, int):
      num = data
    else:
      num = len(data)
    ang = 360 / num
    R = 330
    self.Nodes = []
    for i in range(num):
      rad = math.radians(i * ang)
      x = int(math.cos(rad) * R)
      y = int(math.sin(rad) * R)
      node = [i, str(i), False, [x, y], False]
      if isinstance(data, list):
        node = node+data[i]
      self.Nodes.append(Node(node))
    return self.Nodes



  def edge_select(self, node1, node2):
    node_id = [node1.id, node2.id]
    for edge in self.Edges:
      if edge.node1_id in node_id and edge.node2_id in node_id:
        return edge

  # def set_display_path_(self, node_ids: list):  # 根据节点顺序，创建路径,自动闭环
  #   self.Path = []
  #   for i in range(len(node_ids)):
  #     if i < len(node_ids) - 1:
  #       id1 = node_ids[i];id2 = node_ids[i + 1]
  #     else:
  #       id1 = node_ids[i];id2 = node_ids[0]
  #     node_id = [id1, id2]
  #     for edge in self.Edges:
  #       if edge.node1_id in node_id and edge.node2_id in node_id:
  #         edge.is_flagged = True  # 标记为路径
  #         self.Path.append(edge)
  #   return self.Path


  def set_display_path(self, node_ids:list, Edges:list):  # 根据节点顺序，创建路径,自动闭环,并计算成本
    self.Path = []
    self.path_distance_count = 0
    self.path_time_count = 0
    for i in range(len(node_ids)):
      if i < len(node_ids) - 1:
        id1 = node_ids[i]
        id2 = node_ids[i + 1]
      else:
        id1 = node_ids[i]
        id2 = node_ids[0]
      node_id = [id1, id2]
      for edge in Edges:
        if edge.node1_id in node_id and edge.node2_id in node_id:
          edge.is_flagged = True
          self.Path.append(edge)  # 添加到路径
          self.path_distance_count += edge.distance  # 计算距离成本
          self.path_time_count += edge.time  # 计算时间成本
    return self.Path, self.path_distance_count, self.path_time_count

  def set_display_conn(self, node_ids: list, more=False):  # 选择显示哪些连接，自动闭环
    for i in range(len(node_ids)):
      if i < len(node_ids) - 1:
        id1 = node_ids[i]
        id2 = node_ids[i + 1]
      else:
        id1 = node_ids[i]
        id2 = node_ids[0]
      node_id = [id1, id2]
      seq = random.randint(0,2)
      for edge in self.Edges:
        if edge.node1_id in node_id and edge.node2_id in node_id:
          if not more:
            if edge.sequence_number == seq:
              edge.is_displayed = True
              break
          else:
            edge.is_displayed = True  # 标记为连接可视


  def creat_graph(self, Nodes, is_distance=True):  # 创建邻接图
    '''默认统计距离成本，否则统计时间成本'''
    # 路径归一，让节点之间的路径只留一条权重最小的路径
    self.graph = dict()
    min_edges = [] # 任一两点间的最短路径
    # 限定遍历的两点间路径
    for i in range(len(Nodes)):
      for j in range(i + 1, len(Nodes)):
        ids = [Nodes[i].id, Nodes[j].id]  # 确定点间路径
        min_value = float('inf')
        min_edge = None
        for edge in self.Edges:
          if edge.node1_id in ids and edge.node2_id in ids:
            if edge.is_displayed:   # 显示标志为True,表示已连接
              if is_distance:
                if min_value > edge.distance:
                  min_value = edge.distance
                  min_edge = edge
              else:
                if min_value > edge.time:
                  min_value = edge.time
                  min_edge = edge
        if min_edge is not None:
          min_edges.append(min_edge)

    for node in Nodes:
      self.graph[node.id] = []
      for edge in min_edges:
        if edge.is_displayed:  # 显示标志为True,表示已连接
          node_ids = [edge.node1_id, edge.node2_id]
          if node.id in node_ids:
            node_ids.remove(node.id)  # 去掉自己
            if is_distance:
              self.graph[node.id].append((node_ids[0], edge.distance))
            else:
              self.graph[node.id].append((node_ids[0], edge.time))
    # pprint(self.graph)
    return self.graph, min_edges  # 返回邻接图和点间最短路径列表

  def creat_graph_(self, Path, is_distance=True):  # 根据路径创建邻接图
    self.graph = dict()
    order_nodes = self.Path_to_nodes(Path)
    for node in order_nodes:
      self.graph[node] = []
      for edge in Path:
        if edge.is_displayed:
          node_ids = [edge.node1_id, edge.node2_id]
          if node in node_ids:
            node_ids.remove(node)
            if is_distance:
              self.graph[node].append((node_ids[0], edge.distance))
            else:
              self.graph[node].append((node_ids[0], edge.time))




  def set_display_all_conn(self):  # 显示所有连接
    for edge in self.Edges:
      edge.is_displayed = True

  ###################################  11.8 ##########################
  def find_complete_cycles(self, graph, start_node=0):
    """
    寻找图中所有能够回到起点的完整连接路径。

    Parameters:
    - graph: 图的邻接表示，以字典形式表示每个节点的邻居和权重。
    - start_node: 起始节点，默认为0。

    Returns:
    一个列表，包含所有能够回到起点的完整连接路径。
    每个路径都表示为一个列表，包含按顺序访问的节点。
    """

    def dfs(node, visited, path):
      visited[node] = True
      path.append(node)

      # 如果路径长度等于节点总数 并且最后一个节点是起点的邻接点，表示找到完整的连接路径
      if len(path) == len(graph) and path[-1] in start_neighbors:
        # 找到了一个完整的连接路径
        cycles.append(path.copy())

      # 遍历当前节点的邻居
      for neighbor, _ in graph[node]:
        if not visited[neighbor]:
          dfs(neighbor, visited.copy(), path.copy())

    cycles = []
    visited = [False] * len(graph)
    start_neighbors = [node for node, _ in graph[start_node]]  # 获取起始节点的邻接点
    dfs(start_node, visited, [])
    return cycles

  def find_min_cycles(self,graph,start_node, must_nodes):
    def must_nodes_check(must_nodes, path):
      for node in must_nodes:
        if node not in path:
          return False
      return True
    def dfs(node, visited,path):
      visited[node] = True
      path.append(node)
      # 如果路径长度大于2节点 并且最后一个节点是起点的邻接点，表示找到完整的连接路径
      if len(path) > 2 and path[-1] in start_neighbors:
        if must_nodes_check(must_nodes, path): min_cycles.append(path.copy())
      # 遍历当前节点的邻居
      for neighbor, _ in graph[node]:
        if not visited[neighbor]:
          dfs(neighbor, visited.copy(), path.copy())
    min_cycles = []
    visited = [False] * len(graph)
    start_neighbors = [node for node, _ in graph[start_node]]  # 获取起始节点的邻接点
    dfs(start_node, visited, [])
    return min_cycles

  def traversal_search_to_path(self, graph, start_node=0, must_node=None):  # 遍历搜索
    import time
    start_time = time.time()  # 记录开始时间
    if must_node is not None:
      all_paths = self.find_min_cycles(graph, start_node, must_node)  # 获取所有完整路径
    else:
      all_paths = self.find_complete_cycles(graph, start_node)
    if len(all_paths) == 0:
      return False, f"当前图无法获取完整路径,请检查节点连接是否完整"
    min_path = []  # 计算每个排列组合的路径长度
    min_value = float('inf')
    for permutation in all_paths:  # 遍历所有路径

      current_path = list(permutation) + [start_node]
      current_value = self.calculate_path_dort(graph,
                                              current_path)
      if current_value < min_value:  # 选取距离最小的路径
        min_path = [] # 清空路径
        min_value = current_value
        min_path.append(current_path)
      elif current_value == min_value:
        min_path.append(current_path)
    end_time = time.time()  # 记录结束时间
    self.elapsed_time = end_time - start_time  # 计算运行时间
    return min_path, min_value, self.elapsed_time

  def indeterminate_search_to_path(self, start_node=0, must_nodes=None):
    # 确定必经点和起始点是否有一条完整路径
    for i in range(len(must_nodes)):
      self.graph_check_connectivity(start_node, must_nodes[i])

    pass

  def calculate_path_dort(self, graph, path):  # 根据节点顺序计算节点权重（时间或者距离）
    min_value = 0
    for i in range(len(path) - 1):
      current_node = path[i]
      next_node = path[i + 1]
      if graph[current_node] is not []:
        for edge in graph[current_node]:
          if edge[0] == next_node:
            min_value += edge[1]
            break
      else:
        break
    return min_value

  #############################################
  ############################# 11.9 ########################################
  def greedy_search_to_path(self, graph, start_node=0, must_node=None):

    import time
    start_time = time.time()  # 记录开始时间
    start_neighbors = [node for node, _ in graph[start_node]]  # 获取起始节点的邻接点
    # num_nodes = len(graph)  # 获取节点数
    remaining_nodes = set(graph.keys()) - {start_node}  # 剩余节点
    current_node = start_node  # 当前节点
    path = [start_node]  # 记录路径
    while remaining_nodes:
      # 检查当前节点是否有相邻的边
      if not any(graph[current_node]):
        break
      next_node = None  # 搜寻下一节点
      value = float('inf')
      for nv in graph[current_node]:
        if nv[1] < value and nv[0] not in path:  # 选择剩下节点中值最小的且非已选节点的节点，
          value = nv[1]
          next_node = nv[0]
      # 如果未找到符合条件的节点，退出循环
      if next_node is None:
        label, label2 = None, None
        for node in self.Nodes:
          if node.id == current_node:
            label = node.label
          if node.id == list(remaining_nodes)[0]:
            label2 = node.label
        if label and label2:
          return False, (f"当前贪心路径{path}\n'{label}'的节点无直接路径到"
                       f"'{label2}'的节点贪心算法求解失败"), path
      path.append(next_node)
      remaining_nodes.remove(next_node)
      current_node = next_node
    if path[-1] in start_neighbors:
      path.append(start_node)  # 添加到路径
    else:
      label, label2 = None, None
      for node in self.Nodes:
        if node.id == path[-1]:
          label = node.label
        if node.id == start_node:
          label2 = node.label
      if label and label2:
        return False, (f"当前贪心路径{path}\n'{label}'节点无直接路径到"
                     f"'{label2}'节点贪心算法求解失败"), path
    end_time = time.time()  # 记录结束时间
    self.elapsed_time = end_time - start_time  # 计算运行时间
    return [path], self.calculate_path_dort(graph, path), self.elapsed_time

  #####################################################################################

  ############################# 11.10 ########################################
  def graph_check_connectivity(self, node1, node2):
    """
    检查两点之间是否有完整连接

    Parameters:
    - node1: 第一个节点
    - node2: 第二个节点

    Returns:
    - True: 如果两点有完整连接
    - False: 如果两点没有完整连接
    - None: 如果图的节点或边为 None
    """
    # 检查图的节点和边是否存在
    if self.Nodes is not None and self.Edges is not None:
      find = []  # 使用并查集来检测两点是否互通
      # 初始化并查集，每个节点自成一个集合
      for node in self.Nodes:
        find.append(node.id)

      # 根据已有的边来更新并查集
      for edge in self.Edges:
        if edge.is_displayed:
          x = edge.node1_id
          y = edge.node2_id
          # 路径压缩，找到每个节点所在集合的根节点
          while not x == find[x]:
            x = find[x]
          while not y == find[y]:
            y = find[y]
          # 按秩合并，将秩较小的集合合并到秩较大的集合上
          if x < y:
            find[y] = x
          else:
            find[x] = y

      # 查找两个节点所在集合的根节点
      x = node1.id
      y = node2.id
      while not x == find[x]:
        x = find[x]
      while not y == find[y]:
        y = find[y]

      # 判断两个节点是否在同一个集合
      if find[x] == find[y]:
        return True, x, y
      else:
        return False, x, y
    else:
      # 如果图的节点或边为 None，返回 None
      return None

  ############################# 11.10 ########################################

  ############################# 11.11 ########################################
  def check_user_best(self, Path: list, is_distance=True, start_node=0, must_nodes=None):
    '''检查用户输入的路径是否最优'''
    self.graph, min_edges = self.creat_graph(self.Nodes, is_distance)  # 创建邻接图，默认距离最优，取否则时间最优
    if must_nodes and len(must_nodes) != 0:
      revalue = self.traversal_search_to_path(self.graph, start_node, must_nodes)  # 遍历最优路径
    else:
      revalue = self.traversal_search_to_path(self.graph, start_node)  # 遍历最优路径
    min_path = revalue[0][0]  # 获取最小路径
    if not len(Path) + 1 == len(min_path):  # 节点个数不一样就不匹配
      return False
    min_value = revalue[1]  # 获取最小值
    user_min_value = self.path_distance_time_count(Path, is_distance)  # 计算用户输入路径的值
    if user_min_value == min_value:
      return True
    else:
      return False

  def path_distance_time_count(self, Path: list, is_distance=True):
    min_value = 0
    if not is_distance:
      for path in Path:
        min_value += path.time
      return min_value
    else:
      for path in Path:
        min_value += path.distance
      return min_value

  ############################################################################

  ############################# 11.12 ########################################
  def check_is_greedy(self, Path: list, is_distance=True, start_node: int = 0):
    '''检查用户输入的路径是否是贪心路径'''
    self.graph, min_edges = self.creat_graph(self.Nodes, is_distance)  # 临接图
    revalue = self.greedy_search_to_path(self.graph, start_node)  # 先算出贪心路径
    if not revalue[0]:  # 如果没有找到贪心路径
        return False, "当前图贪心算法求解失败"
    min_path = revalue[0][0]
    if not len(Path)+1 == len(min_path):
      return False, None
    user_paths = self.Path_to_nodes(Path)
    num = len(user_paths)
    for i in range(num):  # 逐个节点进行匹配
      if not user_paths[i] == min_path[i]:
        return False, f"正确的贪心节点顺序为{min_path}\n当前路径不符合贪心规则。"  # 返回不匹配的节点
    return True , None # 返回True表示是贪心路径

  def Path_to_nodes(self, Path, start_node=0):
    paths = [start_node]
    next_node = paths[0]
    for path in Path:
      two_nodes = [path.node1_id, path.node2_id]
      if next_node in two_nodes:
        two_nodes.remove(next_node)
        next_node = two_nodes.pop()
        paths.append(next_node)
    return paths








############################################################################

############################# 11.12 ########################################


############################################################################
if __name__ == '__main__':
  def passs():
    pass

  pa = CustomPath()
  # data = grd.get_district("")
  # Nodes = pa.creat_node_data(6)
  # Edges = pa.creat_edge_data(Nodes)
  # pa.set_display_all_conn()
  # pa.Path_to_nodes(Edges)

  # for node in Nodes:
  #   print(node)

  # pa.set_display_all_conn()   # 全连接
  # conn = pa.check_is_greedy([0, 1,2, 0])
  # print(conn) # 打印判断结果

  # while True:
  #     a = int(input('a:'))
  #     b = int(input('b:'))
  #
  #     conn = pa.graph_check_connectivity(Nodes[a], Nodes[b])
  #
  #     print(conn)

  # # pa.set_display_all_conn()
  # pa.creat_graph(is_distance=True)
  # pprint(pa.graph)
  #
  #
  # # 从节点0开始进行深度优先搜索
  # Path, min_dis,time = pa.traversal_search_to_path(pa.graph)
  # print(Path, min_dis, time)
  # #
  # Path, min_dis, time = pa.greedy_search_to_path(pa.graph)
  # print(Path, min_dis, time)

  graph = {0: [(3, 77), (4, 63), (5, 719), (6, 163), (7, 256)],
           1: [(2, 138), (4, 925), (5, 851), (6, 257), (7, 985)],
           2: [(1, 138), (3, 448), (4, 115), (5, 512), (6, 302)],
           3: [(0, 77), (2, 448), (4, 678), (5, 533), (6, 842)],
           4: [(0, 63), (1, 925), (2, 115), (3, 678), (6, 855), (7, 620)],
           5: [(0, 719), (1, 851), (2, 512), (3, 533), (6, 141), (7, 303)],
           6: [(0, 163), (1, 257), (2, 302), (3, 842), (4, 855), (5, 141)],
           7: [(0, 256), (1, 985), (4, 620), (5, 303)]}
  #
  # a = pa.find_complete_cycles(graph)
  b = pa.find_min_cycles(graph,0,[3])

  #
  # print(pa.graph_check_connectivity(pa.Nodes[0], pa.Nodes[2]))
  #
  # pprint(a)
  pprint(b)