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

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

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

This class compute all cycles of a graph containing a specific vertex. The algorithms can be found in "Mesh-based Survivable Networks" by Wayne D.Grover. This class is used in the more general class FindElementaryCycles.

Author:

fabrice.peix@sophia.inria.fr

Constructor Summary

FindElementaryCyclesFrom(G g, V root, AbstractScalar maxLength)
Constructor

FindElementaryCyclesFrom(G g, V root, Map edgeCost, AbstractScalar maxCost)
Constructor.

Method Summary

protected abstract Cycle<V,E>	createCycle(Path<V,E> p, E e) Create a new cycle from a path and the edge closing this path.
protected abstract AbstractScalar	createIntegerScalar(int value) Create a new AbstractScalar of type int.
protected abstract Path<V,E>	createPath() Create a new Path.
java.util.HashSet<Cycle<V,E>>	getCycles() Return the set of cycles containing the given node.
void	run()
void	setEdgeCostContext(java.lang.Object context) Change the context used to access cost of edge 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

FindElementaryCyclesFrom

public FindElementaryCyclesFrom(G g,
                                V root,
                                Map edgeCost,
                                AbstractScalar maxCost)

Constructor.

Parameters:

g - The graph on which we search cycles.

root - The root vertex.

edgeCost - A map giving the cost of each edge.

maxCost - The maximum cost cycle authoized.

FindElementaryCyclesFrom

public FindElementaryCyclesFrom(G g,
                                V root,
                                AbstractScalar maxLength)

Constructor

Parameters:

g - The graph on which we search cycles.

root - The root node used.

maxLength - The maximun length of cycles.

Method Detail

createPath

protected abstract Path<V,E> createPath()

Create a new Path.

Returns:

The newly created path.

createCycle

protected abstract Cycle<V,E> createCycle(Path<V,E> p,
                                          E e)

Create a new cycle from a path and the edge closing this path.

Parameters:

p - The path.

e - The edge closing path p.

Returns:

A new cycle.

createIntegerScalar

protected abstract AbstractScalar createIntegerScalar(int value)

Create a new AbstractScalar of type int.

Parameters:

value - The value of the new integer AbstractScalar.

Returns:

The new create AbstractScalar.

run

public void run()

getCycles

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

Return the set of cycles containing the given node.

Returns:

The set of cycles.

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 edge.

setEdgeCostContext

public void setEdgeCostContext(java.lang.Object context)

Change the context used to access cost of edge in the Map cost. Set context to null for using default context.

Parameters:

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