Class enabling fast retrieval of simplicial, quasi and almost simplicial nodes. More...

#include <simplicialSet.h>

Collaboration diagram for gum::SimplicialSet:

Public Member Functions
Constructors / Destructors
	SimplicialSet (UndiGraph graph, const NodeProperty< double > log_domain_sizes, NodeProperty< double > *log_weights, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	constructor. initializes the simplicial set w.r.t. a given graph
	SimplicialSet (const SimplicialSet &simplicial_from, UndiGraph graph, const NodeProperty< double > log_domain_sizes, NodeProperty< double > *log_weights, bool avoid_check=false)
	copy constructor
	SimplicialSet (SimplicialSet &&from)
	move constructor
	~SimplicialSet ()
	destructor
Accessors / Modifiers
void	makeClique (const NodeId id)
	adds the necessary edges so that node 'id' and its neighbors form a clique
void	eraseClique (const NodeId id)
	removes a node and its adjacent edges from the underlying graph
void	eraseNode (const NodeId id)
	removes a node and its adjacent edges from the underlying graph
void	eraseEdge (const Edge &edge)
	removes an edge from the graph and recomputes the simplicial set
void	addEdge (NodeId first, NodeId second)
	adds a new edge to the graph and recomputes the simplicial set
bool	isSimplicial (const NodeId id)
	indicates whether a given node is a simplicial node
bool	hasSimplicialNode ()
	indicates whether there exists a simplicial node
bool	hasAlmostSimplicialNode ()
	indicates whether there exists an almost simplicial node
bool	hasQuasiSimplicialNode ()
	indicates whether there exists a quasi simplicial node
NodeId	bestSimplicialNode ()
	returns the simplicial node with the lowest clique weight
const PriorityQueue< NodeId, double > &	allSimplicialNodes ()
	returns all the simplicial nodes
NodeId	bestAlmostSimplicialNode ()
	gets the almost simplicial node with the lowest clique weight
const PriorityQueue< NodeId, double > &	allAlmostSimplicialNodes ()
	returns all the almost simplicial nodes
NodeId	bestQuasiSimplicialNode ()
	gets a quasi simplicial node with the lowest clique weight
const PriorityQueue< NodeId, double > &	allQuasiSimplicialNodes ()
	returns all the quasi simplicial nodes
void	setFillIns (bool on_off)
	sets/unset the fill-ins storage in the standard triangulation procedure
const EdgeSet &	fillIns () const
	returns the set of all the fill-ins added to the graph so far
void	setGraph (UndiGraph graph, const NodeProperty< double > log_domain_sizes, NodeProperty< double > *log_weights, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	initialize the simplicial set w.r.t. a new graph
void	replaceLogWeights (NodeProperty< double > old_weigths, NodeProperty< double > new_weights)
	reassigns a new set of cliques' log weights (with the same content)

Private Types
enum class	_Belong_ : char { SIMPLICIAL , ALMOST_SIMPLICIAL , QUASI_SIMPLICIAL , NO_LIST }
	indicates for each node to which list (simplicial, almost simplicial, quasi simplicial) it belongs More...

Private Member Functions
void	_updateList_ (const NodeId id)
	put node id in the correct simplicial/almost simplicial/quasi simplicial list
void	_updateAllNodes_ ()
	put all the nodes in their appropriate list
void	_initialize_ ()
	initialize: compute nb_triangles, nb_adjacent_neighbors, etc when a new graph is set
SimplicialSet &	operator= (const SimplicialSet &)
	prevent a copy operator to be used
	SimplicialSet (const SimplicialSet &)
	prevent the default copy constructor

Private Attributes
UndiGraph *	_graph_
	the graph on which we perform the simplicial computations
NodeProperty< double > *	_log_weights_
	the weights of the nodes (i.e., weight of their clique)
const NodeProperty< double > *	_log_domain_sizes_
	the log of the modalities of the nodes
PriorityQueue< NodeId, double >	_simplicial_nodes_
	a queue of the simplicial nodes ordered by increasing node weight
PriorityQueue< NodeId, double >	_almost_simplicial_nodes_
	a queue of the almost simplicial nodes ordered by increasing node weight
PriorityQueue< NodeId, double >	_quasi_simplicial_nodes_
	a queue of the quasi simplicial nodes ordered by increasing node weight
NodeProperty< _Belong_ >	_containing_list_
EdgeProperty< Size >	_nb_triangles_
	for each edge, keep track of the number of triangles passing through this egde
NodeProperty< Size >	_nb_adjacent_neighbours_
	for each node, the number of pairs of adjacent neighbours
double	_log_tree_width_
	the current (induced) tree width
double	_quasi_ratio_
	for a given node, if the number of pairs of neighbors that are adjacent / the number of adjacent neighbors in a clique is greater than the quasi ratio, then the node should belong the quasi simplicial list
double	_log_threshold_
	quasi and almost simplicial nodes may not be eliminated unless their weight is lower than (1 + threshold) * tree_width
NodeSet	_changed_status_
	the set of nodes that have tensorly changed of status
bool	_we_want_fill_ins_ {false}
	a boolean indicating if we want fill-ins list with the standard triangulation method
EdgeSet	_fill_ins_list_
	fill-ins list

Detailed Description

Class enabling fast retrieval of simplicial, quasi and almost simplicial nodes.

Definition at line 79 of file simplicialSet.h.

Member Enumeration Documentation

◆ _Belong_

enum class gum::SimplicialSet::_Belong_ : char

strongprivate

indicates for each node to which list (simplicial, almost simplicial, quasi simplicial) it belongs

Enumerator
SIMPLICIAL
ALMOST_SIMPLICIAL
QUASI_SIMPLICIAL
NO_LIST

Definition at line 340 of file simplicialSet.h.

340: char { SIMPLICIAL, ALMOST_SIMPLICIAL, QUASI_SIMPLICIAL, NO_LIST };

Constructor & Destructor Documentation

◆ SimplicialSet() [1/4]

gum::SimplicialSet::SimplicialSet	(	UndiGraph *	graph,
		const NodeProperty< double > *	log_domain_sizes,
		NodeProperty< double > *	log_weights,
		double	theRatio = GUM_QUASI_RATIO,
		double	theThreshold = GUM_WEIGHT_THRESHOLD )

explicit

constructor. initializes the simplicial set w.r.t. a given graph

creates a class for managing the simplicial sets of a given undirected graph. When we add or remove nodes or edges within this undirected graph, the simplicial set updates its list of simplicial, almost simplicial and quasi simplicial sets. Recall that a node is simplicial if, along with its neighbors, it forms a clique. A node X is almost simplicial if it has a neighbor, say Y, such that, after removing Y, X and its neighbors form a clique.

Parameters

graph	The undirected graph the simplicial sets of which we are interested in.
log_domain_sizes	The logarithm of the domain sizes of the nodes/variables. This is used for two different reasons: i) it enables to retrieve the simplicial nodes that have the smallest domain size (useful for triangulations); and ii) it enables to compute and update the log-weight of the cliques containing the nodes (the log-weight of a clique is the sum of the log_domain_sizes of its nodes).
log_weights	The logarithm of the weights of cliques.
theRatio	Let L be the number of edges between neighbors of a given node and let L' be the number of all the possible edges between these neighbors (n * (n+1) / 2). If L/L' >= theRatio, then we consider that the node and its neighbors quasi form a clique and, hence is a quasi-simplicial node.
theThreshold	for a safe triangulation (see Bodlaender), almost and quasi-simplicial nodes should not be eliminated, unless their weight is lower than the highest weight of the cliques created so far. Here, we consider it safe if the weight of a new clique is lower than (1+theThreshold) * this highest weight. This enables flexibility.

