mascoptLib.algos.abstractalgos
Class PathGenerator

java.lang.Object
  |
  +--mascoptLib.algos.abstractalgos.PathGenerator

Direct Known Subclasses:

PathBreadthFirstSearch, PathGeneratorRandomWalk

public class PathGenerator

extends Object

Computes main or disjoint paths for a set of request using Dijkstra.

This class computes paths for requests. The requests are contained in a Graph given to the constructor. In option, for each request (an edge of this request graph), the shortest path is computed with Dijkstra. Then, for each edge of this path, we compute an other shortest path on the original Graph without this edge. We obtain a set of path for each request which contains disjoints paths.

Version:

29/07/2002

Author:

jflaland@sophia.inria.fr

Constructor Summary

PathGenerator(mascoptLib.abstractGraph.AbstractGraph g, mascoptLib.abstractGraph.AbstractGraph requests)
Constructs a path generator on a graph for some requests.

Method Summary

void	computeDisjointPathsForGeneratedPaths(boolean protection) We can add some paths generated when removing each edge of the main path.
HashMap	getPaths() Returns paths calculated in a HashMap.
HashSet	getPathsForThisEdge(mascoptLib.abstractGraph.AbstractEdge z) Returns paths for a request z.
void	run() Run the generation of paths.

Methods inherited from class java.lang.Object

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

Constructor Detail

PathGenerator

public PathGenerator(mascoptLib.abstractGraph.AbstractGraph g,
                     mascoptLib.abstractGraph.AbstractGraph requests)

Constructs a path generator on a graph for some requests.

Parameters:

g - the graph

requests - the requests for which we want paths

Method Detail

run

public void run()

Run the generation of paths.

getPaths

public HashMap getPaths()

Returns paths calculated in a HashMap. The hashmap key is the edges of the request graph. The value for each key is a HashSet containing AbstractChain.

Returns:

a hashmap containing path for each request.

getPathsForThisEdge

public HashSet getPathsForThisEdge(mascoptLib.abstractGraph.AbstractEdge z)

Returns paths for a request z. The request is an edge of the request graph.

Parameters:

z - the request

Returns:

a HashSet containing AbstractChain.

computeDisjointPathsForGeneratedPaths

public void computeDisjointPathsForGeneratedPaths(boolean protection)

We can add some paths generated when removing each edge of the main path. You have to provide to the algorithm a 2-connex graph.

Parameters:

protection - true if you want to generate edge-disjoint paths.