Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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(ilosc_wierzcholkow, ilosc_krawedzi, 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()
- 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)
- #for i in range(len(odwiedzone)):
- #if odwiedzone[i] == "bialy":
- #DFS_lkrawedzi(lista_krawedzi, odwiedzone, i, posortowane)
- 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)
- ############################################
- # 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:
- wczytaj_graf(ilosc_wierzcholkow, ilosc_krawedzi, 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)
- if __name__ == '__main__':
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement