import networkx as nx

H = nx.read_adjlist("H.adjlist")

nx.draw_circular(H, with_labels=True, node_color="yellow",edgecolors="black")

Welsh-Powellov algoritam

H.degree()

DegreeView({'a': 3, 'e': 4, 'c': 5, 'b': 6, 'f': 3, 'd': 2, 'g': 5})

nx.greedy_color(H, strategy='largest_first')

{'b': 0, 'c': 1, 'g': 2, 'e': 3, 'a': 2, 'f': 3, 'd': 1}

Slučajni raspored vrhova

for x in range(10):
    bojanje = nx.greedy_color(H, strategy='random_sequential')
    print(bojanje, '   broj boja: ', max(bojanje.values())+1)

{'a': 0, 'e': 1, 'g': 0, 'f': 1, 'c': 2, 'b': 3, 'd': 1}    broj boja:  4
{'f': 0, 'c': 1, 'e': 0, 'a': 2, 'g': 2, 'b': 3, 'd': 0}    broj boja:  4
{'f': 0, 'b': 1, 'a': 0, 'g': 2, 'e': 3, 'd': 0, 'c': 4}    broj boja:  5
{'d': 0, 'a': 0, 'c': 1, 'f': 0, 'b': 2, 'e': 3, 'g': 4}    broj boja:  5
{'a': 0, 'e': 1, 'c': 2, 'd': 0, 'b': 3, 'f': 0, 'g': 4}    broj boja:  5
{'e': 0, 'b': 1, 'g': 2, 'a': 2, 'f': 0, 'c': 3, 'd': 0}    broj boja:  4
{'d': 0, 'c': 0, 'a': 1, 'b': 2, 'f': 1, 'g': 3, 'e': 4}    broj boja:  5
{'f': 0, 'e': 0, 'a': 1, 'c': 2, 'b': 3, 'g': 1, 'd': 0}    broj boja:  4
{'a': 0, 'b': 1, 'f': 0, 'g': 2, 'e': 3, 'd': 0, 'c': 4}    broj boja:  5
{'f': 0, 'b': 1, 'a': 0, 'g': 2, 'e': 3, 'd': 0, 'c': 4}    broj boja:  5

Brelazov algoritam

nx.greedy_color(H, strategy='DSATUR')

{'b': 0, 'c': 1, 'g': 2, 'e': 3, 'a': 2, 'f': 3, 'd': 1}

Bojanje bridova preko linijskog grafa

from pylab import *

figure(figsize=(8,8))
nx.draw(nx.line_graph(H),with_labels=True,node_color='yellow', edgecolors="black",node_size=1300)

for x in range(10):
    bojanje = nx.greedy_color(nx.line_graph(H), strategy='random_sequential')
    print(bojanje, '   broj boja: ', max(bojanje.values())+1)

{('b', 'd'): 0, ('b', 'g'): 1, ('a', 'c'): 0, ('f', 'g'): 0, ('b', 'f'): 2, ('a', 'b'): 3, ('c', 'f'): 1, ('c', 'g'): 2, ('a', 'e'): 1, ('c', 'e'): 3, ('d', 'g'): 3, ('b', 'e'): 4, ('e', 'g'): 5, ('b', 'c'): 5}    broj boja:  6
{('d', 'g'): 0, ('b', 'd'): 1, ('a', 'c'): 0, ('b', 'f'): 0, ('a', 'e'): 1, ('c', 'g'): 1, ('c', 'e'): 2, ('f', 'g'): 2, ('b', 'e'): 3, ('e', 'g'): 4, ('a', 'b'): 2, ('b', 'c'): 4, ('c', 'f'): 3, ('b', 'g'): 5}    broj boja:  6
{('b', 'g'): 0, ('a', 'c'): 0, ('c', 'g'): 1, ('a', 'b'): 1, ('b', 'd'): 2, ('c', 'f'): 2, ('b', 'c'): 3, ('f', 'g'): 3, ('e', 'g'): 2, ('b', 'e'): 4, ('a', 'e'): 3, ('d', 'g'): 4, ('c', 'e'): 5, ('b', 'f'): 5}    broj boja:  6
{('a', 'e'): 0, ('b', 'f'): 0, ('b', 'g'): 1, ('c', 'e'): 1, ('b', 'c'): 2, ('b', 'e'): 3, ('b', 'd'): 4, ('e', 'g'): 2, ('a', 'c'): 3, ('f', 'g'): 3, ('c', 'f'): 4, ('c', 'g'): 0, ('d', 'g'): 5, ('a', 'b'): 5}    broj boja:  6
{('b', 'c'): 0, ('f', 'g'): 0, ('a', 'e'): 0, ('b', 'd'): 1, ('c', 'e'): 1, ('c', 'f'): 2, ('b', 'g'): 2, ('b', 'e'): 3, ('e', 'g'): 4, ('a', 'c'): 3, ('a', 'b'): 4, ('c', 'g'): 5, ('b', 'f'): 5, ('d', 'g'): 3}    broj boja:  6
{('a', 'e'): 0, ('e', 'g'): 1, ('f', 'g'): 0, ('d', 'g'): 2, ('b', 'e'): 2, ('c', 'f'): 1, ('c', 'g'): 3, ('b', 'd'): 0, ('a', 'b'): 1, ('b', 'c'): 4, ('b', 'f'): 3, ('b', 'g'): 5, ('a', 'c'): 2, ('c', 'e'): 5}    broj boja:  6
{('b', 'e'): 0, ('b', 'd'): 1, ('a', 'e'): 1, ('c', 'f'): 0, ('b', 'g'): 2, ('d', 'g'): 0, ('a', 'c'): 2, ('c', 'e'): 3, ('b', 'c'): 4, ('e', 'g'): 4, ('f', 'g'): 1, ('b', 'f'): 3, ('c', 'g'): 5, ('a', 'b'): 5}    broj boja:  6
{('c', 'g'): 0, ('d', 'g'): 1, ('b', 'f'): 0, ('b', 'e'): 1, ('c', 'e'): 2, ('a', 'c'): 1, ('f', 'g'): 2, ('e', 'g'): 3, ('b', 'd'): 2, ('a', 'b'): 3, ('b', 'g'): 4, ('a', 'e'): 0, ('b', 'c'): 5, ('c', 'f'): 3}    broj boja:  6
{('d', 'g'): 0, ('c', 'e'): 0, ('a', 'e'): 1, ('b', 'f'): 0, ('c', 'f'): 1, ('c', 'g'): 2, ('b', 'd'): 1, ('a', 'c'): 3, ('b', 'e'): 2, ('f', 'g'): 3, ('a', 'b'): 4, ('b', 'c'): 5, ('b', 'g'): 6, ('e', 'g'): 4}    broj boja:  7
{('c', 'g'): 0, ('b', 'c'): 1, ('a', 'b'): 0, ('b', 'f'): 2, ('d', 'g'): 1, ('b', 'e'): 3, ('a', 'c'): 2, ('e', 'g'): 2, ('a', 'e'): 1, ('f', 'g'): 3, ('c', 'e'): 4, ('b', 'g'): 4, ('b', 'd'): 5, ('c', 'f'): 5}    broj boja:  6

nx.greedy_color(nx.line_graph(H), strategy='largest_first')

{('b', 'g'): 0,
 ('b', 'c'): 1,
 ('b', 'e'): 2,
 ('c', 'g'): 2,
 ('a', 'b'): 3,
 ('e', 'g'): 1,
 ('b', 'f'): 4,
 ('c', 'e'): 0,
 ('c', 'f'): 3,
 ('f', 'g'): 5,
 ('a', 'c'): 4,
 ('b', 'd'): 5,
 ('d', 'g'): 3,
 ('a', 'e'): 5}

nx.greedy_color(nx.line_graph(H), strategy='DSATUR')

{('b', 'g'): 0,
 ('b', 'c'): 1,
 ('b', 'e'): 2,
 ('a', 'b'): 3,
 ('b', 'f'): 4,
 ('b', 'd'): 5,
 ('c', 'g'): 2,
 ('c', 'f'): 0,
 ('a', 'c'): 4,
 ('c', 'e'): 3,
 ('e', 'g'): 1,
 ('f', 'g'): 3,
 ('d', 'g'): 4,
 ('a', 'e'): 0}