Warning: Note that, by the aGrUM's constructor parameter's rule, the fact that an argument is passed as a pointer means that it is not copied within the SimplicialSet, but rather it is only referenced within it.

Exceptions

OperationNotAllowed exception is thrown if the graph, the log_modalities or the log_weights are null pointers.

Warning: Note that we allow log_domain_sizes to be defined over nodes/variables that do not belong to graph. These sizes will simply be ignored. However, it is compulsory that all the nodes of graph belong to log_domain_sizes.

References GUM_QUASI_RATIO, and GUM_WEIGHT_THRESHOLD.

Referenced by SimplicialSet(), SimplicialSet(), SimplicialSet(), and operator=().

Here is the caller graph for this function:

◆ SimplicialSet() [2/4]

gum::SimplicialSet::SimplicialSet	(	const SimplicialSet &	simplicial_from,
		UndiGraph *	graph,
		const NodeProperty< double > *	log_domain_sizes,
		NodeProperty< double > *	log_weights,
		bool	avoid_check = false )

copy constructor

The constructor tries to make a copy of simplicial_from. In addition, it requires a graph that is a perfect copy of that of simplicial_from, as well as perfect copies of the log domain sizes and weights of simplicial_from. This requirement is necessary to avoid a mess: as the graph, the log domain sizes and the log weights are the only data that are not copied into the SimplicialSet, creating a copy of simplicial_from without using, say, a new graph would result in the new SimplicialSet asserting that some nodes are simplicial while they are not because the graph has been changed by simplicial_from. With these new copies, this kind of case cannot occur.

