aud.example.graph.MaxFlowExample Class Reference

Example for computing the maximum flow using a Ford-Fulkerson type algorithm. More...

Inheritance diagram for aud.example.graph.MaxFlowExample:

Collaboration diagram for aud.example.graph.MaxFlowExample:

Public Member Functions
	MaxFlowExample ()
	create application More...
void	computeMaxFlow (MyGraph g)
	main algorithm (calls findAugmentingPath and addPath More...
Public Member Functions inherited from aud.util.SingleStepper
	SingleStepper (JFrame parent)
	create new instance More...
	SingleStepper (String caption)
	create new instance More...
JFrame	parent ()
	get parent widget More...
void	halt (String text, int timeout)
	display text and wait for user or timeout More...
void	setTimeout (int timeout)
	Set global timeout. More...
SingleStepper	whereAmI ()
	print location of calling code More...
SingleStepper	showSource ()
	jmp to caller's location in editor (emacs only) More...
void	halt (String text)
	display text and wait for user (or global timeout) More...
void	halt ()
	wait for user More...

Static Public Member Functions
static void	main (String[] args)
	example (see also usage) More...
static void	main (String[] args)

Protected Member Functions
void	onHalt ()
Protected Member Functions inherited from aud.util.SingleStepper
JComponent	createComponents ()
void	onNext ()
	call on button pressed More...
void	println (String text)
	print to both, text area and stdout More...
void	onHalt ()

Static Protected Member Functions
static void	usage ()
static MyGraph	createGraph ()
	create a small example graph More...

Protected Attributes
DotViewer	viewer_
Protected Attributes inherited from aud.util.SingleStepper
JFrame	frame
JTextArea	history
JButton	next
Object	monitor = new Object()
int	timeout = 0

Detailed Description

Example for computing the maximum flow using a Ford-Fulkerson type algorithm.

Actually, the class implements the Edmonds-Karp algorithm, which uses a breadth-first search to find augmenting paths.

The main part of the algorithm is found in computeMaxFlow calling #findAugmentingPath and #addPath

The implementation manipulates the graph and temporarily adds backward edges to model the return flow.

Definition at line 21 of file MaxFlowExample.java.

Constructor & Destructor Documentation

MaxFlowExample()

aud.example.graph.MaxFlowExample.MaxFlowExample

(

)

create application

Definition at line 34 of file MaxFlowExample.java.

                          {
    super("aud.example.graph.MaxFlowExample");
  }

Member Function Documentation

computeMaxFlow()

void aud.example.graph.MaxFlowExample.computeMaxFlow

(

MyGraph

g

)

main algorithm (calls findAugmentingPath and addPath

Definition at line 60 of file MaxFlowExample.java.

                                        {
    initialize(g);
 
    double cp;
 
    while (!Double.isInfinite(cp=findAugmentingPath())) {
      addPath(cp);
    }
 
    cleanup();
  }

createGraph()

static MyGraph aud.example.graph.MaxFlowExample.createGraph ( )

staticprotected

create a small example graph

Definition at line 239 of file MaxFlowExample.java.

                                         {
    MyGraph g=new MyGraph(true);
    MyNode s=g.addNode(), t=g.addNode(), a=g.addNode(), b=g.addNode();
    s.setLabel("s");
    t.setLabel("t");
    s.setPosition(0.0,0.0);
    t.setPosition(4.0,0.0);
    a.setPosition(2.0,2.0);
    b.setPosition(2.0,-2.0);
    g.addEdge(s,a).setWeight(4.0);
    g.addEdge(s,b).setWeight(2.0);
    g.addEdge(a,b).setWeight(3.0);
    g.addEdge(a,t).setWeight(1.0);
    g.addEdge(b,t).setWeight(6.0);
    return g;
  }

References aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.addEdge(), aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.addNode(), aud.graph.SimpleNode.setLabel(), and aud.graph.SimpleNode.setPosition().

Here is the call graph for this function:

main()

static void aud.example.graph.MaxFlowExample.main ( String[]  args )

static

example (see also usage)

Reimplemented from aud.util.SingleStepper.

Definition at line 257 of file MaxFlowExample.java.

                                         {
    MyGraph g=new MyGraph(true);
 
    File graph=null;
    double widthfactor=2.0; // emphasize pen width for visualization
 
    for (int i=0;i<args.length;++i) {
      if (args[i].compareTo("-g")==0)
        graph=new File(args[++i]);
      if (args[i].compareTo("-w")==0)
        widthfactor=Double.parseDouble(args[++i]);
    }
 
    MaxFlowExample app=new MaxFlowExample();
    app.widthfactor=widthfactor;
 
    if (graph==null)
      g=createGraph();
    else {
      new GraphParser(g.getAbstractGraph()).parse(graph);
    }
 
    // compute max-flow
    app.computeMaxFlow(g);
    app.halt("DONE");
 
    System.exit(0);
  }

onHalt()

void aud.example.graph.MaxFlowExample.onHalt ( )

protected

Reimplemented from aud.util.SingleStepper.

Definition at line 29 of file MaxFlowExample.java.

                                    {
      viewer_.display(g_);
  }

References aud.util.DotViewer.display(), and aud.example.graph.MaxFlowExample.viewer_.

Here is the call graph for this function:

usage()

static void aud.example.graph.MaxFlowExample.usage ( )

staticprotected

Definition at line 231 of file MaxFlowExample.java.

                                {
    System.err.println(
          "java aud.example.graph.MaxFlowExample "+
          "[-g graphfile] [-w factor]");
    System.exit(-1);
  }

Member Data Documentation

viewer_

DotViewer aud.example.graph.MaxFlowExample.viewer_

protected

Initial value:

= DotViewer.displayWindow
    ((String) null,"aud.example.graph.MaxFlowExample")

Definition at line 26 of file MaxFlowExample.java.

Referenced by aud.example.graph.MaxFlowExample.onHalt().

---

The documentation for this class was generated from the following file:

• MaxFlowExample.java