Как построить этот граф в Python?

Question

Я практикую Python, хочу создать граф на Python с начальным узлом и некоторыми требованиями для детей. Значение каждого узла будет 3 цифры (например, 320, 110), и я хочу сгенерировать дочерние элементы в следующем порядке:

• 1 вычитается из первой цифры
• 1 добавляется к первой цифре
• 1 вычитается из второй цифры
• 1 добавляется ко второй цифре
• 1 вычитается из третьей цифры
• 1 добавляется к третьей цифре

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

Ограничения:

• Вы не можете добавить к цифре 9 или вычесть из цифры 0;
• Вы не можете сделать ход, который преобразует текущее число в одно из запрещенные номера;
• Вы не можете изменить одну и ту же цифру дважды за два последовательных хода.

Обратите внимание, что, поскольку числа имеют 3 цифры, в начале не более 6 возможных ходов от начального узла. После первого перемещения коэффициент ветвления составляет не более 4 из-за ограничений на перемещения и особенно из-за ограничения 3.

Я уже реализовал класс Node для своего графика, но у меня проблемы с созданием графика.

Вот что я сделал с классом Node:

class Node(object):
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = []

    def add_child(self, obj):
        self.children.append(obj)

    def add_parent(self, obj):
        self.parent.append(obj)

root = Node(320)

def get_root():
    print(root.data)

# some things I've tried
# p = Node(root.data-100)
# p.add_parent(root.data)
# root.add_child(p.data)
# set_root(320)
get_root()
# print(root.data)
# print(root.children)
# print(p.parent)
# p = Node(root.data-100)

Я реализовал BFS, которая выдает правильный путь при выводе графа, но я не могу создать реальный граф для использования в этой BFS. Вот мой BFS:

visited = set()

def bfs(graph_to_search, start, end):
    queue = [[start]]
    # visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes 
            set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path 
                    and push it into the queue
            for current_neighbour in graph_to_search.get(vertex[]):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)

* * Пример одна тысяча тридцать восемь: С начальным узлом: 320 и конечным узлом: 110, без запрещенных узлов, поиск BFS на этом графике будет выглядеть так:

Любая помощь будет принята с благодарностью. Спасибо.

Answer 1

Прежде всего, чтобы создать модель Node и способ генерации графа, мы должны сделать несколько предположений:

• это неориентированный граф
• расстояние между узлами равноценно или не имеет значения
• Node потребует какой-то идентификационный номер
• генерация соседей относительно текущего Node, следовательно, функциональность должна быть частью Node instance
• если мы не укажем предел, Graph может быть сгенерирован бесконечно, поэтому мы должны ввести понятие max_spread

Следовательно, код для Node будет выглядеть так:

from copy import copy

def check_three_digits(value_name, digits):
    assert len(digits) == 3, "The {} should be of precise length 3. Actual: {}".format(value_name, digits)
    assert digits.isdigit(), "The {} should consist of 3 digits. Actual {}".format(value_name, digits)