Parameters

simplicial_from	the simplicial set we wish to copy
graph	The undirected graph the simplicial sets of which we are interested in. It should be identical to that used by simplicial_from.
log_domain_sizes	The logarithm of the domain sizes of the nodes/variabless. This is used for two different reasons: i) it enables to retrieve the simplicial nodes that have the smallest domain sizes (useful for triangulations); and ii) it enables to compute and update the log-weight of the cliques containing the nodes (the log-weight of a clique is the sum of the log_domain_sizes of its nodes). log_domain_sizes should be identical to that used by simplicial_from.
log_weights	The logarithm of the weights of the cliques.
avoid_check	if this Boolean is set to true, the SimplicialSet will not check whether the graph, the log_domain_sizes and the log_weights are OK. It will simply assume that everything is OK. Never use this unless you know what you do: setting avoid_check to true results in a faster constructor but can also lead to a mess that is quite complicated to fix.

Warning: Note that, by the aGrUM's constructor parameter's rule, the fact that an argument is passed as a pointer means that it is not copied within the SimplicialSet, but rather it is only referenced within it.; Note that we allow log_domain_sizes to be defined over nodes/variables that do not belong to graph. These sizes will simply be ignored. However, it is compulsory that all the nodes of graph belong to log_domain_sizes.

Exceptions

OperationNotAllowed exception is thrown if the graph, the log_domain_sizes or the log_weights are null pointers, or if these data are different from those stored into simplicial_from

References SimplicialSet().

Here is the call graph for this function:

◆ SimplicialSet() [3/4]

gum::SimplicialSet::SimplicialSet ( SimplicialSet && from )

move constructor

References SimplicialSet().

Here is the call graph for this function:

◆ ~SimplicialSet()

gum::SimplicialSet::~SimplicialSet ( )

destructor

◆ SimplicialSet() [4/4]

gum::SimplicialSet::SimplicialSet ( const SimplicialSet & )

private

prevent the default copy constructor

If we did not prevent this operator to be used, we would be in a mess since the graph, the domain sizes and the weights would be shared and updated by several Simplicial sets whereas the number of triangles and the number of joined neighbors would not be shared.

References SimplicialSet().

Here is the call graph for this function:

Member Function Documentation

◆ _initialize_()

void gum::SimplicialSet::_initialize_ ( )

private

initialize: compute nb_triangles, nb_adjacent_neighbors, etc when a new graph is set

This method initializes the log_weights, the number of triangles and the number of adjacent neighbors given the current graph. This is to be used in constructors and method setGraph

◆ _updateAllNodes_()

void gum::SimplicialSet::_updateAllNodes_ ( )

private

put all the nodes in their appropriate list

◆ _updateList_()

void gum::SimplicialSet::_updateList_ ( const NodeId id )

private

put node id in the correct simplicial/almost simplicial/quasi simplicial list

