ca.uqac.lif.ecp.graphs

Class GreedyHypergraphEdgeCover

java.lang.Object

ca.uqac.lif.ecp.graphs.HypergraphEdgeCover

ca.uqac.lif.ecp.graphs.GreedyHypergraphEdgeCover

public class GreedyHypergraphEdgeCover
extends HypergraphEdgeCover

Solves the hypergraph edge cover by a greedy approach. The algorithm simply picks the hyperedge that covers the most remaining vertices.

Author:

Sylvain Hallé

Field Summary

Fields inherited from class ca.uqac.lif.ecp.graphs.HypergraphEdgeCover

m_graph

Constructor Summary

Constructors

Constructor and Description
GreedyHypergraphEdgeCover(Hypergraph g)

Method Summary

Modifier and Type	Method and Description
MathSet<Hypergraph.Hyperedge>	getCover() Gets a covering of the hyperedges
static int	intersect(MathSet<java.lang.Integer> x, MathSet<java.lang.Integer> y) Counts of many elements of x are present in y
HypergraphEdgeCover	newSolver(Hypergraph g) Gets a new, empty instance of this solver

Methods inherited from class java.lang.Object

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

Constructor Detail

GreedyHypergraphEdgeCover

public GreedyHypergraphEdgeCover(Hypergraph g)

Method Detail

getCover

public MathSet<Hypergraph.Hyperedge> getCover()

Description copied from class: HypergraphEdgeCover

Gets a covering of the hyperedges

Specified by:

getCover in class HypergraphEdgeCover

Returns:

The covering

intersect

public static int intersect(MathSet<java.lang.Integer> x,
                            MathSet<java.lang.Integer> y)

Counts of many elements of x are present in y

Parameters:

x - A first set

y - A second set

Returns:

The number

newSolver

public HypergraphEdgeCover newSolver(Hypergraph g)

Description copied from class: HypergraphEdgeCover

Gets a new, empty instance of this solver

Specified by:

newSolver in class HypergraphEdgeCover

Parameters:

g - The hypergraph to solve

Returns:

The solver