mascoptDev.algos.networks
Class ApproxMinCostFlow

java.lang.Object
  |
  +--mascoptDev.algos.networks.ApproxMinCostFlow

Direct Known Subclasses:

ApproxMinCostFlowDev, ApproxMinCostFlowStages, ApproxMinCostFlowStraight

public class ApproxMinCostFlow

extends Object

Provides an algorithm of approximation of fractionnal MCF by "Lagrangienne" relaxation. TIME IS OUT OF BOUND on examples of file/nfsnet.mgl and file/americain-mieux.mgl Initialize the flow with the shortest path (Bellman) in terms of the congestion cost for all requests, no constraint of capacity. while the capacity constraints isn't satisfaied, divert the flow between the most loaded paths and the least loaded paths, to use an other deviation see ApproxMinCostFlowDev. Use the congestion cost(Arc) = exp(congestion(Arc)), to use other cost see ApproxMinCostFlowStages, ApproxMinCostFlowStraight.

Field Summary

String	CAPACITY_STRING_VALUE String which is read on arc for the capacity.
Vector	congestion The string which is read on a cable for the congestion.
double	CONGESTION_MAX The CONGESTION_MAX represent the maximun congestionq of the network.
Vector	costCongestion The string which is read on a cable for the congestion.
static double	EPSILON The epsilon when diverting the flow.
static double	EPSILON_END The epsilon to finish the resolution.
Vector	flowAllocated The string which is read on a cable for the congestion.
String	INDEX The string which is used as index on a cable.
int	nbArc Number of cables
int	nbRequest Number of requests
String	REQUEST_SIZE The string which is read on a request for the size of request.
int	W Number of wavelength per fiber.

Constructor Summary

ApproxMinCostFlow(WDMNetwork n)
Constructor.

Method Summary

void	addFlow(Arc cable, Arc request, Double addFlow) add flow on a cable for one request.
int	deCongest() Decongest the network while the capacity constraints are satisfaying.
void	deCongestFlow() Decongest the network while the capacity constraints are satisfaying.
Double	getCongestion(Arc a) return the congestion of arc a
Double	getFlow(Arc cable, Arc request) Return the flow allocated at cable for request.
Double	getFlowAllocated(Arc a) return the flow on arc a
void	printFlow() print the flow of all arc for all requests
void	setCongestion(Arc a, Double c) set the congestion of arc a with value c
void	setFlow(Arc cable, Arc request, Double flow) set flow on a cable for one request.
void	setFlowAllocated(Arc a, Double f) set the flow on arc a with value f
void	writeSolution() Write solution on file of Network object

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

costCongestion

public Vector costCongestion

The string which is read on a cable for the congestion.

flowAllocated

public Vector flowAllocated

The string which is read on a cable for the congestion.

congestion

public Vector congestion

The string which is read on a cable for the congestion.

INDEX

public String INDEX

The string which is used as index on a cable.

REQUEST_SIZE

public String REQUEST_SIZE

The string which is read on a request for the size of request.

CAPACITY_STRING_VALUE

public String CAPACITY_STRING_VALUE

String which is read on arc for the capacity.

EPSILON

public static double EPSILON

The epsilon when diverting the flow.

EPSILON_END

public static double EPSILON_END

The epsilon to finish the resolution.

CONGESTION_MAX

public double CONGESTION_MAX

The CONGESTION_MAX represent the maximun congestionq of the network.

W

public int W

Number of wavelength per fiber.

nbArc

public int nbArc

Number of cables

nbRequest

public int nbRequest

Number of requests

Constructor Detail

ApproxMinCostFlow

public ApproxMinCostFlow(WDMNetwork n)

Constructor.

Parameters:

n - WDMNetwork representing the network.

Method Detail

setFlow

public void setFlow(Arc cable,
                    Arc request,
                    Double flow)

set flow on a cable for one request.

Parameters:

cable - the Arc representing the cable where change the flow.

request - the Arc representing the request where divert the flow.

flow - the Double representing the flow of cable for request.

getFlow

public Double getFlow(Arc cable,
                      Arc request)

Return the flow allocated at cable for request.

Parameters:

cable - the Arc representing a cable of the problem.

request - the Arc representing a request of the problem.

Returns:

the flow allocated at cable for request.

addFlow

public void addFlow(Arc cable,
                    Arc request,
                    Double addFlow)

add flow on a cable for one request.

Parameters:

cable - the Arc representing a cable of the problem.

request - the Arc representing a request of the problem.

addFlow - the Double representing the adding flow of cable for request.

printFlow

public void printFlow()

print the flow of all arc for all requests

writeSolution

public void writeSolution()

Write solution on file of Network object

getFlowAllocated

public Double getFlowAllocated(Arc a)

return the flow on arc a

Parameters:

a - the Arc representing a cable of the problem.

Returns:

a Double which is the value of flow on arc a

setFlowAllocated

public void setFlowAllocated(Arc a,
                             Double f)

set the flow on arc a with value f

Parameters:

a - the Arc representing a cable of the problem.

f - the Double representing the Double value of the flow on a

getCongestion

public Double getCongestion(Arc a)

return the congestion of arc a

Parameters:

a - the Arc representing a cable of the problem.

Returns:

a Double which is the value of congestion of arc a

setCongestion

public void setCongestion(Arc a,
                          Double c)

set the congestion of arc a with value c

Parameters:

a - the Arc representing a cable of the problem.

c - the Double representing the Double value of the congestion of a

deCongestFlow

public void deCongestFlow()

Decongest the network while the capacity constraints are satisfaying. to within about EPSILON. The order of request is a random order.

deCongest

public int deCongest()

Decongest the network while the capacity constraints are satisfaying. The order of request is a random order.