class Cell:
    def __init__(self,v = None, next = None, prev = None, linked = None):
        self.val = v
        self.next = next
        self.prev = prev
        self.linked = linked

class ListDoublChain: # Declarer vide en tant que ListDoubleChain()
    # Creation du pointeur
    def __init__(self,firstCell = None,lastCell = None):
        self.first = firstCell
        self.last = lastCell
        self.size = 0

    def push(self, val): # Ajouter une cellule au tout début de la liste chainee
        tmp = Cell(val)

        tmp.next = self.first

        if self.first != None: # Si on a bien deja une premiere cellule
            self.first.prev = tmp
        else: # Si on a une liste chainee entierement vidée sans cellule
            self.last = tmp # Le dernier et le premier element sont tmp

        self.first = tmp
        self.size += 1

    def push_fin(self, val): # Ajouter une cellule à la fin de la liste chainee
        tmp = Cell(val)

        if self.first != None: # Si on a bien deja une premiere cellule
            self.last.next = tmp # Le dernier et le premier element sont tmp
            tmp.prev = self.last

        else: # Si on a une liste chainee entierement vidée sans cellule
            self.first = tmp

        self.last = tmp
        self.size += 1

    def create_link(self, sommet, linked_values):
        i = 0
        encours = Cell()
        encours.next = self.first
        while encours.next != None:
            encours = encours.next # On passe à la cellule suivante
            i += 1
            if encours.val == sommet:
                encours.linked = linked_values
                return
        print("L'élément {} n'a pas été trouvé".format(sommet))
        return

    def search(self, value):
        i = 0
        encours = Cell()
        encours.next = self.first
        while encours.next != None:
            encours = encours.next # On passe à la cellule suivante
            i += 1
            if encours.val == value:
                return True
        return False

    def afficher(self):
        encours = Cell()
        encours = self.first
        if encours == None:
            print("La liste est vide")
            return
        while encours != None:
            print(encours.val, end = " ")
            encours = encours.next

    def afficher_sommets(self):
        encours = Cell()
        encours = self.first
        print("---- AFFICHAGE DE LA LISTE DOUBLEMENT CHAINEE----")
        if encours == None:
            print("La liste est vide")
            return
        while encours != None:
            if encours.linked != None:
                print("{} : ".format(encours.val), end="")
                encours.linked.afficher()

            print("\n" if encours.next != None else "")
            encours = encours.next

        print("\n---- FIN AFFICHAGE ----")

    def has_value_linked(self, sommet, val):
        encours = Cell()
        encours = self.first
        if encours == None:
            return False
        while encours != None:
            if encours.val == sommet:
                encours_links = Cell()
                encours_links = encours.linked.first
                while encours_links != None:
                    if encours_links.val == val:
                        return True

                    encours_links = encours_links.next

            encours = encours.next
        return False


    def can_be_oriented_graph(self):
        encours_sommets = Cell()
        encours_sommets = self.first
        while encours_sommets != None: # On parcourt les sommets
            encours_links = Cell()
            encours_links = encours_sommets.linked.first
            while encours_links != None: # On parcourt les liens du sommet
                if not self.has_value_linked(encours_links.val, encours_sommets.val): # Si on tombe sur un sommet qui n'existe pas alors False
                    return False

                encours_links = encours_links.next

            encours_sommets = encours_sommets.next

        return True

def is_oriented_graph(A):
    for i in range(len(A)):
        for j in range(len(A[i])):
            if A[i][j] != A[j][i]:
                return False
    return True


if __name__ == '__main__':
    sommets = ListDoublChain()
    sommets.push_fin(0)
    sommet0 = ListDoublChain()
    sommet0.push_fin(1)
    sommet0.push_fin(3)

    sommets.push_fin(1)
    sommet1 = ListDoublChain()
    sommet1.push_fin(0)
    sommet1.push_fin(3)

    sommets.push_fin(2)
    sommet2 = ListDoublChain()
    sommet2.push_fin(3)

    sommets.push_fin(3)
    sommet3 = ListDoublChain()
    sommet3.push_fin(0)
    sommet3.push_fin(1)
    sommet3.push_fin(2)


    sommets.create_link(0,sommet0)
    sommets.create_link(1,sommet1)
    sommets.create_link(2,sommet2)
    sommets.create_link(3,sommet3)

    sommets.afficher_sommets()
    print(sommets.can_be_oriented_graph())
    print("sep")
    #print(sommets.has_value_linked(3,2))