Reputation: 67
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:
I want the 'A' node to be on the far left and the 'H' node on the far right.
Upvotes: 3
Views: 7703
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:
Upvotes: 3
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'
)
)
Upvotes: 9
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