AISD_Grafy_v3

import sys
import random
import copy

# Globalna zmienna ktora okresla czy istnieja cykle w grafie
cyclic = False

###############################################################
# Funkcje Sluzace Generowaniu Reprezentacji Maszynowych Grafu #
###############################################################

def wczytaj_graf(lista_krawedzi):
    nazwa_pliku = input("Podaj nazwe pliku odczytu: ")
    try:
        plik = open(nazwa_pliku, 'r')
    except FileNotFoundError:
        print("Nie znaleziono wskazanego pliku!")
        plik.close()
        sys.exit()
    ilosc_wierzcholkow, ilosc_krawedzi = plik.readline().split()
    ilosc_wierzcholkow = int(ilosc_wierzcholkow)
    ilosc_krawedzi = int(ilosc_krawedzi)
    for line in plik:
        if not line.split():
            break
        wierzcholek1, wierzcholek2 = line.split()
        wierzcholek1 = int(wierzcholek1)
        wierzcholek2 = int(wierzcholek2)
        lista_krawedzi.append([wierzcholek1, wierzcholek2])
    if cykle(lista_krawedzi, ilosc_wierzcholkow) == False:
        print("Graf z pliku nie jest acykliczny!")
        plik.close()
        sys.exit()
    #print(cyclic)
    plik.close()
    return ilosc_wierzcholkow, ilosc_krawedzi

def generuj_graf(ilosc_wierzcholkow, ilosc_krawedzi, nasycenie, lista_krawedzi):
    ilosc_krawedzi = int(ilosc_wierzcholkow*(ilosc_wierzcholkow - 1)*0.5*(nasycenie/100))
    for i in range(ilosc_krawedzi):
        brak_cykli = False
        while brak_cykli == False:
            powtarza_sie = False
            wierzcholek1 = random.randrange(0, ilosc_wierzcholkow)
            wierzcholek2 = copy.copy(wierzcholek1)
            while wierzcholek1 == wierzcholek2:
                wierzcholek2 = random.randrange(0, ilosc_wierzcholkow)
            for krawedz in lista_krawedzi:
                if krawedz == [wierzcholek1, wierzcholek2] or krawedz == [wierzcholek2, wierzcholek1]:
                    powtarza_sie = True
                    break
            if powtarza_sie == False:
                lista_krawedzi.append([wierzcholek1, wierzcholek2])
                if cykle(copy.copy(lista_krawedzi), ilosc_wierzcholkow) == True:
                    #print("Jest dodany!")
                    brak_cykli = True
                else:
                    lista_krawedzi.pop()

def tworz_lnastepnikow(ilosc_wierzcholkow, lista_krawedzi, lista_nastepnikow):
    for i in range(ilosc_wierzcholkow):
        lista_nastepnikow.append([])
    for krawedz in lista_krawedzi:
        lista_nastepnikow[krawedz[0]].append(krawedz[1])
    for i in range(len(lista_nastepnikow)):
        lista_nastepnikow[i].sort()
    #print(lista_nastepnikow)

def tworz_msasiedztwa(ilosc_wierzcholkow, lista_krawedzi, macierz_sasiedztwa):
    # wypelnianie macierzy WxW zerami
    for i in range(ilosc_wierzcholkow):
        macierz_sasiedztwa.append([])
        for j in range(ilosc_wierzcholkow):
            macierz_sasiedztwa[i].append(0)
    # wpisywanie jedynek w odpowiednie miejsca, tam gdzie istnieje krawedz (luk)
    for krawedz in lista_krawedzi:
        macierz_sasiedztwa[krawedz[0]][krawedz[1]] = 1
    print(macierz_sasiedztwa)

def DFS_test(lista_krawedzi, odwiedzone, wierzcholek):
    #print(type(wierzcholek))
    global cyclic
    odwiedzone[wierzcholek] = "szary"
    for krawedz in lista_krawedzi:
        if krawedz[0] == wierzcholek:
            if odwiedzone[krawedz[1]] == "czarny":
                continue
            if odwiedzone[krawedz[1]] == "szary":
                #print("Cykliczny!")
                cyclic = True
                return False
            DFS_test(lista_krawedzi, odwiedzone, krawedz[1])
            odwiedzone[krawedz[1]] = "czarny"
    for i in range(len(odwiedzone)):
        if odwiedzone[i] == "bialy":
            DFS_test(lista_krawedzi, odwiedzone, i)

