agape.algos

Class MinDFVS<V,E>

java.lang.Object

agape.algos.Algorithms<V,E>

agape.algos.MinDFVS<V,E>

Type Parameters:

V - Vertices type

E - Edges type

public class MinDFVS<V,E>
extends Algorithms<V,E>

This class is dedicated to the minimum directed feedback vertex set. This problem consists in finding the minimum number of vertices to delete in order to get a directed acyclic graph from a directed graph.

Author:

V. Levorato, J.-F. Lalande, P. Berthome

Constructor Summary

Constructors

Constructor and Description
MinDFVS(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<E> edgeFactory)

Method Summary

Methods

Modifier and Type	Method and Description
java.util.Set<java.util.ArrayList<V>>	enumAllCircuitsTarjan(edu.uci.ics.jung.graph.Graph<V,E> G) Enumerate all the elementary circuits of a directed graph.
java.util.Set<V>	greedyMinFVS(edu.uci.ics.jung.graph.Graph<V,E> G) This method gives an approximation of the FVS problem using Big Degree heuristic.
java.util.Set<V>	maximumDirectedAcyclicSubset(edu.uci.ics.jung.graph.Graph<V,E> Ginit) Return the Maximum Directed Acyclic Subset of G.
java.util.Set<V>	minimumFeedbackVertexSet(edu.uci.ics.jung.graph.Graph<V,E> G) Computes the minimum directed acyclic subset of the graph G.

Methods inherited from class agape.algos.Algorithms

getEdgeFactory, getGraphFactory, getVertexFactory, setEdgeFactoy, setGraphFactoy, setVertexFactoy

Methods inherited from class java.lang.Object

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

Constructor Detail

MinDFVS

public MinDFVS(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
       org.apache.commons.collections15.Factory<E> edgeFactory)

Method Detail

enumAllCircuitsTarjan

public java.util.Set<java.util.ArrayList<V>> enumAllCircuitsTarjan(edu.uci.ics.jung.graph.Graph<V,E> G)

Enumerate all the elementary circuits of a directed graph. The method is based on R. Tarjan paper "Enumeration of the elementary circuits of a directed graph" (1973)

Parameters:

G - graph

Returns:

return a set of lists where a list corresponds to a path.

greedyMinFVS

public java.util.Set<V> greedyMinFVS(edu.uci.ics.jung.graph.Graph<V,E> G)

This method gives an approximation of the FVS problem using Big Degree heuristic.

Parameters:

G - graph

Returns:

approximative size of a FVS in G

maximumDirectedAcyclicSubset

public java.util.Set<V> maximumDirectedAcyclicSubset(edu.uci.ics.jung.graph.Graph<V,E> Ginit)

Return the Maximum Directed Acyclic Subset of G. This method is based on the Razgon work ("Computing Minimum Directed Feedback Vertex Set in O*(1.9977^n)" 2007). The algorithm solves the problem in time O(1.9977^n). The complement of the solution gives a directed FVS. It uses kernelization techniques presented in "A 4k2 kernel for feedback vertex set" by Thomassé 2010.

Parameters:

Ginit - graph

Returns:

a Maximum Directed Acyclic Subset of G.

minimumFeedbackVertexSet

public java.util.Set<V> minimumFeedbackVertexSet(edu.uci.ics.jung.graph.Graph<V,E> G)

Computes the minimum directed acyclic subset of the graph G. Uses the maximumDirectedAcyclicSubset method.

Parameters:

G - graph

Returns:

the minimum directed acyclic subset of G

See Also:

maximumDirectedAcyclicSubset(edu.uci.ics.jung.graph.Graph<V, E>)