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}
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}