brandon-greedy.py

"""
Brandon Short Greedy Algorithm

Background: Bollobás proves in his book "Random Graphs", proves the LOWER bound for k colorings is:
    k <= (n / 2*logd(n)) * (1 + (log log n) / log n))
    d = 1 / (1 - p)

It sorts each edge by degree (k), sets up that many 'indepenedent' sets (where no two nodes share an edge).
My thought process was simple enough: set up the least number of sets needed to color the graph (which is k),
considering it is specialized to working with random graphs.
There is likely more colors needed than that, but it's a great start for how many independent sets.
This should cover the majority of nodes, leaving a simple coloring algorithm perfect for the remaining nodes.

Steps:
1. Finds k, which is the lower bound to how many colors would be needed (but likely more than that).
2. Create that many independent sets, and 1 "extra" set.
3. Attempt to place node in indepentent sets, one at a time.
4. Otherwise place it in the extra set.
5. Assign colors for independent sets.
6. Apply a simple coloring algorithm to the extra set.

"""

import networkx as nx
import math

def calculate_k(n, p):
    """Calculate the lower bound for the number of colors based on Bollobás' formula."""
    d = 1 / (1 - p)
    k = (n / (2 * (math.log(n))/math.log(d))) * (1 + (math.log(math.log(n)) / math.log(n)))
    return math.ceil(k)

def greedy_coloring(G):
    """Perform a greedy coloring algorithm based on independent sets."""
    n = len(G.nodes)  # Number of nodes
    p = (len(G.edges) * 2) / (n * (n - 1))  # Approximate probability based on edges
    k = calculate_k(n, p)  # Find the lower bound for the number of colors
    
    independent_sets = {i: [] for i in range(k)}  # Now each set is a list
    extra_set = []
    colored_nodes = {}  # Dictionary to store colors of nodes
    
    # Attempt to place nodes in independent sets or the extra set
    for node in G.nodes:
        placed = False
        
        # Try placing the node in one of the independent sets
        for i in independent_sets:
            # Ensure the node does not share an edge with any other node in the independent set
            if not set(G.neighbors(node)) & set(independent_sets[i]):
                independent_sets[i].append(node)  # This is where append is used
                colored_nodes[node] = i
                placed = True
                break
        
        if not placed:
            # If it couldn't fit in independent sets, place in the extra set
            extra_set.append(node)  # Simply add to extra set, no color assigned yet
    
    # Color the extra set nodes
    colored_nodes = color_extra_set(G, extra_set, colored_nodes, k)
    
    return colored_nodes

def color_extra_set(G, extra_set, colored_nodes, k):
    """Color the nodes in the extra set."""
    for node in extra_set:
        for color in range(k + 1):  # Try all colors, including new ones if necessary
            # Ensure that no adjacent nodes have the same color
            if all(neighbor not in colored_nodes or colored_nodes[neighbor] != color for neighbor in G.neighbors(node)):
                colored_nodes[node] = color
                break

    return colored_nodes

def main():
    G = nx.gnp_random_graph(n=300, p=0.3)  # Create a random graph with n=100 and p=0.1
    color_map = greedy_coloring(G)
    print(color_map)

if __name__ == "__main__":
    main()