Шаблоны Python - реализация графов


Гвидо ван Россум, "Python Patterns - Implementing Graphs"
Перевод: С.Тезадов


Графы - это сети, состоящие из узлов, соединенных ребрами или дугами. В ориентированных графах соединения между узлами имеют направление и называются дугами; в неориентированных графах соединения не имеют направления и называются ребрами. Мы, в основном, обсудим ориентированные графы. Алгоритмы для графов включают поиск пути между двумя узлами, поиск кратчайшего пути между двумя узлами, нахождение циклов в графе (цикл - это непустой путь, соединяющий узел с самим собой), поиск пути, проходящего через все узлы (знаменитая "задача коммивояжера"), и т.д. Иногда узлы или дуги графа имеют вес или цену, ассоциированную с ними, и нас интересует нахождение пути наименьшей цены.

Существует значительная литература, посвященная алгоритмам для графов, которые являются важной частью дискретной математики. Графы также имеют большое практическое применение в компьютерных алгоритмах. Очевидные примеры можно найти в управлении сетями, но примеры изобилуют и во многих прочих областях. К примеру, связь вызывающий-вызываемый в компьютерной программе можно представить как граф (в котором циклы означают рекурсию, а недостижимые узлы - "мертвый" код).

Несколько языков программирования предоставляют прямую поддержку графов как типа данных, и Python не исключение. Однако, графы легко реализуются с помощью списков и словарей. Например, ниже приводится простой граф:


    A -> B

    A -> C

    B -> C

    B -> D

    C -> D

    D -> C

    E -> F

    F -> C

У этого графа шесть узлов (A-F) и восемь дуг. Он может быть представлен посредством следующих структур данных Python:

    graph = {'A': ['B', 'C'],

             'B': ['C', 'D'],

             'C': ['D'],

             'D': ['C'],

             'E': ['F'],

             'F': ['C']}

Это словарь, чьи ключи являются узлами графа. Для каждого ключа соответствующее значение - это список, содержащий узлы, соединенные прямой дугой из данного узла. Это настолько просто, насколько возможно (даже еще проще, ведь узлы могли быть представлены числами, а не именами, но имена более удобны и могут быть легко заменены на несущие больше информации, такие как названия городов).

Давайте напишем простую функцию, определяющую путь между двумя узлами. Она будет принимать граф, начальный и конечный узлы в качестве аргументов. Возвращать же она будет список узлов (включая начальный и конечный) входящих в искомый путь. Если никакого пути не может быть найдено, она вернет None. Один и тот же узел будет входить не более одного раза в возвращаемый путь (т.е. он не содержит циклов). Алгоритм использует важную технику, называемую "бектрекинг" (backtracking): она пробует все возможности прохода перед тем, как находит решение.


    def find_path(graph, start, end, path=[]):

        path = path + [start]

        if start == end:

            return path

        if not graph.has_key(start):

            return None

        for node in graph[start]:

            if node not in path:

                newpath = find_path(graph, node, end, path)

                if newpath: return newpath

        return None

Образец вызова (используя граф показанный выше):

    >>> find_path(graph, 'A', 'D')

    ['A', 'B', 'C', 'D']

    >>> 

Второй оператор 'if' необходим только в том случае, если имееются узлы, которые перечислены как концевые точки дуг, но сами не имеют выходящих дуг, и поэтому не упоминаются в графе. Такие узлы могут также включяться в граф, с пустым списком выходящих дуг, но иногда удобнее не требовать этого.

Заметьте, что хотя пользователь вызывает find_graph() с тремя аргументами, сама себя она вызывает с четвертым аргументом: текущим путем. Значением по умолчанию этого аргумента является пустой список, '[]', означающий, что мы еще не посетили ни один узел. Данный аргумент используется для избежания циклов(первый 'if' внутри цикла 'for'). Аргумент 'path' не модифицируется: присваивание "path = path + [start]" создает новый список. Если бы вместо этого мы написали "path.append(start)", то мы модифицировали бы переменную 'path' стоящую в месте вызова, с катастрофическим результатом. (Используя тьюплы, мы могли бы быть уверены, что этого не произойдет, ценой записи "path = path + (start,)", поскольку "(start)" вовсе не одноэлементный тьюпл -- это просто выражение в скобках.)

Очень просто привести эту функцию к виду, возвращающему список всех путей (без циклов) вместо возврата первого попавшегося пути:


    def find_all_paths(graph, start, end, path=[]):

        path = path + [start]

        if start == end:

            return [path]

        if not graph.has_key(start):

            return []

        paths = []

        for node in graph[start]:

            if node not in path:

                newpaths = find_all_paths(graph, node, end, path)

                for newpath in newpaths:

                    paths.append(newpath)

        return paths

Пример вызова:

    >>> find_all_paths(graph, 'A', 'D')

    [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

    >>> 

Другой вариант находит наикратчайший путь:

    def find_shortest_path(graph, start, end, path=[]):

        path = path + [start]

        if start == end:

            return path

        if not graph.has_key(start):

            return None

        shortest = None

        for node in graph[start]:

            if node not in path:

                newpath = find_path(graph, node, end, path)

                if newpath:

                    if not shortest or len(newpath) < len(shortest):

                        shortest = newpath

        return shortest

Запуск:

    >>> find_shortest_path(graph, 'A', 'D')

    ['A', 'C', 'D']

    >>> 

Эти функции просты почти настолько, насколько они могут быть. И все же они близки к оптимальному (для кода, написанного на Python). В следующих колонках "Шаблоны Python" я попытаюсь проанализировать их скорость работы и улучшить их исполнение ценой увеличения кода.

Другой вариацией было бы придание большей абстракции данным: создать класс для представления графов, методы которого реализуют важные алгоритмы. Хотя этого требует желание структурного программирования, это не сделает код более эффективным. Это, на самом деле, делает проще добавление различных меток к узлам или дугам и добавление алгоритмов, использующих эти метки при счете (например, для поиска кратчайшего маршрута между двумя городами на карте). Это, кстати, также будет предметом других колонок.

[Содержание]