fr.inria.opengve.bridge.algorithms.common
Class FindElementaryCycles<V,E extends Link<V>,G extends Graph<V,E>>

java.lang.Object
  fr.inria.opengve.bridge.algorithms.common.FindElementaryCycles<V,E,G>

public abstract class FindElementaryCycles<V,E extends Link<V>,G extends Graph<V,E>>
extends java.lang.Object

This algorithms compute all the elementary cycles on a graph. Note that the graph can be oriented or not. The graph must be connected. The algorithms can be found in "Mesh-based Survivable Networks" by Wayne D.Grover.

Author:

fabrice.peix@sophia.inria.fr

Constructor Summary

FindElementaryCycles(G g, AbstractScalar maxCost)
This Constructor initialize algorithms with a cost of one on each edges.

FindElementaryCycles(G g, Map edgeCost, AbstractScalar maxCost)
Constructor.

Method Summary

protected abstract CopyGraph<V,E,G>	createCopyGraph() Create a new copy tool.
protected abstract FindElementaryCyclesFrom<V,E,G>	createFindElementaryCyclesFrom(G g, V root, Map edgeCost, AbstractScalar maxCost) Create a new object of type FindElementaryCyclesFrom.
java.util.HashSet<Cycle<V,E>>	getSolution() Give the set of cycles in graph g.
void	run() Compute all the elementary cycles of graph.
void	setEdgeCostContext(java.lang.Object context) Change the context used to access cost of edges in the Map cost.
void	setEdgeCostName(java.lang.String name) Change the name used to access cost of edge in the Map cost.

Methods inherited from class java.lang.Object

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

Constructor Detail

FindElementaryCycles

public FindElementaryCycles(G g,
                            Map edgeCost,
                            AbstractScalar maxCost)

Constructor.

Parameters:

g - The graph on which we search cycles.

edgeCost - A map containing association of edge with AbstractScalar representing the cost of the edge.

maxCost - The maximun cost of the computed cycles.

FindElementaryCycles

public FindElementaryCycles(G g,
                            AbstractScalar maxCost)

This Constructor initialize algorithms with a cost of one on each edges.

Parameters:

g - The graph on which we search cycles.

maxCost - The maximun length cycles.

Method Detail

createCopyGraph

protected abstract CopyGraph<V,E,G> createCopyGraph()

Create a new copy tool.

Returns:

The newly created copyGraph.

createFindElementaryCyclesFrom

protected abstract FindElementaryCyclesFrom<V,E,G> createFindElementaryCyclesFrom(G g,
                                                                                  V root,
                                                                                  Map edgeCost,
                                                                                  AbstractScalar maxCost)

Create a new object of type FindElementaryCyclesFrom.

Parameters:

g - The graph on which we search cycles.

root - The "root" node of the cycles.

edgeCost - The map containing cost of edges.

maxCost - The maximum cost allowed for cycle.

Returns:

The new created FindElementaryCyclesFrom object.

run

public void run()

Compute all the elementary cycles of graph.

setEdgeCostName

public void setEdgeCostName(java.lang.String name)

Change the name used to access cost of edge in the Map cost.

Parameters:

name - The new name used to access cost of edges.

setEdgeCostContext

public void setEdgeCostContext(java.lang.Object context)

Change the context used to access cost of edges in the Map cost.

Parameters:

context - The new context used to access cost of edge.

getSolution

public java.util.HashSet<Cycle<V,E>> getSolution()

Give the set of cycles in graph g.

Returns:

The set of solution.