class Node:

    _node_count = 0

    def __init__(self, data: str):
        check_three_digits("data param", data)
        self._id = Node._node_count
        self._data = data
        self._neighbours = []
        Node._node_count += 1

    @property
    def id(self):
        return self._id

    @property
    def data(self):
        return copy(self._data)

    @property
    def neighbours(self):
        return copy(self._neighbours)

    def add_neighbour(self, neighbour):
        self._neighbours.append(neighbour)

    def _new_neighbour(self, data):
        new_neighbour = Node(data)
        new_neighbour.add_neighbour(self)
        return new_neighbour

    def generate_neighbours(self, forbidden_nodes_digits=[]):
        first_digit = self._data[0]
        second_digit = self._data[1]
        third_digit = self._data[2]

        first_digit_num = int(first_digit)
        second_digit_num = int(second_digit)
        third_digit_num = int(third_digit)
        sub_first_digit_num = first_digit_num - 1
        add_first_digit_num = first_digit_num + 1

        sub_second_digit_num = second_digit_num - 1
        add_second_digit_num = second_digit_num + 1

        sub_third_digit_num = third_digit_num - 1
        add_third_digit_num = third_digit_num + 1

        sub_first_digit_num = first_digit_num if sub_first_digit_num < 0 else sub_first_digit_num
        add_first_digit_num = first_digit_num if add_first_digit_num > 9 else add_first_digit_num

        sub_second_digit_num = second_digit_num if sub_second_digit_num < 0 else sub_second_digit_num
        add_second_digit_num = second_digit_num if add_second_digit_num > 9 else add_second_digit_num

        sub_third_digit_num = third_digit_num if sub_third_digit_num < 0 else sub_third_digit_num
        add_third_digit_num = third_digit_num if add_third_digit_num > 9 else add_third_digit_num


        for ndigits in [
            "{}{}{}".format(str(sub_first_digit_num), second_digit, third_digit),
            "{}{}{}".format(str(add_first_digit_num), second_digit, third_digit),
            "{}{}{}".format(first_digit, str(sub_second_digit_num), third_digit),
            "{}{}{}".format(first_digit, str(add_second_digit_num), third_digit),
            "{}{}{}".format(first_digit, second_digit, str(sub_third_digit_num)),
            "{}{}{}".format(first_digit, second_digit, str(add_third_digit_num)),
        ]:
            if ndigits in forbidden_nodes_digits:
                continue

            self._neighbours.append(self._new_neighbour(ndigits))


    def __repr__(self):
        return str(self)

    def __str__(self):
        return "Node({})".format(self._data)

для генерации графа имеем:

def generate_nodes(node, end_node_digits, forbidden_nodes_digits, visited_nodes=None, current_spread=0, max_spread=4):
    """
    Handles the generation of the graph.

    :node: the current node to generate neighbours for
    :end_node_digits: the digits at which to stop spreading further the graph from the current spread.
    :visited_nodes: Marks the nodes for which neighbours generation happened, to avoid repetition and infinite recursion.
    :current_spread: Marks the current level at which neighbours are being generated.
    :max_spread: Defined the max spread over which the graph should no longer generate neighbours for nodes.
    """

    # initialize the kwargs with None values
    if visited_nodes is None:
        visited_nodes = []

    # mark the current node as visited
    visited_nodes.append(node.id)

    # no reason to generate further since we hit the max spread limit
    if current_spread >= max_spread:
        return

    # generate the neighbours for the current node
    node.generate_neighbours(forbidden_nodes_digits)

    # if we generated the end node, fall back, no need to generate further
    if end_node_digits in [n.data for n in node.neighbours]:
        return

    # make sure to generate neighbours for the current node's neighbours as well
    for neighbour in node.neighbours:
        if neighbour.id in visited_nodes:
            continue

        generate_nodes(
            neighbour, end_node_digits, forbidden_nodes_digits,
            visited_nodes=visited_nodes, current_spread=current_spread + 1, max_spread=max_spread
        )

Алгоритм поиска в ширину для такой модели будет выглядеть так:

def bfs(node, end_node_digits, visited_nodes=None, path=None):
    """
    Looks for a specific digit sequence in the graph starting from a specific node.
    :node: the node to start search from.
    :end_node_digits: The digit sequence to look for.
    :visited_nodes: The nodes for which BFS was already performed. Used to avoid infinite recursion and cyclic traversal.
    :path: The search path that lead to this node.
    """

    # initialize the None kwargs
    if visited_nodes is None:
        visited_nodes = []

    if path is None:
        path = ""
    path += "({}, {}) ".format(node.id, node.data)

    # mark the current node as visited
    visited_nodes.append(node.id)

    # if we find the end node we can safely report back the match
    if node.data == end_node_digits:
        return path

    # if the current node doesn't match the end node then we look into the neighbours
    for neighbour in node.neighbours:

        # exclude the visited nodes (obviously excluding the node that generated these nodes)
        if neighbour.id in visited_nodes:
            continue

        # do a BFS in the subdivision of the graph
        result_path = bfs(neighbour, end_node_digits, visited_nodes, path)

        # if a match was found in the neighbour subdivision, report it back
        if result_path is not None:
            return result_path

    return None