◆ addEdge()

void gum::SimplicialSet::addEdge	(	NodeId	first,
		NodeId	second )

adds a new edge to the graph and recomputes the simplicial set

Parameters

first	the id of one extremal node of the new inserted edge
second	the id of the other extremal node of the new inserted edge

Warning: if the edge already exists, nothing is done. In particular, no exception is raised.

Exceptions

InvalidNode if first and/or second do not belong to the graph nodes

◆ allAlmostSimplicialNodes()

const PriorityQueue< NodeId, double > & gum::SimplicialSet::allAlmostSimplicialNodes ( )

returns all the almost simplicial nodes

In the priority queue returned, the doubles correspond to the log-weight of the cliques formed by the nodes and their neighbors.

◆ allQuasiSimplicialNodes()

const PriorityQueue< NodeId, double > & gum::SimplicialSet::allQuasiSimplicialNodes ( )

returns all the quasi simplicial nodes

In the priority queue returned, the doubles correspond to the weight of cliques formed by the nodes and their neighbors.

◆ allSimplicialNodes()

const PriorityQueue< NodeId, double > & gum::SimplicialSet::allSimplicialNodes ( )

returns all the simplicial nodes

In the priority queue returned, the doubles correspond to the log-weight of the cliques the nodes belong to.

◆ bestAlmostSimplicialNode()

NodeId gum::SimplicialSet::bestAlmostSimplicialNode ( )

gets the almost simplicial node with the lowest clique weight

◆ bestQuasiSimplicialNode()

NodeId gum::SimplicialSet::bestQuasiSimplicialNode ( )

gets a quasi simplicial node with the lowest clique weight

◆ bestSimplicialNode()

NodeId gum::SimplicialSet::bestSimplicialNode ( )

returns the simplicial node with the lowest clique weight

A simplicial node is a node such that the latter and its neighbors form a clique.

◆ eraseClique()

void gum::SimplicialSet::eraseClique ( const NodeId id )

removes a node and its adjacent edges from the underlying graph

The node should form a clique with its neighbors.

Parameters

id	the id of the node which, along with its neighbors, forms the clique that will be removed

Exceptions

NotFound exception is thrown if the node cannot be found in the graph or if it is not a clique.

◆ eraseEdge()

void gum::SimplicialSet::eraseEdge ( const Edge & edge )

removes an edge from the graph and recomputes the simplicial set

Parameters

edge	the edge to be removed

Warning: if the edge does not exist, nothing is done. In particular, no exception is thrown.

◆ eraseNode()

void gum::SimplicialSet::eraseNode ( const NodeId id )

removes a node and its adjacent edges from the underlying graph

Parameters

id	the id of the node which, along with its adjacent edges, will be removed

Exceptions

NotFound exception is thrown if the node cannot be found in the graph.

◆ fillIns()

const EdgeSet & gum::SimplicialSet::fillIns ( ) const

returns the set of all the fill-ins added to the graph so far

◆ hasAlmostSimplicialNode()

bool gum::SimplicialSet::hasAlmostSimplicialNode ( )

indicates whether there exists an almost simplicial node

◆ hasQuasiSimplicialNode()

bool gum::SimplicialSet::hasQuasiSimplicialNode ( )

indicates whether there exists a quasi simplicial node

◆ hasSimplicialNode()

bool gum::SimplicialSet::hasSimplicialNode ( )

indicates whether there exists a simplicial node

A simplicial node is a node such that the latter and its neighbors form a clique.

◆ isSimplicial()

bool gum::SimplicialSet::isSimplicial ( const NodeId id )

indicates whether a given node is a simplicial node

A simplicial node is a node such that the latter and its neighbors form a clique.

Parameters

id	the ID of the node the simpliciality of which we test

◆ makeClique()

void gum::SimplicialSet::makeClique ( const NodeId id )

adds the necessary edges so that node 'id' and its neighbors form a clique

Parameters

id	the node which will form, with its neighbors, a clique

◆ operator=()

SimplicialSet & gum::SimplicialSet::operator= ( const SimplicialSet & )

private

prevent a copy operator to be used

If we did not prevent this operator to be used, we would be in a mess since the graph, the modalities and the weights would be shared and updated by several Simplicial sets whereas the number of triangles and the number of joined neighbors would not be shared.

References SimplicialSet().

Here is the call graph for this function:

◆ replaceLogWeights()

void gum::SimplicialSet::replaceLogWeights	(	NodeProperty< double > *	old_weigths,
		NodeProperty< double > *	new_weights )

reassigns a new set of cliques' log weights (with the same content)

This method is useful for move constructors in elimination sequences.

Exceptions

InvalidArgument is raised if the old_weights argument is different from the current log_weights pointer.

◆ setFillIns()

void gum::SimplicialSet::setFillIns ( bool on_off )

sets/unset the fill-ins storage in the standard triangulation procedure

Parameters

on_off when true means that the SimplicialSet will compute the fill-ins added to the graph. When on_off is false, the fill-ins are not computed. Note that, to produce a correct result, you should call setFillIns before any modification to the graph.

◆ setGraph()

void gum::SimplicialSet::setGraph	(	UndiGraph *	graph,
		const NodeProperty< double > *	log_domain_sizes,
		NodeProperty< double > *	log_weights,
		double	theRatio = GUM_QUASI_RATIO,
		double	theThreshold = GUM_WEIGHT_THRESHOLD )

initialize the simplicial set w.r.t. a new graph

Parameters

graph	The undirected graph the simplicial sets of which we are interested in.
log_domain_sizes	The logarithm of the domain sizes of the nodes/variables. This is used for two different reasons: i) it enables to retrieve the simplicial nodes that have the smallest domain sizes (useful for triangulations); and ii) it enables to compute and update the log-weight of the cliques containing the nodes (the log-weight of a clique is the sum of the log_domain_sizes of its nodes).
log_weights	The logarithm of the weights of the cliques.
theRatio	Let L be the number of edges between neighbors of a given node and let L' be the number of all the possible edges between these neighbors (n * (n+1) / 2). If L/L' >= theRatio, then we consider that the node and its neighbors quasi form a clique and, hence is a quasi-simplicial node.
theThreshold	for a safe triangulation (see Bodlaender), almost and quasi-simplicial nodes should not be eliminated, unless their weight is lower than the highest weight of the cliques created so far. Here, we consider it safe if the weight of a new clique is lower than (1+theThreshold) * this highest weight. This enables flexibility.

Warning: Note that we allow log_domain_sizes to be defined over nodes/variables that do not belong to graph. These sizes will simply be ignored. However, it is compulsory that all the nodes of graph belong to log_domain_sizes.; Note that, by the aGrUM's constructor parameter's rule, the fact that an argument is passed as a pointer means that it is not copied within the SimplicialSet, but rather it is only referenced within it.

References GUM_QUASI_RATIO, and GUM_WEIGHT_THRESHOLD.

Member Data Documentation

◆ _almost_simplicial_nodes_

PriorityQueue< NodeId, double > gum::SimplicialSet::_almost_simplicial_nodes_

private

a queue of the almost simplicial nodes ordered by increasing node weight

Definition at line 333 of file simplicialSet.h.

◆ _changed_status_

NodeSet gum::SimplicialSet::_changed_status_

private

the set of nodes that have tensorly changed of status

Definition at line 370 of file simplicialSet.h.

◆ _containing_list_

NodeProperty< _Belong_ > gum::SimplicialSet::_containing_list_

private

Definition at line 341 of file simplicialSet.h.

◆ _fill_ins_list_

EdgeSet gum::SimplicialSet::_fill_ins_list_

private

fill-ins list

Definition at line 377 of file simplicialSet.h.

◆ _graph_

UndiGraph* gum::SimplicialSet::_graph_

private

the graph on which we perform the simplicial computations

Definition at line 321 of file simplicialSet.h.

◆ _log_domain_sizes_

const NodeProperty< double >* gum::SimplicialSet::_log_domain_sizes_

private

the log of the modalities of the nodes

