Untitled

# Import networkx library for graph operations
import networkx as nx
import matplotlib.pyplot as plt

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

#   def add_node(self, node):
#        if node not in self.graph:
#            self.graph[node] = []

    # def add_edge(self, node1, node2):
    #     if node1 not in self.graph:
    #         self.add_node(node1)
    #     if node2 not in self.graph:
    #         self.add_node(node2)
    #     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:
            print("Please enter a valid integer!")
            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:
                used_colors.add(colors[(u, w)])
            if (w, u) in colors:
                used_colors.add(colors[(w, u)])
        for w in G.neighbors(v):
            if (v, w) in colors:
                used_colors.add(colors[(v, w)])
            if (w, v) in colors:
                used_colors.add(colors[(w, v)])
        # 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()
    # Ask the user how many num_vertices they want to add
    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) + ": ")
        G.add_node(name)
        print("Added vertex", name)
    
    # Ask the user how many edges they want to add
    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,
                      "cannot be adjacent to itself.")
            # Ask the user to enter again
            u, v = input(
                "Enter the names of the endpoints of edge "+str(j)+": ").split()

        G.add_edge(u, v)
        print("Added edge", u, v)

    # 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_nodes_from([1, 3])
# 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_nodes_from(['A', 'B', 'C', 'D', 'E'])
# 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())