aGrUM  0.13.2
gum::prm::gspan::DFSTree< GUM_SCALAR > Class Template Reference

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 >:

Public Member Functions

Constructor and destructor.
 DFSTree (const InterfaceGraph< GUM_SCALAR > &graph, SearchStrategy< GUM_SCALAR > *strategy=0)
 Default constructor. More...
 
 ~DFSTree ()
 Destructor. More...
 
DFSTree getters and setters.
const InterfaceGraph< GUM_SCALAR > & graph () const
 Returns the list of root patterns in this DFSTree. More...
 
std::list< NodeId > & roots ()
 Returns the list of root patterns in this DFSTree. More...
 
const std::list< NodeId > & roots () const
 Returns the list of root patterns in this DFSTree. More...
 
Patternparent (const Pattern &p)
 Returns the parent of p in this DFSTree. More...
 
const Patternparent (const Pattern &p) const
 Returns the parent of p in this DFSTree. More...
 
std::list< NodeId > & children (const Pattern &p)
 Returns the list of p children in this DFSTree. More...
 
const std::list< NodeId > & children (const Pattern &p) const
 Returns the list of p children in this DFSTree. More...
 
Patternpattern (NodeId id)
 Returns the pattern represented by id in this DFSTree. More...
 
const Patternpattern (NodeId id) const
 Returns the pattern represented by id in this DFSTree. More...
 
void addRoot (LabelData &data)
 Add a one edge Pattern in this DFSTree. More...
 
PatterngrowPattern (Pattern &p, EdgeGrowth< GUM_SCALAR > &edge_growth, Size min_freq)
 Add a one edge growth of p as one of its child. More...
 
Isomorphisms for patterns in this DFSTree.
UndiGraphiso_graph (const Pattern &p)
 Returns the isomorphism graph of p in the interface graph. More...
 
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. More...
 
Set< NodeId > & max_indep_set (const Pattern &p)
 Returns the maximal independent set of p isomorphism graph. More...
 
double frequency (const Pattern &p) const
 Returns the frequency of p respecting it's maximal independent set. More...
 
PatternDatadata (const Pattern &p)
 
const PatternDatadata (const Pattern &p) const
 
SearchStrategy< GUM_SCALAR > & strategy ()
 strategy getter More...
 
const SearchStrategy< GUM_SCALAR > & strategy () const
 strategy getter More...
 

Classes

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

Detailed Description

template<typename 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 68 of file DFSTree.h.

Member Typedef Documentation

Definition at line 78 of file arcGraphPart.h.

types for STL compliance

Definition at line 258 of file nodeGraphPart.h.

types for STL compliance

Definition at line 260 of file nodeGraphPart.h.

types for STL compliance

Definition at line 257 of file nodeGraphPart.h.

types for STL compliance

Definition at line 259 of file nodeGraphPart.h.

Definition at line 267 of file nodeGraphPart.h.

Definition at line 266 of file nodeGraphPart.h.

Constructor & Destructor Documentation

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

Default constructor.

Definition at line 372 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__strategy.

374  :
375  __graph(&graph),
377  GUM_CONSTRUCTOR(DFSTree);
378 
379  if (!__strategy) __strategy = new FrequenceSearch< GUM_SCALAR >(2);
380 
381  __strategy->setTree(this);
382  }
const InterfaceGraph< GUM_SCALAR > * __graph
The interface graph on which this DFSTree applies.
Definition: DFSTree.h:261
SearchStrategy< GUM_SCALAR > * __strategy
The strategy used to prune the search tree.
Definition: DFSTree.h:274
const InterfaceGraph< GUM_SCALAR > & graph() const
Returns the list of root patterns in this DFSTree.
Definition: DFSTree_tpl.h:497
SearchStrategy< GUM_SCALAR > & strategy()
strategy getter
Definition: DFSTree_tpl.h:527
DFSTree(const InterfaceGraph< GUM_SCALAR > &graph, SearchStrategy< GUM_SCALAR > *strategy=0)
Default constructor.
Definition: DFSTree_tpl.h:372
template<typename GUM_SCALAR >
gum::prm::gspan::DFSTree< GUM_SCALAR >::~DFSTree ( )

Destructor.

Definition at line 34 of file DFSTree_tpl.h.

34  {
35  GUM_DESTRUCTOR(DFSTree);
36 
37  for (const auto& elt : __data) {
38  delete elt.first;
39  delete elt.second;
40  }
41 
42  delete __strategy;
43  }
SearchStrategy< GUM_SCALAR > * __strategy
The strategy used to prune the search tree.
Definition: DFSTree.h:274
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
DFSTree(const InterfaceGraph< GUM_SCALAR > &graph, SearchStrategy< GUM_SCALAR > *strategy=0)
Default constructor.
Definition: DFSTree_tpl.h:372

Member Function Documentation

template<typename 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 158 of file DFSTree_tpl.h.

References gum::NodeGraphPart::addNode(), and gum::prm::gspan::Pattern::code().

159  {
160  // Adding child to the tree
161  NodeId node = DiGraph::addNode();
162  __node_map.insert(node, child);
163  // Adding child in p's children list
164  std::list< NodeId >& children = __data[&p]->children;
165 
166  if (children.empty()) {
167  children.push_back(node);
168  } else {
169  size_t size = children.size();
170 
171  for (std::list< NodeId >::iterator iter = children.begin();
172  iter != children.end();
173  ++iter) {
174  if (child->code() < pattern(*iter).code()) {
175  children.insert(iter, node);
176  break;
177  }
178  }
179 
180  if (size == children.size()) { children.push_back(node); }
181  }
182  }
std::list< NodeId > & children(const Pattern &p)
Returns the list of p children in this DFSTree.
Definition: DFSTree_tpl.h:426
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
DFSCode & code()
Returns the DFSCode of this Pattern.
Definition: pattern_inl.h:170
virtual NodeId addNode()
insert a new node and return its id
Size size() const
alias for sizeNodes
Pattern & pattern(NodeId id)
Returns the pattern represented by id in this DFSTree.
Definition: DFSTree_tpl.h:445
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268

+ Here is the call graph for this function:

template<typename 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 185 of file DFSTree_tpl.h.

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.

186  {
187  NodeId v = edge_growth.v;
188 
189  // First we check if the edge is legal
190  if (v == 0) { v = child->addNodeWithLabel(*(edge_growth.l_v)); }
191 
192  child->addArc(edge_growth.u, v, *(edge_growth.edge));
193  // Neighborhood restriction is checked by the Pattern class
194  EdgeCode& edge = child->edgeCode(edge_growth.u, v);
195 
196  // Then we check if the edge we added is valid
197  if (edge < *(child->code().codes.front())) {
198  GUM_ERROR(OperationNotAllowed,
199  "added edge code is lesser than the first "
200  "one in the pattern's DFSCode");
201  }
202 
203  if (edge.isBackward()) {
204  typedef std::vector< EdgeCode* >::iterator EdgeIter;
205 
206  for (EdgeIter iter = child->code().codes.begin();
207  (iter + 1) != child->code().codes.end();
208  ++iter) {
209  if ((((**iter).i == v) || ((**iter).j == v)) && edge < (**iter)) {
210  GUM_ERROR(
211  OperationNotAllowed,
212  "added backward edge is lesser than an existing edge on v");
213  }
214  }
215  }
216 
217  // Finally we check if child is minimal.
218  if (!child->isMinimal()) {
219  GUM_ERROR(OperationNotAllowed,
220  "the DFSCode for this growth is not minimal");
221  }
222  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

template<typename 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
pA Pattern.
seqA sequence of EdgeData<GUM_SCALAR>.

Definition at line 90 of file DFSTree_tpl.h.

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNode(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::exists(), gum::Set< Key, Alloc >::insert(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::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().

91  {
92  DFSTree< GUM_SCALAR >::PatternData* data = __data[p];
93  std::vector< NodeId > degree_list;
94 
95  for (auto iter = edge_seq.begin(); iter != edge_seq.end(); ++iter) {
96  const auto& edge = *iter;
97  Sequence< PRMInstance< GUM_SCALAR >* >* seq =
98  new Sequence< PRMInstance< GUM_SCALAR >* >();
99 
100  // Creating the multiset of instances matching p
101  bool u_first = (edge->l_u->id < edge->l_v->id);
102  seq->insert((u_first) ? edge->u : edge->v);
103  seq->insert((!u_first) ? edge->u : edge->v);
104 
105  NodeId an_id = data->iso_graph.addNode();
106  data->iso_map.insert(an_id, seq);
107  degree_list.push_back(an_id);
108 
109  // Adding edges between two isomorphisms of p sharing at least one
110  // instance
111  for (const auto& elt : data->iso_map)
112  if (elt.first != an_id)
113  for (auto iter = elt.second->begin(); iter != elt.second->end();
114  ++iter)
115  if (seq->exists(*iter)) {
116  data->iso_graph.addEdge(an_id, elt.first);
117  break;
118  }
119  }
120 
121  // Computing p->max_indep_set using a greedy algorithm
122  DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
123  std::sort(degree_list.begin(), degree_list.end(), my_operator);
124  Set< NodeId > removed;
125 
126  for (const auto node : degree_list) {
127  if (!removed.exists(node)) {
128  removed.insert(node);
129 
130  for (const auto neighbor : data->iso_graph.neighbours(node))
131  removed.insert(neighbor);
132 
133  data->max_indep_set.insert(node);
134  }
135  }
136  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
PatternData & data(const Pattern &p)
Definition: DFSTree_tpl.h:516
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613

+ Here is the call graph for this function:

template<typename 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 139 of file DFSTree_tpl.h.

141  {
142  for (const auto& elt : iso_map) {
143  bool found = false;
144 
145  for (const auto& inst : seq)
146  if (!(elt.second->exists(inst))) {
147  found = true;
148  break;
149  }
150 
151  if (!found) { return false; }
152  }
153 
154  return true;
155  }
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 ma...
Definition: DFSTree_tpl.h:473
template<typename 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 339 of file DFSTree_tpl.h.

341  {
342  try {
343  for (const auto& elt : x)
344  if (y[elt.first] != elt.second) return false;
345  } catch (NotFound&) { return false; }
346 
347  return true;
348  }
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 88 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::eraseArc().

88  {
89  for (const auto arc : set)
90  eraseArc(arc);
91  }
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart

+ Here is the call graph for this function:

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 121 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::eraseArc().

121  {
122  for (const auto& arc : set)
124  }
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart

+ Here is the call graph for this function:

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

insert a new arc into the directed graph

Parameters
tailthe id of the tail of the new inserted arc
headthe 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
InvalidNodeif head or tail does not belong to the graph nodes

Reimplemented from gum::ArcGraphPart.

Reimplemented in gum::DAG.

Definition at line 32 of file diGraph_inl.h.

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

Referenced by gum::EssentialGraph::__buildEssentialGraph(), gum::MarkovBlanket::__buildMarkovBlanket(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_latents(), gum::learning::Miic::_orientation_miic(), gum::learning::Miic::_propagatesHead(), gum::prm::gspan::Pattern::addArc(), gum::DAG::addArc(), and gum::DAGCycleDetector::addArc().

32  {
33  if (!exists(head)) { GUM_ERROR(InvalidNode, "head node"); }
34 
35  if (!exists(tail)) { GUM_ERROR(InvalidNode, "tail node"); }
36 
37  ArcGraphPart::addArc(tail, head);
38  }
virtual void addArc(const NodeId tail, const NodeId head)
insert a new arc into the ArcGraphPart
bool exists(const NodeId id) const
alias for existsNode
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 247 of file nodeGraphPart_inl.h.

References GUM_EMIT1.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::__addChild(), gum::prm::StructuredInference< GUM_SCALAR >::__addEdgesInReducedGraph(), gum::prm::o3prm::O3InterfaceFactory< GUM_SCALAR >::__addInterface2Dag(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::__addNode(), gum::prm::o3prm::O3TypeFactory< GUM_SCALAR >::__addTypes2Dag(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__buildPatternGraph(), gum::prm::StructuredInference< GUM_SCALAR >::__buildPatternGraph(), gum::prm::o3prm::O3ClassFactory< GUM_SCALAR >::__checkAndAddNodesToDag(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::gspan::DFSTree< GUM_SCALAR >::__initialiaze_root(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_insertNode(), gum::prm::PRMSystem< GUM_SCALAR >::add(), gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::clear(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::IncrementalGraphLearner(), gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::insert(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::MultiDimFunctionGraph(), and gum::LeafAggregator::update().

247  {
248  NodeId newNode;
249 
250  // fill the first hole if holes exist
251  if (__holes && (!__holes->empty())) {
252  newNode = *(__holes->begin());
253  __eraseHole(newNode);
254  } else {
255  newNode = __boundVal;
256  ++__boundVal;
258  }
259 
260  GUM_EMIT1(onNodeAdded, newNode);
261 
262  return newNode;
263  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
#define GUM_EMIT1(signal, arg1)
Definition: signaler1.h:40
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
iterator begin() const
The usual unsafe begin iterator to parse the set.
Definition: set_tpl.h:517
void __updateEndIteratorSafe()
updating endIterator (always at __max+1)
Signaler1< NodeId > onNodeAdded
void __eraseHole(NodeId id)
to delete hole.

+ Here is the caller graph for this function:

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

insert n nodes

Parameters
nthe number of nodes to add
Returns
the vector of chosen ids

Definition at line 265 of file nodeGraphPart_inl.h.

265  {
266  std::vector< NodeId > v;
267  v.reserve(N);
268  for (Idx i = 0; i < N; i++)
269  v.push_back(this->addNode());
270  return v;
271  }
unsigned long Idx
Type for indexes.
Definition: types.h:43
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
DuplicateElementexception if the id already exists

Definition at line 126 of file nodeGraphPart.cpp.

References gum::NodeGraphPart::__boundVal, gum::NodeGraphPart::__eraseHole(), gum::NodeGraphPart::__holes, gum::NodeGraphPart::__inHoles(), gum::NodeGraphPart::__updateEndIteratorSafe(), GUM_EMIT1, GUM_ERROR, gum::Set< Key, Alloc >::insert(), and gum::NodeGraphPart::onNodeAdded.

Referenced by gum::prm::PRMClass< GUM_SCALAR >::__addCastDescendants(), gum::prm::PRMInterface< GUM_SCALAR >::__addCastDescendants(), gum::EssentialGraph::__buildEssentialGraph(), gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__computeInAComponent(), gum::prm::PRMClass< GUM_SCALAR >::__implementInterfaces(), gum::prm::PRMInterface< GUM_SCALAR >::__inheritInterface(), gum::learning::genericBNLearner::__learnDAG(), gum::prm::PRMInterface< GUM_SCALAR >::__overloadAttribute(), gum::prm::PRMClass< GUM_SCALAR >::__overloadAttribute(), gum::learning::genericBNLearner::__prepare_miic_3off2(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::InfluenceDiagram< GUM_SCALAR >::_addNode(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::prm::PRMInterface< GUM_SCALAR >::add(), gum::prm::PRMClass< GUM_SCALAR >::add(), gum::BayesNet< GUM_SCALAR >::add(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::prm::PRMClass< GUM_SCALAR >::inheritAggregates(), gum::prm::PRMClass< GUM_SCALAR >::inheritAttributes(), gum::prm::PRMClass< GUM_SCALAR >::inheritParameters(), gum::prm::PRMClass< GUM_SCALAR >::inheritReferenceSlots(), gum::prm::PRMClass< GUM_SCALAR >::inheritSlotChains(), gum::BayesNetFragment< GUM_SCALAR >::installNode(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph(), gum::learning::Miic::learnStructure(), gum::UndiGraph::partialUndiGraph(), and gum::learning::StructuralConstraintDAG::StructuralConstraintDAG().

126  {
127  if (id >= __boundVal) {
128  if (id > __boundVal) { // we have to add holes
129  if (!__holes) __holes = new NodeSet();
130 
131  for (NodeId i = __boundVal; i < id; ++i)
132  __holes->insert(i);
133  }
134 
135  __boundVal = id + 1;
136 
138  } else {
139  if (__inHoles(id)) { // we fill a hole
140  __eraseHole(id);
141  } else {
142  GUM_ERROR(DuplicateElement, "Id " << id << " is already used");
143  }
144  }
145 
146  GUM_EMIT1(onNodeAdded, id);
147  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
#define GUM_EMIT1(signal, arg1)
Definition: signaler1.h:40
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __inHoles(NodeId id) const
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
void __updateEndIteratorSafe()
updating endIterator (always at __max+1)
Signaler1< NodeId > onNodeAdded
void __eraseHole(NodeId id)
to delete hole.
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

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

Add a one edge Pattern in this DFSTree.

Parameters
dataData 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 46 of file DFSTree_tpl.h.

References gum::prm::gspan::Pattern::addArc(), gum::NodeGraphPart::addNode(), gum::prm::gspan::Pattern::addNodeWithLabel(), and gum::HashTable< Key, Val, Alloc >::insert().

46  {
47  HashTable< Pattern*, std::pair< Idx, Idx > > roots;
48  HashTable< Pattern*, Sequence< EdgeData< GUM_SCALAR >* >* > roots_edges;
49 
50  for (const auto edge : __graph->edges(&label)) {
51  bool u_first = (edge->l_u->id < edge->l_v->id);
52  Idx u_idx = (u_first) ? edge->l_u->id : edge->l_v->id;
53  Idx v_idx = (!u_first) ? edge->l_u->id : edge->l_v->id;
54 
55  bool found = false;
56 
57  for (const auto& elt : roots)
58  if ((elt.second.first == u_idx) && (elt.second.second == v_idx)) {
59  roots_edges[elt.first]->insert(edge);
60  found = true;
61  break;
62  }
63 
65  if (!found) {
66  Pattern* p = new Pattern();
67  roots.insert(p, std::make_pair(u_idx, v_idx));
68  roots_edges.insert(p, new Sequence< EdgeData< GUM_SCALAR >* >());
69  roots_edges[p]->insert(edge);
70  DFSTree< GUM_SCALAR >::PatternData* data =
71  new DFSTree< GUM_SCALAR >::PatternData(p);
72  NodeId u = p->addNodeWithLabel((u_first) ? *edge->l_u : *edge->l_v);
73  NodeId v = p->addNodeWithLabel((!u_first) ? *edge->l_u : *edge->l_v);
74  p->addArc(u, v, label);
75  __node_map.insert(DiGraph::addNode(), p);
76  __data.insert(p, data);
77  __roots.push_back(__node_map.first(p));
78  }
79  }
80 
81  // This is used to compute the max independent set of p->max_indep_set
82  for (const auto& elt : roots_edges) {
83  __initialiaze_root(elt.first, *elt.second);
84  strategy().accept_root(elt.first);
85  delete elt.second;
86  }
87  }
const InterfaceGraph< GUM_SCALAR > * __graph
The interface graph on which this DFSTree applies.
Definition: DFSTree.h:261
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
std::list< NodeId > __roots
The list of root patterns in this DFSTree.
Definition: DFSTree.h:264
virtual NodeId addNode()
insert a new node and return its id
std::list< NodeId > & roots()
Returns the list of root patterns in this DFSTree.
Definition: DFSTree_tpl.h:385
SearchStrategy< GUM_SCALAR > & strategy()
strategy getter
Definition: DFSTree_tpl.h:527
void __initialiaze_root(Pattern *p, Sequence< EdgeData< GUM_SCALAR > * > &seq)
This initialize the DSFTree with a new root.
Definition: DFSTree_tpl.h:90
PatternData & data(const Pattern &p)
Definition: DFSTree_tpl.h:516
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268
unsigned long Idx
Type for indexes.
Definition: types.h:43

+ Here is the call graph for this function:

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

returns the set of arcs stored within the ArcGraphPart

Definition at line 36 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs.

Referenced by gum::MarkovBlanket::arcs(), gum::EssentialGraph::arcs(), gum::DAGmodel::arcs(), gum::prm::gspan::Pattern::arcs(), and gum::DiGraph::toDot().

36 { return __arcs; }
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the caller graph for this function:

template<typename VAL >
ArcProperty< VAL > gum::ArcGraphPart::arcsProperty ( VAL(*)(const Arc &)  f,
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
fa function assigning a VAL to any arc
sizean 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.
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
athe default value assigned to each arc in the returned Property
sizean 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.
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())
rather than
for(const auto n : asNodeSet())
as this is faster and consumes much less memory.

Definition at line 355 of file nodeGraphPart_inl.h.

References gum::Set< Key, Alloc >::insert().

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::getPartialTemporalOrder().

355  {
356  NodeSet son(sizeNodes());
357 
358  if (!empty()) {
359  for (NodeId n = 0; n < __boundVal; ++n) {
360  if (!__inHoles(n)) son.insert(n);
361  }
362  }
363 
364  return son;
365  }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __inHoles(NodeId id) const
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
bool empty() const
alias for emptyNodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Definition at line 327 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), and gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot().

327  {
328  NodeGraphPartIterator it(*this);
329  it._validate(); // stop the iterator at the first not-in-holes
330  return it;
331  }
friend class NodeGraphPartIterator

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Definition at line 313 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

313  {
314  NodeGraphPartIteratorSafe it(*this);
315  it._validate(); // stop the iterator at the first not-in-holes
316  return it;
317  }
friend class NodeGraphPartIteratorSafe

+ Here is the call graph for this function:

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

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

Definition at line 302 of file nodeGraphPart_inl.h.

Referenced by gum::NodeGraphPart::__clearNodes(), gum::StaticTriangulation::__computeEliminationTree(), gum::NodeGraphPartIterator::_setPos(), and gum::NodeGraphPartIterator::_validate().

302 { return __boundVal; }
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE 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 426 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, and GUM_ERROR.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::children().

426  {
427  try {
428  return __data[const_cast< Pattern* >(&p)]->children;
429  } catch (NotFound&) {
430  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
431  }
432  }
std::list< NodeId > & children(const Pattern &p)
Returns the list of p children in this DFSTree.
Definition: DFSTree_tpl.h:426
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE 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 436 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, gum::prm::gspan::DFSTree< GUM_SCALAR >::children(), and GUM_ERROR.

436  {
437  try {
438  return __data[const_cast< Pattern* >(&p)]->children;
439  } catch (NotFound&) {
440  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
441  }
442  }
std::list< NodeId > & children(const Pattern &p)
Returns the list of p children in this DFSTree.
Definition: DFSTree_tpl.h:426
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

INLINE const NodeSet & gum::ArcGraphPart::children ( const 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
idthe node which is the tail of the arcs returned

Definition at line 59 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__checkChildren(), and gum::ArcGraphPart::__children.

Referenced by gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__AR(), gum::EssentialGraph::__buildEssentialGraph(), gum::prm::PRMClass< GUM_SCALAR >::__checkInterface(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__connect(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__directedPath(), gum::prm::gspan::Pattern::__expandCodeIsMinimal(), gum::DAG::__hasDirectedPath(), gum::IBayesNet< GUM_SCALAR >::__minimalCondSetVisitDn(), gum::IBayesNet< GUM_SCALAR >::__minimalCondSetVisitUp(), gum::prm::gspan::Pattern::__not_rec(), gum::prm::PRMClass< GUM_SCALAR >::__overloadReference(), gum::prm::gspan::Pattern::__rec(), gum::InfluenceDiagram< GUM_SCALAR >::_getChildrenDecision(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::_initialize(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::_makeInferenceNodeToNeighbours(), gum::ArcGraphPart::ArcGraphPart(), gum::MarkovBlanket::children(), gum::EssentialGraph::children(), gum::DAGmodel::children(), gum::ArcGraphPart::directedUnorientedPath(), gum::InfluenceDiagram< GUM_SCALAR >::erase(), gum::ArcGraphPart::eraseChildren(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), gum::prm::gspan::Pattern::isMinimal(), gum::IBayesNet< GUM_SCALAR >::minimalCondSet(), gum::MixedGraph::mixedUnorientedPath(), gum::BayesBall::relevantPotentials(), gum::dSeparation::relevantPotentials(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparation::requisiteNodes(), gum::MarkovBlanket::toDot(), gum::EssentialGraph::toDot(), gum::InfluenceDiagram< GUM_SCALAR >::toDot(), gum::MixedGraph::toDot(), and gum::ArcGraphPart::unvirtualizedEraseChildren().

59  {
60  __checkChildren(id);
61  return *(__children[id]);
62  }
void __checkChildren(const NodeId id) const
when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set ent...
NodeProperty< NodeSet * > __children
for each arc, the set of its children
Definition: arcGraphPart.h:272

+ Here is the call graph for this function:

INLINE void gum::DiGraph::clear ( )
virtualinherited

removes all the nodes and arcs from the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 40 of file diGraph_inl.h.

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

Referenced by gum::DiGraph::operator=().

40  {
43  }
void clearArcs()
removes all the arcs from the ArcGraphPart
virtual void clearNodes()
remove all the nodes from the NodeGraphPart

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void gum::ArcGraphPart::clearArcs ( )
inherited

removes all the arcs from the ArcGraphPart

Definition at line 76 of file arcGraphPart.cpp.

References gum::ArcGraphPart::__arcs, gum::ArcGraphPart::__children, gum::ArcGraphPart::__parents, gum::Set< Key, Alloc >::clear(), GUM_EMIT2, and gum::ArcGraphPart::onArcDeleted.

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

76  {
77  for (const auto& elt : __parents)
78  delete elt.second;
79 
80  __parents.clear();
81 
82  for (const auto& elt : __children)
83  delete elt.second;
84 
85  __children.clear();
86 
87  // we need this copy only if at least one onArcDeleted listener exists
88  if (onArcDeleted.hasListener()) {
89  ArcSet tmp = __arcs;
90  __arcs.clear();
91 
92  for (const auto& arc : tmp)
93  GUM_EMIT2(onArcDeleted, arc.tail(), arc.head());
94  } else {
95  __arcs.clear();
96  }
97  }
Set< Arc > ArcSet
Some typdefs and define for shortcuts ...
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269
NodeProperty< NodeSet * > __children
for each arc, the set of its children
Definition: arcGraphPart.h:272
Signaler2< NodeId, NodeId > onArcDeleted
Definition: arcGraphPart.h:81
void clear()
Removes all the elements, if any, from the set.
Definition: set_tpl.h:375
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

INLINE void gum::NodeGraphPart::clearNodes ( )
virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 304 of file nodeGraphPart_inl.h.

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

304 { __clearNodes(); }
void __clearNodes()
code for clearing nodes (called twice)

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data ( const Pattern p)
Parameters
pThe pattern

Definition at line 516 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data.

516  {
517  return *(__data[const_cast< Pattern* >(&p)]);
518  }
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
template<typename GUM_SCALAR >
INLINE const DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data ( const Pattern p) const
Parameters
pThe pattern

Definition at line 522 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data.

522  {
523  return *(__data[const_cast< Pattern* >(&p)]);
524  }
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
const std::vector< NodeId > gum::ArcGraphPart::directedPath ( const NodeId  node1,
const NodeId  node2 
) const
inherited

returns a directed path from node1 to node2 belonging to the set of arcs

Parameters
node1the id from which the path begins
node2the id to which the path ends
Exceptions
NotFoundexception is raised if no path can be found between the two nodes

Definition at line 152 of file arcGraphPart.cpp.

References gum::List< Val, Alloc >::empty(), gum::HashTable< Key, Val, Alloc >::exists(), gum::List< Val, Alloc >::front(), GUM_ERROR, gum::HashTable< Key, Val, Alloc >::insert(), gum::ArcGraphPart::parents(), gum::List< Val, Alloc >::popFront(), and gum::List< Val, Alloc >::pushBack().

Referenced by gum::learning::Miic::_orientation_latents().

153  {
154  // not recursive version => use a FIFO for simulating the recursion
155  List< NodeId > nodeFIFO;
156  nodeFIFO.pushBack(n2);
157 
158  // mark[node] = successor if visited, else mark[node] does not exist
159  NodeProperty< NodeId > mark;
160  mark.insert(n2, n2);
161 
162  NodeId current;
163 
164  while (!nodeFIFO.empty()) {
165  current = nodeFIFO.front();
166  nodeFIFO.popFront();
167 
168  // check the parents
169 
170  for (const auto new_one : parents(current)) {
171  if (mark.exists(new_one)) // if this node is already marked, do not
172  continue; // check it again
173 
174  mark.insert(new_one, current);
175 
176  if (new_one == n1) {
177  std::vector< NodeId > v;
178 
179  for (current = n1; current != n2; current = mark[current])
180  v.push_back(current);
181 
182  v.push_back(n2);
183 
184  return v;
185  }
186 
187  nodeFIFO.pushBack(new_one);
188  }
189  }
190 
191  GUM_ERROR(NotFound, "no path found");
192  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

const std::vector< NodeId > gum::ArcGraphPart::directedUnorientedPath ( const NodeId  node1,
const NodeId  node2 
) const
inherited

returns an unoriented (directed) path from node1 to node2 in the arc set

Parameters
node1the id from which the path begins
node2the id to which the path ends
Exceptions
NotFoundexception is raised if no path can be found between the two nodes

Definition at line 195 of file arcGraphPart.cpp.

References gum::ArcGraphPart::children(), gum::List< Val, Alloc >::empty(), gum::HashTable< Key, Val, Alloc >::exists(), gum::List< Val, Alloc >::front(), GUM_ERROR, gum::HashTable< Key, Val, Alloc >::insert(), gum::ArcGraphPart::parents(), gum::List< Val, Alloc >::popFront(), and gum::List< Val, Alloc >::pushBack().

195  {
196  // not recursive version => use a FIFO for simulating the recursion
197  List< NodeId > nodeFIFO;
198  nodeFIFO.pushBack(n2);
199 
200  // mark[node] = successor if visited, else mark[node] does not exist
201  NodeProperty< NodeId > mark;
202  mark.insert(n2, n2);
203 
204  NodeId current;
205 
206  while (!nodeFIFO.empty()) {
207  current = nodeFIFO.front();
208  nodeFIFO.popFront();
209 
210  // check the parents
211  for (const auto new_one : parents(current)) {
212  if (mark.exists(new_one)) // the node has already been visited
213  continue;
214 
215  mark.insert(new_one, current);
216 
217  if (new_one == n1) {
218  std::vector< NodeId > v;
219 
220  for (current = n1; current != n2; current = mark[current])
221  v.push_back(current);
222 
223  v.push_back(n2);
224 
225  return v;
226  }
227 
228  nodeFIFO.pushBack(new_one);
229  }
230 
231  // check the children
232  for (const auto new_one : children(current)) {
233  if (mark.exists(new_one)) // the node has already been visited
234  continue;
235 
236  mark.insert(new_one, current);
237 
238  if (new_one == n1) {
239  std::vector< NodeId > v;
240 
241  for (current = n1; current != n2; current = mark[current])
242  v.push_back(current);
243 
244  v.push_back(n2);
245 
246  return v;
247  }
248 
249  nodeFIFO.pushBack(new_one);
250  }
251  }
252 
253  GUM_ERROR(NotFound, "no path found");
254  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

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

alias for emptyNodes

Definition at line 300 of file nodeGraphPart_inl.h.

Referenced by gum::prm::gspan::Pattern::remove().

300 { return emptyNodes(); }
bool emptyNodes() const
indicates whether there exists nodes in the NodeGraphPart

+ Here is the caller graph for this function:

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

indicates wether the ArcGraphPart contains any arc

Definition at line 32 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs, and gum::Set< Key, Alloc >::empty().

32 { return __arcs.empty(); }
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the call graph for this function:

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

indicates whether there exists nodes in the NodeGraphPart

Definition at line 298 of file nodeGraphPart_inl.h.

298 { return (sizeNodes() == 0); }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
INLINE const NodeGraphPartIterator & gum::NodeGraphPart::end ( ) const
noexceptinherited

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

Definition at line 333 of file nodeGraphPart_inl.h.

Referenced by gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot().

333  {
334  return __endIteratorSafe;
335  }
NodeGraphPartIteratorSafe __endIteratorSafe
the end iterator (used to speed-up parsings of the NodeGraphPart)

+ Here is the caller graph for this function:

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

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

Definition at line 323 of file nodeGraphPart_inl.h.

323  {
324  return __endIteratorSafe;
325  }
NodeGraphPartIteratorSafe __endIteratorSafe
the end iterator (used to speed-up parsings of the NodeGraphPart)
INLINE void gum::ArcGraphPart::eraseArc ( const Arc arc)
virtualinherited

removes an arc from the ArcGraphPart

Parameters
arcthe 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 76 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs, gum::ArcGraphPart::__children, gum::ArcGraphPart::__parents, gum::Set< Key, Alloc >::erase(), gum::ArcGraphPart::existsArc(), GUM_EMIT2, gum::Arc::head(), gum::ArcGraphPart::onArcDeleted, and gum::Arc::tail().

Referenced by gum::EssentialGraph::__buildEssentialGraph(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::learning::genericBNLearner::__learnDAG(), gum::ArcGraphPart::_eraseSetOfArcs(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_latents(), gum::learning::Miic::_orientation_miic(), gum::BayesNetFragment< GUM_SCALAR >::_uninstallArc(), gum::ArcGraphPart::_unvirtualizedEraseSetOfArcs(), gum::DAGCycleDetector::eraseArc(), gum::InfluenceDiagram< GUM_SCALAR >::eraseArc(), gum::BayesNet< GUM_SCALAR >::eraseArc(), gum::ArcGraphPart::eraseChildren(), gum::ArcGraphPart::eraseParents(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), gum::prm::gspan::Pattern::pop_back(), gum::BayesNet< GUM_SCALAR >::reverseArc(), gum::ArcGraphPart::unvirtualizedEraseChildren(), and gum::ArcGraphPart::unvirtualizedEraseParents().

76  {
77  // ASSUMING tail and head exists in __parents anf __children
78  // (if not, it is an error)
79  if (existsArc(arc)) {
80  NodeId tail = arc.tail(), head = arc.head();
81  __parents[head]->erase(tail);
82  __children[tail]->erase(head);
83  __arcs.erase(arc);
84  GUM_EMIT2(onArcDeleted, tail, head);
85  }
86  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
void erase(const Key &k)
Erases an element from the set.
Definition: set_tpl.h:656
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269
bool existsArc(const Arc &arc) const
indicates whether a given arc exists
NodeProperty< NodeSet * > __children
for each arc, the set of its children
Definition: arcGraphPart.h:272
Signaler2< NodeId, NodeId > onArcDeleted
Definition: arcGraphPart.h:81
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

removes all the children of a given node

Parameters
idthe 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 107 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__children, gum::Set< Key, Alloc >::beginSafe(), gum::ArcGraphPart::children(), gum::Set< Key, Alloc >::endSafe(), and gum::ArcGraphPart::eraseArc().

107  {
108  if (__children.exists(id)) {
109  NodeSet& children = *(__children[id]);
110 
111  for (auto iter = children.beginSafe(); // safe iterator needed here
112  iter != children.endSafe();
113  ++iter) {
114  // warning: use this erase so that you actually use the vritualized
115  // arc removal function
116  eraseArc(Arc(id, *iter));
117  }
118  }
119  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
NodeProperty< NodeSet * > __children
for each arc, the set of its children
Definition: arcGraphPart.h:272

+ Here is the call graph for this function:

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

remove a node and its adjacent arcs from the graph

Parameters
idthe 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 66 of file diGraph_inl.h.

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

Referenced by gum::prm::PRMClass< GUM_SCALAR >::__checkInterface(), gum::prm::PRMClass< GUM_SCALAR >::__checkRefInterface(), gum::BarrenNodesFinder::barrenNodes(), gum::BayesNet< GUM_SCALAR >::erase(), gum::InfluenceDiagram< GUM_SCALAR >::erase(), gum::prm::gspan::Pattern::pop_back(), gum::prm::gspan::Pattern::remove(), and gum::BayesNetFragment< GUM_SCALAR >::uninstallNode().

66  {
67  // warning: to remove the arcs adjacent to id, use the unvirtualized
68  // versions
69  // of arc removals
72 
74  }
void unvirtualizedEraseChildren(const NodeId id)
same function as eraseChildren but without any virtual call to an erase
void unvirtualizedEraseParents(const NodeId id)
same function as eraseParents but without any virtual call to an erase
virtual void eraseNode(const NodeId id)
erase the node with the given id

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

erase all the parents of a given node

Parameters
idthe 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 93 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__parents, gum::Set< Key, Alloc >::beginSafe(), gum::Set< Key, Alloc >::endSafe(), gum::ArcGraphPart::eraseArc(), and gum::ArcGraphPart::parents().

Referenced by gum::prm::PRMClass< GUM_SCALAR >::__overloadAttribute().

93  {
94  if (__parents.exists(id)) {
95  NodeSet& parents = *(__parents[id]);
96 
97  for (auto iter = parents.beginSafe(); // safe iterator needed here
98  iter != parents.endSafe();
99  ++iter) {
100  // warning: use this erase so that you actually use the virtualized
101  // arc removal function
102  eraseArc(Arc(*iter, id));
103  }
104  }
105  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

INLINE bool gum::NodeGraphPart::exists ( const NodeId  id) const
inherited
INLINE bool gum::ArcGraphPart::existsArc ( const Arc arc) const
inherited

indicates whether a given arc exists

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

Definition at line 38 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs, and gum::Set< Key, Alloc >::contains().

Referenced by gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__AorR(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__AR(), gum::MarkovBlanket::__buildMarkovBlanket(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__connect(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__directedPath(), gum::learning::Miic::__existsDirectedPath(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__jump_multi(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__jump_poly(), gum::prm::gspan::Pattern::__not_rec(), gum::prm::gspan::Pattern::__rec(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_latents(), gum::learning::Miic::_orientation_miic(), gum::learning::Miic::_updateProbaTriples(), gum::prm::PRMClass< GUM_SCALAR >::addArc(), gum::DAGCycleDetector::addArc(), gum::ArcGraphPart::eraseArc(), gum::DAGCycleDetector::eraseArc(), gum::InfluenceDiagram< GUM_SCALAR >::eraseArc(), gum::prm::gspan::Pattern::exists(), and gum::BayesNet< GUM_SCALAR >::reverseArc().

38  {
39  return __arcs.contains(arc);
40  }
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:581
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

indicates whether a given arc exists

Parameters
tailthe tail of the arc we test the existence in the ArcGraphPart
headthe head of the arc we test the existence in the ArcGraphPart

Definition at line 42 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__parents.

42  {
43  return __parents.exists(head) && __parents[head]->exists(tail);
44  }
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269
INLINE bool gum::NodeGraphPart::existsNode ( const NodeId  id) const
inherited
template<typename GUM_SCALAR >
INLINE double gum::prm::gspan::DFSTree< GUM_SCALAR >::frequency ( const Pattern p) const

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

Parameters
pThe pattern

Definition at line 510 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, gum::prm::gspan::DFSTree< GUM_SCALAR >::max_indep_set(), and gum::Set< Key, Alloc >::size().

510  {
511  return (double)__data[const_cast< Pattern* >(&p)]->max_indep_set.size();
512  }
Set< NodeId > & max_indep_set(const Pattern &p)
Returns the maximal independent set of p isomorphism graph.
Definition: DFSTree_tpl.h:487
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE const InterfaceGraph< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::graph ( ) const

Returns the list of root patterns in this DFSTree.

Definition at line 497 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__graph.

497  {
498  return *__graph;
499  }
const InterfaceGraph< GUM_SCALAR > * __graph
The interface graph on which this DFSTree applies.
Definition: DFSTree.h:261
template<typename 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
pThe Pattern from which a one edge growth is spawned.
edge_growthThe data about the edge growth of p.
min_freqminimum number of occurrence to be used as a pattern
Exceptions
FatalErrorRaised if the grow is an illegal backedge growth.
OperationNotAllowedRaised if the grow is found to be not minimal.

Definition at line 225 of file DFSTree_tpl.h.

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNode(), gum::prm::gspan::Pattern::code(), gum::prm::gspan::DFSCode::codes, GUM_ERROR, gum::Set< Key, Alloc >::insert(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::insert(), gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::iso_graph, gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::iso_map, gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::matches, gum::prm::gspan::DFSTree< GUM_SCALAR >::PatternData::max_indep_set, gum::EdgeGraphPart::neighbours(), gum::NodeGraphPart::nodes(), and gum::NodeGraphPart::size().

226  {
227  Pattern* child = new Pattern(p);
228 
229  try {
230  __checkGrowth(p, child, edge_growth);
231  } catch (OperationNotAllowed&) {
232  delete child;
233  throw;
234  }
235 
236  // Now we need to build the pattern data about child
237  DFSTree< GUM_SCALAR >::PatternData* data =
238  new DFSTree< GUM_SCALAR >::PatternData(child);
239  std::vector< NodeId > degree_list;
240  NodeProperty< Sequence< PRMInstance< GUM_SCALAR >* >* >& p_iso_map =
241  __data[&p]->iso_map;
242  typename NodeProperty<
243  std::pair< PRMInstance< GUM_SCALAR >*,
244  PRMInstance< GUM_SCALAR >* > >::iterator_safe match;
245  // Using p information to build child's isomorphism graph
246  NodeId id = 0;
247 
248  for (const auto& elt : p_iso_map) {
249  auto match = edge_growth.matches.begin();
250 
251  for (; match != edge_growth.matches.end(); ++match) {
252  // Adding the isomorphism in the iso_graph and building the iso_map.
253  if (child->code().codes.back()->isForward()) {
254  if (elt.second->exists(match.val().first)
255  && !(elt.second->exists(match.val().second))) {
256  // Let's see if the new match is already matched
257  Sequence< PRMInstance< GUM_SCALAR >* >* new_seq =
258  new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);
259  new_seq->insert(match.val().second);
260 
261  if (__is_new_seq(*new_seq, data->iso_map)) {
262  id = data->iso_graph.addNode();
263  data->iso_map.insert(id, new_seq);
264  } else {
265  delete new_seq;
266  }
267 
268  break;
269  }
270  } else {
271  if (elt.second->exists(match.val().first)
272  && elt.second->exists(match.val().second)) {
273  Sequence< PRMInstance< GUM_SCALAR >* >* new_seq =
274  new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);
275 
276  if (__is_new_seq(*new_seq, data->iso_map)) {
277  id = data->iso_graph.addNode();
278  data->iso_map.insert(id, new_seq);
279  } else {
280  delete new_seq;
281  }
282 
283  break;
284  }
285  }
286  }
287 
288  if (match != edge_growth.matches.end()) {
289  // Adding edges in the iso_graph
290  for (const auto node : data->iso_graph.nodes())
291  if (node != id)
292  for (const auto m : *data->iso_map[id])
293  if (data->iso_map[node]->exists(m)) {
294  data->iso_graph.addEdge(node, id);
295  break;
296  }
297 
298  degree_list.push_back(id);
299  edge_growth.matches.erase(match.key());
300  }
301  }
302 
303  if (data->iso_graph.size() < min_freq) {
304  delete data;
305  delete child;
306  GUM_ERROR(OperationNotAllowed, "child is not frequent enough");
307  }
308 
309  // Now we can compute the maximal independent set of child
310  DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
311  std::sort(degree_list.begin(), degree_list.end(), my_operator);
312  Set< NodeId > removed;
313 
314  for (const auto node : degree_list) {
315  if (!removed.exists(node)) {
316  removed.insert(node);
317 
318  for (const auto neighbor : data->iso_graph.neighbours(node))
319  removed.insert(neighbor);
320 
321  data->max_indep_set.insert(node);
322  }
323  }
324 
325  __data.insert(child, data);
326 
327  if (!__strategy->accept_growth(&p, child, edge_growth)) {
328  __data.erase(child);
329  delete data;
330  delete child;
331  GUM_ERROR(OperationNotAllowed, "child is not frequent enough");
332  }
333 
334  __addChild(p, child, edge_growth);
335  return *child;
336  }
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
SearchStrategy< GUM_SCALAR > * __strategy
The strategy used to prune the search tree.
Definition: DFSTree.h:274
void __addChild(Pattern &p, Pattern *child, EdgeGrowth< GUM_SCALAR > &edge_growth)
Add a child to this DFSTree.
Definition: DFSTree_tpl.h:158
bool __is_new_seq(Sequence< PRMInstance< GUM_SCALAR > * > &seq, NodeProperty< Sequence< PRMInstance< GUM_SCALAR > * > * > &iso_map)
Check if an instance match is redundant.
Definition: DFSTree_tpl.h:139
PatternData & data(const Pattern &p)
Definition: DFSTree_tpl.h:516
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
void __checkGrowth(Pattern &p, Pattern *child, EdgeGrowth< GUM_SCALAR > &edge_growth)
Raise different exceptions if child is invalid or illegal.
Definition: DFSTree_tpl.h:185
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE 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
pThe pattern for which we want the isomorphism graph.
Returns
The isomorphism graph of p.
Exceptions
NotFoundRaised if p is not a node in this DFSTree.

Definition at line 463 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, and GUM_ERROR.

463  {
464  try {
465  return __data[const_cast< Pattern* >(&p)]->iso_graph;
466  } catch (NotFound&) {
467  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
468  }
469  }
UndiGraph & iso_graph(const Pattern &p)
Returns the isomorphism graph of p in the interface graph.
Definition: DFSTree_tpl.h:463
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename GUM_SCALAR >
INLINE 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
pThe pattern for which we want a match in the interface graph.
nodeThe 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
NotFoundRaised if p or node does not exists.

Definition at line 473 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, and GUM_ERROR.

473  {
474  try {
475  return *(__data[const_cast< Pattern* >(&p)]->iso_map[node]);
476  } catch (NotFound&) {
477  if (__data.exists(const_cast< Pattern* >(&p))) {
478  GUM_ERROR(NotFound, "node not found in Pattern's isomorphism graph");
479  } else {
480  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
481  }
482  }
483  }
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 ma...
Definition: DFSTree_tpl.h:473
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename VAL >
List< VAL > gum::ArcGraphPart::listMapArcs ( VAL(*)(const Arc &)  f) 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
fa function assigning a VAL to any arc
template<typename VAL >
List< VAL > gum::NodeGraphPart::listMapNodes ( VAL(*)(const NodeId &)  f) 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
fa function assigning a VAL to any node
template<typename GUM_SCALAR >
INLINE Set< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::max_indep_set ( const Pattern p)

Returns the maximal independent set of p isomorphism graph.

Parameters
pThe pattern for which we want its maximal independent set.
Exceptions
NotFoundRaised if p is not a node in this DFSTree.

Definition at line 487 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__data, and GUM_ERROR.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::frequency().

487  {
488  try {
489  return __data[const_cast< Pattern* >(&p)]->max_indep_set;
490  } catch (NotFound&) {
491  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
492  }
493  }
Set< NodeId > & max_indep_set(const Pattern &p)
Returns the maximal independent set of p isomorphism graph.
Definition: DFSTree_tpl.h:487
HashTable< Pattern *, PatternData * > __data
Data about patterns in this DFSTree.
Definition: DFSTree.h:271
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the caller graph for this function:

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);
is basically not thread safe !!
Returns
a node id not yet used by any node within the NodeGraphPart

Definition at line 223 of file nodeGraphPart_inl.h.

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::_addNode(), and gum::BayesNet< GUM_SCALAR >::add().

223  {
224  NodeId next = 0;
225 
226  // return the first hole if holes exist
227  if (__holes && (!__holes->empty()))
228  next = *(__holes->begin());
229  else // in other case
230  next = __boundVal;
231 
232  return next;
233  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
iterator begin() const
The usual unsafe begin iterator to parse the set.
Definition: set_tpl.h:517

+ Here is the caller graph for this function:

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

return *this as a NodeGraphPart

Definition at line 367 of file nodeGraphPart_inl.h.

Referenced by gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__compute(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::credal::CNMonteCarloSampling< GUM_SCALAR, BNInferenceEngine >::__threadUpdate(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::InfluenceDiagram< GUM_SCALAR >::_removeTables(), gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::StaticTriangulation::fillIns(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::UndiGraph::hasUndirectedCycle(), gum::MarkovBlanket::nodes(), gum::EssentialGraph::nodes(), gum::prm::gspan::Pattern::nodes(), gum::MarkovBlanket::toDot(), gum::EssentialGraph::toDot(), gum::InfluenceDiagram< GUM_SCALAR >::toDot(), gum::UndiGraph::toDot(), gum::DiGraph::toDot(), and gum::MixedGraph::toDot().

367  {
368  return *(static_cast< const NodeGraphPart* >(this));
369  }
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor

+ Here is the caller graph for this function:

template<typename VAL >
NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( VAL(*)(const NodeId &)  f,
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
fa function assigning a VAL to any node
sizean 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.

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::_getChildrenDecision(), gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), and gum::UndiGraph::hasUndirectedCycle().

+ Here is the caller graph for this function:

template<typename VAL >
NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( 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
athe default value assigned to each edge in the returned Property
sizean 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.
INLINE bool gum::ArcGraphPart::operator!= ( const ArcGraphPart p) const
inherited

tests whether two ArcGraphParts contain different arcs

Parameters
pthe ArcGraphPart that we compare with this

Definition at line 154 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs.

154  {
155  return __arcs != p.__arcs;
156  }
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266
INLINE bool gum::DiGraph::operator!= ( const DiGraph g) const
inherited

tests whether two DiGraphs are different

Parameters
gthe DiGraph with which "this" is compared

Definition at line 80 of file diGraph_inl.h.

References gum::DiGraph::operator==().

80  {
81  return !operator==(p);
82  }
bool operator==(const DiGraph &g) const
tests whether two DiGraphs are identical (same nodes, same arcs)
Definition: diGraph_inl.h:76

+ Here is the call graph for this function:

INLINE bool gum::NodeGraphPart::operator!= ( const NodeGraphPart p) const
inherited

check whether two NodeGraphParts contain different nodes

Parameters
pthe NodeGraphPart to be compared with "this"

Definition at line 351 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::operator==().

351  {
352  return !operator==(p);
353  }
bool operator==(const NodeGraphPart &p) const
check whether two NodeGraphParts contain the same nodes

+ Here is the call graph for this function:

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

tests whether two ArcGraphParts contain the same arcs

Parameters
pthe ArcGraphPart that we compare with this

Definition at line 150 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs.

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

150  {
151  return __arcs == p.__arcs;
152  }
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the caller graph for this function:

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

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

Parameters
gthe DiGraph with which "this" is compared

Definition at line 76 of file diGraph_inl.h.

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

Referenced by gum::DiGraph::operator!=().

76  {
78  }
bool operator==(const NodeGraphPart &p) const
check whether two NodeGraphParts contain the same nodes
bool operator==(const ArcGraphPart &p) const
tests whether two ArcGraphParts contain the same arcs

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

check whether two NodeGraphParts contain the same nodes

Parameters
pthe NodeGraphPart to be compared with "this"

Definition at line 337 of file nodeGraphPart_inl.h.

References gum::NodeGraphPart::__boundVal, and gum::NodeGraphPart::__holes.

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

337  {
338  if (__boundVal != p.__boundVal) return false;
339 
340  if (__holes)
341  if (p.__holes)
342  return (*__holes == *p.__holes);
343  else
344  return false;
345  else if (p.__holes)
346  return false;
347 
348  return true;
349  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart

+ Here is the caller graph for this function:

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

Returns the parent of p in this DFSTree.

Definition at line 395 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__node_map, gum::NodeGraphPart::begin(), GUM_ERROR, and gum::ArcGraphPart::parents().

395  {
396  try {
397  return *(__node_map.second(
398  *(DiGraph::parents(__node_map.first(const_cast< Pattern* >(&p)))
399  .begin())));
400  } catch (NotFound&) {
401  if (__node_map.existsSecond(const_cast< Pattern* >(&p))) {
402  GUM_ERROR(NotFound, "the given pattern is a root node");
403  } else {
404  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
405  }
406  }
407  }
node_iterator begin() const noexcept
a begin iterator to parse the set of nodes contained in the NodeGraphPart
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

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

Returns the parent of p in this DFSTree.

Definition at line 410 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__node_map, gum::NodeGraphPart::begin(), GUM_ERROR, and gum::ArcGraphPart::parents().

410  {
411  try {
412  return *(__node_map.second(
413  *(DiGraph::parents(__node_map.first(const_cast< Pattern* >(&p)))
414  .begin())));
415  } catch (NotFound&) {
416  if (__node_map.existsSecond(const_cast< Pattern* >(&p))) {
417  GUM_ERROR(NotFound, "the given pattern is a root node");
418  } else {
419  GUM_ERROR(NotFound, "pattern not found in this DFSTree");
420  }
421  }
422  }
node_iterator begin() const noexcept
a begin iterator to parse the set of nodes contained in the NodeGraphPart
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

INLINE const NodeSet & gum::ArcGraphPart::parents ( const 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
idthe node toward which the arcs returned are pointing

Definition at line 54 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__checkParents(), and gum::ArcGraphPart::__parents.

Referenced by gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__AR(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__connect(), gum::learning::Miic::__existsDirectedPath(), gum::prm::gspan::Pattern::__expandCodeIsMinimal(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClass(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClasses(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateCluster(), gum::IBayesNet< GUM_SCALAR >::__minimalCondSetVisitDn(), gum::IBayesNet< GUM_SCALAR >::__minimalCondSetVisitUp(), gum::prm::gspan::Pattern::__not_rec(), gum::prm::gspan::Pattern::__rec(), gum::EssentialGraph::__strongly_protected(), gum::InfluenceDiagram< GUM_SCALAR >::_copyTables(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::_initialize(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::_makeInferenceNodeToNeighbours(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::learning::Miic::_orientation_miic(), gum::learning::Miic::_propagatesHead(), gum::BarrenNodesFinder::barrenNodes(), gum::ArcGraphPart::directedPath(), gum::ArcGraphPart::directedUnorientedPath(), gum::learning::BNDatabaseGenerator< GUM_SCALAR >::drawSamples(), gum::ArcGraphPart::eraseParents(), gum::InfluenceDiagram< GUM_SCALAR >::getPartialTemporalOrder(), gum::prm::gspan::Pattern::isMinimal(), gum::learning::Miic::learnStructure(), gum::IBayesNet< GUM_SCALAR >::minimalCondSet(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), gum::MarkovBlanket::parents(), gum::EssentialGraph::parents(), gum::DAGmodel::parents(), gum::BayesBall::relevantPotentials(), gum::dSeparation::relevantPotentials(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparation::requisiteNodes(), gum::prm::gspan::Pattern::rightmostPath(), and gum::ArcGraphPart::unvirtualizedEraseParents().

54  {
55  __checkParents(id);
56  return *(__parents[id]);
57  }
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269
void __checkParents(const NodeId id) const
when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entr...

+ Here is the call graph for this function:

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

Returns the pattern represented by id in this DFSTree.

Definition at line 445 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__node_map, and GUM_ERROR.

445  {
446  try {
447  return *(__node_map.second(id));
448  } catch (NotFound&) {
449  GUM_ERROR(NotFound, "no pattern matching the given id");
450  }
451  }
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename GUM_SCALAR >
INLINE const Pattern & gum::prm::gspan::DFSTree< GUM_SCALAR >::pattern ( NodeId  id) const

Returns the pattern represented by id in this DFSTree.

Definition at line 454 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__node_map, and GUM_ERROR.

454  {
455  try {
456  return *(__node_map.second(id));
457  } catch (NotFound&) {
458  GUM_ERROR(NotFound, "no pattern matching the given id");
459  }
460  }
Bijection< NodeId, Pattern * > __node_map
The mapping between nodes in this DFSTree and the patterns they represents.
Definition: DFSTree.h:268
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
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
sthe NodeGraphPart to be copied

Definition at line 61 of file nodeGraphPart.cpp.

References gum::NodeGraphPart::__boundVal, gum::NodeGraphPart::__holes, gum::NodeGraphPart::__holes_resize_policy, gum::NodeGraphPart::__holes_size, gum::NodeGraphPart::__updateEndIteratorSafe(), and gum::NodeGraphPart::clear().

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

61  {
62  clear(); // "virtual" flush of the nodes set
63  __holes_size = s.__holes_size;
64  __holes_resize_policy = s.__holes_resize_policy;
65 
66  if (s.__holes) __holes = new NodeSet(*s.__holes);
67 
68  __boundVal = s.__boundVal;
69 
71  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __holes_resize_policy
value for __holes configuration
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
Size __holes_size
value for __holes configuration
void __updateEndIteratorSafe()
updating endIterator (always at __max+1)
virtual void clear()
alias for clearNodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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.

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

Returns the list of root patterns in this DFSTree.

Definition at line 385 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__roots.

385  {
386  return __roots;
387  }
std::list< NodeId > __roots
The list of root patterns in this DFSTree.
Definition: DFSTree.h:264
template<typename GUM_SCALAR >
INLINE const std::list< NodeId > & gum::prm::gspan::DFSTree< GUM_SCALAR >::roots ( ) const

Returns the list of root patterns in this DFSTree.

Definition at line 390 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__roots.

390  {
391  return __roots;
392  }
std::list< NodeId > __roots
The list of root patterns in this DFSTree.
Definition: DFSTree.h:264
INLINE Size gum::ArcGraphPart::sizeArcs ( ) const
inherited

indicates the number of arcs stored within the ArcGraphPart

Definition at line 34 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs, and gum::Set< Key, Alloc >::size().

Referenced by gum::MarkovBlanket::sizeArcs(), gum::EssentialGraph::sizeArcs(), gum::DAGmodel::sizeArcs(), gum::prm::gspan::Pattern::sizeArcs(), gum::InfluenceDiagram< GUM_SCALAR >::toString(), and gum::IBayesNet< GUM_SCALAR >::toString().

34 { return __arcs.size(); }
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701
Set< Arc > __arcs
the set of all the arcs contained within the ArcGraphPart
Definition: arcGraphPart.h:266

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

returns the number of nodes in the NodeGraphPart

Definition at line 274 of file nodeGraphPart_inl.h.

Referenced by gum::BinaryJoinTreeConverterDefault::__markConnectedComponent(), gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), gum::EliminationSequenceStrategy::setGraph(), gum::MarkovBlanket::sizeNodes(), and gum::EssentialGraph::sizeNodes().

274  {
275  return (__holes) ? (__boundVal - __holes->size()) : __boundVal;
276  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701

+ Here is the caller graph for this function:

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

strategy getter

Definition at line 527 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__strategy.

527  {
528  return *__strategy;
529  }
SearchStrategy< GUM_SCALAR > * __strategy
The strategy used to prune the search tree.
Definition: DFSTree.h:274
template<typename GUM_SCALAR >
INLINE const SearchStrategy< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::strategy ( ) const

strategy getter

Definition at line 533 of file DFSTree_tpl.h.

References gum::prm::gspan::DFSTree< GUM_SCALAR >::__strategy.

533  {
534  return *__strategy;
535  }
SearchStrategy< GUM_SCALAR > * __strategy
The strategy used to prune the search tree.
Definition: DFSTree.h:274
const std::string gum::DiGraph::toDot ( ) const
virtualinherited

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

Parameters
nameThe graph name in the dot syntax. Default is G.
Returns
Returns a string describing the graph in the dot syntax

Reimplemented in gum::MixedGraph.

Definition at line 65 of file diGraph.cpp.

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

65  {
66  std::stringstream strBuff;
67  std::string tab = " ";
68  strBuff << "digraph {" << std::endl;
69 
70  for (const auto node : nodes())
71  strBuff << tab << node << ";" << std::endl;
72 
73  strBuff << std::endl;
74 
75  for (const auto& arc : arcs())
76  strBuff << tab << arc.tail() << " -> " << arc.head() << ";" << std::endl;
77 
78  strBuff << "}" << std::endl << std::endl;
79  return strBuff.str();
80  }
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart

+ Here is the call graph for this function:

const Sequence< NodeId > & gum::DiGraph::topologicalOrder ( bool  clear = true) const
inherited

The topological order stays the same as long as no variable or arcs are added or erased src the topology.

Parameters
clearIf false returns the previously created topology.
Exceptions
InvalidDirectedCycleRaised if this DiGraph contains cycles.

Definition at line 88 of file diGraph.cpp.

References gum::DiGraph::__mutableTopologicalOrder, gum::DiGraph::__topologicalOrder(), and gum::SequenceImplementation< Key, Alloc, Gen >::clear().

Referenced by gum::prm::o3prm::O3ClassFactory< GUM_SCALAR >::__setO3ClassCreationOrder(), gum::prm::o3prm::O3InterfaceFactory< GUM_SCALAR >::__setO3InterfaceCreationOrder(), gum::prm::o3prm::O3TypeFactory< GUM_SCALAR >::__setO3TypeCreationOrder(), gum::learning::Miic::learnStructure(), and gum::DAGmodel::topologicalOrder().

88  {
89  if (clear
91  == nullptr)) { // we have to call _topologicalOrder
92  if (__mutableTopologicalOrder == nullptr) {
94  } else {
95  // clear is True
97  }
98 
100  }
101 
103  }
void __topologicalOrder() const
Returns a topological order of this DAGModel.
Definition: diGraph.cpp:105
void clear()
Clear the sequence.
Definition: sequence_tpl.h:268
Sequence< NodeId > * __mutableTopologicalOrder
The topology sequence of this Directed Graphical Model.
Definition: diGraph.h:198

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

to friendly display the content of the graph

Reimplemented in gum::MixedGraph.

Definition at line 58 of file diGraph.cpp.

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

Referenced by gum::operator<<().

58  {
59  std::string s = NodeGraphPart::toString();
60  s += " , ";
62  return s;
63  }
std::string toString() const
a function to display the set of nodes
const std::string toString() const
to friendly display the content of the ArcGraphPart

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Parameters
idthe node whose outgoing arcs will be removed

Definition at line 138 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__children, gum::Set< Key, Alloc >::beginSafe(), gum::ArcGraphPart::children(), gum::Set< Key, Alloc >::endSafe(), and gum::ArcGraphPart::eraseArc().

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

138  {
139  if (__children.exists(id)) {
140  NodeSet& children = *(__children[id]);
141 
142  for (auto iter = children.beginSafe(); // safe iterator needed here
143  iter != children.endSafe();
144  ++iter) {
145  ArcGraphPart::eraseArc(Arc(id, *iter));
146  }
147  }
148  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
NodeProperty< NodeSet * > __children
for each arc, the set of its children
Definition: arcGraphPart.h:272

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Parameters
idthe node whose ingoing arcs will be removed

Definition at line 126 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__parents, gum::Set< Key, Alloc >::beginSafe(), gum::Set< Key, Alloc >::endSafe(), gum::ArcGraphPart::eraseArc(), and gum::ArcGraphPart::parents().

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

126  {
127  if (__parents.exists(id)) {
128  NodeSet& parents = *(__parents[id]);
129 
130  for (auto iter = parents.beginSafe(); // safe iterator needed here
131  iter != parents.endSafe();
132  ++iter) {
133  ArcGraphPart::eraseArc(Arc(*iter, id));
134  }
135  }
136  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
NodeProperty< NodeSet * > __parents
for each arc, the sets of its parents
Definition: arcGraphPart.h:269

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

template<typename 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 261 of file DFSTree.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::graph().

template<typename 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 268 of file DFSTree.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::pattern().

template<typename GUM_SCALAR>
std::list< NodeId > gum::prm::gspan::DFSTree< GUM_SCALAR >::__roots
private

The list of root patterns in this DFSTree.

Definition at line 264 of file DFSTree.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::roots().

template<typename GUM_SCALAR>
SearchStrategy< GUM_SCALAR >* gum::prm::gspan::DFSTree< GUM_SCALAR >::__strategy
private

The strategy used to prune the search tree.

Definition at line 274 of file DFSTree.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::DFSTree(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::strategy().

Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcAdded
inherited
Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcDeleted
inherited

Definition at line 81 of file arcGraphPart.h.

Referenced by gum::ArcGraphPart::clearArcs(), and gum::ArcGraphPart::eraseArc().

Signaler1< NodeId > gum::NodeGraphPart::onNodeAdded
inherited

Definition at line 271 of file nodeGraphPart.h.

Referenced by gum::NodeGraphPart::addNodeWithId().

Signaler1< NodeId > gum::NodeGraphPart::onNodeDeleted
inherited

Definition at line 272 of file nodeGraphPart.h.

Referenced by gum::NodeGraphPart::__clearNodes().


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