veven.py

# библиотека для графов
import networkx as nx
# библиотека для построения графиков
import matplotlib.pyplot as plt
# статические массивы
import numpy as np
# комбинаторика
from itertools import permutations

# константы для названия станций
C1 = 'C1'
C2 = 'C2'
C3 = 'C3'
C4 = 'C4'
C5 = 'C5'
C6 = 'C6'

# массив станций
nodes = [C1, C2, C3, C4, C5, C6]

# все соединения в формате (станция1, станция2, время)
edges = [
    (C1, C4, 30),
    (C1, C6, 76),
    (C2, C5, 40),
    (C2, C4, 20),
    (C3, C4, 24),
    (C4, C5, 20),
    (C5, C6, 56)
]

# отрисовка первоначального графа соединений в задании


G = nx.Graph()  # создание графа
G.add_nodes_from(nodes)  # добавление точек графа (станций)
G.add_weighted_edges_from(edges)  # добавление рёбер графа (соединений)
pos = nx.spring_layout(G)  # корректировка расположения вершин графа на графике

# непосредственно отрисовка
nx.draw(G, pos, with_labels=True)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()


def all_pairs(lst):
    """
    Нахождение всех возможных комбинаций станций на магистралях.
    Обычные комбинаторические методы не работают, т.к. станции представляют собой
    сочетания перестановок. Иначе говоря, требуется группировать попарно станции,
    при этом порядок станций не важен, а затем размещать эти пары  на три возможные
    позиции, здесь порядок уже имеет значение.
    Эта функция возвращает только все возможные попарные соединения станций БЕЗ
    учета их порядка.
    :param lst: множество станций, которые нужно попарно сложить
    :return: все возможные попарные сочетания станций
    """
    if len(lst) < 2:
        yield lst
        return
    a = lst[0]
    for i in range(1, len(lst)):
        pair = (a, lst[i])
        for rest in all_pairs(lst[1:i] + lst[i + 1:]):
            yield [pair] + rest


variations = []  # все возможные комбинации попарных сочетаний станций
for x in all_pairs(nodes):
    variations.append(x)


def get_conflicts(stations, printing=0):
    """
    Формирует матрицу конфликтов, исходя из распределения станций по магистралям.
    :param stations: распределение станций по магистралям в формате ((С#, C#), (C#, C#), (C#, C#)),
    где C# - это некоторая станция. Номер пары означает номер магистрали (0, 1, 2).
    :param printing: параметр для вывода всей информации о составляемых графах. Используется
    в конце для формирования отчета о наилучшем расположении станций.
    :return: матрица конфликтов NxN, нумерация соединений сответствует соединениям в edges.
    """
    station1, station2, station3 = stations  # развертка записи по всем станциям в каждую станцию по отделности
    conflicts = np.zeros((len(edges), len(edges)))  # инициализация матрицы конфликтов (по умолчанию заполнена нулями)

    """
    Нахождение конфликтов двух соединений определяется исходя из графовой картины формирования соединений.
    Создается некоторый граф, в котором по магистралям распределены станции в соответствии со входными данными.
    В этот граф также добавляются три вершины, каждая из которых соответствует магистральному каналу. Эта
    вершина выступает своего рода семафором для соединений между станциями, индицирующая, какие 
    магистрали задействованы. Вершины-магистрали соединены между собой в соответствии с заданием.
    """

    # создание графа
    G = nx.Graph()

    # R# -> Regulator# -> регулятор, магистральная вершина магистрали под номером #
    G.add_node('R1', pos=(3, 2))  # параметр pos везде отвечает за расположение вершины при отрисовке
    G.add_node(station1[0], pos=(1, 1))  # добавляем в граф первую вершину станции 1
    G.add_node(station1[1], pos=(5, 1))  # добавляем в граф первую вершину станции 2, далее аналогично
    # добавляем в граф ребро между регулятором 1 и первой вершиной станции 1, далее аналогично
    G.add_edge('R1', station1[0])
    G.add_edge('R1', station1[1])

    G.add_node('R2', pos=(7, 2))
    G.add_node(station2[0], pos=(5, 3))
    G.add_node(station2[1], pos=(9, 3))
    G.add_edge('R2', station2[0])
    G.add_edge('R2', station2[1])

    G.add_node('R3', pos=(11, 2))
    G.add_node(station3[0], pos=(9, 1))
    G.add_node(station3[1], pos=(13, 1))
    G.add_edge('R3', station3[0])
    G.add_edge('R3', station3[1])

    G.add_edge('R1', 'R2')
    G.add_edge('R2', 'R3')

    # циклом попарно проходимся по всем соединениям, проверяя, конфликтуют ли они друг с другом
    for row, connection1 in enumerate(edges):
        for column, connection2 in enumerate(edges):
            # находим для каждого соединеие кратчайшие пути как множество вершин графа
            path1 = nx.shortest_path(G, connection1[0], connection1[1])
            path2 = nx.shortest_path(G, connection2[0], connection2[1])
            # переводим множество вершин графа в тип данных неупорядоченного множества
            path1 = set(path1)
            path2 = set(path2)
            # если есть пересечения между 1 и 2 путем, это конфликт соединений, помечаем это в матрице конфликтов
            conflicts[row][column] = len(path1.intersection(path2)) > 0
    np.fill_diagonal(conflicts, 0)  # корректировка, помечаем диагональные элементы матрицы как неконфликтующие
    if printing:
        pos = nx.get_node_attributes(G, 'pos')
        nx.draw(G, with_labels=True, pos=pos)
        plt.show()
    return conflicts


