# Untitled

unknown
plain_text
a year ago
7.2 kB
3
Indexable
Never
```# Import networkx library for graph operations
import networkx as nx
import matplotlib.pyplot as plt

#class Graph:
#   def __init__(self):
#        self.graph = {}

#        if node not in self.graph:
#            self.graph[node] = []

#     if node1 not in self.graph:
#     if node2 not in self.graph:
#     self.graph[node1].append(node2)
#     self.graph[node2].append(node1)

# function to input a valid and non negative integer
def input_int(message):
while True:
try:
num = int(input(message))
except ValueError:
continue
if num < 0:
print("Please enter a non negative integer!")
continue
else:
break
return num

# Function check existence string in list
def check_existence_string_in_list(list, string):
for i in list:
if i == string:
return True
return False

# Function to check input name vertices in graph: Name vertices must be string and not duplicate
def check_input_name_vertices_in_graph(list, message):
name = input(message)
while check_existence_string_in_list(list, name):
print("Name vertices must be string and not duplicate")
name = input(message)
return name

def greedy_edge_coloring(G):

# Initialize an empty dictionary to store the colors of each edge
colors = {}
# Initialize a variable to keep track of the maximum color used so far
max_color = 0
# Loop through the edges of G in any order
for u, v in G.edges():  # G.edges() returns a non-duplicated list of edges
# print("Current edge is ", (u, v))
# Initialize an empty set to store the colors of the adjacent edges
used_colors = set()  # Use set to avoid duplicates
# Loop through the neighbors of u and v and add their edge colors to used_colors
print(G[u])
print(G[v])
for w in G.neighbors(u):
print(u,w)
if (u, w) in colors:
if (w, u) in colors:
for w in G.neighbors(v):
if (v, w) in colors:
if (w, v) in colors:
# print(used_colors)
# Find the minimum positive integer that is not in used_colors
color = 1
while color in used_colors:
color += 1
# Assign this color to the edge (u, v) and update max_color if needed
colors[(u, v)] = color
if color > max_color:
max_color = color
# Return the dictionary of edge colors and the maximum color used
return colors, max_color

# Define a function that takes a graph G and an edge coloring C and visualizes them using networkx library

def visualize_edge_coloring(G, Edges_color):
print(Edges_color)
# Create a list of edge colors based on C
edge_colors = [Edges_color[e] for e in G.edges()]
# Draw the graph with networkx using spring layout and customizing node size and width
nx.draw(G,
# is a layout algorithm that positions nodes on a 2D plane
pos=nx.shell_layout(G),
node_size=500,
width=3,
with_labels=True,
font_size=15,
font_weight='bold',
edge_color=edge_colors,
edge_cmap=plt.cm.rainbow, #plt.cm.rainbow is a colormap which orders colors from red to blue,
# set seed
seed=1)
plt.show()

# Define a function that takes no input and returns a graph defined by the user
def create_graph():
# Initialize an empty graph using networkx library
#M = Graph()
G = nx.Graph()
num_vertices = input_int("How many num_vertices do you want to add? ")

# Loop through num_vertices times and ask the user for the name of each vertex and add it to G
for i in range(1, num_vertices+1):
name = check_input_name_vertices_in_graph(G.nodes(), "Enter the name of vertex " + str(i) + ": ")

num_edges = input_int(f"How many edges do you want to add?(0 -> {int(num_vertices * (num_vertices-1)/2)}) ")

# Check if edges is valid (not negative or too large)
while num_edges < 0 or num_edges > num_vertices*(num_vertices-1)/2:
if num_edges < 0:
print("Invalid number of edges. Please enter a non-negative integer.")
elif num_edges > num_vertices*(num_vertices-1)/2:
print("Invalid number of edges. Please enter an integer at most", int(num_vertices*(num_vertices-1)/2))
# Ask the user to enter again
num_edges = input_int(f"How many edges do you want to add?(0 -> {int(num_vertices * (num_vertices-1)/2)}) ")

# Loop through edges times and ask the user for the names of the endpoints of each edge and add it to G
for j in range(1, num_edges+1):
u, v = input("Enter the names of the endpoints of edge " +
str(j)+": ").split()

# Check if u and v are valid (exist in G and not equal)
# while u not in G.nodes() or v not in G.nodes() or u == v:
while u not in G.nodes() or v not in G.nodes():
if u not in G.nodes():
print("Invalid endpoint. Vertex", u, "does not exist.")
elif v not in G.nodes():
print("Invalid endpoint. Vertex", v, "does not exist.")
elif u == v:
print("Invalid endpoint. Vertex", u,
# Ask the user to enter again
u, v = input(
"Enter the names of the endpoints of edge "+str(j)+": ").split()

# Return the graph G
return G

# Create a sample graph with six num_vertices and nine edges using networkx library
# G = nx.Graph()
# G.add_edges_from([(1, 3), (1, 2), (2, 3)])

# Use

# print("The nodes of the graph are:")
# print(G.nodes())

# print(G.edges())

# print("Neighbor of node 1:")
# for w in G.neighbors(1):
#     print(w)
# G = create_graph()
G = nx.Graph()
# G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')])
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E'), ('D', 'E')])

# Call greedy_edge_coloring function on G and print its output
C, max_color = greedy_edge_coloring(G)
print(f"Color dict is {C}")
print("The greedy edge coloring uses", max_color, "colors.")
print("The colors of each edge are:", C)

# Call visualize_edge_coloring function on G and C
visualize_edge_coloring(G, C)

# import matplotlib.pyplot as plt
# # print list of color of plt.cm.rainbow
# print(plt.cm.rainbow.colors())```