如何将节点放置在特定位置 - networkx

Question

我正在做一个 Ford-Fulkerson 方法，它在每个阶段绘制图形。我想将源和接收器放置在特定位置（我希望源位于图表的最左侧，而接收器位于最右侧）。我已经尝试过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}),

])

Ford-Fulkerson 算法：

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

我建议您使用带有 DOT 可视化的 agraph 中的graphviz 布局：

    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'
    )
)