def compute_time(c, printing=0):
    """
    Подсчитываем время работы магистралей для матрицы конфликтов C. Подсчет осуществляется исходя из
    нахождения максимального независимого множества вершин и поэтапного удаления из графа уже рассмотренных
    вершин. Задача нахождения максимального независимого множества вершин NP-полная, поэтому реализованная
    функция поиска такого множества является аппроксимированной. Тем не менее, нахождение не самого большого
    непересекающегося множества вершин не является критической проблемой для этого алгоритма, так как в
    результате такие множества лишь поменяеются местами при выполнении, оставляя суммарное время тем же.
    :param c: матрица конфликтов
    :param printing: параметр для вывода всей информации о происходящих процессах. Используется
    в конце для формирования отчета о наилучшем расположении станций.
    :return: время, за которое отработала система при заданном расположении станций
    """
    # инициализируем граф, созданный на основе матрицы конфликтов
    conf_graph = nx.Graph(c)
    # создаем вспомогательные словари
    _labels, timings = {}, {}
    for i in range(len(edges)):
        _labels[i] = edges[i][0] + edges[i][1][-1]  # переименовывает соединения из (C1, C2) в C12
        timings[i] = edges[i][2]  # хранит время выполнения соответствующего соединения

    # задаем вершинам новые обозначения и время выполнения
    nx.set_node_attributes(conf_graph, _labels, 'label')
    nx.set_node_attributes(conf_graph, timings, 'time')
    nx.relabel_nodes(conf_graph, _labels, copy=False)

    if printing:
        _pos = nx.shell_layout(conf_graph)
        nx.draw(conf_graph, _pos, with_labels=True)
        plt.show()

    current_tasks = []  # список нынешних задач в обработке
    completed_time = 0  # суммарное время выполнения на данный момент
    time_to_complete = {}  # время, оставшееся для выполнения для каждой задачи в отдельности

    while len(conf_graph) > 0:  # пока граф не пустой
        current_tasks = nx.maximal_independent_set(conf_graph, current_tasks)  # берем все возможные задачи
        for task in current_tasks:  # проходимся по выполняемым сейчас задачам
            if task not in time_to_complete.keys():  # если у задачи еще не замерено время
                time_to_complete[task] = conf_graph.node[task]['time']  # задаем ей оставшееся время как время задачи
                if printing:
                    print('{} started at {} sec'.format(task, completed_time))
        awaiting_time = min(time_to_complete.values())  # ожидаем, пока хотя бы одна из задач кончится
        completed_time += awaiting_time  # отмечаем, что это время мы прождали
        for key, value in time_to_complete.items():
            time_to_complete[key] -= awaiting_time  # из каждой задачи вычетаем количество прошедшего времени
        to_delete = []  # здесь храним те задачи, которые стали пустыми (нельзя удалить задачу во время работы с ней)
        for key, value in time_to_complete.items():
            if value == 0:  # если оставшееся время выполнения задачи - 0, т.е. задача выполнена
                to_delete.append(key)  # добавляем задачу в список удаляемых задач
                conf_graph.remove_node(key)  # удаляем вершину задачи из графа
                current_tasks.remove(key)  # удаляем задачу из множества выполняемых сейчас задач
                # print('{} done at {} sec'.format(key, completed_time))

        for key in to_delete:
            time_to_complete.pop(key)  # удаляем тайминги выполненых задач, отмеченных выше
        if printing:
            print('{} done at {} sec'.format(key, completed_time))
            _pos = nx.shell_layout(conf_graph)
            nx.draw(conf_graph, _pos, with_labels=True)
            plt.show()
    return completed_time


best_time = 999999  # налиучшее время, берем очень большим, чтобы точно обновилось новым значением
for combination in variations:  # берем возможные парные сочетания вершин
    for single_variant in permutations(combination):  # рассматриваем все их перестановки
        c = get_conflicts(single_variant)  # находим матрицу конфликтов
        total_time = compute_time(c)  # считаем суммарное время выполнения на такой расстановке станций
        if total_time < best_time:  # если время работы меньше нынешнего минимума по времени
            best_time = total_time  # сохраняем новое лучшее время
            best_conf = c  # сохраняем наилучшую матрицу конфликтов
            best_combination = single_variant  # сохраняем наилучшую комбинацию станций

print('Minimum time: {}'.format(compute_time(get_conflicts(best_combination, printing=1), printing=1)))
print('Stations: {}'.format(best_combination))