Package de.uni_mannheim.informatik.dws.melt.matching_jena_matchers.util.graph

Class CycleRemoval<T extends Comparable<T>>

java.lang.Object

de.uni_mannheim.informatik.dws.melt.matching_jena_matchers.util.graph.CycleRemoval<T>

Type Parameters:

T - The type of node

public class CycleRemoval<T extends Comparable<T>>
extends Object

This class removes cycles based on the Agony algorithm.

Field Summary

Fields

Modifier and Type	Field	Description
private final Function<Map<T,Set<T>>,List<List<T>>>	cycleDetection
private final Map<T,Set<T>>	graph

Constructor Summary

Constructors

Constructor	Description
CycleRemoval()
CycleRemoval(Map<T,Set<T>> graph)
CycleRemoval(Map<T,Set<T>> graph, Function<Map<T,Set<T>>,List<List<T>>> cycleDetection)	Constructor which accepts the graph and a function which computes cycles.
CycleRemoval(Map<T,Set<T>> graph, List<List<T>> precomputedCycles)	Constructor which accepts the graph and precomputed cycles.

Method Summary

Modifier and Type	Method	Description
void	addEdge(T source, T target)
private void	findEdgeToBeRemoved(List<T> cycle, Set<Map.Entry<T,T>> edgesToBeRemoved, Map<T,Integer> rankPerNode)
Map<T,Set<T>>	getCycleFreeGraph()
Set<Map.Entry<T,T>>	getEdgesToBeRemoved()
private int	getRankDiff(Map.Entry<T,T> edge, Map<T,Integer> rankPerNode)
void	removeEdge(T source, T target)

Methods inherited from class java.lang.Object

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

Field Details

graph

private final Map<T extends Comparable<T>,Set<T extends Comparable<T>>> graph

cycleDetection

private final Function<Map<T extends Comparable<T>,Set<T extends Comparable<T>>>,List<List<T extends Comparable<T>>>> cycleDetection

Constructor Details

CycleRemoval

public CycleRemoval(Map<T,Set<T>> graph,
 List<List<T>> precomputedCycles)

Constructor which accepts the graph and precomputed cycles. Important: Use this only when no edges are added or removed (via addEdge and removeEdge).

Parameters:

graph - the graph

precomputedCycles - the precomputed cycles.

CycleRemoval

public CycleRemoval(Map<T,Set<T>> graph,
 Function<Map<T,Set<T>>,List<List<T>>> cycleDetection)

Constructor which accepts the graph and a function which computes cycles. This can be CycleDetection or jgrapht algorithms.

Parameters:

graph - the representation of the graph

cycleDetection - a function which expects a graph and compute cycles in them.

CycleRemoval

public CycleRemoval(Map<T,Set<T>> graph)

CycleRemoval

public CycleRemoval()

Method Details

addEdge

public void addEdge(T source,
 T target)

removeEdge

public void removeEdge(T source,
 T target)

getEdgesToBeRemoved

public Set<Map.Entry<T,T>> getEdgesToBeRemoved()

findEdgeToBeRemoved

private void findEdgeToBeRemoved(List<T> cycle,
 Set<Map.Entry<T,T>> edgesToBeRemoved,
 Map<T,Integer> rankPerNode)

getRankDiff

private int getRankDiff(Map.Entry<T,T> edge,
 Map<T,Integer> rankPerNode)

getCycleFreeGraph

public Map<T,Set<T>> getCycleFreeGraph()