Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph. More...

#include <SizeMaxIndepSetAlg.h>

Public Member Functions
void	run (Ideal &ideal)
	Run the algorithm on ideal. More...

mpz_class	getMaxIndepSetSize ()
	Returns the largest size over all independent sets of the hypergraph passed to run. More...

Private Types
enum	VarState { IsMaybeInSet = 0 , IsNotInSet = 1 , IsInSet = 2 }
	Is used for encoding the state of a partially-decided set of nodes/variables in the backtracking algorithm. More...

Private Member Functions
bool	isIndependentIncludingMaybe (size_t pos)
	Returns true if _state is an independent set according to every term in _edges from pos and forward. More...

bool	couldBeDependence (size_t pos, size_t nextPos, size_t &maybeCount)
	Returns true if the term encoded in _edges between pos and nextPos makes or might make the set in _state dependent. More...

void	recurse (size_t pos, size_t excluded)
	The recursive method that implements the algortihm. More...

Private Attributes
size_t	_varCount
	The number of variables in the ideal passed to run. More...

size_t	_minExcluded
	The minimal number of excluded elements in any independent set found so far. More...

vector< VarState >	_state
	The current state of the backtracking algorithm. More...

vector< vector< size_t > >	_undo
	Stores information on how to restore the state of _state after having done backtracking on one possibility. More...

bool	_noIndependentSets
	Is true if there are no independent sets for the argument to run. More...

vector< size_t >	_edges
	Sparse encoding of the parameter to run. More...

size_t	_endPos
	The size of _edges. More...

Detailed Description

Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.

Currently the only functionality is to compute the size of such a set. This amounts to finding the dimension of a monomial ideal, which can be done by taking the radical and then using this algorithm.

The algorithm is a branch-and-bound algorithm lifted from Macaulay 2, though the implementation here is much faster as of July 2009. I don't know why it is so much faster, since it is nearly equivalent to what Macalay 2 does.

The state of the algortihm is a partially-decided set of nodes of the hypergraph, where each node can be definitely in the set, definitely not in the set or undecided. In the beginning every variable is undecided.

The algorithm then scans through the edges. For each edge, it may be that it definitely does not make the current set dependent. If so, we skip past the edge. It may also definitely make the current set dependent. If so, we discard the current set. If it is undecided whether the edge makes the set dependent, we choose some undecided node that makes this happen, and recurse on the possibility where it is not in the set (and so makes the set not dependent according to this edge). When we are done, we then consider the case where the node is definitely in the set, restarting the case-distinctions above.

The bound used is simply the number of definitely excluded nodes. If this is more than or equal to the least number of excluded nodes seen so far, then there is no reason to consider such a set further, since it can lead to no improvement.

Note that in the base case, not every independent set considered is maximal according to inclusion, but since we only consider the size-maximal ones, the ones we care about are maximal with respect to inclusion.

Definition at line 61 of file SizeMaxIndepSetAlg.h.

Member Enumeration Documentation

◆ VarState

enum SizeMaxIndepSetAlg::VarState

private

Is used for encoding the state of a partially-decided set of nodes/variables in the backtracking algorithm.

Enumerator
IsMaybeInSet
IsNotInSet
IsInSet

Definition at line 84 of file SizeMaxIndepSetAlg.h.

Member Function Documentation

◆ couldBeDependence()

bool SizeMaxIndepSetAlg::couldBeDependence	(	size_t	pos,
		size_t	nextPos,
		size_t &	maybeCount
	)

inlineprivate

Returns true if the term encoded in _edges between pos and nextPos makes or might make the set in _state dependent.

If so, maybeCount is set to the number of IsMaybeInSet from _state on the support of that term.

Definition at line 93 of file SizeMaxIndepSetAlg.cpp.

◆ getMaxIndepSetSize()

mpz_class SizeMaxIndepSetAlg::getMaxIndepSetSize ( )

Returns the largest size over all independent sets of the hypergraph passed to run.

Returns varCount + 1 if the hypergraph has no independent sets, which is to say that ideal is generated by the identity. The returned value is undefined if run has not been called first.

Definition at line 67 of file SizeMaxIndepSetAlg.cpp.

◆ isIndependentIncludingMaybe()

bool SizeMaxIndepSetAlg::isIndependentIncludingMaybe ( size_t pos )

private

Returns true if _state is an independent set according to every term in _edges from pos and forward.

Definition at line 78 of file SizeMaxIndepSetAlg.cpp.

◆ recurse()

void SizeMaxIndepSetAlg::recurse	(	size_t	pos,
		size_t	excluded
	)

private

The recursive method that implements the algortihm.

See the description for this class for a description of the algortihm. Pos is the current term, while excluded is the number of definitely excluded elements, and also an index into _undo, which works since it increases by one at each recursive sub-call.

Definition at line 106 of file SizeMaxIndepSetAlg.cpp.

◆ run()

void SizeMaxIndepSetAlg::run ( Ideal & ideal )

Run the algorithm on ideal.

Should work but has not been tested when called more than once on the same object. May rearrange the generators of ideal. ideal must be square free and minimally generated. Thus ideal is the edge ideal of some hypergraph, and it is this hypergraph that the algorithm runs on.

Definition at line 23 of file SizeMaxIndepSetAlg.cpp.

Member Data Documentation

◆ _edges

vector<size_t> SizeMaxIndepSetAlg::_edges

private

Sparse encoding of the parameter to run.

The encoding is that the first entry is the size $n$ of the support of a term/edge, and the next $n$ entries are the variables/nodes that are included in that term. Then the next term follows, encoded in the same way. It is efficient to store all of this in one place to increase locality of reference for the cache.

Definition at line 143 of file SizeMaxIndepSetAlg.h.

◆ _endPos

size_t SizeMaxIndepSetAlg::_endPos

private

The size of _edges.

Stored like this for efficiency.

Definition at line 146 of file SizeMaxIndepSetAlg.h.

◆ _minExcluded

size_t SizeMaxIndepSetAlg::_minExcluded

private

The minimal number of excluded elements in any independent set found so far.

Definition at line 118 of file SizeMaxIndepSetAlg.h.

◆ _noIndependentSets

bool SizeMaxIndepSetAlg::_noIndependentSets

private

Is true if there are no independent sets for the argument to run.

Definition at line 134 of file SizeMaxIndepSetAlg.h.

◆ _state

vector<VarState> SizeMaxIndepSetAlg::_state

private

The current state of the backtracking algorithm.

Recurse changes this as it runs, and then restores the previous value using information stored in _undo.

Definition at line 124 of file SizeMaxIndepSetAlg.h.

◆ _undo

vector<vector<size_t> > SizeMaxIndepSetAlg::_undo

private

Stores information on how to restore the state of _state after having done backtracking on one possibility.

Definition at line 129 of file SizeMaxIndepSetAlg.h.

◆ _varCount

size_t SizeMaxIndepSetAlg::_varCount

private

The number of variables in the ideal passed to run.

I.e. the number of nodes in the hypergraph.

Definition at line 114 of file SizeMaxIndepSetAlg.h.

The documentation for this class was generated from the following files:

src/SizeMaxIndepSetAlg.h
src/SizeMaxIndepSetAlg.cpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ VarState

Member Function Documentation

◆ couldBeDependence()

◆ getMaxIndepSetSize()

◆ isIndependentIncludingMaybe()

◆ recurse()

◆ run()

Member Data Documentation

◆ _edges

◆ _endPos

◆ _minExcluded

◆ _noIndependentSets

◆ _state

◆ _undo

◆ _varCount