def cykle(lista_krawedzi, ilosc_wierzcholkow):
    global cyclic
    cyclic = False
    if(len(lista_krawedzi) == 0):
        return True
    odwiedzone = []
    for i in range(ilosc_wierzcholkow):
        odwiedzone.append("bialy")
    DFS_test(lista_krawedzi, odwiedzone, lista_krawedzi[0][0])
    if cyclic == True:
        return False
    else:
        return True

def wyswietl_krawedzie(lista_krawedzi):
    for krawedz in lista_krawedzi:
        print(krawedz[0], krawedz[1], sep='->')

#############################################
# Funkcje Sluzace Sortowaniu Topologicznemu #
#############################################

#Kontroluje wszystkie algorytmy sortowania topologicznego poprzez DFS
def DFS_manager(lista_krawedzi, lista_nastepnikow, macierz_sasiedztwa, ilosc_wierzcholkow):
    print("Sortowanie topologicznie DFS")
    # Krawedzie
    odwiedzone_krawedzie = []
    posortowane_wierzcholki1 = []
    for i in range(ilosc_wierzcholkow):
        odwiedzone_krawedzie.append("bialy")
    for i in range(len(odwiedzone_krawedzie)):
        if odwiedzone_krawedzie[i] == "bialy":
            DFS_lkrawedzi(lista_krawedzi, odwiedzone_krawedzie, i, posortowane_wierzcholki1)
    print("Lista krawedzi:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki1)
    # Nastepniki
    odwiedzone_nastepniki = []
    posortowane_wierzcholki2 = []
    for i in range(ilosc_wierzcholkow):
        odwiedzone_nastepniki.append("bialy")
    for i in range(len(odwiedzone_krawedzie)):
        if odwiedzone_nastepniki[i] == "bialy":
            DFS_lnastepnikow(lista_nastepnikow, odwiedzone_nastepniki, i, posortowane_wierzcholki2)
    print("Lista nastepnikow:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki2)
    # Macierz
    odwiedzone_macierz = []
    posortowane_wierzcholki3 = []
    for i in range(ilosc_wierzcholkow):
        odwiedzone_macierz.append("bialy")
    for i in range(len(odwiedzone_krawedzie)):
        if odwiedzone_macierz[i] == "bialy":
            DFS_msasiedztwa(macierz_sasiedztwa, odwiedzone_macierz, i, posortowane_wierzcholki3)
    print("Macierz sasiedztwa:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki3)

def DFS_lkrawedzi(lista_krawedzi, odwiedzone, wierzcholek, posortowane):
    odwiedzone[wierzcholek] = "szary"
    for krawedz in lista_krawedzi:
        if krawedz[0] == wierzcholek:
            if odwiedzone[krawedz[1]] == "czarny":
                continue
            if odwiedzone[krawedz[1]] == "szary":
                return False
            DFS_lkrawedzi(lista_krawedzi, odwiedzone, krawedz[1], posortowane)
    odwiedzone[wierzcholek] = "czarny"
    posortowane.insert(0, wierzcholek)

def DFS_lnastepnikow(lista_nastepnikow, odwiedzone, wierzcholek, posortowane):
    odwiedzone[wierzcholek] = "szary"
    for i in range(len(lista_nastepnikow[wierzcholek])):
        if odwiedzone[lista_nastepnikow[wierzcholek][i]] == "czarny":
            continue
        if odwiedzone[lista_nastepnikow[wierzcholek][i]] == "szary":
            return False
        DFS_lnastepnikow(lista_nastepnikow, odwiedzone, lista_nastepnikow[wierzcholek][i], posortowane)
    odwiedzone[wierzcholek] = "czarny"
    posortowane.insert(0, wierzcholek)

def DFS_msasiedztwa(macierz_sasiedztwa, odwiedzone, wierzcholek, posortowane):
    odwiedzone[wierzcholek] = "szary"
    for i in range(len(macierz_sasiedztwa[wierzcholek])):
        if macierz_sasiedztwa[wierzcholek][i] == 1:
            if odwiedzone[i] == "czarny":
                continue
            if odwiedzone[i] == "szary":
               return False
            DFS_msasiedztwa(macierz_sasiedztwa, odwiedzone, i, posortowane)
    odwiedzone[wierzcholek] = "czarny"
    posortowane.insert(0, wierzcholek)

def DEL_manager(lista_krawedzi, lista_nastepnikow, macierz_sasiedztwa, ilosc_wierzcholkow):
    print("Sortowanie topologiczne DEL")
    posortowane_wierzcholki1 = []
    posortowane_wierzcholki2 = []
    posortowane_wierzcholki3 = []
    stopnie1 = []
    stopnie2 = []
    stopnie3 = []
    for i in range(ilosc_wierzcholkow):
        stopnie1.append(0)
        stopnie2.append(0)
        stopnie3.append(0)
    DEL_lkrawedzi(lista_krawedzi, stopnie1, posortowane_wierzcholki1)
    print("Lista krawedzi:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki1)
    DEL_lnastepnikow(lista_nastepnikow, stopnie2, posortowane_wierzcholki2)
    print("Lista nastepnikow:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki2)
    DEL_msasiedztwa(macierz_sasiedztwa, stopnie3, posortowane_wierzcholki3)
    print("Macier sasiedztwa:")
    print("Wierzcholki posortowane topologicznie:", posortowane_wierzcholki3)

def DEL_lkrawedzi(lista_krawedzi, stopnie, posortowane):
    for i in range(len(stopnie)):
        for krawedz in lista_krawedzi:
            if krawedz[1] == i:
                stopnie[i] += 1
    while len(stopnie) != len(posortowane):
        for i in range(len(stopnie)):
            if stopnie[i] == 0 and i not in posortowane:
                for krawedz in lista_krawedzi:
                    if krawedz[0] == i:
                        stopnie[krawedz[1]] -= 1
                posortowane.append(i)

def DEL_lnastepnikow(lista_nastepnikow, stopnie, posortowane):
    for nastepniki in lista_nastepnikow:
        for nastepnik in nastepniki:
            stopnie[nastepnik] += 1
    while len(stopnie) != len(posortowane):
        for i in range(len(stopnie)):
            if stopnie[i] == 0 and i not in posortowane:
                for nastepniki in lista_nastepnikow[i]:
                    stopnie[nastepniki] -= 1
                posortowane.append(i)

def DEL_msasiedztwa(macierz_sasiedztwa, stopnie, posortowane):
    for i in range(len(macierz_sasiedztwa)):
        for j in range(len(macierz_sasiedztwa)):
            if macierz_sasiedztwa[i][j] == 1:
                stopnie[j] += 1
    while len(stopnie) != len(posortowane):
        for i in range(len(stopnie)):
            if stopnie[i] == 0 and i not in posortowane:
                for j in range(len(macierz_sasiedztwa[i])):
                    if macierz_sasiedztwa[i][j] == 1:
                        stopnie[j] -= 1
                posortowane.append(i)


############################################
# Funkcja Glowna                           #
############################################

def main():
    # przechowuje opcje jaka wybral uzytkownik
    usr_input = 0
    # ilosc wierzcholkow grafu
    ilosc_wierzcholkow = 0
    # ilosc krawedzi grafu
    ilosc_krawedzi = 0
    # procent nasycenia krawedzi w grafie
    nasycenie = 0
    # lista krawedzi grafu
    lista_krawedzi = []
    # lista nastepnikow grafu
    lista_nastepnikow = []
    # macierz sasiedztwa grafu
    macierz_sasiedztwa = []
    while usr_input != 1 and usr_input != 2:
        try:
            usr_input = int(input("Wybierz opcję: 1) Wczytaj graf 2) Generuj graf: "))
        except ValueError:
            print("Podano zle dane wejsciowe!")
    print(usr_input)
    if usr_input == 1:
        ilosc_wierzcholkow, ilosc_krawedzi = wczytaj_graf(lista_krawedzi)
    else:
        while ilosc_wierzcholkow <= 0:
            try:
                ilosc_wierzcholkow = int(input("Podaj ilosc wierzcholkow: "))
            except ValueError:
                print("Podano zle dane wejsciowe!")
        while nasycenie <= 0 or nasycenie > 100:
            try:
                nasycenie = int(input("Podaj poziom nasycenia (1-100%): "))
            except ValueError:
                print("Podano zle dane wejsciowe!")
        generuj_graf(ilosc_wierzcholkow, lista_krawedzi, nasycenie, lista_krawedzi)
    wyswietl_krawedzie(lista_krawedzi)
    tworz_lnastepnikow(ilosc_wierzcholkow, lista_krawedzi, lista_nastepnikow)
    tworz_msasiedztwa(ilosc_wierzcholkow, lista_krawedzi, macierz_sasiedztwa)
    DFS_manager(lista_krawedzi, lista_nastepnikow, macierz_sasiedztwa, ilosc_wierzcholkow)
    DEL_manager(copy.copy(lista_krawedzi), copy.copy(lista_nastepnikow), copy.copy(macierz_sasiedztwa), ilosc_wierzcholkow)

if __name__ == '__main__':
    main()