Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs

---

flow_dire_graph Class Reference

#include <rm3_flow_dire_graph.h>

Inheritance diagram for flow_dire_graph:

[legend]

Collaboration diagram for flow_dire_graph:

[legend]

List of all members.

Public Member Functions
	flow_dire_graph ()
	~flow_dire_graph ()
	flow_dire_graph (const undi_graph &)
	flow_dire_graph (const dire_graph &)
	flow_dire_graph (const flow_dire_graph &)
flow_dire_graph &	operator= (const undi_graph &)
flow_dire_graph &	operator= (const dire_graph &)
flow_dire_graph &	operator= (const flow_dire_graph &)
void	local_get (gdt::gdtnode_map< struct_flow_dire_node_info > *&p1, gdt::gdtedge_map< struct_flow_dire_edge_info > *&p2)
int	get_balance (gdtnode v) const
int	get_upper_capacity (gdtedge e) const
int	get_lower_capacity (gdtedge e) const
int	get_flow (gdtedge e) const
int	get_cost (gdtedge e) const
int	flow_cost () const
int	in_flow (gdtnode v)
int	out_flow (gdtnode v)
int	diff_flow (gdtnode v)
bool	balance_is_consistent () const
bool	flow_is_consistent (gdtedge e) const
bool	flow_is_consistent (gdtnode v)
bool	flow_is_consistent ()
bool	is_consistent ()
void	clear ()
void	set_balance (gdtnode v, int b)
void	set_upper_capacity (gdtedge e, int uc)
void	set_lower_capacity (gdtedge e, int lc)
void	set_cost (gdtedge e, int c)
void	set_flow (gdtedge e, int f)
void	set_edge_info (gdtedge e, int uc, int lc, int c, int f)
void	steal_from (dire_graph &dg)
void	mirror (flow_dire_graph &fdg)
void	forget ()
bool	min_cost_flow ()

---

Detailed Description

CLASS flow_dire_graph A flow_dire_graph F is a directed graph such that:

• • Any gdtnode v of F has an associated function "balance(v)" such that Sum_v[balance(v)] = 0:
  • if (balance(v) > 0) v "supplies" flow;
  • if (balance(v) < 0) v "demands" flow;
  • if (balance(v) = 0) v "manteins" flow.
• Any gdtedge e of F has associated the following functions:
  • lower_cap(e) >= 0;
  • upper_cap(e) >= lower_cap(e);
  • cost(e);
  • flow(e):
    1. lower_cap(e) <= flow(e) <= upper_cap(e);
    2. Sum_v[flow(v,w)] - Sum_u[flow(u,v)] = balance(v) for each gdtnode v in F.

Definition: We call "cost" of F the following: Sum_e[cost(e)*flow(e)].

NOTE: all the above mathematical functions are considered integral (that is with integer values only)

Definition at line 128 of file rm3_flow_dire_graph.h.

---

Constructor & Destructor Documentation

flow_dire_graph::flow_dire_graph

(

)

Empty constructor.

flow_dire_graph::~flow_dire_graph

(

)

Destructor.

flow_dire_graph::flow_dire_graph

(

const undi_graph &

)

Constructor from the undi_graph class. PRECONDITIONS: all undi_graph-edges must be directed

flow_dire_graph::flow_dire_graph

(

const dire_graph &

)

Constructor from the dire_graph class.

flow_dire_graph::flow_dire_graph

(

const flow_dire_graph &

)

Copy constructor.

---

Member Function Documentation

flow_dire_graph& flow_dire_graph::operator=

(

const undi_graph &

)

Equality operator from the undi_graph. PRECONDITIONS: all undi_graph-edges must be directed

Reimplemented from dire_graph.

flow_dire_graph& flow_dire_graph::operator=

(

const dire_graph &

)

Equality operator from the dire_graph.

flow_dire_graph& flow_dire_graph::operator=

(

const flow_dire_graph &

)

Copy equality operator.

void flow_dire_graph::local_get	(	gdt::gdtnode_map< struct_flow_dire_node_info > *&	p1,
		gdt::gdtedge_map< struct_flow_dire_edge_info > *&	p2
	)

Get all private variables.

int flow_dire_graph::get_balance

(

gdtnode

v

)

const

Return the balance of gdtnode.

int flow_dire_graph::get_upper_capacity

(

gdtedge

e

)

const

Return the upper capacity of gdtedge.

int flow_dire_graph::get_lower_capacity

(

gdtedge

e

)

const

Return the lower capacity of gdtedge.

int flow_dire_graph::get_flow

(

gdtedge

e

)

const

Return the flow of gdtedge.

int flow_dire_graph::get_cost

(

gdtedge

e

)

const

Return the cost of gdtedge.

int flow_dire_graph::flow_cost

(

)

const

Return the cost of the flow.

int flow_dire_graph::in_flow

(

gdtnode

v

)

Return the flow entering in gdtnode.

int flow_dire_graph::out_flow

(

gdtnode

v

)

Return the flow leaving gdtnode.

int flow_dire_graph::diff_flow

(

gdtnode

v

)

Return the difference from out_flow and in_flow of gdtnode.

bool flow_dire_graph::balance_is_consistent

(

)

const

Return false if some balance properties are violated.

bool flow_dire_graph::flow_is_consistent

(

gdtedge

e

)

const

Return false if the property
lower_cap(e) <= flow(e) <= upper_cap(e)
is violated on given gdtedge.

bool flow_dire_graph::flow_is_consistent

(

gdtnode

v

)

Return false if the property
Sum_v[flow(v,w)] - Sum_u[flow(u,v)] = balance(v)
is violated on given gdtnode.

bool flow_dire_graph::flow_is_consistent

(

)

Return return false if either:

1. lower_cap(e) <= flow(e) <= upper_cap(e)
2. Sum_w[flow(v,w)] - Sum_u[flow(u,v)] = balance(v)

are violated on some edges or nodes.

bool flow_dire_graph::is_consistent

(

)

Return false if some flow network properties are violated.

void flow_dire_graph::clear

(

)

Delete all nodes and edges.

Reimplemented from dire_graph.

void flow_dire_graph::set_balance	(	gdtnode	v,
		int	b
	)

Set the balance of gdtnode with int.

void flow_dire_graph::set_upper_capacity	(	gdtedge	e,
		int	uc
	)

Set the upper capacity of gdtedge with int.

void flow_dire_graph::set_lower_capacity	(	gdtedge	e,
		int	lc
	)

Set the lower capacity of gdtedge with int.

void flow_dire_graph::set_cost	(	gdtedge	e,
		int	c
	)

Set the cost of the gdtedge with int.

void flow_dire_graph::set_flow	(	gdtedge	e,
		int	f
	)

Set the flow of the gdtedge with int.

void flow_dire_graph::set_edge_info	(	gdtedge	e,
		int	uc,
		int	lc,
		int	c,
		int	f
	)

Set upper cap., lower cap., cost and flow of gdtedge with the int values specified in this order.

void flow_dire_graph::steal_from

(

dire_graph &

dg

)

Make *this with the dire_graph dg internal variables and cut these variables from dg. This method is used to make a dire_graph as a flow_dire_graph, manteining the same internal variables. WARNING: dg has an empty body after this method is applied

void flow_dire_graph::mirror

(

flow_dire_graph &

fdg

)

Copy all private variables of flow_dire_graph in *this.

void flow_dire_graph::forget

(

)

Cut all private variables in *this.

Reimplemented from undi_graph.

bool flow_dire_graph::min_cost_flow

(

)

Compute a min cost flow on the network. Return false if a fesible flow does not exist. PRECONDITIONS: current implementation only works for nonnegative costs.

---

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

• rm3_flow_dire_graph.h

---