A DFSTree is used by gspan to sort lexicographically patterns discovered in an interface graph. More...

#include <agrum/PRM/gspan/DFSTree.h>

Inheritance diagram for gum::prm::gspan::DFSTree< GUM_SCALAR >:

Collaboration diagram for gum::prm::gspan::DFSTree< GUM_SCALAR >:

Classes
struct	PatternData
class	NeighborDegreeSort
	This is used to generate the max_indep_set of a Pattern. More...

Public Member Functions
Constructor and destructor.
	DFSTree (const InterfaceGraph< GUM_SCALAR > &graph, SearchStrategy< GUM_SCALAR > *strategy=0)
	Default constructor.
	~DFSTree () override
	Destructor.
DFSTree getters and setters.
const InterfaceGraph< GUM_SCALAR > &	internalGraph () const
	Returns the list of root patterns in this DFSTree.
std::list< NodeId > &	roots ()
	Returns the list of root patterns in this DFSTree.
const std::list< NodeId > &	roots () const
	Returns the list of root patterns in this DFSTree.
Pattern &	parent (const Pattern &p)
	Returns the parent of p in this DFSTree.
const Pattern &	parent (const Pattern &p) const
	Returns the parent of p in this DFSTree.
std::list< NodeId > &	children (const Pattern &p)
	Returns the list of p children in this DFSTree.
const std::list< NodeId > &	children (const Pattern &p) const
	Returns the list of p children in this DFSTree.
Pattern &	pattern (NodeId id)
	Returns the pattern represented by id in this DFSTree.
const Pattern &	pattern (NodeId id) const
	Returns the pattern represented by id in this DFSTree.
void	addRoot (LabelData &data)
	Add a one edge Pattern in this DFSTree.
Pattern &	growPattern (Pattern &p, EdgeGrowth< GUM_SCALAR > &edge_growth, Size min_freq)
	Add a one edge growth of p as one of its child.
Isomorphisms for patterns in this DFSTree.
UndiGraph &	iso_graph (const Pattern &p)
	Returns the isomorphism graph of p in the interface graph.
Sequence< PRMInstance< GUM_SCALAR > * > &	iso_map (const Pattern &p, NodeId node)
	Given a pattern and a node in its isomorphism graph, this methods returns the sequence of instance matching p in the interface graph.
Set< NodeId > &	max_indep_set (const Pattern &p)
	Returns the maximal independent set of p isomorphism graph.
double	frequency (const Pattern &p) const
	Returns the frequency of p respecting it's maximal independent set.
PatternData &	data (const Pattern &p)
const PatternData &	data (const Pattern &p) const
SearchStrategy< GUM_SCALAR > &	strategy ()
	strategy getter
const SearchStrategy< GUM_SCALAR > &	strategy () const
	strategy getter

Private Types
using	ArcIterator = ArcSetIterator
using	NodeIterator = NodeGraphPartIterator
using	NodeConstIterator = NodeGraphPartIterator
using	NodeIteratorSafe = NodeGraphPartIteratorSafe
using	NodeConstIteratorSafe = NodeGraphPartIteratorSafe

using	node_iterator = NodeGraphPartIterator
	types for STL compliance
using	node_const_iterator = NodeGraphPartIterator
	types for STL compliance
using	node_iterator_safe = NodeGraphPartIteratorSafe
	types for STL compliance
using	node_const_iterator_safe = NodeGraphPartIteratorSafe
	types for STL compliance

Private Member Functions

void _checkGrowth_ (Pattern &p, Pattern *child, EdgeGrowth< GUM_SCALAR > &edge_growth)

Raise different exceptions if child is invalid or illegal.

void _addChild_ (Pattern &p, Pattern *child, EdgeGrowth< GUM_SCALAR > &edge_growth)

Add a child to this DFSTree.

bool _is_new_seq_ (Sequence< PRMInstance< GUM_SCALAR > * > &seq, NodeProperty< Sequence< PRMInstance< GUM_SCALAR > * > * > &iso_map)

Check if an instance match is redundant.

void _initialiaze_root_ (Pattern *p, Sequence< EdgeData< GUM_SCALAR > * > &seq)

This initialize the DSFTree with a new root.

bool _test_equality_ (HashTable< PRMClassElement< GUM_SCALAR > *, Size > &x, HashTable< PRMClassElement< GUM_SCALAR > *, Size > &y)

bool hasDirectedPath (NodeId from, NodeId to) const

checks whether there exists a directed path from from to to

std::optional< std::vector< NodeId > > directedPath (NodeId node1, NodeId node2) const

returns a directed path from node1 to node2, or std::nullopt if none

std::optional< std::vector< NodeId > > directedUnorientedPath (NodeId node1, NodeId node2) const

returns a shortest path from node1 to node2 ignoring arc orientation, or std::nullopt if none

NodeSet ancestors (NodeId id) const

returns the set of all ancestors of id (nodes from which id is reachable)

NodeSet descendants (NodeId id) const

returns the set of all descendants of id (nodes reachable from id)

NodeSet family (NodeId id) const

returns { id } ∪ parents(id)

NodeSet family (const NodeSet &ids) const

returns the union of families of all nodes in ids

NodeProperty< NodeId > connectedComponents () const

returns a property {node:id of weakly connected component}

void eraseSetOfArcs_ (const ArcSet &set)

a (virtualized) function to remove a given set of arcs

void unvirtualizedEraseSetOfArcs_ (const ArcSet &set)

similar to eraseSetOfArcs_ except that it is unvirtualized

void _checkParents_ (NodeId id)

when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entry to parents[id]

void _checkChildren_ (NodeId id)

when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set entry to children[id]

Operators

bool operator== (const DiGraph &g) const

tests whether two DiGraphs are identical (same nodes, same arcs)

Operators

bool operator== (const ArcGraphPart &p) const

tests whether two ArcGraphParts contain the same arcs

Accessors/Modifiers

tests whether two DiGraphs are different

Parameters

g	the DiGraph with which "this" is compared

void addArc (const NodeId tail, const NodeId head) override

insert a new arc into the directed graph

void eraseNode (const NodeId id) override

remove a node and its adjacent arcs from the graph

void clear () override

removes all the nodes and arcs from the graph

std::string toString () const override

to friendly display the content of the graph

virtual std::string toDot () const

to friendly display the content of the graph in the DOT syntax

Sequence< NodeId > topologicalOrder () const

Build and return a topological order.

Accessors/Modifiers

virtual void eraseArc (const Arc &arc)

removes an arc from the ArcGraphPart

bool existsArc (const Arc &arc) const

indicates whether a given arc exists

bool existsArc (NodeId tail, NodeId head) const

indicates whether a given arc exists

bool emptyArcs () const

indicates wether the ArcGraphPart contains any arc

void clearArcs ()

removes all the arcs from the ArcGraphPart

Size sizeArcs () const

indicates the number of arcs stored within the ArcGraphPart

const ArcSet & arcs () const

returns the set of arcs stored within the ArcGraphPart

const NodeSet & parents (NodeId id) const

returns the set of nodes with arc ingoing to a given node

NodeSet parents (const NodeSet &ids) const

returns the set of parents of a set of nodes

NodeSet children (const NodeSet &ids) const

returns the set of nodes which consists in the node and its parents returns the set of children of a set of nodes

const NodeSet & children (NodeId id) const

returns the set of nodes with arc outgoing from a given node

void eraseParents (NodeId id)

erase all the parents of a given node

void unvirtualizedEraseParents (NodeId id)

same function as eraseParents but without any virtual call to an erase

void eraseChildren (NodeId id)

removes all the children of a given node

void unvirtualizedEraseChildren (NodeId id)

same function as eraseChildren but without any virtual call to an erase

template<typename VAL>

ArcProperty< VAL > arcsProperty (VAL(*f)(const Arc &), Size size=0) const

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

template<typename VAL>

ArcProperty< VAL > arcsProperty (const VAL &a, Size size=0) const

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL a)

template<typename VAL>

List< VAL > listMapArcs (VAL(*f)(const Arc &)) const

a method to create a list of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Operators

bool operator== (const NodeGraphPart &p) const

check whether two NodeGraphParts contain the same nodes

Accessors/Modifiers

void populateNodes (const NodeGraphPart &s)

populateNodes clears *this and fills it with the same nodes as "s"

template<typename T>

void populateNodesFromProperty (const NodeProperty< T > &h)

populateNodesFromProperty clears *this and fills it with the keys of "h"

NodeId nextNodeId () const

returns a new node id, not yet used by any node

virtual NodeId addNode ()

insert a new node and return its id

std::vector< NodeId > addNodes (Size n)

insert n nodes

virtual void addNodeWithId (const NodeId id)

try to insert a node with the given id

bool existsNode (const NodeId id) const

returns true iff the NodeGraphPart contains the given nodeId

bool exists (const NodeId id) const

alias for existsNode

bool emptyNodes () const

indicates whether there exists nodes in the NodeGraphPart

bool empty () const

alias for emptyNodes

virtual void clearNodes ()

remove all the nodes from the NodeGraphPart

Size sizeNodes () const

returns the number of nodes in the NodeGraphPart

Size size () const

alias for sizeNodes

NodeId bound () const

returns a number n such that all node ids are strictly lower than n

NodeSet asNodeSet () const

returns a copy of the set of nodes represented by the NodeGraphPart

const NodeGraphPart & nodes () const

return *this as a NodeGraphPart

node_iterator_safe beginSafe () const

a begin iterator to parse the set of nodes contained in the NodeGraphPart

const node_iterator_safe & endSafe () const noexcept

the end iterator to parse the set of nodes contained in the NodeGraphPart

node_iterator begin () const noexcept

a begin iterator to parse the set of nodes contained in the NodeGraphPart

const node_iterator & end () const noexcept

the end iterator to parse the set of nodes contained in the NodeGraphPart

std::string nameFromId (NodeId id) const

returns the name of node id, or "<id>" if no name is set

std::optional< NodeId > idFromName (const std::string &name) const

returns the id of the node with the given name, or std::nullopt

void setName (NodeId id, const std::string &name)

sets the name of node id

bool hasName (NodeId id) const

returns true iff node id has an explicit name

std::string dotNodeLabel (NodeId id) const

returns " [label=\"...\"]" with DOT-escaped name, or "" if no name

template<typename VAL>

NodeProperty< VAL > nodesPropertyFromFunction (VAL(*f)(const NodeId &), Size size=0) const

a method to create a HashTable with key:NodeId and value:VAL

template<typename VAL>

NodeProperty< VAL > nodesPropertyFromVal (const VAL &a, Size size=0) const

a method to create a hashMap with key:NodeId and value:VAL

template<typename VAL>

List< VAL > listMapNodes (VAL(*f)(const NodeId &)) const

a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))

Static Private Member Functions
Constructors / Destructors
static DiGraph	completeGraph (int n)
	Build a complete DiGraph with n nodes.

Private Attributes
const InterfaceGraph< GUM_SCALAR > *	_graph_
	The interface graph on which this DFSTree applies.
std::list< NodeId >	_roots_
	The list of root patterns in this DFSTree.
Bijection< NodeId, Pattern * >	_node_map_
	The mapping between nodes in this DFSTree and the patterns they represents.
HashTable< Pattern , PatternData >	_data_
	Data about patterns in this DFSTree.
SearchStrategy< GUM_SCALAR > *	_strategy_
	The strategy used to prune the search tree.
Signaler< NodeId, NodeId >	onArcAdded
Signaler< NodeId, NodeId >	onArcDeleted
Set< Arc >	_arcs_
	the set of all the arcs contained within the ArcGraphPart
NodeProperty< NodeSet * >	_parents_
	for each arc, the sets of its parents
NodeProperty< NodeSet * >	_children_
	for each arc, the set of its children
Signaler< NodeId >	onNodeAdded
Signaler< NodeId >	onNodeDeleted

Detailed Description

template<GUM_Numeric GUM_SCALAR>
class gum::prm::gspan::DFSTree< GUM_SCALAR >

A DFSTree is used by gspan to sort lexicographically patterns discovered in an interface graph.

Definition at line 77 of file DFSTree.h.

Member Typedef Documentation

◆ ArcIterator

using gum::ArcGraphPart::ArcIterator = ArcSetIterator

inherited

Definition at line 100 of file arcGraphPart.h.

◆ node_const_iterator

using gum::NodeGraphPart::node_const_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 270 of file nodeGraphPart.h.

◆ node_const_iterator_safe

using gum::NodeGraphPart::node_const_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 272 of file nodeGraphPart.h.

◆ node_iterator

using gum::NodeGraphPart::node_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 269 of file nodeGraphPart.h.

◆ node_iterator_safe

using gum::NodeGraphPart::node_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 271 of file nodeGraphPart.h.

◆ NodeConstIterator

using gum::NodeGraphPart::NodeConstIterator = NodeGraphPartIterator

inherited

Definition at line 279 of file nodeGraphPart.h.

◆ NodeConstIteratorSafe

using gum::NodeGraphPart::NodeConstIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 281 of file nodeGraphPart.h.

◆ NodeIterator

using gum::NodeGraphPart::NodeIterator = NodeGraphPartIterator

inherited

Definition at line 278 of file nodeGraphPart.h.

◆ NodeIteratorSafe

using gum::NodeGraphPart::NodeIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 280 of file nodeGraphPart.h.

Constructor & Destructor Documentation

◆ DFSTree()

template<GUM_Numeric GUM_SCALAR>

gum::prm::gspan::DFSTree< GUM_SCALAR >::DFSTree	(	const InterfaceGraph< GUM_SCALAR > &	graph,
		gspan::SearchStrategy< GUM_SCALAR > *	strategy = 0 )

Default constructor.

Definition at line 384 of file DFSTree_tpl.h.

                                                                                  :
          _graph_(&graph), _strategy_(strategy) {
        GUM_CONSTRUCTOR(DFSTree);
 
        if (!_strategy_) _strategy_ = new FrequenceSearch< GUM_SCALAR >(2);
 
        _strategy_->setTree(this);
      }

References DFSTree(), gum::prm::gspan::FrequenceSearch< GUM_SCALAR >::FrequenceSearch(), _graph_, _strategy_, and strategy().

Referenced by DFSTree(), and ~DFSTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ~DFSTree()

template<GUM_Numeric GUM_SCALAR>

gum::prm::gspan::DFSTree< GUM_SCALAR >::~DFSTree ( )

override

Destructor.

Definition at line 58 of file DFSTree_tpl.h.

                                      {
        GUM_DESTRUCTOR(DFSTree);
 
        for (const auto& elt: _data_) {
          delete elt.first;
          delete elt.second;
        }
 
        delete _strategy_;
      }

References DFSTree(), _data_, and _strategy_.

Here is the call graph for this function:

Member Function Documentation

◆ _addChild_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_	(	Pattern &	p,
		Pattern *	child,
		EdgeGrowth< GUM_SCALAR > &	edge_growth )

private

Add a child to this DFSTree.

Definition at line 181 of file DFSTree_tpl.h.

                                                                                    {
        // Adding child to the tree
        NodeId node = DiGraph::addNode();
        _node_map_.insert(node, child);
        // Adding child in p's children list
        std::list< NodeId >& children = _data_[&p]->children;
 
        if (children.empty()) {
          children.push_back(node);
        } else {
          size_t size = children.size();
 
          for (std::list< NodeId >::iterator iter = children.begin(); iter != children.end();
               ++iter) {
            if (child->code() < pattern(*iter).code()) {
              children.insert(iter, node);
              break;
            }
          }
 
          if (size == children.size()) { children.push_back(node); }
        }
      }

References _data_, _node_map_, gum::NodeGraphPart::addNode(), children(), gum::prm::gspan::Pattern::code(), pattern(), and gum::NodeGraphPart::size().

Referenced by growPattern().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _checkChildren_()

INLINE void gum::ArcGraphPart::_checkChildren_ ( NodeId id )

privateinherited

when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set entry to children[id]

Parameters

id	the node whose children[id] is checked

Definition at line 72 of file arcGraphPart_inl.h.

                                                     {
    if (!_children_.exists(id)) { _children_.insert(id, new NodeSet); }
  }

References _children_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _checkGrowth_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::gspan::DFSTree< GUM_SCALAR >::_checkGrowth_	(	Pattern &	p,
		Pattern *	child,
		EdgeGrowth< GUM_SCALAR > &	edge_growth )

private

Raise different exceptions if child is invalid or illegal.

Definition at line 208 of file DFSTree_tpl.h.

                                                                                       {
        NodeId v = edge_growth.v;
 
        // First we check if the edge is legal
        if (v == 0) { v = child->addNodeWithLabel(*(edge_growth.l_v)); }
 
        child->addArc(edge_growth.u, v, *(edge_growth.edge));
        // Neighborhood restriction is checked by the Pattern class
        const EdgeCode& edge = child->edgeCode(edge_growth.u, v);
 
        // Then we check if the edge we added is valid
        if (edge < *(child->code().codes.front())) {
          GUM_ERROR(OperationNotAllowed,
                    "added edge code is lesser than the first "
                    "one in the pattern's DFSCode");
        }
 
        if (edge.isBackward()) {
          for (auto iter = child->code().codes.begin(); (iter + 1) != child->code().codes.end();
               ++iter) {
            if ((((**iter).i == v) || ((**iter).j == v)) && edge < (**iter)) {
              GUM_ERROR(OperationNotAllowed,
                        "added backward edge is lesser than an existing edge on v");
            }
          }
        }
 
        // Finally, we check if child is minimal.
        if (!child->isMinimal()) {
          GUM_ERROR(OperationNotAllowed, "the DFSCode for this growth is not minimal")
        }
      }

References gum::prm::gspan::Pattern::addArc(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::prm::gspan::Pattern::code(), gum::prm::gspan::DFSCode::codes, gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::edge, gum::prm::gspan::Pattern::edgeCode(), GUM_ERROR, gum::prm::gspan::EdgeCode::isBackward(), gum::prm::gspan::Pattern::isMinimal(), gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::l_v, gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::u, and gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::v.

Referenced by growPattern().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _checkParents_()

INLINE void gum::ArcGraphPart::_checkParents_ ( NodeId id )

privateinherited

when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entry to parents[id]

Parameters

id	the node whose parents[id] is checked

Definition at line 68 of file arcGraphPart_inl.h.

                                                    {
    if (!_parents_.exists(id)) { _parents_.insert(id, new NodeSet); }
  }

References _parents_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _initialiaze_root_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::gspan::DFSTree< GUM_SCALAR >::_initialiaze_root_	(	Pattern *	p,
		Sequence< EdgeData< GUM_SCALAR > * > &	seq )

private

This initialize the DSFTree with a new root.

Parameters

p	A Pattern.
seq	A sequence of EdgeData<GUM_SCALAR>.

Definition at line 114 of file DFSTree_tpl.h.

                                                                                                   {
        DFSTree< GUM_SCALAR >::PatternData* data = _data_[p];
        std::vector< NodeId >               degree_list;
 
        for (auto iter = edge_seq.begin(); iter != edge_seq.end(); ++iter) {
          const auto&                             edge = *iter;
          Sequence< PRMInstance< GUM_SCALAR >* >* seq
              = new Sequence< PRMInstance< GUM_SCALAR >* >();
 
          // Creating the multiset of instances matching p
          bool u_first = (edge->l_u->id < edge->l_v->id);
          seq->insert((u_first) ? edge->u : edge->v);
          seq->insert((!u_first) ? edge->u : edge->v);
 
          NodeId an_id = data->iso_graph.addNode();
          data->iso_map.insert(an_id, seq);
          degree_list.push_back(an_id);
 
          // Adding edges between two isomorphisms of p sharing at least one
          // instance
          for (const auto& elt: data->iso_map)
            if (elt.first != an_id)
              for (auto iter = elt.second->begin(); iter != elt.second->end(); ++iter)
                if (seq->exists(*iter)) {
                  data->iso_graph.addEdge(an_id, elt.first);
                  break;
                }
        }
 
        // Computing p->max_indep_set using a greedy algorithm
        DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
        std::sort(degree_list.begin(), degree_list.end(), my_operator);
        Set< NodeId > removed;
 
        for (const auto node: degree_list) {
          if (!removed.exists(node)) {
            removed.insert(node);
 
            for (const auto neighbor: data->iso_graph.neighbours(node))
              removed.insert(neighbor);
 
            data->max_indep_set.insert(node);
          }
        }
      }

References _data_, gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNode(), data(), gum::SequenceImplementation< Key, Gen >::exists(), gum::Set< Key >::exists(), gum::SequenceImplementation< Key, Gen >::insert(), gum::Set< Key >::insert(), gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::iso_graph, gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::iso_map, gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::max_indep_set, and gum::EdgeGraphPart::neighbours().

Referenced by addRoot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _is_new_seq_()

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::gspan::DFSTree< GUM_SCALAR >::_is_new_seq_	(	Sequence< PRMInstance< GUM_SCALAR > * > &	seq,
		NodeProperty< Sequence< PRMInstance< GUM_SCALAR > * > * > &	iso_map )

private

Check if an instance match is redundant.

Definition at line 162 of file DFSTree_tpl.h.

                                                                            {
        for (const auto& elt: iso_map) {
          bool found = false;
 
          for (const auto& inst: seq)
            if (!(elt.second->exists(inst))) {
              found = true;
              break;
            }
 
          if (!found) { return false; }
        }
 
        return true;
      }

References iso_map().

Referenced by growPattern().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _test_equality_()

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::gspan::DFSTree< GUM_SCALAR >::_test_equality_	(	HashTable< PRMClassElement< GUM_SCALAR > *, Size > &	x,
		HashTable< PRMClassElement< GUM_SCALAR > *, Size > &	y )

private

Definition at line 354 of file DFSTree_tpl.h.

                                                                {
        for (const auto& elt: x) {
          if (auto p = y.tryGet(elt.first); !p || *p != elt.second) return false;
        }
 
        return true;
      }

◆ addArc()

INLINE void gum::DiGraph::addArc	(	const NodeId	tail,
		const NodeId	head )

overridevirtualinherited

insert a new arc into the directed graph

Parameters

tail	the id of the tail of the new inserted arc
head	the id of the head of the new inserted arc

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

Exceptions

InvalidNode if head or tail does not belong to the graph nodes

Reimplemented from gum::ArcGraphPart.

Reimplemented in gum::PDAG, and gum::prm::gspan::Pattern.

Definition at line 59 of file diGraph_inl.h.

                                                                  {
    if (!exists(head)) { GUM_ERROR(InvalidNode, "no head node : " << head) }
 
    if (!exists(tail)) { GUM_ERROR(InvalidNode, "no tail node : " << tail) }
 
    ArcGraphPart::addArc(tail, head);
  }

References gum::ArcGraphPart::addArc(), gum::NodeGraphPart::exists(), and GUM_ERROR.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::DAG::addArc(), gum::DAGCycleDetector::addArc(), gum::PDAG::addArc(), gum::prm::gspan::Pattern::addArc(), completeGraph(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::graph::moralizedAncestralGraph(), gum::learning::IBNLearner::prepareFCI_(), gum::learning::IBNLearner::prepareMiic_(), gum::learning::IBNLearner::preparePC_(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::learning::StructuralConstraintDAG::setGraphAlone(), and gum::PAG::toMixedGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addNode()

INLINE NodeId gum::NodeGraphPart::addNode ( )

virtualinherited

insert a new node and return its id

Returns: the id chosen by the internal idFactory

Reimplemented in gum::CliqueGraph.

Definition at line 269 of file nodeGraphPart_inl.h.

                                       {
    NodeId newNode;
 
    // fill the first hole if holes exist
    if (_holes_ && (!_holes_->empty())) {
      newNode = *(_holes_->begin());
      _eraseHole_(newNode);
    } else {
      newNode = _boundVal_;
      ++_boundVal_;
      _updateEndIteratorSafe_();
    }
 
    GUM_EMIT1(onNodeAdded, newNode);
 
    return newNode;
  }

References _boundVal_, _eraseHole_(), _holes_, _updateEndIteratorSafe_(), gum::Set< Key >::begin(), gum::Set< Key >::empty(), GUM_EMIT1, and onNodeAdded.

Referenced by gum::IncrementalGraphLearner< AttributeSelection, isScalar >::IncrementalGraphLearner(), gum::MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraph(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::StructuredInference< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_initialiaze_root_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot(), populateNodesFromProperty(), and gum::LeafAggregator::update().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addNodes()

INLINE std::vector< NodeId > gum::NodeGraphPart::addNodes ( Size n )

inherited

insert n nodes

Parameters

n	the number of nodes to add

Returns: the vector of chosen ids

Definition at line 287 of file nodeGraphPart_inl.h.

                                                           {
    std::vector< NodeId > v;
    v.reserve(N);
    for (Idx i = 0; i < N; i++)
      v.push_back(this->addNode());
    return v;
  }

Referenced by gum::DiGraph::completeGraph(), gum::UndiGraph::completeGraph(), and populateNodesFromProperty().

Here is the caller graph for this function:

◆ addNodeWithId()

void gum::NodeGraphPart::addNodeWithId ( const NodeId id )

virtualinherited

try to insert a node with the given id

Warning: This method should be carefully used. Please prefer populateNodes or populateNodesFromProperty when possible

Exceptions

DuplicateElement exception if the id already exists

Reimplemented in gum::CliqueGraph.

Definition at line 214 of file nodeGraphPart.cpp.

                                                   {
    if (id >= _boundVal_) {
      if (id > _boundVal_) {   // we have to add holes
        if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);
 
        for (NodeId i = _boundVal_; i < id; ++i)
          _holes_->insert(i);
      }
 
      _boundVal_ = id + 1;
 
      _updateEndIteratorSafe_();
    } else {
      if (_inHoles_(id)) {   // we fill a hole
        _eraseHole_(id);
      } else {
        GUM_ERROR(DuplicateElement, "Id " << id << " is already used")
      }
    }
 
    GUM_EMIT1(onNodeAdded, id);
  }

References _boundVal_, _eraseHole_(), _holes_, _holes_resize_policy_, _holes_size_, _inHoles_(), _updateEndIteratorSafe_(), GUM_EMIT1, GUM_ERROR, gum::Set< Key >::insert(), and onNodeAdded.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph(), gum::EssentialGraph::_buildEssentialGraph_(), gum::SpanningForestPrim::_computeInAComponent_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::Separation::isForwardSeparated(), gum::learning::IBNLearner::learnDag_(), gum::learning::FCI::learnPAG(), gum::learning::KTBNLearner< GUM_SCALAR >::learnParameters(), gum::learning::SimpleMiic::learnStructure(), gum::graph::markovBlanket(), gum::UndiGraph::partialUndiGraph(), populateNodesFromProperty(), gum::learning::IBNLearner::prepareFCI_(), gum::learning::IBNLearner::prepareMiic_(), gum::learning::IBNLearner::preparePC_(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), gum::learning::StructuralConstraintDAG::setGraphAlone(), gum::EssentialGraph::skeleton(), gum::CausalModel< GUM_ELEMENT >::toDot(), and gum::PAG::toMixedGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addRoot()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot ( LabelData & data )

Add a one edge Pattern in this DFSTree.

Parameters

data	Data over the edge used to create a root of this DFSTree.

Returns: Returns the Pattern added as a root of this DFSTree.

Definition at line 70 of file DFSTree_tpl.h.

                                                          {
        HashTable< Pattern*, std::pair< Idx, Idx > >                roots;
        HashTable< Pattern*, Sequence< EdgeData< GUM_SCALAR >* >* > roots_edges;
 
        for (const auto& edge: _graph_->edges(&label)) {
          bool u_first = (edge->l_u->id < edge->l_v->id);
          Idx  u_idx   = (u_first) ? edge->l_u->id : edge->l_v->id;
          Idx  v_idx   = (!u_first) ? edge->l_u->id : edge->l_v->id;
 
          bool found = false;
 
          for (const auto& elt: roots)
            if ((elt.second.first == u_idx) && (elt.second.second == v_idx)) {
              roots_edges[elt.first]->insert(edge);
              found = true;
              break;
            }
          if (!found) {
            Pattern* p = new Pattern();
            roots.insert(p, std::make_pair(u_idx, v_idx));
            roots_edges.insert(p, new Sequence< EdgeData< GUM_SCALAR >* >());
            roots_edges[p]->insert(edge);
            DFSTree< GUM_SCALAR >::PatternData* data = new DFSTree< GUM_SCALAR >::PatternData(p);
            NodeId u = p->addNodeWithLabel((u_first) ? *edge->l_u : *edge->l_v);
            NodeId v = p->addNodeWithLabel((!u_first) ? *edge->l_u : *edge->l_v);
            p->addArc(u, v, label);
            _node_map_.insert(DiGraph::addNode(), p);
            _data_.insert(p, data);
            _roots_.push_back(_node_map_.first(p));
          }
        }
 
        // This is used to compute the max independent set of p->max_indep_set
        for (const auto& elt: roots_edges) {
          _initialiaze_root_(elt.first, *elt.second);
          strategy().accept_root(elt.first);
          delete elt.second;
        }
      }

References gum::prm::gspan::Pattern::Pattern(), _data_, _graph_, _initialiaze_root_(), _node_map_, _roots_, gum::prm::gspan::Pattern::addArc(), gum::NodeGraphPart::addNode(), gum::prm::gspan::Pattern::addNodeWithLabel(), data(), gum::HashTable< Key, Val >::insert(), roots(), and strategy().

Here is the call graph for this function:

◆ ancestors()

INLINE NodeSet gum::DiGraph::ancestors ( NodeId id ) const

inherited

returns the set of all ancestors of id (nodes from which id is reachable)

Definition at line 119 of file diGraph_inl.h.

119{ return graph::ancestors(*this, id); }

gum::graph::ancestors

NodeSet ancestors(const G &g, NodeId id)

Returns the set of all ancestors of id (nodes from which id is reachable following arc direction).

Definition reachability_tpl.h:57

References gum::graph::ancestors().

Referenced by gum::DAGmodel::ancestors(), gum::EssentialGraph::ancestors(), gum::MarkovBlanket::ancestors(), gum::Separation::isAncestorOf(), and gum::DoorCriteria::nodesOnDirectedPaths().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ arcs()

INLINE const ArcSet & gum::ArcGraphPart::arcs ( ) const

inherited

returns the set of arcs stored within the ArcGraphPart

Definition at line 60 of file arcGraphPart_inl.h.

60{ return _arcs_; }

gum::ArcGraphPart::_arcs_

Set< Arc > _arcs_

the set of all the arcs contained within the ArcGraphPart

Definition arcGraphPart.h:281

References _arcs_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::PRMClass< GUM_SCALAR >::_inheritClass_(), gum::prm::ClassBayesNet< GUM_SCALAR >::_init_(), gum::learning::ConstraintBasedLearning::applyStructuralConstraints_(), gum::DAGmodel::arcs(), gum::EssentialGraph::arcs(), gum::MarkovBlanket::arcs(), gum::prm::gspan::Pattern::arcs(), gum::learning::FCI::learnPAG(), gum::learning::SimpleMiic::learnStructure(), gum::learning::Miic::orientationMiic_(), and gum::DiGraph::toDot().

Here is the caller graph for this function:

◆ arcsProperty() [1/2]

template<typename VAL>

ArcProperty< VAL > gum::ArcGraphPart::arcsProperty	(	const VAL &	a,
		Size	size = 0 ) const

inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL a)

Parameters

a	the default value assigned to each arc in the returned Property
size	an optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of arcs. If you do not specify this parameter, the method will assign it for you.

◆ arcsProperty() [2/2]

template<typename VAL>

ArcProperty< VAL > gum::ArcGraphPart::arcsProperty	(	VAL(*	f )(const Arc &),
		Size	size = 0 ) const

inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Parameters

f	a function assigning a VAL to any arc
size	an optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of arcs. If you do not specify this parameter, the method will assign it for you.

◆ asNodeSet()

INLINE NodeSet gum::NodeGraphPart::asNodeSet ( ) const

inherited

returns a copy of the set of nodes represented by the NodeGraphPart

Warning: this function is o(n) where n is the number of nodes. In space and in time. Usually, when you need to parse the nodes of a NodeGraphPart, prefer using
for(const auto n : nodes())

gum::NodeGraphPart::nodes
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
Definition nodeGraphPart_inl.h:379

rather than
for(const auto n : asNodeSet())

gum::NodeGraphPart::asNodeSet
NodeSet asNodeSet() const
returns a copy of the set of nodes represented by the NodeGraphPart
Definition nodeGraphPart_inl.h:367

as this is faster and consumes much less memory.

Definition at line 367 of file nodeGraphPart_inl.h.

                                                {
    NodeSet son(sizeNodes());
 
    if (!empty()) {
      for (NodeId n = 0; n < _boundVal_; ++n) {
        if (!_inHoles_(n)) son.insert(n);
      }
    }
 
    return son;
  }

References _boundVal_, _inHoles_(), empty(), gum::Set< Key >::insert(), and sizeNodes().

Referenced by gum::MarginalTargetedInference< GUM_SCALAR >::MarginalTargetedInference(), gum::MarginalTargetedMRFInference< GUM_SCALAR >::MarginalTargetedMRFInference(), gum::DoCalculus< GUM_SCALAR >::_ancestorsIn_(), gum::DoCalculus< GUM_SCALAR >::_cDecomposition_(), gum::DoCalculus< GUM_SCALAR >::_ID_(), gum::DoCalculus< GUM_SCALAR >::_topoObserved_(), populateNodesFromProperty(), and gum::ImportanceSampling< GUM_SCALAR >::unsharpenBN_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin()

INLINE NodeGraphPartIterator gum::NodeGraphPart::begin ( ) const

noexceptinherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 346 of file nodeGraphPart_inl.h.

                                                                   {
    NodeGraphPartIterator it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

References NodeGraphPartIterator, and gum::NodeGraphPartIterator::validate_().

Referenced by gum::Estimator< GUM_SCALAR >::Estimator(), gum::learning::ConstraintBasedLearning::initGraph_(), populateNodesFromProperty(), and gum::Estimator< GUM_SCALAR >::setFromBN().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ beginSafe()

INLINE NodeGraphPartIteratorSafe gum::NodeGraphPart::beginSafe ( ) const

inherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 334 of file nodeGraphPart_inl.h.

                                                                  {
    NodeGraphPartIteratorSafe it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

References NodeGraphPartIteratorSafe, and gum::NodeGraphPartIterator::validate_().

Referenced by populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bound()

INLINE NodeId gum::NodeGraphPart::bound ( ) const

inherited

returns a number n such that all node ids are strictly lower than n

Definition at line 323 of file nodeGraphPart_inl.h.

323{ return _boundVal_; }

References _boundVal_.

Referenced by _clearNodes_(), gum::StaticTriangulation::_computeEliminationTree_(), populateNodesFromProperty(), gum::NodeGraphPartIterator::validate_(), and gum::NodeGraphPartIteratorSafe::whenNodeDeleted().

Here is the caller graph for this function:

◆ children() [1/4]

INLINE NodeSet gum::ArcGraphPart::children ( const NodeSet & ids ) const

inherited

returns the set of nodes which consists in the node and its parents returns the set of children of a set of nodes

returns the set of children of a set of nodes

Definition at line 82 of file arcGraphPart_inl.h.

                                                                {
    NodeSet res;
    for (const auto node: ids)
      res += children(node);
    return res;
  }

References children().

Referenced by ArcGraphPart(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::_addArcs_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::DoorCriteria::_existsUnblockedDirectedPath_(), gum::prm::gspan::Pattern::_expandCodeIsMinimal_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::DoCalculus< GUM_SCALAR >::_removeInIntoDoing_outOfKnowing_(), gum::DoCalculus< GUM_SCALAR >::_topoObserved_(), gum::BarrenNodesFinder::barrenNodes(), children(), gum::DAGmodel::children(), gum::DAGmodel::children(), gum::EssentialGraph::children(), gum::EssentialGraph::children(), gum::MarkovBlanket::children(), gum::MarkovBlanket::children(), gum::DoorCriteria::enumerateFrontdoorSets(), eraseChildren(), gum::PDAG::hasMixedReallyOrientedPath(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::initialize_(), gum::Separation::isBackdoorSeparated(), gum::Separation::isForwardSeparated(), gum::prm::gspan::Pattern::isMinimal(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::makeInferenceNodeToNeighbours_(), operator<<(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::rec_hasMixedReallyOrientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::prm::gspan::Pattern::remove(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), gum::EssentialGraph::toDot(), gum::MarkovBlanket::toDot(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and unvirtualizedEraseChildren().

Here is the call graph for this function:

◆ children() [2/4]

INLINE const NodeSet & gum::ArcGraphPart::children ( NodeId id ) const

inherited

returns the set of nodes with arc outgoing from a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is outgoing from the given node.

Parameters

id	the node which is the tail of the arcs returned

Definition at line 97 of file arcGraphPart_inl.h.

                                                              {
    if (_children_.exists(id)) return *_children_[id];
    else return emptyNodeSet;
  }

References _children_, and gum::emptyNodeSet.

◆ children() [3/4]

template<GUM_Numeric GUM_SCALAR>

std::list< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::children ( const Pattern & p )

Returns the list of p children in this DFSTree.

Definition at line 427 of file DFSTree_tpl.h.

                                                                         {
        auto pd = _data_.tryGet(const_cast< Pattern* >(&p));
        if (!pd) GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        return (*pd)->children;
      }

References _data_, and GUM_ERROR.

Referenced by _addChild_().

Here is the caller graph for this function:

◆ children() [4/4]

template<GUM_Numeric GUM_SCALAR>

const std::list< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::children ( const Pattern & p ) const

Returns the list of p children in this DFSTree.

Definition at line 434 of file DFSTree_tpl.h.

                                                                                     {
        auto pd = _data_.tryGet(const_cast< Pattern* >(&p));
        if (!pd) GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        return (*pd)->children;
      }

References _data_, and GUM_ERROR.

◆ clear()

INLINE void gum::DiGraph::clear ( )

overridevirtualinherited

removes all the nodes and arcs from the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 67 of file diGraph_inl.h.

                             {
    ArcGraphPart::clearArcs();
    NodeGraphPart::clearNodes();
  }

References gum::ArcGraphPart::clearArcs(), and gum::NodeGraphPart::clearNodes().

Referenced by operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clearArcs()

void gum::ArcGraphPart::clearArcs ( )

inherited

removes all the arcs from the ArcGraphPart

Definition at line 104 of file arcGraphPart.cpp.

                               {
    for (const auto& elt: _parents_)
      delete elt.second;
 
    _parents_.clear();
 
    for (const auto& elt: _children_)
      delete elt.second;
 
    _children_.clear();
 
    // we need this copy only if at least one onArcDeleted listener exists
    if (onArcDeleted.hasListener()) {
      ArcSet tmp = _arcs_;
      _arcs_.clear();
 
      for (const auto& arc: tmp)
        GUM_EMIT2(onArcDeleted, arc.tail(), arc.head());
    } else {
      _arcs_.clear();
    }
  }

References _arcs_, _children_, _parents_, gum::Set< Key >::clear(), GUM_EMIT2, gum::__sig__::BasicSignaler< Args... >::hasListener(), and onArcDeleted.

Referenced by ~ArcGraphPart(), gum::DiGraph::clear(), gum::MixedGraph::clear(), operator=(), operator=(), and gum::MixedGraph::operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )

virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 325 of file nodeGraphPart_inl.h.

325{ _clearNodes_(); }

gum::NodeGraphPart::_clearNodes_

void _clearNodes_()

code for clearing nodes (called twice)

Definition nodeGraphPart.cpp:237

References _clearNodes_().

Referenced by gum::DiGraph::clear(), gum::MixedGraph::clear(), gum::UndiGraph::clear(), gum::MixedGraph::operator=(), operator=(), and populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ completeGraph()

DiGraph gum::DiGraph::completeGraph ( int n )

staticinherited

Build a complete DiGraph with n nodes.

Parameters

int n

Returns: the complete DiGraph

Definition at line 58 of file diGraph.cpp.

                                      {
    DiGraph g;
    g.addNodes(n);
 
    for (int j = 0; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        g.addArc(j, k);
      }
    }
    return g;
  }

References DiGraph(), addArc(), and gum::NodeGraphPart::addNodes().

Here is the call graph for this function:

◆ connectedComponents()

INLINE NodeProperty< NodeId > gum::DiGraph::connectedComponents ( ) const

inherited

returns a property {node:id of weakly connected component}

Definition at line 127 of file diGraph_inl.h.

                                                                   {
    return graph::connectedComponents(*this);
  }

References gum::graph::connectedComponents().

Referenced by gum::DAGmodel::connectedComponents().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ data() [1/2]

template<GUM_Numeric GUM_SCALAR>

DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data ( const Pattern & p )

Parameters

p	The pattern

Definition at line 493 of file DFSTree_tpl.h.

                                                                                             {
        return *(_data_[const_cast< Pattern* >(&p)]);
      }

References _data_.

Referenced by _initialiaze_root_(), addRoot(), and growPattern().

Here is the caller graph for this function:

◆ data() [2/2]

template<GUM_Numeric GUM_SCALAR>

const DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data ( const Pattern & p ) const

Parameters

p	The pattern

Definition at line 499 of file DFSTree_tpl.h.

                                                            {
        return *(_data_[const_cast< Pattern* >(&p)]);
      }

References _data_.

◆ descendants()

INLINE NodeSet gum::DiGraph::descendants ( NodeId id ) const

inherited

returns the set of all descendants of id (nodes reachable from id)

Definition at line 121 of file diGraph_inl.h.

121{ return graph::descendants(*this, id); }

gum::graph::descendants

NodeSet descendants(const G &g, NodeId id)

Returns the set of all descendants of id (nodes reachable from id following arc direction).

Definition reachability_tpl.h:73

References gum::graph::descendants().

Referenced by gum::DAGmodel::descendants(), gum::EssentialGraph::descendants(), gum::MarkovBlanket::descendants(), gum::DoorCriteria::enumerateBackdoorSets(), gum::Separation::isDescendantOf(), gum::DoorCriteria::nodesOnDirectedPaths(), and gum::DoorCriteria::satisfiesBackdoorCriterion().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ directedPath()

INLINE std::optional< std::vector< NodeId > > gum::DiGraph::directedPath	(	NodeId	node1,
		NodeId	node2 ) const

inherited

returns a directed path from node1 to node2, or std::nullopt if none

Definition at line 109 of file diGraph_inl.h.

                                                                                          {
    return graph::directedPath(*this, node1, node2);
  }

References gum::graph::directedPath().

Here is the call graph for this function:

◆ directedUnorientedPath()

INLINE std::optional< std::vector< NodeId > > gum::DiGraph::directedUnorientedPath	(	NodeId	node1,
		NodeId	node2 ) const

inherited

returns a shortest path from node1 to node2 ignoring arc orientation, or std::nullopt if none

Definition at line 115 of file diGraph_inl.h.

                                                                         {
    return graph::directedUnorientedPath(*this, node1, node2);
  }

References gum::graph::directedUnorientedPath().

Here is the call graph for this function:

◆ dotNodeLabel()

std::string gum::NodeGraphPart::dotNodeLabel ( NodeId id ) const

inherited

returns " [label=\"...\"]" with DOT-escaped name, or "" if no name

Definition at line 188 of file nodeGraphPart.cpp.

                                                       {
    if (!hasName(id)) return "";
    const std::string& name = _names_->second(id);
    std::string        result;
    result.reserve(name.size() * 2 + 24);
    result = " [label=\"(";
    result += std::to_string(id);
    result += ") ";
    for (const char c: name) {
      switch (c) {
        case '"' : result += "\\\""; break;
        case '\\' : result += "\\\\"; break;
        case '\n' : result += "\\n"; break;
        case '\r' : result += "\\r"; break;
        default : result += c;
      }
    }
    result += "\"]";
    return result;
  }

References _names_, and hasName().

Referenced by populateNodesFromProperty(), gum::DiGraph::toDot(), gum::MixedGraph::toDot(), gum::PAG::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ empty()

INLINE bool gum::NodeGraphPart::empty ( ) const

inherited

alias for emptyNodes

Definition at line 321 of file nodeGraphPart_inl.h.

321{ return emptyNodes(); }

gum::NodeGraphPart::emptyNodes

bool emptyNodes() const

indicates whether there exists nodes in the NodeGraphPart

Definition nodeGraphPart_inl.h:319

References emptyNodes().

Referenced by asNodeSet(), populateNodesFromProperty(), gum::prm::gspan::Pattern::remove(), and gum::PDAG::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emptyArcs()

INLINE bool gum::ArcGraphPart::emptyArcs ( ) const

inherited

indicates wether the ArcGraphPart contains any arc

Definition at line 56 of file arcGraphPart_inl.h.

56{ return _arcs_.empty(); }

References _arcs_, and gum::Set< Key >::empty().

Here is the call graph for this function:

◆ emptyNodes()

INLINE bool gum::NodeGraphPart::emptyNodes ( ) const

inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 319 of file nodeGraphPart_inl.h.

319{ return (sizeNodes() == 0); }

References sizeNodes().

Referenced by empty(), and populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ end()

INLINE const NodeGraphPartIterator & gum::NodeGraphPart::end ( ) const

noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 352 of file nodeGraphPart_inl.h.

                                                                        {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIterator.

Referenced by gum::Estimator< GUM_SCALAR >::Estimator(), gum::learning::ConstraintBasedLearning::initGraph_(), populateNodesFromProperty(), and gum::Estimator< GUM_SCALAR >::setFromBN().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ endSafe()

INLINE const NodeGraphPartIteratorSafe & gum::NodeGraphPart::endSafe ( ) const

noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 342 of file nodeGraphPart_inl.h.

                                                                                {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIteratorSafe.

Referenced by populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseArc()

INLINE void gum::ArcGraphPart::eraseArc ( const Arc & arc )

virtualinherited

removes an arc from the ArcGraphPart

Parameters

arc	the arc to be removed

Warning: if the arc does not exist, nothing is done. In particular, no exception is thrown. However, the signal onArcDeleted is fired only if a node is effectively removed.

Definition at line 114 of file arcGraphPart_inl.h.

                                                   {
    // ASSUMING tail and head exists in  _parents_ anf  _children_
    // (if not, it is an error)
    if (existsArc(arc)) {
      NodeId tail = arc.tail();
      NodeId head = arc.head();
      _parents_[head]->erase(tail);
      _children_[tail]->erase(head);
      _arcs_.erase(arc);
      GUM_EMIT2(onArcDeleted, tail, head);
    }
  }

References _arcs_, _children_, _parents_, gum::Set< Key >::erase(), existsArc(), GUM_EMIT2, gum::Arc::head(), onArcDeleted, and gum::Arc::tail().

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::DoCalculus< GUM_SCALAR >::_removeIncomingInto_(), gum::DoCalculus< GUM_SCALAR >::_removeInIntoDoing_outOfKnowing_(), gum::BarrenNodesFinder::barrenNodes(), gum::DAGCycleDetector::eraseArc(), eraseChildren(), eraseParents(), eraseSetOfArcs_(), gum::Separation::isBackdoorSeparated(), gum::learning::IBNLearner::learnDag_(), gum::learning::SimpleMiic::learnStructure(), gum::learning::ConstraintBasedLearning::orientDoubleHeadedArcs_(), gum::prm::gspan::Pattern::pop_back(), gum::BayesNet< GUM_SCALAR >::reverseArc(), unvirtualizedEraseChildren(), unvirtualizedEraseParents(), and unvirtualizedEraseSetOfArcs_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseChildren()

INLINE void gum::ArcGraphPart::eraseChildren ( NodeId id )

inherited

removes all the children of a given node

Parameters

id	the node all the children of which will be removed

Warning: although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseChildren; if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 146 of file arcGraphPart_inl.h.

                                                   {
    if (_children_.exists(id)) {
      const NodeSet& children = *(_children_[id]);
 
      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        // warning: use this erase so that you actually use the virtualized
        // arc removal function
        eraseArc(Arc(id, *iter));
      }
    }
  }

References gum::Arc::Arc(), _children_, gum::Set< Key >::beginSafe(), children(), gum::Set< Key >::endSafe(), and eraseArc().

Here is the call graph for this function:

◆ eraseNode()

INLINE void gum::DiGraph::eraseNode ( const NodeId id )

overridevirtualinherited

remove a node and its adjacent arcs from the graph

Parameters

id	the id of the node to be removed

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

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 93 of file diGraph_inl.h.

                                                {
    // warning: to remove the arcs adjacent to id, use the unvirtualized
    // versions
    // of arc removals
    ArcGraphPart::unvirtualizedEraseParents(id);
    ArcGraphPart::unvirtualizedEraseChildren(id);
 
    NodeGraphPart::eraseNode(id);
  }

References gum::NodeGraphPart::eraseNode(), gum::ArcGraphPart::unvirtualizedEraseChildren(), and gum::ArcGraphPart::unvirtualizedEraseParents().

Referenced by gum::BarrenNodesFinder::barrenNodes(), gum::prm::gspan::Pattern::pop_back(), gum::Separation::reduceForDSeparation(), and gum::prm::gspan::Pattern::remove().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseParents()

INLINE void gum::ArcGraphPart::eraseParents ( NodeId id )

inherited

erase all the parents of a given node

Parameters

id	the node all the parents of which will be removed

Warning: although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseParents; if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 132 of file arcGraphPart_inl.h.

                                                  {
    if (_parents_.exists(id)) {
      const NodeSet& parents = *(_parents_[id]);
 
      for (auto iter = parents.beginSafe();   // safe iterator needed here
           iter != parents.endSafe();
           ++iter) {
        // warning: use this erase so that you actually use the virtualized
        // arc removal function
        eraseArc(Arc(*iter, id));
      }
    }
  }

References gum::Arc::Arc(), _parents_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), eraseArc(), and parents().

Here is the call graph for this function:

◆ eraseSetOfArcs_()

INLINE void gum::ArcGraphPart::eraseSetOfArcs_ ( const ArcSet & set )

protectedinherited

a (virtualized) function to remove a given set of arcs

Warning: this function uses eraseArc, which is a virtual function. Hence the behaviour of this function is that of a virtual function

Definition at line 127 of file arcGraphPart_inl.h.

                                                             {
    for (const auto& arc: set)
      eraseArc(arc);
  }

References eraseArc().

Referenced by listMapArcs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ exists()

INLINE bool gum::NodeGraphPart::exists ( const NodeId id ) const

inherited

alias for existsNode

Definition at line 307 of file nodeGraphPart_inl.h.

307{ return existsNode(node); }

gum::NodeGraphPart::existsNode

bool existsNode(const NodeId id) const

returns true iff the NodeGraphPart contains the given nodeId

Definition nodeGraphPart_inl.h:301

References existsNode().

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_removeNode_(), gum::DiGraph::addArc(), gum::prm::gspan::Pattern::addArc(), gum::UndiGraph::addEdge(), gum::DAGmodel::exists(), gum::prm::gspan::Pattern::exists(), gum::UGmodel::exists(), gum::learning::IBNLearner::learnDag_(), and populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ existsArc() [1/2]

INLINE bool gum::ArcGraphPart::existsArc ( const Arc & arc ) const

inherited

indicates whether a given arc exists

Parameters

arc	the arc we test whether or not it belongs to the ArcGraphPart

Definition at line 62 of file arcGraphPart_inl.h.

62{ return _arcs_.contains(arc); }

gum::Set::contains

bool contains(const Key &k) const

Indicates whether a given elements belong to the set.

Definition set_tpl.h:468

References _arcs_, and gum::Set< Key >::contains().

Referenced by gum::DoorCriteria::_existsUnblockedDirectedPath_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::EssentialGraph::_strongly_protected_(), gum::DAGCycleDetector::addArc(), gum::DoorCriteria::enumerateBackdoorSets(), eraseArc(), gum::DAGCycleDetector::eraseArc(), gum::prm::gspan::Pattern::exists(), gum::DAGmodel::existsArc(), gum::Separation::isBackdoorSeparated(), gum::learning::ConstraintBasedLearning::isForbiddenArc_(), gum::learning::ConstraintBasedLearning::isForbiddenEdge_(), and gum::graph::markovBlanket().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ existsArc() [2/2]

INLINE bool gum::ArcGraphPart::existsArc	(	NodeId	tail,
		NodeId	head ) const

inherited

indicates whether a given arc exists

Parameters

tail	the tail of the arc we test the existence in the ArcGraphPart
head	the head of the arc we test the existence in the ArcGraphPart

Definition at line 64 of file arcGraphPart_inl.h.

                                                                    {
    return _parents_.exists(head) && _parents_[head]->exists(tail);
  }

References _parents_.

◆ existsNode()

INLINE bool gum::NodeGraphPart::existsNode ( const NodeId id ) const

inherited

returns true iff the NodeGraphPart contains the given nodeId

Definition at line 301 of file nodeGraphPart_inl.h.

                                                               {
    if (node >= _boundVal_) return false;
 
    return (!_inHoles_(node));
  }

References _boundVal_, and _inHoles_().

Referenced by gum::SpanningForestPrim::_compute_(), gum::SpanningForestPrim::_computeInAComponent_(), gum::CausalFormula< GUM_SCALAR >::_ensureVariablesExist(), gum::SpanningForestPrim::_exploreNode_(), gum::OrderedEliminationSequenceStrategy::_isOrderNeeded_(), gum::DefaultPartialOrderedEliminationSequenceStrategy::eliminationUpdate(), gum::OrderedEliminationSequenceStrategy::eliminationUpdate(), eraseNode(), gum::PAG::eraseNode(), exists(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::Separation::isForwardSeparated(), gum::PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded_(), gum::graph::markovBlanket(), gum::graph::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), populateNodesFromProperty(), gum::Separation::reduceForDSeparation(), setName(), gum::OrderedEliminationSequenceStrategy::setOrder(), and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ family() [1/2]

INLINE NodeSet gum::DiGraph::family ( const NodeSet & ids ) const

inherited

returns the union of families of all nodes in ids

Definition at line 125 of file diGraph_inl.h.

125{ return graph::family(*this, ids); }

gum::graph::family

NodeSet family(const G &g, NodeId id)

Returns the family of id : { id } ∪ parents(id).

Definition reachability_tpl.h:89

References gum::graph::family().

Here is the call graph for this function:

◆ family() [2/2]

INLINE NodeSet gum::DiGraph::family ( NodeId id ) const

inherited

returns { id } ∪ parents(id)

Definition at line 123 of file diGraph_inl.h.

123{ return graph::family(*this, id); }

References gum::graph::family().

Referenced by gum::DAGmodel::family(), and gum::DAGmodel::family().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ frequency()

template<GUM_Numeric GUM_SCALAR>

double gum::prm::gspan::DFSTree< GUM_SCALAR >::frequency ( const Pattern & p ) const

Returns the frequency of p respecting it's maximal independent set.

Parameters

p	The pattern

Definition at line 488 of file DFSTree_tpl.h.

                                                                    {
        return (double)_data_[const_cast< Pattern* >(&p)]->max_indep_set.size();
      }

References _data_, and max_indep_set().

Here is the call graph for this function:

◆ growPattern()

template<GUM_Numeric GUM_SCALAR>

Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern	(	Pattern &	p,
		EdgeGrowth< GUM_SCALAR > &	edge_growth,
		Size	min_freq )

Add a one edge growth of p as one of its child.

The child is inserted lexicographically among the children of p. However if the child is found to be not minimal an OperationNotAllowed is raised.

Parameters

p	The Pattern from which a one edge growth is spawned.
edge_growth	The data about the edge growth of p.
min_freq	minimum number of occurrence to be used as a pattern

Exceptions

FatalError	Raised if the grow is an illegal backedge growth.
OperationNotAllowed	Raised if the grow is found to be not minimal.

Definition at line 244 of file DFSTree_tpl.h.

                                                                                      {
        auto* child = new Pattern(p);
 
        try {
          _checkGrowth_(p, child, edge_growth);
        } catch (OperationNotAllowed const&) {
          delete child;
          throw;
        }
 
        // Now we need to build the pattern data about child
        auto*                 data = new DFSTree< GUM_SCALAR >::PatternData(child);
        std::vector< NodeId > degree_list;
        NodeProperty< Sequence< PRMInstance< GUM_SCALAR >* >* >& p_iso_map = _data_[&p]->iso_map;
        // typename NodeProperty< std::pair< PRMInstance< GUM_SCALAR >*,
        //                                   PRMInstance< GUM_SCALAR >* > >::iterator_safe match;
        //  Using p information to build child's isomorphism graph
        NodeId id = 0;
 
        for (const auto& elt: p_iso_map) {
          auto match = edge_growth.matches.begin();
 
          for (; match != edge_growth.matches.end(); ++match) {
            // Adding the isomorphism in the iso_graph and building the iso_map.
            if (child->code().codes.back()->isForward()) {
              if (elt.second->exists(match.val().first)
                  && !(elt.second->exists(match.val().second))) {
                // Let's see if the new match is already matched
                auto* new_seq = new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);
                new_seq->insert(match.val().second);
 
                if (_is_new_seq_(*new_seq, data->iso_map)) {
                  id = data->iso_graph.addNode();
                  data->iso_map.insert(id, new_seq);
                } else {
                  delete new_seq;
                }
 
                break;
              }
            } else {
              if (elt.second->exists(match.val().first) && elt.second->exists(match.val().second)) {
                Sequence< PRMInstance< GUM_SCALAR >* >* new_seq
                    = new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);
 
                if (_is_new_seq_(*new_seq, data->iso_map)) {
                  id = data->iso_graph.addNode();
                  data->iso_map.insert(id, new_seq);
                } else {
                  delete new_seq;
                }
 
                break;
              }
            }
          }
 
          if (match != edge_growth.matches.end()) {
            // Adding edges in the iso_graph
            for (const auto node: data->iso_graph.nodes())
              if (node != id)
                for (const auto m: *data->iso_map[id])
                  if (data->iso_map[node]->exists(m)) {
                    data->iso_graph.addEdge(node, id);
                    break;
                  }
 
            degree_list.push_back(id);
            edge_growth.matches.erase(match.key());
          }
        }
 
        if (data->iso_graph.size() < min_freq) {
          delete data;
          delete child;
          GUM_ERROR(OperationNotAllowed, "child is not frequent enough")
        }
 
        // Now we can compute the maximal independent set of child
        DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
        std::sort(degree_list.begin(), degree_list.end(), my_operator);
        Set< NodeId > removed;
 
        for (const auto node: degree_list) {
          if (!removed.exists(node)) {
            removed.insert(node);
 
            for (const auto neighbor: data->iso_graph.neighbours(node))
              removed.insert(neighbor);
 
            data->max_indep_set.insert(node);
          }
        }
 
        _data_.insert(child, data);
 
        if (!_strategy_->accept_growth(&p, child, edge_growth)) {
          _data_.erase(child);
          delete data;
          delete child;
          GUM_ERROR(OperationNotAllowed, "child is not frequent enough")
        }
 
        _addChild_(p, child, edge_growth);
        return *child;
      }

References gum::prm::gspan::Pattern::Pattern(), _addChild_(), _checkGrowth_(), _data_, _is_new_seq_(), _strategy_, data(), gum::Set< Key >::exists(), GUM_ERROR, gum::SequenceImplementation< Key, Gen >::insert(), gum::Set< Key >::insert(), and gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::matches.

Here is the call graph for this function:

◆ hasDirectedPath()

bool gum::DiGraph::hasDirectedPath	(	NodeId	from,
		NodeId	to ) const

inherited

checks whether there exists a directed path from from to to

If from==to, this function checks if a directed cycle containing from exists.

Parameters

from
to

Returns: true if a directed path exists

Definition at line 114 of file diGraph.cpp.

                                                                        {
    return graph::hasDirectedPath(*this, from, to);
  }

References gum::graph::hasDirectedPath().

Referenced by gum::DAG::addArc(), and gum::PDAG::addArc().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasName()

bool gum::NodeGraphPart::hasName ( NodeId id ) const

inherited

returns true iff node id has an explicit name

Definition at line 186 of file nodeGraphPart.cpp.

186{ return _names_ && _names_->existsFirst(id); }

References _names_.

Referenced by dotNodeLabel(), and populateNodesFromProperty().

Here is the caller graph for this function:

◆ idFromName()

std::optional< NodeId > gum::NodeGraphPart::idFromName ( const std::string & name ) const

inherited

returns the id of the node with the given name, or std::nullopt

Definition at line 165 of file nodeGraphPart.cpp.

                                                                             {
    if (_names_ && _names_->existsSecond(name)) return _names_->first(name);
    return std::nullopt;
  }

References _names_.

Referenced by populateNodesFromProperty().

Here is the caller graph for this function:

◆ internalGraph()

template<GUM_Numeric GUM_SCALAR>

const InterfaceGraph< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::internalGraph ( ) const

Returns the list of root patterns in this DFSTree.

Definition at line 477 of file DFSTree_tpl.h.

                                                                                     {
        return *_graph_;
      }

References _graph_.

◆ iso_graph()

template<GUM_Numeric GUM_SCALAR>

UndiGraph & gum::prm::gspan::DFSTree< GUM_SCALAR >::iso_graph ( const Pattern & p )

Returns the isomorphism graph of p in the interface graph.

The isomorphism graph is a undirected graph in which each node represents a set of PRMInstance<GUM_SCALAR> matching p in the interface graph.

If there exists an edge between two nodes in the isomorphism graph, then the two respective set of instances are not disjoint.

Parameters

p	The pattern for which we want the isomorphism graph.

Returns: The isomorphism graph of p.

Exceptions

NotFound Raised if p is not a node in this DFSTree.

Definition at line 453 of file DFSTree_tpl.h.

                                                                  {
        auto pd = _data_.tryGet(const_cast< Pattern* >(&p));
        if (!pd) GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        return (*pd)->iso_graph;
      }

References _data_, and GUM_ERROR.

◆ iso_map()

template<GUM_Numeric GUM_SCALAR>

Sequence< PRMInstance< GUM_SCALAR > * > & gum::prm::gspan::DFSTree< GUM_SCALAR >::iso_map	(	const Pattern &	p,
		NodeId	node )

Given a pattern and a node in its isomorphism graph, this methods returns the sequence of instance matching p in the interface graph.

The sequence of instances respect DSF subscripting. Each node in the pattern's graph have a DSF subscript from 1 to n, where n is the number of nodes in the pattern's graph.

If for a given match you want the k-th instance repecting p's DFS subscripting, then it will be the (k - 1)th element in the sequence.

Parameters

p	The pattern for which we want a match in the interface graph.
node	The node in p isomorphism graph for which we want the matching set if instances.

Returns: Returns the sequence of instances matching p and node.

Exceptions

NotFound Raised if p or node does not exists.

Definition at line 460 of file DFSTree_tpl.h.

                                                                                                  {
        auto pd = _data_.tryGet(const_cast< Pattern* >(&p));
        if (!pd) GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        auto p_iso = (*pd)->iso_map.tryGet(node);
        if (!p_iso) GUM_ERROR(NotFound, "node not found in Pattern's isomorphism graph")
        return *(*p_iso);
      }

References _data_, and GUM_ERROR.

Referenced by _is_new_seq_().

Here is the caller graph for this function:

◆ listMapArcs()

template<typename VAL>

List< VAL > gum::ArcGraphPart::listMapArcs ( VAL(* f )(const Arc &) ) const

inherited

a method to create a list of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Parameters

f	a function assigning a VAL to any arc

References eraseSetOfArcs_(), and unvirtualizedEraseSetOfArcs_().

Here is the call graph for this function:

◆ listMapNodes()

template<typename VAL>

List< VAL > gum::NodeGraphPart::listMapNodes ( VAL(* f )(const NodeId &) ) const

inherited

a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))

Parameters

f	a function assigning a VAL to any node

References listMapNodes().

Referenced by listMapNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ max_indep_set()

template<GUM_Numeric GUM_SCALAR>

Set< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::max_indep_set ( const Pattern & p )

Returns the maximal independent set of p isomorphism graph.

Parameters

p	The pattern for which we want its maximal independent set.

Exceptions

NotFound Raised if p is not a node in this DFSTree.

Definition at line 470 of file DFSTree_tpl.h.

                                                                          {
        auto pd = _data_.tryGet(const_cast< Pattern* >(&p));
        if (!pd) GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        return (*pd)->max_indep_set;
      }

References _data_, and GUM_ERROR.

Referenced by frequency().

Here is the caller graph for this function:

◆ nameFromId()

std::string gum::NodeGraphPart::nameFromId ( NodeId id ) const

inherited

returns the name of node id, or "<id>" if no name is set

Definition at line 160 of file nodeGraphPart.cpp.

                                                     {
    if (_names_ && _names_->existsFirst(id)) return _names_->second(id);
    return std::to_string(id);
  }

References _names_.

Referenced by populateNodesFromProperty().

Here is the caller graph for this function:

◆ nextNodeId()

INLINE NodeId gum::NodeGraphPart::nextNodeId ( ) const

inherited

returns a new node id, not yet used by any node

Warning: a code like
id=nextNodeId();addNode(id);

gum::NodeGraphPart::nextNodeId
NodeId nextNodeId() const
returns a new node id, not yet used by any node
Definition nodeGraphPart_inl.h:243

is basically not thread safe !!

Returns: a node id not yet used by any node within the NodeGraphPart

Definition at line 243 of file nodeGraphPart_inl.h.

                                                {
    NodeId next = 0;
 
    // return the first hole if holes exist
    if (_holes_ && (!_holes_->empty())) next = *(_holes_->begin());
    else   // in other case
      next = _boundVal_;
 
    return next;
  }

References _boundVal_, _holes_, gum::Set< Key >::begin(), and gum::Set< Key >::empty().

Referenced by populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nodes()

INLINE const NodeGraphPart & gum::NodeGraphPart::nodes ( ) const

inherited

return *this as a NodeGraphPart

Definition at line 379 of file nodeGraphPart_inl.h.

                                                         {
    return *(static_cast< const NodeGraphPart* >(this));
  }

References NodeGraphPart().

Here is the call graph for this function:

◆ nodesPropertyFromFunction()

template<typename VAL>

NodeProperty< VAL > gum::NodeGraphPart::nodesPropertyFromFunction	(	VAL(*	f )(const NodeId &),
		Size	size = 0 ) const

inherited

a method to create a HashTable with key:NodeId and value:VAL

VAL are computed from the nodes using for all node x, VAL f(x). This method is a wrapper of the same method in HashTable.

See also: HashTable::map.

Parameters

f	a function assigning a VAL to any node
size	an optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of nodes. If you do not specify this parameter, the method will assign it for you.

References nodesPropertyFromFunction(), and size().

Referenced by nodesPropertyFromFunction().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nodesPropertyFromVal()

template<typename VAL>

NodeProperty< VAL > gum::NodeGraphPart::nodesPropertyFromVal	(	const VAL &	a,
		Size	size = 0 ) const

inherited

a method to create a hashMap with key:NodeId and value:VAL

for all nodes, the value stored is a. This method is a wrapper of the same method in HashTable.

See also: HashTable::map.

Parameters

a	the default value assigned to each edge in the returned Property
size	an optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of nodes. If you do not specify this parameter, the method will assign it for you.

References nodesPropertyFromVal(), and size().

Referenced by gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), and nodesPropertyFromVal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [1/3]

INLINE bool gum::ArcGraphPart::operator== ( const ArcGraphPart & p ) const

inherited

tests whether two ArcGraphParts contain the same arcs

Parameters

p	the ArcGraphPart that we compare with this

Definition at line 189 of file arcGraphPart_inl.h.

189{ return _arcs_ == p._arcs_; }

References ArcGraphPart(), and _arcs_.

Referenced by gum::DiGraph::operator==(), and gum::MixedGraph::operator==().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [2/3]

INLINE bool gum::DiGraph::operator== ( const DiGraph & g ) const

inherited

tests whether two DiGraphs are identical (same nodes, same arcs)

Parameters

g	the DiGraph with which "this" is compared

Definition at line 103 of file diGraph_inl.h.

                                                      {
    return ArcGraphPart::operator==(p) && NodeGraphPart::operator==(p);
  }

References DiGraph(), gum::ArcGraphPart::operator==(), and gum::NodeGraphPart::operator==().

Here is the call graph for this function:

◆ operator==() [3/3]

INLINE bool gum::NodeGraphPart::operator== ( const NodeGraphPart & p ) const

inherited

check whether two NodeGraphParts contain the same nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 356 of file nodeGraphPart_inl.h.

                                                                  {
    if (_boundVal_ != p._boundVal_) return false;
 
    if (_holes_)
      if (p._holes_) return (*_holes_ == *p._holes_);
      else return false;
    else if (p._holes_) return false;
 
    return true;
  }

References NodeGraphPart(), _boundVal_, and _holes_.

Referenced by gum::DiGraph::operator==(), gum::MixedGraph::operator==(), and gum::UndiGraph::operator==().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ parent() [1/2]

template<GUM_Numeric GUM_SCALAR>

Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::parent ( const Pattern & p )

Returns the parent of p in this DFSTree.

Definition at line 405 of file DFSTree_tpl.h.

                                                             {
        if (!_node_map_.existsSecond(const_cast< Pattern* >(&p))) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        }
        auto        node = _node_map_.first(const_cast< Pattern* >(&p));
        const auto& par  = DiGraph::parents(node);
        if (par.empty()) { GUM_ERROR(NotFound, "the given pattern is a root node") }
        return *(_node_map_.second(*(par.begin())));
      }

References _node_map_, GUM_ERROR, and gum::ArcGraphPart::parents().

Here is the call graph for this function:

◆ parent() [2/2]

template<GUM_Numeric GUM_SCALAR>

const Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::parent ( const Pattern & p ) const

Returns the parent of p in this DFSTree.

Definition at line 416 of file DFSTree_tpl.h.

                                                                         {
        if (!_node_map_.existsSecond(const_cast< Pattern* >(&p))) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree")
        }
        auto        node = _node_map_.first(const_cast< Pattern* >(&p));
        const auto& par  = DiGraph::parents(node);
        if (par.empty()) { GUM_ERROR(NotFound, "the given pattern is a root node") }
        return *(_node_map_.second(*(par.begin())));
      }

References _node_map_, GUM_ERROR, and gum::ArcGraphPart::parents().

Here is the call graph for this function:

◆ parents() [1/2]

INLINE NodeSet gum::ArcGraphPart::parents ( const NodeSet & ids ) const

inherited

returns the set of parents of a set of nodes

Definition at line 90 of file arcGraphPart_inl.h.

                                                               {
    NodeSet res;
    for (const auto node: ids)
      res += parents(node);
    return res;
  }

References parents().

Here is the call graph for this function:

◆ parents() [2/2]

INLINE const NodeSet & gum::ArcGraphPart::parents ( NodeId id ) const

inherited

returns the set of nodes with arc ingoing to a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is ingoing into the given node.

Parameters

id	the node toward which the arcs returned are pointing

Definition at line 76 of file arcGraphPart_inl.h.

                                                             {
    if (_parents_.exists(id)) return *(_parents_[id]);
    else return emptyNodeSet;
  }

References _parents_, and gum::emptyNodeSet.

◆ pattern() [1/2]

template<GUM_Numeric GUM_SCALAR>

Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::pattern ( NodeId id )

Returns the pattern represented by id in this DFSTree.

Definition at line 441 of file DFSTree_tpl.h.

                                                       {
        if (!_node_map_.existsFirst(id)) GUM_ERROR(NotFound, "no pattern matching the given id")
        return *(_node_map_.second(id));
      }

References _node_map_, and GUM_ERROR.

Referenced by _addChild_().

Here is the caller graph for this function:

◆ pattern() [2/2]

template<GUM_Numeric GUM_SCALAR>

const Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::pattern ( NodeId id ) const

Returns the pattern represented by id in this DFSTree.

Definition at line 447 of file DFSTree_tpl.h.

                                                                   {
        if (!_node_map_.existsFirst(id)) GUM_ERROR(NotFound, "no pattern matching the given id")
        return *(_node_map_.second(id));
      }

References _node_map_, and GUM_ERROR.

◆ populateNodes()

void gum::NodeGraphPart::populateNodes ( const NodeGraphPart & s )

inherited

populateNodes clears *this and fills it with the same nodes as "s"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

Parameters

s	the NodeGraphPart to be copied

Definition at line 97 of file nodeGraphPart.cpp.

                                                          {
    clear();   // "virtual" flush of the nodes set
    _holes_size_          = s._holes_size_;
    _holes_resize_policy_ = s._holes_resize_policy_;
 
    if (s._holes_) _holes_ = new NodeSet(*s._holes_);
 
    _names_ = s._cloneNames_();
 
    _boundVal_ = s._boundVal_;
 
    _updateEndIteratorSafe_();
  }

References NodeGraphPart(), _boundVal_, _cloneNames_(), _holes_, _holes_resize_policy_, _holes_size_, _names_, _updateEndIteratorSafe_(), and clear().

Referenced by operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ populateNodesFromProperty()

template<typename T>

void gum::NodeGraphPart::populateNodesFromProperty ( const NodeProperty< T > & h )

inherited

populateNodesFromProperty clears *this and fills it with the keys of "h"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

References NodeGraphPart(), addNode(), addNodes(), addNodeWithId(), asNodeSet(), begin(), beginSafe(), bound(), clear(), clearNodes(), dotNodeLabel(), empty(), emptyNodes(), end(), endSafe(), eraseNode(), exists(), existsNode(), hasName(), idFromName(), nameFromId(), nextNodeId(), nodes(), setName(), size(), sizeNodes(), and toString().

Here is the call graph for this function:

◆ roots() [1/2]

template<GUM_Numeric GUM_SCALAR>

std::list< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::roots ( )

Returns the list of root patterns in this DFSTree.

Definition at line 395 of file DFSTree_tpl.h.

                                                      {
        return _roots_;
      }

References _roots_.

Referenced by addRoot().

Here is the caller graph for this function:

◆ roots() [2/2]

template<GUM_Numeric GUM_SCALAR>

const std::list< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::roots ( ) const

Returns the list of root patterns in this DFSTree.

Definition at line 400 of file DFSTree_tpl.h.

                                                                  {
        return _roots_;
      }

References _roots_.

◆ setName()

void gum::NodeGraphPart::setName	(	NodeId	id,
		const std::string &	name )

inherited

sets the name of node id

Exceptions

DuplicateElement if name is already used by another node

Definition at line 170 of file nodeGraphPart.cpp.

                                                              {
    if (!existsNode(id)) GUM_ERROR(InvalidNode, "node " << id << " does not exist")
    if (_names_) {
      auto owner = _names_->tryFirst(name);
      if (owner.has_value()) {
        if (*owner != id)
          GUM_ERROR(DuplicateElement, "name '" << name << "' already used by node " << *owner)
        return;
      }
      if (_names_->existsFirst(id)) _names_->eraseFirst(id);
    } else {
      _names_ = std::make_unique< Bijection< NodeId, std::string > >();
    }
    _names_->insert(id, name);
  }

References _names_, existsNode(), and GUM_ERROR.

Referenced by gum::GraphicalModel::_nameNodes_(), gum::CausalModel< GUM_SCALAR >::causalDAG(), populateNodesFromProperty(), gum::EssentialGraph::skeleton(), and gum::CausalModel< GUM_ELEMENT >::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

INLINE Size gum::NodeGraphPart::size ( ) const

inherited

alias for sizeNodes

Definition at line 299 of file nodeGraphPart_inl.h.

299{ return sizeNodes(); }

References sizeNodes().

