networks(deprecated)/dinic - Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : networks(deprecated)/dinic

networks[dinic] - augmenting-path flow algorithm

Calling Sequence

dinic(G, s, t, eset, comp)

dinic(G, s, t, eset, comp, n)

Parameters

G

-

graph or network

s

-

source vertex for the flow

t

-

sink vertex for the flow

eset

-

name to return the set of saturated edges

comp

-

name to return the set of vertices in eset

n

-

integer upper bound for the flow

Description

• 

Important: The networks package has been deprecated.  Use the superseding package GraphTheory instead.

• 

This routine returns the maximum flow from s to t in G.  It is normally called by the routine flow() which performs some setup and preliminary analysis based on edge-connectivity calculations.

• 

Edge weights of G are interpreted as capacities.

• 

If a non-negative integer upper bound n is specified for the flow then the routine terminates after a flow of n in G is found even if greater flows are possible.

• 

This routine is normally loaded via the command with(networks) but may also be referenced using the full name networks[dinic](...).

Examples

Important: The networks package has been deprecated.  Use the superseding package GraphTheory instead.

withnetworks:

G:=petersen:

dinicG,1,2,eset,comp

3

(1)

eset

1,2,1,5,1,6,2,3,2,8,3,4,4,7,5,9,6,7,8,9

(2)

comp

1

(3)

eset:='eset':comp:='comp':

flowG,1,5,eset,comp,maxflow=1

1

(4)

eset

1,5

(5)

See Also

GraphTheory, networks(deprecated)[shortpathtree], networks(deprecated)[spantree]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam