Skip to main content
 首页 » 编程设计

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

2024年11月24日10kuangbin

我正在使用 Ford-Fulkerson 方法在每个阶段绘制图表。我想将 source 和 sink 放在特定位置(我希望 source 位于图表的最左侧,sink 位于最右侧)。我已经在 spring_layout 函数中尝试了 pos 参数,但这似乎不起作用。

这是我的图表:

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]}) 

这是我得到的结果:

Result

我希望“A”节点位于最左侧,“H”节点位于最右侧。

请您参考如下方法:

我推荐你使用graphviz layout来自带有 DOT 可视化的图表:

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

它强制nx.draw 调用DOT 程序来获取图形布局。 DOT 旨在与有向图(尤其是无环图)一起使用。这里可以看到这个布局的用法(注意必须安装graphviz和agraph-Python connector):

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