CODEWITHSUNDEEP
pythongraphcolorstheoryvertex
Python
Python

Reputation: 219

Vertex coloring by python- Chromatic number X(G)

I'm trying to write a small code in python to color graph vertices, and count the number of colors that used so no two connected vertices have the same color. this is my code and I don't know what is wrong with it, any help w? it's not a homework!

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black','Pink','Orange','White','Gray','Purpul','Brown','Navy']

G.nodes = [1,2,3,4,5]
G.edges= [{1,5},{1,3},{1,2},{1,4},{4,5}]
colors_of_nodes={}

def coloring(node, color):
   for neighbor in G.edges:
       color_of_neighbor = colors_of_nodes(neighbor)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes:
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

Upvotes: 2

Views: 9049

Answers (3)

Tomáš Sláma
Tomáš Sláma

Reputation: 122

An alternative way to find the chromatic number is to convert this program into a linear optimalization problem and feed it to a solver. Here is an example in Python:

from pulp import *

edges = [(1,2), (3,2), (2,4), (1,4), (2,5), (6,5), (3,6), (1,5)]
n = len(set([u for u, v in edges] + [v for u, v in edges]))

model = LpProblem(sense=LpMinimize)

chromatic_number = LpVariable(name="chromatic number", cat='Integer')
variables = [[LpVariable(name=f"x_{i}_{j}", cat='Binary') \
              for i in range(n)] for j in range(n)]

for i in range(n):
    model += lpSum(variables[i]) == 1

for u, v in edges:
    for color in range(n):
        model += variables[u - 1][color] + variables[v - 1][color] <= 1

for i in range(n):
    for j in range(n):
        model += chromatic_number >= (j + 1) * variables[i][j]

model += chromatic_number

status = model.solve(PULP_CBC_CMD(msg=False))

print("chromatic number:", int(chromatic_number.value()))
print("\n".join([f"vertex {i} has color {j}" \
      for i in range(n) for j in range(n) if variables[i][j].value()]))

I'm using the pulp Python library. This approach will always yield the chromatic number but is not feasible for larger graphs (since this problem is NP-complete). It is, however, quite compact.

Upvotes: 0

brent.payne
brent.payne

Reputation: 5507

Multiple Issues are in this code:

  1. small spelling error Purpul -> Purple
  2. Syntax Error: colors_of_nodes is a dictionary so it is not callable as a function. so colors_of_nodes(neighbor) will fail. You can index a dictionary in two ways colors_of_nodes[node] or colors_of_nodes.get(node, default_value_if_node_is_not_a_key). You want to do the second.
  3. Logical Error: neighbor is being set to an edge value not a node. You want to cycle over the nodes which are neighbors or a specific node. Luckily networkx has a simple function for this: G.neighbors(node). Additionally, an edge is a set which is not hashable therfor cannot be a dictionary key.
  4. Semantic Error: you did not use the correct semantics to create and access an networkx graph. Look at the website for networkx. G.add_nodes_from([1,2,3,4,5]), G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(4,5)]), G.nodes()

Below is your edited code in a working format.

author = 'brent'

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black', 'Pink', 'Orange', 'White', 'Gray', 'Purple', 'Brown', 'Navy']

G.add_nodes_from([1,2,3,4,5])
G.add_edges_from([(1,5),(1,3),(1,2),(1,4),(4,5)])
colors_of_nodes={}


def coloring(node, color):
   for neighbor in G.neighbors(node):
       color_of_neighbor = colors_of_nodes.get(neighbor, None)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes():
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

Note that this is a greedy technique for coloring a graph and does not necessarily give you an optimal coloring of a graph.

Upvotes: 3

Seth
Seth

Reputation: 46433

You should post the errors that you're getting, what you're expecting and what's actually happening.

Minimally, this: 

color_of_neighbor = colors_of_nodes(neighbor)

Will raise a TypeError: 'dict' object is not callable error.

Upvotes: 0

Related Questions