Мы можем проиллюстрировать функциональность кода, написанного на примере input.txt, например:

320
221
330 420

и блок __main__, например:

if __name__ == '__main__':

    # retrieve the nodes from the input file
    start_node_digits = None
    end_node_digits = None
    forbidden_nodes_digits = []

    with open("input.txt", "r") as pf:
        start_node_digits = pf.readline().strip()
        end_node_digits = pf.readline().strip()
        forbidden_nodes_digits = pf.readline().split()

    forbidden_nodes_digits = [fnode.strip() for fnode in forbidden_nodes_digits]
    print("Start node digits: {}".format(start_node_digits))
    print("End node digits: {}".format(end_node_digits))
    print("Forbidden nodes digits: {}".format(forbidden_nodes_digits))

    # validate the input nodes data
    check_three_digits("start node", start_node_digits)
    check_three_digits("end node", end_node_digits)
    for fnode_digits in forbidden_nodes_digits:
        check_three_digits("forbidden node", fnode_digits)

    # create the first node and generate the graph
    first_node = Node(start_node_digits)
    print("Generate nodes for graph....")
    max_spread = 2
    generate_nodes(first_node, end_node_digits, forbidden_nodes_digits, max_spread=max_spread)

    # poerform a BFS for a sequence of digits
    print("BFS for {}".format(end_node_digits))
    match_path = bfs(first_node, end_node_digits)
    print("BFS search result: {}".format(match_path))

Мы могли бы также визуализировать график, используя следующие функции:

import networkx as nx
import matplotlib.pyplot as plt

def _draw_node(graph, node, visited_nodes=None):

    # initialize kwargs with None values
    if visited_nodes is None:
        visited_nodes = []

    # mark node as visited
    visited_nodes.append(node.id)

    for neighbour in node.neighbours:
        if neighbour.id in visited_nodes:
            continue

        graph.add_node(neighbour.id)
        graph.add_edge(node.id, neighbour.id)
        nx.set_node_attributes(graph, {neighbour.id: {'data': neighbour.data}})

        _draw_node(graph, neighbour, visited_nodes)


def draw_graph(first_node, start_node_digits, end_node_digits, forbidden_nodes_digits, fig_scale, fig_scale_exponent=1.2):
    g = nx.Graph()

    # add first node to the draw figure
    g.add_node(first_node.id)
    nx.set_node_attributes(g, {first_node.id: {'data': first_node.data}})
    _draw_node(g, first_node)

    # prepare graph drawing
    labels = nx.get_node_attributes(g, 'data')
    fig = plt.figure(frameon=False)
    INCH_FACTOR = 5  # inches
    fig_scale = fig_scale ** fig_scale_exponent
    fig.set_size_inches(fig_scale * INCH_FACTOR, fig_scale * INCH_FACTOR)

    nodes_attributes = nx.get_node_attributes(g, 'data')

    color_map = []
    for n in g:
        ndata = nodes_attributes[n]
        if ndata == start_node_digits:
            color_map.append('yellow')
        elif ndata == end_node_digits:
            color_map.append('cyan')
        elif ndata in forbidden_nodes_digits:
            # just in case something slips
            color_map.append('red')
        else:
            color_map.append("#e5e5e5")

    # actually draw the graph and save it to a PNG.
    nx.draw_networkx(
        g, with_labels=True, labels=labels, node_size=600,
        node_color=color_map,
        # node_color='#e5e5e5',
        font_weight='bold', font_size="10",
        pos=nx.drawing.nx_agraph.graphviz_layout(g)
    )
    plt.savefig("graph.png", dpi=100)

, который можно вызвать в блоке __main__, например:

print("Draw graph...")
draw_graph(first_node, start_node_digits, end_node_digits, forbidden_nodes_digits, fig_scale=max_spread, fig_scale_exponent=1)

График выглядит так:

Для которого результат BFS будет примерно таким: (0, 320) (1, 220) (10, 221)

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

Для networkx graphviz вам потребуется установить через pip пакет pygraphviz, а если вы работаете в Linux, вам может понадобиться sudo apt-get install graphviz libgraphviz-dev pkg-config