# Numerická a aplikovaná matematika - teória grafov
# Uvedené príklady sa nachádzajú v bakalárskej práci študentky R. Szabóovej (2020).
#
# Graf G=(V,H) je definovaný, keď je zadaná jeho množina vrcholov a hrán. Typ grafu môže byť orientovaný alebo neorientovaný.
# Príklad: V={0,1,2,3,4}, H={[0,1],[0,2],[0,3],[2,1],[2,4],[3,0]}.

# Príklad 1
# Kreslenie neorientovaného grafu
D = Graph({0:[1,2,3], 2:[1,4], 3:[0]})
D.graphplot().show()

# Príklad 2
# Kreslenie orientovaného grafu
D = DiGraph({0:[1,2,3], 2:[1,4], 3:[0]})
D.graphplot().show()

# Príklad 3
# Incidenčná matica
D.incidence_matrix(oriented=True)

[-1 -1 -1  0  0  1]
[ 1  0  0  1  0  0]
[ 0  1  0 -1 -1  0]
[ 0  0  1  0  0 -1]
[ 0  0  0  0  1  0]

# Príklad 4
# Matica susednosti
D.adjacency_matrix()

[0 1 1 1 0]
[0 0 0 0 0]
[0 1 0 0 1]
[1 0 0 0 0]
[0 0 0 0 0]

# Príklad 5
# Kreslenie ľubovoľného grafu
@interact
def DwGraph(
     edges = input_box(default = {0:[1,2,3], 2:[1,4], 3:[0]}),
     gr = selector(values = ["Yes", "No"], label = "DiGraph", default = "No" ),
     auto_update=False):

     if (gr == "Yes"): D=DiGraph(edges)
     if (gr == "No"): D=Graph(edges)
     D.graphplot().show()

# Príklad 6  - matematický model - graf vzdušného priestoru EÚ pred zavedením FRA (Free Route Airspace)
# FRA = vzdušný priestor voľných tratí
# vrcholy grafu: V - vzdušné priestory jednotlivých krajín Európy
# mdezi susednými vzdušnými prietormi vznikajú hrany grafu H
# D=(V,H) je graf matematický model európskeho vzdušného priestoru

D = Graph({
1: [2, 3, 12], 
2: [1, 3],
3: [1, 2, 4, 5, 10, 11, 12],
4: [3, 5, 10],
5: [3, 4, 6, 10],
6: [5, 7, 10], 
7: [6, 8, 10],
8: [7, 9, 10],
9: [8, 10, 17, 18, 19, 21, 22],
10: [3, 4, 5, 6, 7, 8,9, 11, 17],
11: [3, 10, 12, 16, 17],
12: [1, 3, 11, 13, 14, 16],
13: [12, 14, 15],
14: [12, 13, 15, 16],
15: [13, 14, 49, 50, 51, 53],
16: [11, 12, 14, 17, 18, 44, 51],
17: [9, 10, 11, 16, 18],
18: [9, 16, 17, 19, 43, 44],
19: [9, 18, 20, 21, 43],
20: [19, 21, 24, 39, 41, 42, 43],
21: [9, 19, 20, 22, 24],
22: [9, 21, 23, 24, 25, 26],
23: [22, 24, 25, 27, 40],
24: [20, 21, 22, 23, 39, 40],
25: [22, 23],
26: [22, 27, 28, 29, 30, 31, 32],
27: [22, 23, 26, 32, 34, 40],
28: [26, 29],
29: [26, 28],
30: [26, 31],
31: [26, 30, 32, 33, 36, 37, 38],
32: [26, 27, 31, 33, 34],
33: [31, 32, 34, 35, 38, 40],
34: [27, 32, 33, 35, 40],
35: [33, 34, 40],
36: [31, 37],
37: [31, 36, 38, 42, 47, 48],
38: [31, 33, 37, 39, 40, 42],
39: [20, 24, 38, 40, 41, 42],
40: [23, 24, 27, 33, 34, 35, 38, 39],
41: [20, 39, 42],
42: [20, 38, 39, 41, 43, 45, 47],
43: [18, 19, 20, 42, 44, 45],
44: [16, 18, 43, 45, 51],
45: [42, 43, 44, 46, 47, 51],
46: [45, 47, 48, 50, 51],
47: [37, 42, 45, 46, 48],
48: [37, 46, 47, 49, 50, 52],
49: [15, 48, 50, 52, 53],
50: [15, 46, 48, 49, 51],
51: [14, 15, 16, 44, 45, 46, 50],
52: [48, 49, 53, 54],
53: [15, 49, 52, 54, 55, 62],
54: [52, 53, 55, 56, 57, 59],
55: [53, 54, 59, 60, 62],
56: [54, 57, 58],
57: [54, 56, 58, 59],
58: [56, 57, 59, 61],
59: [54, 55, 57, 58, 60, 61],
60: [55, 59, 61],
61: [55, 58, 59, 60, 62],
62: [53, 55, 61]})
for u,v,l in D.edges():
    D.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')')
D.graphplot( vertex_size=200, edge_labels=true,graph_border=True).show(figsize=[12,12])

# Príklad 7 - konvertovanie grafu, matematického modelu vzdušného priestoru do systému MATLAB
# V MATLABe grafy sú definované pomocou dvoch vektorov s,t. Dvojice (si,ti) definujú hrany grafu.

