Как отредактировать код генетического алгоритма в Python?

Как мне изменить код, чтобы он генерировал для меня граф (10 стран, то есть граф представляет собой карту из 10 стран), которые раскрашены в 4 цвета, чтобы ни одна пара соседних стран не была окрашена в один и тот же цвет.

import networkx as nx
import time
import random
import matplotlib.pyplot as plt
from antColoring import coloring


# Считываем граф из текстового файла
def read_from_file():
    inputMatrix = open('input.txt', 'r')
    graph = []
    for row in inputMatrix:
        graph.append(row.replace('\n', '').split(' '))
    for i in range(len(graph)):
        for j in range(len(graph)):
            graph[i][j] = int(graph[i][j])
    return graph



# Генерируем случайный граф
def random_graph(n,d):
    # graph = nx.fast_gnp_random_graph(n, 0.3)
    graph = nx.random_regular_graph(d,n)
    m = nx.to_numpy_matrix(graph)
    graph = []
    for i in range(len(m)):
        row = []
        for j in range(len(m)):
            row.append(int(m[i,j]))
        graph.append(row)
    return graph



# Отрисовка графа без отмеченного паросочетания и с ним
def print_graph(graph,colors):
    g = nx.DiGraph()
    edges = []
    for i in range(len(graph)):
        for j in range(len(graph)):
            if graph[i][j] == 1:
                edges.append((i,j))
    g.add_edges_from(edges)

    r = lambda: random.randint(0, 255)

    nodes = list(g.nodes.keys())
    match = [i for i in range(len(colors))]
    for i in range(len(colors)):
        match[i] = colors[nodes[i]]
    colors = match

# Получение случайных цветов
    for i in colors:
        if isinstance(i,int):
            color = '#{:02x}{:02x}{:02x}{:02x}'.format(r(), r(), r(), r())
            for j in range(len(colors)):
                if i == colors[j]:
                    colors[j] = color

    pos = nx.spring_layout(g)
    nx.draw_networkx_nodes(g, pos, cmap=plt.get_cmap('jet'),
                           node_color='LightGray', node_size=300)
    nx.draw_networkx_labels(g, pos)
    nx.draw_networkx_edges(g, pos, edgelist=g.edges, edge_color='black', arrows=False)
    plt.show()

    pos = nx.spring_layout(g)
    nx.draw_networkx_nodes(g, pos, cmap=plt.get_cmap('jet'),
                           node_color=colors, node_size=300)
    nx.draw_networkx_labels(g, pos)
    nx.draw_networkx_edges(g, pos, edgelist=g.edges, edge_color='black', arrows=False)
    plt.show()



graph = random_graph(8,4)
s1 = time.time()
colors = coloring(graph)
print_graph(graph,colors)

antColoring.py

from random import randint
maxiter = 80


class Ant:
    def __init__(self, color, pos):
        self.color = color
        self.pos = pos


def create_colony(n,colorCount):
    colony = []
    for i in range(n):
        for j in range(n):
            ant = Ant(randint(0, colorCount), i)
            colony.append(ant)
    return colony


def check_coloring(graph,colors):
    n = len(graph)
    flag = True
    for i in range(n):
        for j in range(i + 1, n):
            if graph[i][j] == 1 and colors[i] == colors[j]:
                flag = False
    return flag


def coloring(g):

    # находим количество вершин в графе
    n = len(g)

    # вычисляем количество ребер в графе,
    # так как граница количества цветов n^2/(n^2-2m)
    # также создаем список смежных вершин для каждой вершины
    numberEdges = 0
    spisok = {i: [] for i in range(n)}
    for i in range(n):
        for j in range(n):
            if g[i][j] == 1:
                if i > j:
                    numberEdges += 1
                spisok[i].append(j)
    print(spisok)

    numberEdges = int(n * n / (n * n - 2 * numberEdges))
    colors = [0]*n

    while numberEdges != n:

        # создаем начальную колонию муравьев
        colony = create_colony(n,numberEdges)

        for iter in range(maxiter):
            nodes = [{color: 0 for color in range(numberEdges + 1)} for j in range(n)]
            for ant in colony:
                nodes[ant.pos][ant.color] += 1
            for i in range(len(nodes)):
                maxInd = 0
                max = 0
                for j in nodes[i].keys():
                    if nodes[i][j] > max:
                        maxInd = j
                        max = nodes[i][j]
                colors[i] = maxInd

            for ant in colony:
                if ant.color != colors[ant.pos]:
                    flag = True
                    for i in spisok[ant.pos]:
                        if colors[i] == ant.color:
                            ant.pos = i
                            flag = False
                    if flag:
                        ant.pos = spisok[ant.pos][randint(0, len(spisok[ant.pos]) - 1)]

            for i in range(n):
                for j in range(i + 1, n):
                    if g[i][j] == 1 and colors[i] == colors[j]:
                        c1 = 0
                        c2 = 0
                        color = colors[i]
                        for ant in colony:
                            if ant.pos == i and ant.color == color:
                                c1 += 1
                            elif ant.pos == j and ant.color == color:
                                c2 += 1
                        if c1 > c2:
                            for ant in colony:
                                if ant.pos == j and ant.color == color:
                                    ant.pos = i
                        else:
                            for ant in colony:
                                if ant.pos == i and ant.color == color:
                                    ant.pos = j

            buffer = set(node for node in range(n))
            for ant in colony:
                if ant.pos in buffer:
                    buffer.remove(ant.pos)
            for node in buffer:
                for i in range(n):
                    ant = Ant(randint(0, numberEdges), node)
                    colony.append(ant)

            if check_coloring(g,colors):
                return colors
        numberEdges += 1
    return [color for color in range(numberEdges + 1)]

Ответы (0 шт):