<jupyter_start><jupyter_text>function code_toggle() {    if (code_shown){      $('div.input').hide('500');      $('toggleButton').val('Show Code')    } else {      $('div.input').show('500');      $('toggleButton').val('Hide Code')    }    code_shown = !code_shown  }  $( document ).ready(function(){    code_shown=false;    $('div.input').hide()  });<jupyter_code>%matplotlib inline
import random
import itertools
import matplotlib.pyplot as plt
import networkx as nx<jupyter_output><empty_output><jupyter_text>List of Strategies Used:1. Greedy Graph Coloring Algorithm (Vanilla)2. Greedy Graph Coloring By Ordering Nodes By Largest Degree First3. Greedy Graph Coloring By Random Ordering of Nodes4. <NAME>5. Greedy Graph Colouring Using BFS6. Greedy Graph Colouring Using DFS  Helper Functions<jupyter_code>def colour(n):
    ret = {}
    for i in range(n):
        r = int(random.random() * 256)
        g = int(random.random() * 256)
        b = int(random.random() * 256)
        ret[i] = "#{:02x}{:02x}{:02x}".format(r,g,b) 
    return ret
colorList = colour(5000)
minDegNode = lambda G: min(G, key=G.degree)
maxDegNode = lambda G: max(G, key=G.degree)

def transformDict(myDict):
    for key,value in myDict.items():
        myDict[key] = colorList[value]
    return myDict<jupyter_output><empty_output><jupyter_text>Greedy Graph Coloring (Vanilla)<jupyter_code>def greedyGraphColoring(G):
    colors = {}
    graphNodes = G.nodes()
    
    for node in graphNodes:
        adjColors = set()
        for adjNode in G.neighbors(node):
            if adjNode in colors:
                adjColors.add(colors[adjNode])
                
        for color in itertools.count():
            if color not in adjColors:
                break
                
        colors[node] = color
    return colors<jupyter_output><empty_output><jupyter_text>Greedy Graph Coloring By Ordering Nodes (Largest Degree First)<jupyter_code>def greedyDegreeSort(G):
    colors = {}
    graphNodes = list(G.nodes())
    graphNodes.sort(key=lambda node: -G.degree(node))
    
    for node in graphNodes:
        adjColors = set()
        for adjNode in G.neighbors(node):
            if adjNode in colors:
                adjColors.add(colors[adjNode])
                
        for color in itertools.count():
            if color not in adjColors:
                break
                
        colors[node] = color
    return colors<jupyter_output><empty_output><jupyter_text>Greedy Graph Coloring By Random Shuffling<jupyter_code>def greedyRandomShuffling(G):
    colors = {}
    graphNodes = G.nodes()
    random.shuffle(list(graphNodes))
    
    for node in graphNodes:
        adjColors = set()
        for adjNode in G.neighbors(node):
            if adjNode in colors:
                adjColors.add(colors[adjNode])
                
        for color in itertools.count():
            if color not in adjColors:
                break
                
        colors[node] = color
    return colors<jupyter_output><empty_output><jupyter_text>Welsh Powell Algorithm<jupyter_code>def welsh_powell2(G):  
    x = sorted(G.degree, key=lambda x: x[1], reverse=True)
    len_g = len(G)
    no_colored = 0
    k = 1
    colors = dict()
    while no_colored <  len_g:
        colored = set()
        colorednodes = set()
        for node in x:
            y = set(G.neighbors(node[0]))
            if y.intersection(colorednodes) == set():
                colors[node[0]] = k
                no_colored +=1
                colored.add(node)
                colorednodes.add(node[0])
        x = list(set(x) - colored)
        k+=1
    return colors
def welsh_powell(G):
    colors = {}  
    x = sorted(G.degree, key=lambda x: x[1], reverse=True)
    len_g = len(G)
    no_colored = 0
    k = 1
    while no_colored <  len_g:
        colored = set()
        for new_node in x:
            if colored not in G.neighbors(new_node[0]):
                colors[new_node[0]] = k
                no_colored +=1
                colored.add(new_node)
        x = list(set(x) - colored)
        k+=1
    return colors
def strategy_connected_sequential_bfs(G, colors):
    return strategy_connected_sequential(G, colors, 'bfs')
def strategy_connected_sequential_dfs(G, colors):
    return strategy_connected_sequential(G, colors, 'dfs')
def strategy_connected_sequential(G, colors, traversal='bfs'):
    for component_graph in nx.connected_component_subgraphs(G):
        source = component_graph.nodes()[0]
        yield source
        if traversal == 'bfs':
            tree = nx.bfs_edges(component_graph, source)
        elif traversal == 'dfs':
            tree = nx.dfs_edges(component_graph, source)
        else:
            raise nx.NetworkXError('Please specify bfs or dfs for connected sequential ordering')
        for (_, end) in tree:
            yield end