Referenced by gum::StaticTriangulation::StaticTriangulation(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::KTBNInference< GUM_SCALAR >::_compileWindow_(), gum::StaticTriangulation::_computeMaxPrimeJunctionTree_(), gum::StaticTriangulation::_computeRecursiveThinning_(), gum::OrderedEliminationSequenceStrategy::_isOrderNeeded_(), gum::StaticTriangulation::_triangulate_(), gum::BarrenNodesFinder::barrenNodes(), gum::PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded_(), nodesPropertyFromFunction(), nodesPropertyFromVal(), populateNodesFromProperty(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGmodel::size(), gum::EssentialGraph::size(), gum::MarkovBlanket::size(), gum::prm::gspan::Pattern::size(), gum::UGmodel::size(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sizeArcs()

INLINE Size gum::ArcGraphPart::sizeArcs ( ) const

inherited

indicates the number of arcs stored within the ArcGraphPart

Definition at line 58 of file arcGraphPart_inl.h.

58{ return _arcs_.size(); }

gum::Set::size

Size size() const noexcept

Returns the number of elements in the set.

Definition set_tpl.h:607

References _arcs_, and gum::Set< Key >::size().

Referenced by gum::DAGmodel::sizeArcs(), gum::EssentialGraph::sizeArcs(), gum::MarkovBlanket::sizeArcs(), and gum::prm::gspan::Pattern::sizeArcs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sizeNodes()

INLINE Size gum::NodeGraphPart::sizeNodes ( ) const

inherited

returns the number of nodes in the NodeGraphPart

Definition at line 295 of file nodeGraphPart_inl.h.

                                             {
    return (_holes_) ? (_boundVal_ - _holes_->size()) : _boundVal_;
  }

References _boundVal_, _holes_, and gum::Set< Key >::size().

Referenced by gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_(), asNodeSet(), gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), emptyNodes(), populateNodesFromProperty(), gum::EliminationSequenceStrategy::setGraph(), size(), gum::EssentialGraph::sizeNodes(), and gum::MarkovBlanket::sizeNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ strategy() [1/2]

template<GUM_Numeric GUM_SCALAR>

SearchStrategy< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::strategy ( )

strategy getter

Definition at line 504 of file DFSTree_tpl.h.

                                                                    {
        return *_strategy_;
      }

References _strategy_.

Referenced by DFSTree(), and addRoot().

Here is the caller graph for this function:

◆ strategy() [2/2]

template<GUM_Numeric GUM_SCALAR>

const SearchStrategy< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::strategy ( ) const

strategy getter

Definition at line 509 of file DFSTree_tpl.h.

                                                                                {
        return *_strategy_;
      }

References _strategy_.

◆ toDot()

std::string gum::DiGraph::toDot ( ) const

virtualinherited

to friendly display the content of the graph in the DOT syntax

Parameters

name	The graph name in the dot syntax. Default is G.

Returns: Returns a string describing the graph in the dot syntax

Reimplemented in gum::MixedGraph, gum::PDAG, and gum::prm::gspan::Pattern.

Definition at line 93 of file diGraph.cpp.

                                 {
    std::string strBuff = "digraph {\n";
 
    for (const auto node: nodes())
      strBuff += std::format("     {}{};\n", node, dotNodeLabel(node));
 
    strBuff += "\n";
 
    for (const auto& arc: arcs())
      strBuff += std::format("     {} -> {};\n", arc.tail(), arc.head());
 
    strBuff += "}\n\n";
    return strBuff;
  }

References gum::ArcGraphPart::arcs(), gum::NodeGraphPart::dotNodeLabel(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

◆ topologicalOrder()

INLINE Sequence< NodeId > gum::DiGraph::topologicalOrder ( ) const

inherited

Build and return a topological order.

Exceptions

InvalidDirectedCycle Raised if this DiGraph contains cycles.

Definition at line 131 of file diGraph_inl.h.

                                                            {
    return graph::topologicalOrder(*this);
  }

References gum::graph::topologicalOrder().

Referenced by gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), and gum::DAGmodel::topologicalOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toString()

std::string gum::DiGraph::toString ( ) const

overridevirtualinherited

to friendly display the content of the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 86 of file diGraph.cpp.

                                    {
    std::string s = NodeGraphPart::toString();
    s += " , ";
    s += ArcGraphPart::toString();
    return s;
  }

References gum::ArcGraphPart::toString(), and gum::NodeGraphPart::toString().

Referenced by gum::operator<<().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unvirtualizedEraseChildren()

INLINE void gum::ArcGraphPart::unvirtualizedEraseChildren ( NodeId id )

inherited

same function as eraseChildren but without any virtual call to an erase

Parameters

id	the node whose outgoing arcs will be removed

Definition at line 177 of file arcGraphPart_inl.h.

                                                                {
    if (_children_.exists(id)) {
      const NodeSet& children = *(_children_[id]);
 
      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(id, *iter));
      }
    }
  }

References gum::Arc::Arc(), _children_, gum::Set< Key >::beginSafe(), children(), gum::Set< Key >::endSafe(), and eraseArc().

Referenced by gum::DiGraph::eraseNode(), and gum::MixedGraph::eraseNode().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unvirtualizedEraseParents()

INLINE void gum::ArcGraphPart::unvirtualizedEraseParents ( NodeId id )

inherited

same function as eraseParents but without any virtual call to an erase

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 165 of file arcGraphPart_inl.h.

                                                               {
    if (_parents_.exists(id)) {
      const NodeSet& parents = *(_parents_[id]);
 
      for (auto iter = parents.beginSafe();   // safe iterator needed here
           iter != parents.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(*iter, id));
      }
    }
  }

References gum::Arc::Arc(), _parents_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), eraseArc(), and parents().

Referenced by gum::DiGraph::eraseNode(), and gum::MixedGraph::eraseNode().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unvirtualizedEraseSetOfArcs_()

INLINE void gum::ArcGraphPart::unvirtualizedEraseSetOfArcs_ ( const ArcSet & set )

protectedinherited

similar to eraseSetOfArcs_ except that it is unvirtualized

Warning: this function uses ArcGraphPart::eraseArc, hence, as compared with eraseSetOfArcs_, it removes the arcs without calling a virtual eraseArc

Definition at line 160 of file arcGraphPart_inl.h.

                                                                          {
    for (const auto& arc: set)
      ArcGraphPart::eraseArc(arc);
  }

References eraseArc().

Referenced by listMapArcs().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ _arcs_

Set< Arc > gum::ArcGraphPart::_arcs_

privateinherited

the set of all the arcs contained within the ArcGraphPart

Definition at line 281 of file arcGraphPart.h.

Referenced by ArcGraphPart(), ArcGraphPart(), ArcGraphPart(), addArc(), arcs(), clearArcs(), emptyArcs(), eraseArc(), existsArc(), operator=(), operator=(), operator==(), sizeArcs(), and toString().

◆ _children_

NodeProperty< NodeSet* > gum::ArcGraphPart::_children_

privateinherited

for each arc, the set of its children

Definition at line 287 of file arcGraphPart.h.

Referenced by ArcGraphPart(), ArcGraphPart(), _checkChildren_(), addArc(), children(), clearArcs(), eraseArc(), eraseChildren(), operator=(), operator=(), and unvirtualizedEraseChildren().

◆ _data_

template<GUM_Numeric GUM_SCALAR>

HashTable< Pattern*, PatternData* > gum::prm::gspan::DFSTree< GUM_SCALAR >::_data_

private

Data about patterns in this DFSTree.

Definition at line 277 of file DFSTree.h.

Referenced by ~DFSTree(), _addChild_(), _initialiaze_root_(), addRoot(), children(), children(), data(), data(), frequency(), growPattern(), iso_graph(), iso_map(), and max_indep_set().

◆ _graph_

template<GUM_Numeric GUM_SCALAR>

const InterfaceGraph< GUM_SCALAR >* gum::prm::gspan::DFSTree< GUM_SCALAR >::_graph_

private

The interface graph on which this DFSTree applies.

Definition at line 267 of file DFSTree.h.

Referenced by DFSTree(), addRoot(), and internalGraph().

◆ _node_map_

template<GUM_Numeric GUM_SCALAR>

Bijection< NodeId, Pattern* > gum::prm::gspan::DFSTree< GUM_SCALAR >::_node_map_

private

The mapping between nodes in this DFSTree and the patterns they represents.

Definition at line 274 of file DFSTree.h.

Referenced by _addChild_(), addRoot(), parent(), parent(), pattern(), and pattern().

◆ _parents_

NodeProperty< NodeSet* > gum::ArcGraphPart::_parents_

privateinherited

for each arc, the sets of its parents

Definition at line 284 of file arcGraphPart.h.

Referenced by ArcGraphPart(), ArcGraphPart(), _checkParents_(), addArc(), clearArcs(), eraseArc(), eraseParents(), existsArc(), operator=(), operator=(), parents(), and unvirtualizedEraseParents().

◆ _roots_

template<GUM_Numeric GUM_SCALAR>

std::list< NodeId > gum::prm::gspan::DFSTree< GUM_SCALAR >::_roots_

private

The list of root patterns in this DFSTree.

Definition at line 270 of file DFSTree.h.

Referenced by addRoot(), roots(), and roots().

◆ _strategy_

template<GUM_Numeric GUM_SCALAR>

SearchStrategy< GUM_SCALAR >* gum::prm::gspan::DFSTree< GUM_SCALAR >::_strategy_

private

The strategy used to prune the search tree.

Definition at line 280 of file DFSTree.h.

Referenced by DFSTree(), ~DFSTree(), growPattern(), strategy(), and strategy().

◆ onArcAdded

Signaler< NodeId, NodeId > gum::ArcGraphPart::onArcAdded

inherited

Definition at line 102 of file arcGraphPart.h.

Referenced by ArcGraphPart(), addArc(), operator=(), and operator=().

◆ onArcDeleted

Signaler< NodeId, NodeId > gum::ArcGraphPart::onArcDeleted

inherited

Definition at line 103 of file arcGraphPart.h.

Referenced by clearArcs(), and eraseArc().

◆ onNodeAdded

Signaler< NodeId > gum::NodeGraphPart::onNodeAdded

inherited

Definition at line 283 of file nodeGraphPart.h.

Referenced by addNode(), and addNodeWithId().

◆ onNodeDeleted

Signaler< NodeId > gum::NodeGraphPart::onNodeDeleted

inherited

Definition at line 284 of file nodeGraphPart.h.

Referenced by _clearNodes_(), and eraseNode().

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

agrum/PRM/gspan/DFSTree.h
agrum/PRM/gspan/DFSTree_tpl.h

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ArcIterator

◆ node_const_iterator

◆ node_const_iterator_safe

◆ node_iterator

◆ node_iterator_safe

◆ NodeConstIterator

◆ NodeConstIteratorSafe

◆ NodeIterator

◆ NodeIteratorSafe

Constructor & Destructor Documentation

◆ DFSTree()

◆ ~DFSTree()

Member Function Documentation

◆ _addChild_()

◆ _checkChildren_()

◆ _checkGrowth_()

◆ _checkParents_()

◆ _initialiaze_root_()

◆ _is_new_seq_()

◆ _test_equality_()

◆ addArc()

◆ addNode()

◆ addNodes()

◆ addNodeWithId()

◆ addRoot()

◆ ancestors()

◆ arcs()

◆ arcsProperty() [1/2]

◆ arcsProperty() [2/2]

◆ asNodeSet()

◆ begin()

◆ beginSafe()

◆ bound()

◆ children() [1/4]

◆ children() [2/4]

◆ children() [3/4]

◆ children() [4/4]

◆ clear()

◆ clearArcs()

◆ clearNodes()

◆ completeGraph()

◆ connectedComponents()

◆ data() [1/2]

◆ data() [2/2]

◆ descendants()

◆ directedPath()

◆ directedUnorientedPath()

◆ dotNodeLabel()

◆ empty()

◆ emptyArcs()

◆ emptyNodes()

◆ end()

◆ endSafe()

◆ eraseArc()

◆ eraseChildren()

◆ eraseNode()

◆ eraseParents()

◆ eraseSetOfArcs_()

◆ exists()

◆ existsArc() [1/2]

◆ existsArc() [2/2]

◆ existsNode()

◆ family() [1/2]

◆ family() [2/2]

◆ frequency()

◆ growPattern()

◆ hasDirectedPath()

◆ hasName()

◆ idFromName()

◆ internalGraph()

◆ iso_graph()

◆ iso_map()