Lab_I_1_25_11_2020, Python 3

Language: Layout:

#python 3.6.9

print ("Hello, world!")
print ("Bye bye world!")

# Taras Tkachenko checked that everything is working

graph = {"a": ["c"],
         "b": ["c", "e"],
         "c": ["a", "b", "d", "e"],
         "d": ["c"],
         "e": ["c", "b"],
         "f" : []
        }
# Esrin Sana Mete

graphMB = { "a": ["b", "c", "d","e"],
         "b": ["a","c", "e"],
         "c": ["a", "b", "d", "e"],
         "d": ["a","c"],
         "e": ["a","c", "b"]
         }
# Bokijonov Mukhsinjon

# HAMZA EL KEDMIRI DREW A GRAPH

# Dias Baimakanov drew a graph

graphCD = { "a": ["c"],
           "b" : ["c", "e", "f"],
           "c" : ["a", "b","d", "e"],
           "d" : ["c"],
           "e" : ["b","f","c"],
           "f" : ["b", "e"]
           }
# Caleb Danso

print(graphCD["c"])

for key in graphCD:
    print("Key:", key, "value:", graphCD[key])
# Nam Pham Giang

def generate_edges(graph):
    edges = []
    num_of_appends = 0
    
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))
            num_of_appends += 1
    print("Number of appends is ", num_of_appends)
    return edges
# NEEL MEHTA

print(generate_edges(graph))

print(generate_edges(graphMB))

print(generate_edges(graphCD))

def generate_edges_NO(graph):
    edges = []
    num_of_appends = 0
    for node in graph:
        for neighbour in graph[node]:
            if edges.count((neighbour, node)) == 0:
                edges.append((node, neighbour))
                num_of_appends += 1
    print("Number of appends is ", num_of_appends)
    return edges

graphNO = { 
            "a" : [],
            "b" : [],
            "c" : [],
            "d" : []
           }

print('GRAPH MB', generate_edges(graphMB))
print('GRAPH MB NIKITA', generate_edges_NO(graphMB))

# NIKITA OLIZARENKO

def generate_edges_TT(graph):
    print("This is TT version of generate edges")
    edges = []
    num_of_appends = 0
    for node in graph:
        for neighbour in graph[node]:
            if edges.append((node, neighbour)) != edges.append((neighbour, node)):
                edges.append((node, neighbour))           
            num_of_appends += 1
    print("Number of appends is ", num_of_appends)
    return edges

print(generate_edges_TT(graph))

#Rakhmatkhon Solijonov answered question

def generate_edges_NPG(graph):
    edges = []
    num_of_appends = 0
    for node in graph:
        for neighbour in graph[node]:
            if (neighbour,node) not in edges:
                print (edges)
                edges.append((node, neighbour))
                num_of_appends += 1
    print("Number of appends is ", num_of_appends)
    return edges
# Nam Pham Giang
# Nurbek Bissengali drew some graphs.

print(generate_edges_TT(graph)) 
print(generate_edges_NPG(graph))

print(generate_edges_NO(graph))

# Complexity of the algorithm in the generate_edges can be measured as the number of times the function
# append apppears (this is equal to the number of edges). And the size of the problem can be measured 
# as a function of M, the number of vertices.
# In the worst case, the number of edges is M-1 + M-2 + M-3 + ... + 1 = M*(M-1)/2.
# Thus, the complexity is O(M**2).

[ + ] Show input
Absolute running time: 0.16 sec, cpu time: 0.03 sec, memory peak: 8 Mb, absolute service time: 0,23 sec