Lab_I_2_25_11_2020, Python 3

Language: Layout:

#python 3.6.9

print ("Hello, world!")
print("Begone with you, World!")
# HALIL OZCAN

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }
# Diyorbek Tojikulov

graph1 = {"a" : ["f", "b","c","d","e"],
          "b" : ["a", "c","f", "e"],  
          "c" : ["b", "d", "e", "a"],
          "d" : ["a","c"],
          "e" : ["c", "b","a"],
          "f" : ["a","b"]
        }
# Maksym Ushkanov (^_^') <3 
# Rana Tajiki draw a graph
# Shoakhmad Nazarov draw a graph

graph2 = {"a" : ["b", "c", "e"],
          "b" : ["a", "c", "d", "e"],  
          "c" : ["a", "b", "d", "e"],
          "d" : ["b", "c", "e"],
          "e" : ["a", "b", "c", "d"],
        }
# Valeriia Drozdova

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

return edges

print(generate_edges(graph))
# Rana Tajiki with XuanYang

def generate_edges_DT(graph):
    edges = []
    counter = 0
    # counter counts how many times we append an edge to edges.
    for node in graph:
        for neighbour in graph[node]:
            if (neighbour, node) in edges:
                pass
            else:
                edges.append((node, neighbour))
                counter += 1
    print("The number of edges appended is:", counter)                
    return edges
# Diyorbek Tojikulov, Feyza Vidinli

print(generate_edges_DT(graph))

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

print(generate_edges_DT(graph2))

# In the best case, where there no edges at all, the complexity is O(1). 
# What is the worst case? It is when all vertices are joined by some edges.
# This is the case of the maximal number of edges. 
# For M vertices, the maximal 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.17 sec, cpu time: 0.03 sec, memory peak: 8 Mb, absolute service time: 0,32 sec