Definition at line 327 of file simplicialSet.h.

◆ _log_threshold_

double gum::SimplicialSet::_log_threshold_

private

quasi and almost simplicial nodes may not be eliminated unless their weight is lower than (1 + threshold) * tree_width

Definition at line 367 of file simplicialSet.h.

◆ _log_tree_width_

double gum::SimplicialSet::_log_tree_width_

private

the current (induced) tree width

Warning: Note that what we call tree width here is not the classical definition, i.e., the number of nodes in the largest clique, as this is not, to our mind, what is important for computations: what is important is the size of the tables that would be stored into the cliques, i.e., the product of the modalities of the nodes/variables contained in the cliques

Definition at line 358 of file simplicialSet.h.

◆ _log_weights_

NodeProperty< double >* gum::SimplicialSet::_log_weights_

private

the weights of the nodes (i.e., weight of their clique)

Definition at line 324 of file simplicialSet.h.

◆ _nb_adjacent_neighbours_

NodeProperty< Size > gum::SimplicialSet::_nb_adjacent_neighbours_

private

for each node, the number of pairs of adjacent neighbours

Definition at line 348 of file simplicialSet.h.

◆ _nb_triangles_

EdgeProperty< Size > gum::SimplicialSet::_nb_triangles_

private

for each edge, keep track of the number of triangles passing through this egde

Definition at line 345 of file simplicialSet.h.

◆ _quasi_ratio_

double gum::SimplicialSet::_quasi_ratio_

private

for a given node, if the number of pairs of neighbors that are adjacent / the number of adjacent neighbors in a clique is greater than the quasi ratio, then the node should belong the quasi simplicial list

Definition at line 363 of file simplicialSet.h.

◆ _quasi_simplicial_nodes_

PriorityQueue< NodeId, double > gum::SimplicialSet::_quasi_simplicial_nodes_

private

a queue of the quasi simplicial nodes ordered by increasing node weight

Definition at line 336 of file simplicialSet.h.

◆ _simplicial_nodes_

PriorityQueue< NodeId, double > gum::SimplicialSet::_simplicial_nodes_

private

a queue of the simplicial nodes ordered by increasing node weight

Definition at line 330 of file simplicialSet.h.

◆ _we_want_fill_ins_

bool gum::SimplicialSet::_we_want_fill_ins_ {false}

private

a boolean indicating if we want fill-ins list with the standard triangulation method

Definition at line 374 of file simplicialSet.h.

374{false};

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

agrum/base/graphs/algorithms/simplicialSet.h

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ _Belong_

Constructor & Destructor Documentation

◆ SimplicialSet() [1/4]

◆ SimplicialSet() [2/4]

◆ SimplicialSet() [3/4]

◆ ~SimplicialSet()

◆ SimplicialSet() [4/4]

Member Function Documentation

◆ _initialize_()

◆ _updateAllNodes_()

◆ _updateList_()

◆ addEdge()

◆ allAlmostSimplicialNodes()

◆ allQuasiSimplicialNodes()

◆ allSimplicialNodes()

◆ bestAlmostSimplicialNode()

◆ bestQuasiSimplicialNode()

◆ bestSimplicialNode()

◆ eraseClique()

◆ eraseEdge()

◆ eraseNode()

◆ fillIns()

◆ hasAlmostSimplicialNode()

◆ hasQuasiSimplicialNode()

◆ hasSimplicialNode()

◆ isSimplicial()

◆ makeClique()

◆ operator=()

◆ replaceLogWeights()

◆ setFillIns()

◆ setGraph()

Member Data Documentation

◆ _almost_simplicial_nodes_

◆ _changed_status_

◆ _containing_list_

◆ _fill_ins_list_

◆ _graph_

◆ _log_domain_sizes_

◆ _log_threshold_

◆ _log_tree_width_

◆ _log_weights_

◆ _nb_adjacent_neighbours_

◆ _nb_triangles_

◆ _quasi_ratio_

◆ _quasi_simplicial_nodes_

◆ _simplicial_nodes_

◆ _we_want_fill_ins_