Как разместить узлы в определенной позиции - networkx

Question

Я делаю метод Форда-Фулкерсона, который рисует график на каждом этапе. Я хочу разместить источник и сток в определенных позициях (я хочу, чтобы источник находился в крайнем левом углу графика, а приемник - в крайнем правом). Я уже пробовал аргумент pos внутри функции spring_layout, но, похоже, это не сработало.

Это мой график:

graph.add_edges_from([
    ('A', 'B', {'capacity': 4, 'flow': 0}),
    ('A', 'C', {'capacity': 5, 'flow': 0}),
    ('A', 'D', {'capacity': 7, 'flow': 0}),
    ('B', 'E', {'capacity': 7, 'flow': 0}),
    ('C', 'E', {'capacity': 6, 'flow': 0}),
    ('C', 'F', {'capacity': 4, 'flow': 0}),
    ('C', 'G', {'capacity': 1, 'flow': 0}),
    ('D', 'F', {'capacity': 8, 'flow': 0}),
    ('D', 'G', {'capacity': 1, 'flow': 0}),
    ('E', 'H', {'capacity': 7, 'flow': 0}),
    ('F', 'H', {'capacity': 6, 'flow': 0}),
    ('G', 'H', {'capacity': 4, 'flow': 0}),

])

Алгоритм Форда-Фулкерсона:

def ford_fulkerson(graph, source, sink, debug=None):
    flow, path = 0, True

    while path:
        path, reserve = depth_first_search(graph, source, sink)
        flow += reserve

        for v, u in zip(path, path[1:]):
            if graph.has_edge(v, u):
                graph[v][u]['flow'] += reserve
            else:
                graph[u][v]['flow'] -= reserve

        if callable(debug):
            debug(graph, path, reserve, flow)


def depth_first_search(graph, source, sink):
    undirected = graph.to_undirected()
    explored = {source}
    stack = [(source, 0, dict(undirected[source]))]

    while stack:
        v, _, neighbours = stack[-1]
        if v == sink:
            break

        while neighbours:
            u, e = neighbours.popitem()
            if u not in explored:
                break
        else:
            stack.pop()
            continue

        in_direction = graph.has_edge(v, u)
        capacity = e['capacity']
        flow = e['flow']
        neighbours = dict(undirected[u])

        if in_direction and flow < capacity:
            stack.append((u, capacity - flow, neighbours))
            explored.add(u)
        elif not in_direction and flow:
            stack.append((u, flow, neighbours))
            explored.add(u)

    reserve = min((f for _, f, _ in stack[1:]), default=0)
    path = [v for v, _, _ in stack]

    return path, reserve
ford_fulkerson(graph, 'A', 'H', flow_debug)

И это макет, который я использую:

layout = nx.spring_layout(graph, weight='capacity', dim=2, k=20, pos={'A': [-3, -3], 'H': [5, 1]})

Вот результат, который я получаю:

Я хочу, чтобы узел 'A' находился в крайнем левом положении, а узел 'H' - в крайнем правом.

Answer 1

Проверяя документацию для spring_layout, он говорит:

pos (dict или None необязательно (по умолчанию = None)) - Исходные позициидля узлов в качестве словаря с узлом в качестве ключей и значений в качестве списка координат или кортежа.Если None, используйте случайные начальные позиции.

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

Посмотрите на следующий аргумент:

фиксированный (список или None необязательный (по умолчанию = None)) - узлы, которые должны быть зафиксированы в начальной позиции.

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

Answer 2

После того, как макет узла выполнен, вы получаете все позиции узлов в объекте dict (здесь layout). Вы всегда можете изменить положение некоторых из них по своему желанию. Здесь я устанавливаю позиции узлов A и H слева и справа от центра графика (0,0).

# fix positions of some nodes
layout['A'] = [-3, -3]   # position at left
layout['H'] = [5, 1]     # position at right

На данном этапе, если вы хотите переместить их дальше от центра графика, этот простой код может справиться с этим.

# reposition the nodes further away from center
# need: import numpy as np
xmult = 1.2    # use value greater than 1.0
layout['A'] = layout['A']*np.array([xmult, 1])   # move left
layout['H'] = layout['H']*np.array([xmult, 1])   # move right

Наконец, когда вы строите сеть с

nx.draw_networkx(graph, pos=layout)

Вы должны получить сюжет, похожий на этот:

Answer 3

Я рекомендую вам использовать макет графика из agraph с визуализацией DOT:

    pos=nx.drawing.nx_agraph.graphviz_layout(
        graph,
        prog='dot',
        args='-Grankdir=LR'
    )

Это заставляет nx.draw вызвать программу DOT для получения макета графика.DOT предназначен для использования с ориентированным графом (особенно ациклическим).Здесь вы можете увидеть использование этого макета (обратите внимание, что graphviz и agraph -Python разъем должен быть установлен):

nx.draw(
    graph,
    node_size=2000,
    node_color='#0000FF',
    arrowsize=50,
    with_labels=True,
    labels={n: n for n in graph.nodes},
    font_color='#FFFFFF',
    font_size=35,
    pos=nx.drawing.nx_agraph.graphviz_layout(
        graph,
        prog='dot',
        args='-Grankdir=LR'
    )
)