max_cap_path — maximum capacity path
[p,cap] = max_cap_path(i,j,g)
integers, node numbers
row vector of integer numbers of the arcs of the path if it exists
value of the capacity of the path
max_cap_path
returns the path with maximum capacity from node
i
to node j
for the graph g
if it exists and returns
the empty vector []
otherwise.
The capacities of the edges are given by the field max_cap
of the edges sub field of the graph data structure. If its value is not given (empty vector []
),
max_cap_path
returns the empty vector []
.
The capacities must be strictly positive, i.e negative capacities
are considered as equal to 0 (no capacity at all).
ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17]; he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15]; g=make_graph('foo',1,17,ta,he); g.nodes.graphics.x=[142,82,32,29,82,82,137,136,170,192,252,257,220,312,316,379,321]*1.2; g.nodes.graphics.y=[30,67,112,159,114,160,111,162,216,71,105,160,214,222,94,76,151]*1.2; g = add_edge_data(g,'max_cap',int(rand(1,edge_number(g))*16)+5) g.edges.graphics.display='max_cap'; g.nodes.graphics.display='number'; show_graph(g); hilite_nodes([1 14]) [p,cap]=max_cap_path(1,14,g); hilite_edges(p);