'''
图

若邻接顶点 u 和 v 的次序无所谓, 则 (u, v) 为无向边(undirected edge)

所有边均无方向的图, 即无向图(undigraph)

反之, 有向图(digraph)中均为有向边(directed edge), u v 分别称作边(u, v)的尾(tail), 头(head)
'''


class 顶点():
    data = None
    inDegree = 0  # 入度
    outDegree = 0  # 出度
    status = 'UNDISCOVERED'  # 状态, 有三种, UNDISCOVERED, DISCOVERED, VISITED
    dTime = -1  # 检索时间
    fTime = -1  # 遍历时间
    parent = None  # 在遍历树中的父节点
    priority = None  # 在遍历树中的优先级

    def __init__(self, data=None):
        self.data = data


class 边():
    data = None  # 数据
    weight = None  # 权重
    status = 'UNDETERMINED'

    def __init__(self, data=None, weight=None):
        self.data = data
        self.weight = weight


class 图():
    '''所有方法中的顶点参数都是索引值'''
    顶点集 = []
    边集 = [[]]
    n = 0  # 顶点数
    e = 0  # 边数

    def __init__(self):
        self.n = 0

    def nextNbr(self, 顶点, 当前邻居顶点):
        '''从顶点的当前邻居顶点开始判断, 直到相连'''
        while (-1 < 当前邻居顶点):
            if self.exists(顶点, 当前邻居顶点) is True:
                return 当前邻居顶点
            else:
                当前邻居顶点 -= 1
        return None

    def firstNbr(self, 顶点):
        '''获取当前顶点的第一个相连的邻居节点'''
        return self.nextNbr(顶点, self.n - 1)

    def exists(self, 顶点A, 顶点B):
        '''判断两个顶点是否相连'''
        return (0 <= 顶点A) and (0 <= 顶点B) and (self.n > 顶点A) and (self.n > 顶点B) and self.边集[顶点A][顶点B] is not None

    def insert_顶点(self, data):
        '''添加一个顶点
        顶点集中添加, 边集的一维列表添加一个元素(总数达到n+1, 索引为n), 边集的每个二维列表添加一个元素(每个总元素数达到n+1, 索引为n), 顶点总数增加1, 返回添加的顶点的索引值
        '''
        顶点_obj = 顶点(data)
        self.顶点集.append(顶点_obj)
        self.边集.append([])
        for i in range(0, self.n):
            self.边集[i].append(None)
            self.边集[self.n].append(None)
        self.边集[self.n].append(None)
        self.n += 1
        return self.n - 1

    def remove_顶点(self, 顶点):
        '''删除一个顶点
        将顶点从顶点集中移出, 将顶点从边集的二维列表中一一移出
        将顶点从边界的一维列表中移出, 返回移出的顶点信息
        '''
        eBak = self.顶点集.pop(顶点)
        for i in range(0, self.n):
            if self.exists(顶点, i) is True:
                self.顶点集p[i].outDegree -= 1
            self.边集[i].pop(顶点)
        for i in range(0, self.n - 1):
            if self.exists(i, 顶点) is True:
                self.顶点集p[i].inDegree -= 1
        self.边集.pop(顶点)
        return eBak

    def insert_边(self, 权重, 顶点A, 顶点B):
        '''添加一条边'''
        if self.exists(顶点A, 顶点B) is True:
            return
        self.边集[顶点A][顶点B] = 边(weight=权重)
        self.e += 1
        self.顶点集[顶点A].outDegree += 1
        self.顶点集[顶点B].inDegree += 1

    def remove_边(self, 顶点A, 顶点B):
        '''移除一条边'''
        if self.exists(顶点A, 顶点B) is False:
            return
        eBak = self.edge_边(顶点A, 顶点B)
        self.边集[顶点A][顶点B] = None
        self.e -= 1
        self.顶点集[顶点A].outDegree -= 1
        self.顶点集[顶点B].inDegree -= 1
        return eBak

    def edge_边(self, 顶点A, 顶点B):
        '''获取边的数据'''
        return self.边集[顶点A][顶点B].data

    def status_边(self, 顶点A, 顶点B):
        '''获取边的状态'''
        return self.边集[顶点A][顶点B].status

    def weight_边(self, 顶点A, 顶点B):
        '''获取边的权重'''
        return self.边集[顶点A][顶点B].weight

    def vertex_顶点(self, i):
        '''获取顶点数据'''
        return self.顶点集[i].data

    def inDegree_顶点(self, i):
        '''获取顶点入度'''
        return self.顶点集[i].inDegree

    def outDegree_顶点(self, i):
        '''获取顶点出度'''
        return self.顶点集[i].outDegree

    def status_顶点(self, i):
        '''获取顶点状态'''
        return self.顶点集[i].status

    def dTime_顶点(self, i):
        '''获取顶点检索时间'''
        return self.顶点集[i].dTime

    def fTime_顶点(self, i):
        '''获取顶点遍历时间'''
        return self.顶点集[i].fTime

    def parent_顶点(self, i):
        '''获取顶点在遍历树中的父亲'''
        return self.顶点集[i].parent

    def priority_顶点(self, i):
        '''获取顶点优先级'''
        return self.顶点集[i].priority

    def BFS(self, 顶点, clock=1):
        '''广度优先搜索'''
        # 将顶点指定为检索中, 并添加到队列中
        queue = [顶点]
        self.顶点集[顶点].status = 'DISCOVERED'
        # 循环队列
        while queue is True:
            # 取出一个并添加设置 clock
            顶点 = queue.pop(0)
            self.顶点集[顶点].dTime = clock
            clock += 1
            # 一一获取相连顶点
            相连顶点 = self.firstNbr(self.n - 1)
            while 相连顶点 is not None:
                # 若相连顶点还未检索到, 添加队列并设置检索状态
                if self.status_顶点(相连顶点) == 'UNDISCOVERED':
                    self.顶点集[相连顶点].status = 'DISCOVERED'
                    queue.append(相连顶点)
                    self.边集[顶点][相连顶点].status = 'TREE'  # 树边
                    self.顶点集[相连顶点].parent = 顶点  # 设置父节点
                else:
                    self.边集[顶点][相连顶点].status = 'CROSS'  # 跨边
                相连顶点 = self.nextNbr(相连顶点 - 1)
            # 访问当前顶点
            self.顶点集[顶点].status = 'VISITED'

    def DFS(self, 顶点, clock=1):
        '''深度优先搜索'''
        self.顶点集[顶点].status = 'DISCOVERED'
        self.顶点集[顶点].dTime = clock
        clock += 1
        相连顶点 = self.firstNbr(self.n - 1)
        while 相连顶点 is not None:
            if self.status_顶点(相连顶点) == 'UNDISCOVERED':
                self.边集[顶点][相连顶点].status = 'TREE'  # 树边
                self.顶点集[相连顶点].parent = 顶点  # 设置父节点
                self.DFS(相连顶点, clock)
            elif self.status_顶点(相连顶点) == 'DISCOVERED':  # 已被发现但未访问, 属被后代指向的祖先
                self.边集[顶点][相连顶点].status = 'BACKWARD'
            else:  # 已访问完毕, 视承袭关系分为向前边或跨边
                self.边集[顶点][相连顶点].status = 'FORWARD' if self.dTime_顶点(相连顶点) > self.dTime_顶点(顶点) else 'CROSS'
            相连顶点 = self.nextNbr(相连顶点 - 1)
        # 访问当前顶点
        self.顶点集[顶点].status = 'VISITED'
        self.顶点集[顶点].fTime = clock
        clock += 1

    def __del__(self):
        for i in range(0, self.n):
            for j in range(0, self.n):
                self.边集[i].pop(j)