# Z9-Rešenja

## Functions

# file: 'functions.py'
import sys
from math import inf
from vertex import *

def bfs(G, s):
for u in G:
u.color = VertexColor.WHITE
u.d = inf
u.p = None
s.color = VertexColor.GRAY
s.d = 0
s.p = None
Q = queue()
Q.put(s)
while not Q.empty():
u = Q.get()
for v in u.con:
if v.color == VertexColor.WHITE:
v.color = VertexColor.GRAY
v.d = u.d + 1
v.p = u
Q.put(v)
u.color = VertexColor.BLACK

def print_path(G, s, v):
if v == s:
print(s.val, end = " ")
elif v.p == None:
print ("no path found from", s.val, "to", v.val, "exists")
else:
print_path(G, s, v.p)
print(v.val, end = " ")

def dfs(G):
global time
for u in G:
u.color = VertexColor.WHITE
u.p = None
time = 0
for u in G:
if u.color == VertexColor.WHITE:
dfs_visit(G, u)

def dfs_visit(G, u):
global time
time += 1
u.d = time
u.color = VertexColor.GRAY

for v in u.con:
if v.color == VertexColor.WHITE:
v.p = u
dfs_visit(G, v)
u.color = VertexColor.BLACK
time += 1
u.f = time

def topological_sort(G):
dfs(G)
L = sorted(G, key=lambda x: x.f, reverse=True)
return L


functions.py

## Vertex

# file: 'vertex.py'
import sys
from queue import Queue as queue

global time

class Vertex:
def __init__(self, val):
self.val = val
self.con = []

def print_neighbours(self):
print([i.val for i in self.con])

self.con.append(neighbour)

class VertexColor:
BLACK = 0
GRAY = 127
WHITE = 255


vertex.py

# file: 'z9-1.py'
import sys
from functions import *

if __name__ == "__main__":
print("\n===G1===")
# Create graph 1
G1 = []
for i in range(5):
g = Vertex(i + 1)
G1.append(g)

# Connect graph 1

# Find neighbours of node 4
print("Node 4 neighbours:")
G1.print_neighbours()

# Find path from node 4 to node 1
print("Path 4->1")
bfs(G1, G1)
print_path(G1, G1, G1)

print("\n===G2===")
# Create nodes
undershorts = Vertex("undershorts")
pants = Vertex("pants")
belt = Vertex("belt")
shirt = Vertex("shirt")
tie = Vertex("tie")
jacket = Vertex("jacket")
socks = Vertex("socks")
shoes = Vertex("shoes")
watch = Vertex("watch")

# Create connections
undershorts.con = [pants, shoes]
pants.con = [belt, shoes]
belt.con = [jacket]
shirt.con = [tie, belt]
tie.con = [jacket]
jacket.con = []
socks.con = [shoes]
shoes.con = []
watch.con = []

# Create graph 2
G2 = [shirt, undershorts, pants, belt, tie, jacket, socks, shoes, watch]

# Topological sort
L = topological_sort(G2)
print([(i.val, i.d, i.f) for i in reversed(L)])