D = Graph({
1: [2, 3, 12], 
2: [1, 3],
3: [1, 2, 4, 5, 10, 11, 12],
4: [3, 5, 10],
5: [3, 4, 6, 10],
6: [5, 7, 10], 
7: [6, 8, 10],
8: [7, 9, 10],
9: [8, 10, 17, 18, 19, 21, 22],
10: [3, 4, 5, 6, 7, 8,9, 11, 17],
11: [3, 10, 12, 16, 17],
12: [1, 3, 11, 13, 14, 16],
13: [12, 14, 15],
14: [12, 13, 15, 16],
15: [13, 14, 49, 50, 51, 53],
16: [11, 12, 14, 17, 18, 44, 51],
17: [9, 10, 11, 16, 18],
18: [9, 16, 17, 19, 43, 44],
19: [9, 18, 20, 21, 43],
20: [19, 21, 24, 39, 41, 42, 43],
21: [9, 19, 20, 22, 24],
22: [9, 21, 23, 24, 25, 26],
23: [22, 24, 25, 27, 40],
24: [20, 21, 22, 23, 39, 40],
25: [22, 23],
26: [22, 27, 28, 29, 30, 31, 32],
27: [22, 23, 26, 32, 34, 40],
28: [26, 29],
29: [26, 28],
30: [26, 31],
31: [26, 30, 32, 33, 36, 37, 38],
32: [26, 27, 31, 33, 34],
33: [31, 32, 34, 35, 38, 40],
34: [27, 32, 33, 35, 40],
35: [33, 34, 40],
36: [31, 37],
37: [31, 36, 38, 42, 47, 48],
38: [31, 33, 37, 39, 40, 42],
39: [20, 24, 38, 40, 41, 42],
40: [23, 24, 27, 33, 34, 35, 38, 39],
41: [20, 39, 42],
42: [20, 38, 39, 41, 43, 45, 47],
43: [18, 19, 20, 42, 44, 45],
44: [16, 18, 43, 45, 51],
45: [42, 43, 44, 46, 47, 51],
46: [45, 47, 48, 50, 51],
47: [37, 42, 45, 46, 48],
48: [37, 46, 47, 49, 50, 52],
49: [15, 48, 50, 52, 53],
50: [15, 46, 48, 49, 51],
51: [14, 15, 16, 44, 45, 46, 50],
52: [48, 49, 53, 54],
53: [15, 49, 52, 54, 55, 62],
54: [52, 53, 55, 56, 57, 59],
55: [53, 54, 59, 60, 62],
56: [54, 57, 58],
57: [54, 56, 58, 59],
58: [56, 57, 59, 61],
59: [54, 55, 57, 58, 60, 61],
60: [55, 59, 61],
61: [55, 58, 59, 60, 62],
62: [53, 55, 61]})
s="["
t="["
for u in D.edges():
  s=s+str(u[0])+" "
  t=t+str(u[1])+" "
s=s+"]"
t=t+"]"
print(s)
print(t)

[1 1 1 2 3 3 3 3 3 4 4 5 5 6 6 7 7 8 8 9 9 9 9 9 9 10 10 11 11 11 12 12 12 13 13 14 14 14 15 15 15 15 16 16 16 16 17 18 18 18 19 19 19 20 20 20 20 20 20 21 21 22 22 22 22 22 23 23 23 23 24 24 26 26 26 26 26 26 27 27 27 28 30 31 31 31 31 31 32 32 33 33 33 33 34 34 35 36 37 37 37 37 38 38 38 39 39 39 41 42 42 42 43 43 44 44 45 45 45 46 46 46 46 47 48 48 48 49 49 49 50 52 52 53 53 53 54 54 54 54 55 55 55 55 56 56 57 57 58 58 59 59 60 61 ]
[2 3 12 3 4 5 10 11 12 5 10 6 10 7 10 8 10 9 10 10 17 18 19 21 22 11 17 12 16 17 13 14 16 14 15 15 16 51 49 50 51 53 17 18 44 51 18 19 43 44 20 21 43 21 24 39 41 42 43 22 24 23 24 25 26 27 24 25 27 40 39 40 27 28 29 30 31 32 32 34 40 29 31 32 33 36 37 38 33 34 34 35 38 40 35 40 40 37 38 42 47 48 39 40 42 40 41 42 42 43 45 47 44 45 45 51 46 47 51 47 48 50 51 48 49 50 52 50 52 53 51 53 54 54 55 62 55 56 57 59 59 60 61 62 57 58 58 59 59 61 60 61 61 62 ]

# Príklad 8 - Načítanie grafu z Excel tabuľky
# Načítanie umožňuje univerzálnu aktualizáciu grafov. Tabuľka môže slúžiť ako špeciálne dátové rozhranie

# loading a .csv file to matrix and graph
import csv
# from sage.graphs.graph_input import from_adjacency_matrix
    
with open('FRA_matrix.csv', newline='') as csvfile: 
    L = list(csv.reader(csvfile, delimiter=';'))
with open('FRA_list.csv', newline='') as csvfile: 
    L2 = list(csv.reader(csvfile, delimiter=';'))

M = matrix(ZZ,L[1:])
# print(M)

n=len(L)-1

graph = Graph()
vertices = list()
edges = list()

for i in range(n):
    vertices.append(i+1)
    for j in range(n):
        if M[i][j]==1:
             edges.append((i+1, j+1))

graph.add_vertices(vertices)
graph.add_edges(edges)

graph.graphplot().show()

# n=len(L2)-1
# for i in range(n):
#    if L2[i+1][0]!="":print(L2[i+1][0], L2[i+1][1],"\n", L2[i+1][3])
#    else: 
#            print(L2[i+1][0], L2[i+1][1], L2[i+1][3])