def greedy_color(G, strategy, interchange=False):
    colors = {}
    for node in nodes:
        neighbour_colors = set()
        for neighbour in G.neighbors_iter(node):
            if neighbour in colors:
                neighbour_colors.add(colors[neighbour])
        for color in itertools.count():
            if color not in neighbour_colors:
                break
        colors[node] = color
    return colors<jupyter_output><empty_output><jupyter_text>Test Cases<jupyter_code>def printGraphAndAnalyse(G, sizeoffigure):
    fig = plt.figure(figsize=(2*sizeoffigure,sizeoffigure))
    plt.subplot(1, 2, 1)
    nx.draw(G, with_labels=True)
    plt.subplot(1, 2, 2)
    nodeColors = transformDict(greedyGraphColoring(G))
    nx.draw(G, with_labels=True, node_color=list(nodeColors.values()))
    plt.show()
    print("Time taken by different Algorithms:\n")
    print("Basic Greedy Algorithm:")
    %timeit -n 10 -r 2 greedyGraphColoring(G)
    print("\nGreedy Graph Coloring By Ordering Nodes (By Largest Degree First):")
    %timeit -n 10 -r 2 greedyDegreeSort(G)
    print("\nGreedy Algorithm With Random Shuffling:")
    %timeit -n 10 -r 2 greedyRandomShuffling(G)
    print("\n<NAME>:")
    %timeit -n 10 -r 2 welsh_powell(G)
    print("\nGreedy Algorithm using DFS ")
    %timeit -n 10 -r 2 nx.coloring.greedy_color(G, strategy=nx.coloring.strategy_connected_sequential_dfs)    
    print("\nGreedy Algorithm using BFS ")
    %timeit -n 10 -r 2 nx.coloring.greedy_color(G, strategy=nx.coloring.strategy_connected_sequential_bfs)
def analyse(G):
    print("Basic Greedy Algorithm")
    %timeit -n 10 -r 2 greedyGraphColoring(G)
    print("\nGreedy Graph Coloring By Ordering Nodes (By Largest Degree First)")
    %timeit -n 10 -r 2 greedyDegreeSort(G)
    print("\nGreedy Algorithm With Random Shuffling")
    %timeit -n 10 -r 2 greedyRandomShuffling(G)
    print("\n<NAME>")
    %timeit -n 10 -r 2 welsh_powell(G)
    print("\nGreedy Algorithm using DFS ")
    %timeit -n 10 -r 2 nx.coloring.greedy_color(G, strategy=nx.coloring.strategy_connected_sequential_dfs)    
    print("\nGreedy Algorithm using BFS ")
    %timeit -n 10 -r 2 nx.coloring.greedy_color(G, strategy=nx.coloring.strategy_connected_sequential_bfs)
G = nx.Graph()
G.add_nodes_from([0,1,2])
G.add_edges_from([(0,1),(1,2)])

printGraphAndAnalyse(G, 13)
G = nx.complete_graph(5)
printGraphAndAnalyse(G, 13)
G = nx.balanced_tree(3,2)
printGraphAndAnalyse(G, 13)
G = nx.cycle_graph(10)
printGraphAndAnalyse(G, 13)
G = nx.fast_gnp_random_graph(10,0.5)
printGraphAndAnalyse(G, 13)
G = nx.fast_gnp_random_graph(500,0.5)
analyse(G)<jupyter_output>Basic Greedy Algorithm
11.6 ms ± 232 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)

Greedy Graph Coloring By Ordering Nodes (By Largest Degree First)
13 ms ± 209 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)

Greedy Algorithm With Random Shuffling
11 ms ± 7.36 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)

<NAME>
3.65 ms ± 76.9 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)

Greedy Algorithm using DFS 
362 ms ± 300 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)

Greedy Algorithm using BFS 
356 ms ± 4.4 ms per loop (mean ± std. dev. of 2 runs, 10 loops each)
{'fraction_non_alphanumeric': 0.11042260503160242, 'fraction_numerical': 0.02144007931590036, 'mean_word_length': 2.822832780672667, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '157955', 'license': 'MIT', 'n_tokens_mistral': 2890, 'n_tokens_neox': 2674, 'n_words': 713, 'path': 'Graph_Coloring.ipynb', 'repo_name': 'Vidhin05/Graph-Colouring-Algorithms-Visualisation-and-Time-Analysis', 'size': '8093'}