CODEWITHSUNDEEP
pythongraphnetworkx
Adrian Covaci
Adrian Covaci

Reputation: 67

How to place nodes in a specific position - networkx

I am doing a Ford-Fulkerson method which draws the graph at every stage. I want to place the source and the sink on specific positions (I want the source to be on the far left of the graph and the sink on the far right). I've already tried the pos argument inside the spring_layout function, but that doesn't seem to work.

This is my graph:

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 algorithm:

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)

And this is the layout that I use:

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

This is the result that I get:

Result

I want the 'A' node to be on the far left and the 'H' node on the far right.

Upvotes: 3

Views: 7703

Answers (3)

swatchai
swatchai

Reputation: 18822

After the node layout is done, you get all the nodes' positions in the dict object (here layout). You can always reposition some of them as you wish. Here I set the positions of nodes A and H on the left and right of the graph's center (0,0).

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

At this stage, If you want to move them further away from the graph's center, this simple code can handle that.

# 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

Finally, when you plot the network with

nx.draw_networkx(graph, pos=layout)

You should get the plot similar to this:

enter image description here

Upvotes: 3

vurmux
vurmux

Reputation: 10030

I recommend you to use graphviz layout from agraph with DOT visualization:

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

It forces nx.draw to call DOT program to get the graph layout. DOT is designed to be used with directed graph (especially acyclic). Here you can see the usage of this layout (note that graphviz and agraph-Python connector must be installed):

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

enter image description here

Upvotes: 9

Joel
Joel

Reputation: 23907

Checking the documentation for spring_layout, it says:

pos (dict or None optional (default=None)) – Initial positions for nodes as a dictionary with node as keys and values as a coordinate list or tuple. If None, then use random initial positions.

So you've set the initial positions of the nodes, but the algorithm moves nodes around from the starting position, so it's not a surprise these change.

Look at the next argument:

fixed (list or None optional (default=None)) – Nodes to keep fixed at initial position.

So you need to specify which nodes are fixed in their initial position using this optional argument.

Upvotes: 4

Related Questions