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...
Pattern &	parent (const Pattern &p)
	Returns the parent of p in this DFSTree. More...
const Pattern &	parent (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...
Pattern &	pattern (NodeId id)
	Returns the pattern represented by id in this DFSTree. More...
const Pattern &	pattern (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...
Pattern &	growPattern (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.
UndiGraph &	iso_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...
PatternData &	data (const Pattern &p)
const PatternData &	data (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 71 of file DFSTree.h.

Member Typedef Documentation

ArcIterator

typedef ArcSetIterator gum::ArcGraphPart::ArcIterator

inherited

Definition at line 81 of file arcGraphPart.h.

node_const_iterator

using gum::NodeGraphPart::node_const_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 261 of file nodeGraphPart.h.

node_const_iterator_safe

using gum::NodeGraphPart::node_const_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 263 of file nodeGraphPart.h.

node_iterator

using gum::NodeGraphPart::node_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 260 of file nodeGraphPart.h.

node_iterator_safe

using gum::NodeGraphPart::node_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 262 of file nodeGraphPart.h.

NodeConstIterator

typedef NodeGraphPartIterator gum::NodeGraphPart::NodeConstIterator

inherited

Definition at line 270 of file nodeGraphPart.h.

NodeConstIteratorSafe

typedef NodeGraphPartIteratorSafe gum::NodeGraphPart::NodeConstIteratorSafe

inherited

Definition at line 272 of file nodeGraphPart.h.

NodeIterator

typedef NodeGraphPartIterator gum::NodeGraphPart::NodeIterator

inherited

Definition at line 269 of file nodeGraphPart.h.

NodeIteratorSafe

typedef NodeGraphPartIteratorSafe gum::NodeGraphPart::NodeIteratorSafe

inherited

Definition at line 271 of file nodeGraphPart.h.

Constructor & Destructor Documentation

DFSTree()

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 375 of file DFSTree_tpl.h.

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

                                                      :
          __graph(&graph),
          __strategy(strategy) {
        GUM_CONSTRUCTOR(DFSTree);

        if (!__strategy) __strategy = new FrequenceSearch< GUM_SCALAR >(2);

        __strategy->setTree(this);
      }

~DFSTree()

template<typename GUM_SCALAR >

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

(

)

Destructor.

Definition at line 37 of file DFSTree_tpl.h.

                                      {
        GUM_DESTRUCTOR(DFSTree);

        for (const auto& elt : __data) {
          delete elt.first;
          delete elt.second;
        }

        delete __strategy;
      }

Member Function Documentation

__addChild()

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 161 of file DFSTree_tpl.h.

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

                                                                            {
        // Adding child to the tree
        NodeId node = DiGraph::addNode();
        __node_map.insert(node, child);
        // Adding child in p's children list
        std::list< NodeId >& children = __data[&p]->children;

        if (children.empty()) {
          children.push_back(node);
        } else {
          size_t size = children.size();

          for (std::list< NodeId >::iterator iter = children.begin();
               iter != children.end();
               ++iter) {
            if (child->code() < pattern(*iter).code()) {
              children.insert(iter, node);
              break;
            }
          }

          if (size == children.size()) { children.push_back(node); }
        }
      }

Here is the call graph for this function:

__checkGrowth()

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 188 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.

                                                                            {
        NodeId v = edge_growth.v;

        // First we check if the edge is legal
        if (v == 0) { v = child->addNodeWithLabel(*(edge_growth.l_v)); }

        child->addArc(edge_growth.u, v, *(edge_growth.edge));
        // Neighborhood restriction is checked by the Pattern class
        EdgeCode& edge = child->edgeCode(edge_growth.u, v);

        // Then we check if the edge we added is valid
        if (edge < *(child->code().codes.front())) {
          GUM_ERROR(OperationNotAllowed,
                    "added edge code is lesser than the first "
                    "one in the pattern's DFSCode");
        }

        if (edge.isBackward()) {
          typedef std::vector< EdgeCode* >::iterator EdgeIter;

          for (EdgeIter iter = child->code().codes.begin();
               (iter + 1) != child->code().codes.end();
               ++iter) {
            if ((((**iter).i == v) || ((**iter).j == v)) && edge < (**iter)) {
              GUM_ERROR(
                 OperationNotAllowed,
                 "added backward edge is lesser than an existing edge on v");
            }
          }
        }

        // Finally we check if child is minimal.
        if (!child->isMinimal()) {
          GUM_ERROR(OperationNotAllowed,
                    "the DFSCode for this growth is not minimal");
        }
      }

Here is the call graph for this function:

__initialiaze_root()

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

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

Definition at line 93 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().

                                                                    {
        DFSTree< GUM_SCALAR >::PatternData* data = __data[p];
        std::vector< NodeId >               degree_list;

        for (auto iter = edge_seq.begin(); iter != edge_seq.end(); ++iter) {
          const auto&                             edge = *iter;
          Sequence< PRMInstance< GUM_SCALAR >* >* seq =
             new Sequence< PRMInstance< GUM_SCALAR >* >();

          // Creating the multiset of instances matching p
          bool u_first = (edge->l_u->id < edge->l_v->id);
          seq->insert((u_first) ? edge->u : edge->v);
          seq->insert((!u_first) ? edge->u : edge->v);

          NodeId an_id = data->iso_graph.addNode();
          data->iso_map.insert(an_id, seq);
          degree_list.push_back(an_id);

          // Adding edges between two isomorphisms of p sharing at least one
          // instance
          for (const auto& elt : data->iso_map)
            if (elt.first != an_id)
              for (auto iter = elt.second->begin(); iter != elt.second->end();
                   ++iter)
                if (seq->exists(*iter)) {
                  data->iso_graph.addEdge(an_id, elt.first);
                  break;
                }
        }

        // Computing p->max_indep_set using a greedy algorithm
        DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
        std::sort(degree_list.begin(), degree_list.end(), my_operator);
        Set< NodeId > removed;

        for (const auto node : degree_list) {
          if (!removed.exists(node)) {
            removed.insert(node);

            for (const auto neighbor : data->iso_graph.neighbours(node))
              removed.insert(neighbor);

            data->max_indep_set.insert(node);
          }
        }
      }

Here is the call graph for this function:

__is_new_seq()

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 142 of file DFSTree_tpl.h.

                                                                           {
        for (const auto& elt : iso_map) {
          bool found = false;

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

          if (!found) { return false; }
        }

        return true;
      }

__test_equality()

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 342 of file DFSTree_tpl.h.

                                                               {
        try {
          for (const auto& elt : x)
            if (y[elt.first] != elt.second) return false;
        } catch (NotFound&) { return false; }

        return true;
      }

_eraseSetOfArcs()

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

protectedinherited

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

Warning

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

Definition at line 91 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::eraseArc().

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

Here is the call graph for this function:

_unvirtualizedEraseSetOfArcs()

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

protectedinherited

similar to _eraseSetOfArcs except that it is unvirtualized

Warning

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

Definition at line 124 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::eraseArc().

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

Here is the call graph for this function:

addArc()

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

virtualinherited

insert a new arc into the directed graph

Parameters

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

Warning

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

Exceptions

InvalidNode

if head or tail does not belong to the graph nodes

Reimplemented from gum::ArcGraphPart.

Reimplemented in gum::DAG.

Definition at line 35 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().

                                                                  {
    if (!exists(head)) { GUM_ERROR(InvalidNode, "head node"); }

    if (!exists(tail)) { GUM_ERROR(InvalidNode, "tail node"); }

    ArcGraphPart::addArc(tail, head);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

addNode()

INLINE NodeId gum::NodeGraphPart::addNode ( )

virtualinherited

insert a new node and return its id

Returns

the id chosen by the internal idFactory

Reimplemented in gum::CliqueGraph.

Definition at line 253 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::gspan::DFSTree< GUM_SCALAR >::addRoot(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::IncrementalGraphLearner(), gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::insert(), and gum::LeafAggregator::update().

                                       {
    NodeId newNode;

    // fill the first hole if holes exist
    if (__holes && (!__holes->empty())) {
      newNode = *(__holes->begin());
      __eraseHole(newNode);
    } else {
      newNode = __boundVal;
      ++__boundVal;
      __updateEndIteratorSafe();
    }

    GUM_EMIT1(onNodeAdded, newNode);

    return newNode;
  }

Here is the caller graph for this function:

addNodes()

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

inherited

insert n nodes

Parameters

n	the number of nodes to add

Returns

the vector of chosen ids

Definition at line 271 of file nodeGraphPart_inl.h.

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

addNodeWithId()

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

virtualinherited

try to insert a node with the given id

Warning

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

Exceptions

DuplicateElement

exception if the id already exists

Definition at line 132 of file nodeGraphPart.cpp.

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

Referenced by gum::EssentialGraph::__buildEssentialGraph(), gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__computeInAComponent(), gum::learning::genericBNLearner::__learnDAG(), gum::learning::genericBNLearner::__prepare_miic_3off2(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::InfluenceDiagram< GUM_SCALAR >::_addNode(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::BayesNetFragment< GUM_SCALAR >::installNode(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph(), gum::learning::Miic::learnStructure(), gum::UndiGraph::partialUndiGraph(), gum::EssentialGraph::skeleton(), and gum::learning::StructuralConstraintDAG::StructuralConstraintDAG().

                                                   {
    if (id >= __boundVal) {
      if (id > __boundVal) {   // we have to add holes
        if (!__holes) __holes = new NodeSet(__holes_size, __holes_resize_policy);

        for (NodeId i = __boundVal; i < id; ++i)
          __holes->insert(i);
      }

      __boundVal = id + 1;

      __updateEndIteratorSafe();
    } else {
      if (__inHoles(id)) {   // we fill a hole
        __eraseHole(id);
      } else {
        GUM_ERROR(DuplicateElement, "Id " << id << " is already used");
      }
    }

    GUM_EMIT1(onNodeAdded, id);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

addRoot()

template<typename GUM_SCALAR >

void gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot

(

LabelData &

data

)

Add a one edge Pattern in this DFSTree.

Parameters

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

Returns

Returns the Pattern added as a root of this DFSTree.

Definition at line 49 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().

                                                          {
        HashTable< Pattern*, std::pair< Idx, Idx > >                roots;
        HashTable< Pattern*, Sequence< EdgeData< GUM_SCALAR >* >* > roots_edges;

        for (const auto edge : __graph->edges(&label)) {
          bool u_first = (edge->l_u->id < edge->l_v->id);
          Idx  u_idx = (u_first) ? edge->l_u->id : edge->l_v->id;
          Idx  v_idx = (!u_first) ? edge->l_u->id : edge->l_v->id;

          bool found = false;

          for (const auto& elt : roots)
            if ((elt.second.first == u_idx) && (elt.second.second == v_idx)) {
              roots_edges[elt.first]->insert(edge);
              found = true;
              break;
            }

          if (!found) {
            Pattern* p = new Pattern();
            roots.insert(p, std::make_pair(u_idx, v_idx));
            roots_edges.insert(p, new Sequence< EdgeData< GUM_SCALAR >* >());
            roots_edges[p]->insert(edge);
            DFSTree< GUM_SCALAR >::PatternData* data =
               new DFSTree< GUM_SCALAR >::PatternData(p);
            NodeId u = p->addNodeWithLabel((u_first) ? *edge->l_u : *edge->l_v);
            NodeId v = p->addNodeWithLabel((!u_first) ? *edge->l_u : *edge->l_v);
            p->addArc(u, v, label);
            __node_map.insert(DiGraph::addNode(), p);
            __data.insert(p, data);
            __roots.push_back(__node_map.first(p));
          }
        }

        // This is used to compute the max independent set of p->max_indep_set
        for (const auto& elt : roots_edges) {
          __initialiaze_root(elt.first, *elt.second);
          strategy().accept_root(elt.first);
          delete elt.second;
        }
      }

Here is the call graph for this function:

arcs()

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

inherited

returns the set of arcs stored within the ArcGraphPart

Definition at line 39 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(), gum::learning::DAG2BNLearner< ALLOC >::createBN(), gum::DAG::moralGraph(), and gum::DiGraph::toDot().

{ return __arcs; }

Here is the caller graph for this function:

arcsProperty() [1/2]

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

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

arcsProperty() [2/2]

template<typename VAL >

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

inherited

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

Parameters

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

asNodeSet()

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

inherited

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

Warning

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

for(const auto n : nodes()) 

rather than

for(const auto n : asNodeSet()) 

as this is faster and consumes much less memory.

Definition at line 361 of file nodeGraphPart_inl.h.

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

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

                                                {
    NodeSet son(sizeNodes());

    if (!empty()) {
      for (NodeId n = 0; n < __boundVal; ++n) {
        if (!__inHoles(n)) son.insert(n);
      }
    }

    return son;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

begin()

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

noexceptinherited

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

Definition at line 333 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

beginSafe()

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

inherited

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

Definition at line 319 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

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

Here is the call graph for this function:

bound()

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

inherited

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

Definition at line 308 of file nodeGraphPart_inl.h.

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

{ return __boundVal; }

Here is the caller graph for this function:

children() [1/3]

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 429 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().

                                                             {
        try {
          return __data[const_cast< Pattern* >(&p)]->children;
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree");
        }
      }

Here is the caller graph for this function:

children() [2/3]

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 439 of file DFSTree_tpl.h.

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

                                                                         {
        try {
          return __data[const_cast< Pattern* >(&p)]->children;
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree");
        }
      }

Here is the call graph for this function:

children() [3/3]

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

id	the node which is the tail of the arcs returned

Definition at line 62 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::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__connect(), gum::MCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__directedPath(), gum::prm::gspan::Pattern::__expandCodeIsMinimal(), gum::prm::gspan::Pattern::__not_rec(), 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::DiGraph::hasDirectedPath(), gum::prm::gspan::Pattern::isMinimal(), 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().

                                                                    {
    __checkChildren(id);
    return *(__children[id]);
  }

Here is the call graph for this function:

clear()

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 43 of file diGraph_inl.h.

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

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

clearArcs()

void gum::ArcGraphPart::clearArcs ( )

inherited

removes all the arcs from the ArcGraphPart

Definition at line 79 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().

                               {
    for (const auto& elt : __parents)
      delete elt.second;

    __parents.clear();

    for (const auto& elt : __children)
      delete elt.second;

    __children.clear();

    // we need this copy only if at least one onArcDeleted listener exists
    if (onArcDeleted.hasListener()) {
      ArcSet tmp = __arcs;
      __arcs.clear();

      for (const auto& arc : tmp)
        GUM_EMIT2(onArcDeleted, arc.tail(), arc.head());
    } else {
      __arcs.clear();
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )

virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 310 of file nodeGraphPart_inl.h.

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

{ __clearNodes(); }

Here is the caller graph for this function:

data() [1/2]

template<typename GUM_SCALAR >

INLINE DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data

(

const Pattern &

p

)

Parameters

p	The pattern

Definition at line 519 of file DFSTree_tpl.h.

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

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

data() [2/2]

template<typename GUM_SCALAR >

INLINE const DFSTree< GUM_SCALAR >::PatternData & gum::prm::gspan::DFSTree< GUM_SCALAR >::data

(

const Pattern &

p

)

const

Parameters

p	The pattern

Definition at line 525 of file DFSTree_tpl.h.

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

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

directedPath()

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

node1	the id from which the path begins
node2	the id to which the path ends

Exceptions

NotFound

exception is raised if no path can be found between the two nodes

Definition at line 155 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().

                                                                                {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(n2);

    // mark[node] = successor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);

    NodeId current;

    while (!nodeFIFO.empty()) {
      current = nodeFIFO.front();
      nodeFIFO.popFront();

      // check the parents

      for (const auto new_one : parents(current)) {
        if (mark.exists(new_one))   // if this node is already marked, do not
          continue;                 // check it again

        mark.insert(new_one, current);

        if (new_one == n1) {
          std::vector< NodeId > v;

          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);

          v.push_back(n2);

          return v;
        }

        nodeFIFO.pushBack(new_one);
      }
    }

    GUM_ERROR(NotFound, "no path found");
  }

Here is the call graph for this function:

Here is the caller graph for this function:

directedUnorientedPath()

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

node1	the id from which the path begins
node2	the id to which the path ends

Exceptions

NotFound

exception is raised if no path can be found between the two nodes

Definition at line 198 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().

                                                                                {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(n2);

    // mark[node] = successor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);

    NodeId current;

    while (!nodeFIFO.empty()) {
      current = nodeFIFO.front();
      nodeFIFO.popFront();

      // check the parents
      for (const auto new_one : parents(current)) {
        if (mark.exists(new_one))   // the node has already been visited
          continue;

        mark.insert(new_one, current);

        if (new_one == n1) {
          std::vector< NodeId > v;

          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);

          v.push_back(n2);

          return v;
        }

        nodeFIFO.pushBack(new_one);
      }

      // check the children
      for (const auto new_one : children(current)) {
        if (mark.exists(new_one))   // the node has already been visited
          continue;

        mark.insert(new_one, current);

        if (new_one == n1) {
          std::vector< NodeId > v;

          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);

          v.push_back(n2);

          return v;
        }

        nodeFIFO.pushBack(new_one);
      }
    }

    GUM_ERROR(NotFound, "no path found");
  }

Here is the call graph for this function:

empty()

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

inherited

alias for emptyNodes

Definition at line 306 of file nodeGraphPart_inl.h.

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

{ return emptyNodes(); }

Here is the caller graph for this function:

emptyArcs()

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

inherited

indicates wether the ArcGraphPart contains any arc

Definition at line 35 of file arcGraphPart_inl.h.

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

{ return __arcs.empty(); }

Here is the call graph for this function:

emptyNodes()

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

inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 304 of file nodeGraphPart_inl.h.

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

end()

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

noexceptinherited

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

Definition at line 339 of file nodeGraphPart_inl.h.

                                                                        {
    return __endIteratorSafe;
  }

endSafe()

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

noexceptinherited

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

Definition at line 329 of file nodeGraphPart_inl.h.

                                                                                {
    return __endIteratorSafe;
  }

eraseArc()

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

virtualinherited

removes an arc from the ArcGraphPart

Parameters

arc	the arc to be removed

Warning

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

Definition at line 79 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::ArcGraphPart::eraseChildren(), gum::ArcGraphPart::eraseParents(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), gum::prm::gspan::Pattern::pop_back(), gum::BayesNet< double >::reverseArc(), gum::ArcGraphPart::unvirtualizedEraseChildren(), and gum::ArcGraphPart::unvirtualizedEraseParents().

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

Here is the call graph for this function:

Here is the caller graph for this function:

eraseChildren()

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

inherited

removes all the children of a given node

Parameters

id	the node all the children of which will be removed

Warning

although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseChildren

if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 110 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().

                                                         {
    if (__children.exists(id)) {
      NodeSet& children = *(__children[id]);

      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        // warning: use this erase so that you actually use the vritualized
        // arc removal function
        eraseArc(Arc(id, *iter));
      }
    }
  }

Here is the call graph for this function:

eraseNode()

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

virtualinherited

remove a node and its adjacent arcs from the graph

Parameters

id	the id of the node to be removed

Warning

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

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 69 of file diGraph_inl.h.

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

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

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

    NodeGraphPart::eraseNode(id);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

eraseParents()

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

inherited

erase all the parents of a given node

Parameters

id	the node all the parents of which will be removed

Warning

although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseParents

if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 96 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().

                                                        {
    if (__parents.exists(id)) {
      NodeSet& parents = *(__parents[id]);

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

Here is the call graph for this function:

exists()

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

inherited

alias for existsNode

Definition at line 292 of file nodeGraphPart_inl.h.

Referenced by gum::MarkovBlanket::__buildMarkovBlanket(), gum::prm::ClassBayesNet< GUM_SCALAR >::__get(), gum::learning::genericBNLearner::__learnDAG(), gum::prm::StructuredInference< GUM_SCALAR >::__removeNode(), gum::NodeGraphPartIterator::_setPos(), gum::prm::gspan::Pattern::addArc(), gum::DiGraph::addArc(), gum::UndiGraph::addEdge(), gum::prm::gspan::Pattern::exists(), and gum::DiGraph::hasDirectedPath().

                                                           {
    return existsNode(node);
  }

Here is the caller graph for this function:

existsArc() [1/2]

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

inherited

indicates whether a given arc exists

Parameters

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

Definition at line 41 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::DAGCycleDetector::addArc(), gum::ArcGraphPart::eraseArc(), gum::DAGCycleDetector::eraseArc(), gum::InfluenceDiagram< GUM_SCALAR >::eraseArc(), and gum::prm::gspan::Pattern::exists().

                                                          {
    return __arcs.contains(arc);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

existsArc() [2/2]

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

inherited

indicates whether a given arc exists

Parameters

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

Definition at line 45 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__parents.

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

existsNode()

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

inherited

returns true iff the NodeGraphPart contains the given nodeId

Definition at line 286 of file nodeGraphPart_inl.h.

Referenced by gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__compute(), gum::SpanningForestPrim::__computeInAComponent(), gum::SpanningForestPrim::__exploreNode(), gum::OrderedEliminationSequenceStrategy::__isOrderNeeded(), gum::PartialOrderedEliminationSequenceStrategy::_isPartialOrderNeeded(), gum::OrderedEliminationSequenceStrategy::eliminationUpdate(), gum::DefaultPartialOrderedEliminationSequenceStrategy::eliminationUpdate(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::BayesNetFragment< GUM_SCALAR >::isInstalledNode(), gum::UndiGraph::partialUndiGraph(), gum::OrderedEliminationSequenceStrategy::setOrder(), and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

                                                               {
    if (node >= __boundVal) return false;

    return (!__inHoles(node));
  }

Here is the caller graph for this function:

frequency()

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

p	The pattern

Definition at line 513 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().

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

Here is the call graph for this function:

graph()

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 500 of file DFSTree_tpl.h.

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

                                                      {
        return *__graph;
      }

growPattern()

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

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

Exceptions

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

Definition at line 228 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().

                                                                           {
        Pattern* child = new Pattern(p);

        try {
          __checkGrowth(p, child, edge_growth);
        } catch (OperationNotAllowed&) {
          delete child;
          throw;
        }

        // Now we need to build the pattern data about child
        DFSTree< GUM_SCALAR >::PatternData* data =
           new DFSTree< GUM_SCALAR >::PatternData(child);
        std::vector< NodeId >                                    degree_list;
        NodeProperty< Sequence< PRMInstance< GUM_SCALAR >* >* >& p_iso_map =
           __data[&p]->iso_map;
        typename NodeProperty<
           std::pair< PRMInstance< GUM_SCALAR >*,
                      PRMInstance< GUM_SCALAR >* > >::iterator_safe match;
        // Using p information to build child's isomorphism graph
        NodeId id = 0;

        for (const auto& elt : p_iso_map) {
          auto match = edge_growth.matches.begin();

          for (; match != edge_growth.matches.end(); ++match) {
            // Adding the isomorphism in the iso_graph and building the iso_map.
            if (child->code().codes.back()->isForward()) {
              if (elt.second->exists(match.val().first)
                  && !(elt.second->exists(match.val().second))) {
                // Let's see if the new match is already matched
                Sequence< PRMInstance< GUM_SCALAR >* >* new_seq =
                   new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);
                new_seq->insert(match.val().second);

                if (__is_new_seq(*new_seq, data->iso_map)) {
                  id = data->iso_graph.addNode();
                  data->iso_map.insert(id, new_seq);
                } else {
                  delete new_seq;
                }

                break;
              }
            } else {
              if (elt.second->exists(match.val().first)
                  && elt.second->exists(match.val().second)) {
                Sequence< PRMInstance< GUM_SCALAR >* >* new_seq =
                   new Sequence< PRMInstance< GUM_SCALAR >* >(*elt.second);

                if (__is_new_seq(*new_seq, data->iso_map)) {
                  id = data->iso_graph.addNode();
                  data->iso_map.insert(id, new_seq);
                } else {
                  delete new_seq;
                }

                break;
              }
            }
          }

          if (match != edge_growth.matches.end()) {
            // Adding edges in the iso_graph
            for (const auto node : data->iso_graph.nodes())
              if (node != id)
                for (const auto m : *data->iso_map[id])
                  if (data->iso_map[node]->exists(m)) {
                    data->iso_graph.addEdge(node, id);
                    break;
                  }

            degree_list.push_back(id);
            edge_growth.matches.erase(match.key());
          }
        }

        if (data->iso_graph.size() < min_freq) {
          delete data;
          delete child;
          GUM_ERROR(OperationNotAllowed, "child is not frequent enough");
        }

        // Now we can compute the maximal independent set of child
        DFSTree< GUM_SCALAR >::NeighborDegreeSort my_operator(data->iso_graph);
        std::sort(degree_list.begin(), degree_list.end(), my_operator);
        Set< NodeId > removed;

        for (const auto node : degree_list) {
          if (!removed.exists(node)) {
            removed.insert(node);

            for (const auto neighbor : data->iso_graph.neighbours(node))
              removed.insert(neighbor);

            data->max_indep_set.insert(node);
          }
        }

        __data.insert(child, data);

        if (!__strategy->accept_growth(&p, child, edge_growth)) {
          __data.erase(child);
          delete data;
          delete child;
          GUM_ERROR(OperationNotAllowed, "child is not frequent enough");
        }

        __addChild(p, child, edge_growth);
        return *child;
      }

Here is the call graph for this function:

hasDirectedPath()

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

inherited

checks whether there exists a directed path from from to to

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

Parameters

from
to

Returns

true if a directed path exists

Definition at line 137 of file diGraph.cpp.

References gum::ArcGraphPart::children(), gum::Set< Key, Alloc >::contains(), gum::List< Val, Alloc >::empty(), gum::NodeGraphPart::exists(), gum::List< Val, Alloc >::front(), gum::Set< Key, Alloc >::insert(), gum::List< Val, Alloc >::popFront(), and gum::List< Val, Alloc >::pushBack().

Referenced by gum::DAG::addArc().

                                                                  {
    if (!exists(from)) return false;

    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(from);

    NodeSet marked;
    marked.insert(from);

    NodeId new_one;

    while (!nodeFIFO.empty()) {
      new_one = nodeFIFO.front();
      // std::cout<<new_one<<std::endl;
      nodeFIFO.popFront();

      for (const auto chi : children(new_one)) {
        if (chi == to) return true;

        if (!marked.contains(chi)) {
          nodeFIFO.pushBack(chi);
          marked.insert(chi);
        }
      }
    }

    return false;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

iso_graph()

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

p	The pattern for which we want the isomorphism graph.

Returns

The isomorphism graph of p.

Exceptions

NotFound

Raised if p is not a node in this DFSTree.

Definition at line 466 of file DFSTree_tpl.h.

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

                                                                         {
        try {
          return __data[const_cast< Pattern* >(&p)]->iso_graph;
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree");
        }
      }

iso_map()

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

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

Returns

Returns the sequence of instances matching p and node.

Exceptions

NotFound

Raised if p or node does not exists.

Definition at line 476 of file DFSTree_tpl.h.

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

                                                                         {
        try {
          return *(__data[const_cast< Pattern* >(&p)]->iso_map[node]);
        } catch (NotFound&) {
          if (__data.exists(const_cast< Pattern* >(&p))) {
            GUM_ERROR(NotFound, "node not found in Pattern's isomorphism graph");
          } else {
            GUM_ERROR(NotFound, "pattern not found in this DFSTree");
          }
        }
      }

listMapArcs()

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

f	a function assigning a VAL to any arc

listMapNodes()

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

f	a function assigning a VAL to any node

max_indep_set()

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

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

Exceptions

NotFound

Raised if p is not a node in this DFSTree.

Definition at line 490 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().

                                                                  {
        try {
          return __data[const_cast< Pattern* >(&p)]->max_indep_set;
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "pattern not found in this DFSTree");
        }
      }

Here is the caller graph for this function:

nextNodeId()

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

inherited

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

Warning

a code like

id=nextNodeId();addNode(id); 

is basically not thread safe !!

Returns

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

Definition at line 226 of file nodeGraphPart_inl.h.

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

                                                {
    NodeId next = 0;

    // return the first hole if holes exist
    if (__holes && (!__holes->empty()))
      next = *(__holes->begin());
    else   // in other case
      next = __boundVal;

    return next;
  }

Here is the caller graph for this function:

nodes()

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

inherited

return *this as a NodeGraphPart

Definition at line 373 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::DAG::moralGraph(), 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().

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

Here is the caller graph for this function:

nodesProperty() [1/2]

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

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

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:

nodesProperty() [2/2]

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

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

operator!=() [1/3]

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

inherited

tests whether two ArcGraphParts contain different arcs

Parameters

p	the ArcGraphPart that we compare with this

Definition at line 157 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs.

                                                                  {
    return __arcs != p.__arcs;
  }

operator!=() [2/3]

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

inherited

tests whether two DiGraphs are different

Parameters

g	the DiGraph with which "this" is compared

Definition at line 83 of file diGraph_inl.h.

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

                                                        {
    return !operator==(p);
  }

Here is the call graph for this function:

operator!=() [3/3]

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

inherited

check whether two NodeGraphParts contain different nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 357 of file nodeGraphPart_inl.h.

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

                                                                    {
    return !operator==(p);
  }

Here is the call graph for this function:

operator==() [1/3]

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

inherited

tests whether two ArcGraphParts contain the same arcs

Parameters

p	the ArcGraphPart that we compare with this

Definition at line 153 of file arcGraphPart_inl.h.

References gum::ArcGraphPart::__arcs.

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

                                                                  {
    return __arcs == p.__arcs;
  }

Here is the caller graph for this function:

operator==() [2/3]

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

inherited

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

Parameters

g	the DiGraph with which "this" is compared

Definition at line 79 of file diGraph_inl.h.

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

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

operator==() [3/3]

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

inherited

check whether two NodeGraphParts contain the same nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 343 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==().

                                                                    {
    if (__boundVal != p.__boundVal) return false;

    if (__holes)
      if (p.__holes)
        return (*__holes == *p.__holes);
      else
        return false;
    else if (p.__holes)
      return false;

    return true;
  }

Here is the caller graph for this function:

parent() [1/2]

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 398 of file DFSTree_tpl.h.

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

                                                                    {
        try {
          return *(__node_map.second(
             *(DiGraph::parents(__node_map.first(const_cast< Pattern* >(&p)))
                  .begin())));
        } catch (NotFound&) {
          if (__node_map.existsSecond(const_cast< Pattern* >(&p))) {
            GUM_ERROR(NotFound, "the given pattern is a root node");
          } else {
            GUM_ERROR(NotFound, "pattern not found in this DFSTree");
          }
        }
      }

Here is the call graph for this function:

parent() [2/2]

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 413 of file DFSTree_tpl.h.

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

                                                                                {
        try {
          return *(__node_map.second(
             *(DiGraph::parents(__node_map.first(const_cast< Pattern* >(&p)))
                  .begin())));
        } catch (NotFound&) {
          if (__node_map.existsSecond(const_cast< Pattern* >(&p))) {
            GUM_ERROR(NotFound, "the given pattern is a root node");
          } else {
            GUM_ERROR(NotFound, "pattern not found in this DFSTree");
          }
        }
      }

Here is the call graph for this function:

parents()

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

id	the node toward which the arcs returned are pointing

Definition at line 57 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::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::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::DAG::moralGraph(), 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().

                                                                   {
    __checkParents(id);
    return *(__parents[id]);
  }

Here is the call graph for this function:

pattern() [1/2]

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 448 of file DFSTree_tpl.h.

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

                                                              {
        try {
          return *(__node_map.second(id));
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "no pattern matching the given id");
        }
      }

pattern() [2/2]

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 457 of file DFSTree_tpl.h.

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

                                                                          {
        try {
          return *(__node_map.second(id));
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "no pattern matching the given id");
        }
      }

populateNodes()

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

inherited

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

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

Parameters

s	the NodeGraphPart to be copied

Definition at line 64 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(), and gum::DAG::moralGraph().

                                                          {
    clear();   // "virtual" flush of the nodes set
    __holes_size = s.__holes_size;
    __holes_resize_policy = s.__holes_resize_policy;

    if (s.__holes) __holes = new NodeSet(*s.__holes);

    __boundVal = s.__boundVal;

    __updateEndIteratorSafe();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

populateNodesFromProperty()

template<typename T >

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

inherited

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

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

roots() [1/2]

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 388 of file DFSTree_tpl.h.

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

                                                             {
        return __roots;
      }

roots() [2/2]

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 393 of file DFSTree_tpl.h.

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

                                                                         {
        return __roots;
      }

size()

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

inherited

alias for sizeNodes

Definition at line 284 of file nodeGraphPart_inl.h.

Referenced by gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::StaticTriangulation::__computeRecursiveThinning(), gum::OrderedEliminationSequenceStrategy::__isOrderNeeded(), gum::DiGraph::__topologicalOrder(), gum::StaticTriangulation::__triangulate(), gum::PartialOrderedEliminationSequenceStrategy::_isPartialOrderNeeded(), gum::BarrenNodesFinder::barrenNodes(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), gum::BayesBall::relevantPotentials(), gum::dSeparation::relevantPotentials(), gum::BayesBall::requisiteNodes(), gum::dSeparation::requisiteNodes(), gum::StaticTriangulation::setGraph(), gum::MarkovBlanket::size(), gum::EssentialGraph::size(), gum::DAGmodel::size(), gum::prm::gspan::Pattern::size(), gum::StaticTriangulation::StaticTriangulation(), and gum::UndiGraph::toDot().

{ return sizeNodes(); }

Here is the caller graph for this function:

sizeArcs()

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

inherited

indicates the number of arcs stored within the ArcGraphPart

Definition at line 37 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(), and gum::InfluenceDiagram< GUM_SCALAR >::toString().

{ return __arcs.size(); }

Here is the call graph for this function:

Here is the caller graph for this function:

sizeNodes()

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

inherited

returns the number of nodes in the NodeGraphPart

Definition at line 280 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().

                                             {
    return (__holes) ? (__boundVal - __holes->size()) : __boundVal;
  }

Here is the caller graph for this function:

strategy() [1/2]

template<typename GUM_SCALAR >

INLINE SearchStrategy< GUM_SCALAR > & gum::prm::gspan::DFSTree< GUM_SCALAR >::strategy

(

)

strategy getter

Definition at line 530 of file DFSTree_tpl.h.

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

                                                                           {
        return *__strategy;
      }

strategy() [2/2]

template<typename GUM_SCALAR >

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

(

)

const

strategy getter

Definition at line 536 of file DFSTree_tpl.h.

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

                                                         {
        return *__strategy;
      }

toDot()

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

virtualinherited

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

Parameters

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

Returns

Returns a string describing the graph in the dot syntax

Reimplemented in gum::MixedGraph.

Definition at line 68 of file diGraph.cpp.

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

                                       {
    std::stringstream strBuff;
    std::string       tab = "     ";
    strBuff << "digraph {" << std::endl;

    for (const auto node : nodes())
      strBuff << tab << node << ";" << std::endl;

    strBuff << std::endl;

    for (const auto& arc : arcs())
      strBuff << tab << arc.tail() << " -> " << arc.head() << ";" << std::endl;

    strBuff << "}" << std::endl << std::endl;
    return strBuff.str();
  }

Here is the call graph for this function:

topologicalOrder()

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

clear

If false returns the previously created topology.

Exceptions

InvalidDirectedCycle

Raised if this DiGraph contains cycles.

Definition at line 91 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().

                                                                      {
    if (clear
        || (__mutableTopologicalOrder
            == nullptr)) {   // we have to call _topologicalOrder
      if (__mutableTopologicalOrder == nullptr) {
        __mutableTopologicalOrder = new Sequence< NodeId >();
      } else {
        // clear is True
        __mutableTopologicalOrder->clear();
      }

      __topologicalOrder();
    }

    return *__mutableTopologicalOrder;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

toString()

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

virtualinherited

to friendly display the content of the graph

Reimplemented in gum::MixedGraph.

Definition at line 61 of file diGraph.cpp.

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

Referenced by gum::operator<<().

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

Here is the call graph for this function:

Here is the caller graph for this function:

unvirtualizedEraseChildren()

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

inherited

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

Parameters

id	the node whose outgoing arcs will be removed

Definition at line 141 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().

                                                                      {
    if (__children.exists(id)) {
      NodeSet& children = *(__children[id]);

      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(id, *iter));
      }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

unvirtualizedEraseParents()

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

inherited

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

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 129 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().

                                                                     {
    if (__parents.exists(id)) {
      NodeSet& parents = *(__parents[id]);

      for (auto iter = parents.beginSafe();   // safe iterator needed here
           iter != parents.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(*iter, id));
      }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

__data

template<typename GUM_SCALAR>

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

private

Data about patterns in this DFSTree.

Definition at line 274 of file DFSTree.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::children(), gum::prm::gspan::DFSTree< GUM_SCALAR >::data(), gum::prm::gspan::DFSTree< GUM_SCALAR >::frequency(), gum::prm::gspan::DFSTree< GUM_SCALAR >::iso_graph(), gum::prm::gspan::DFSTree< GUM_SCALAR >::iso_map(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::max_indep_set().

__graph

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 264 of file DFSTree.h.

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

__node_map

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 271 of file DFSTree.h.

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

__roots

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 267 of file DFSTree.h.

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

__strategy

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 277 of file DFSTree.h.

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

onArcAdded

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

inherited

Definition at line 83 of file arcGraphPart.h.

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

onArcDeleted

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

inherited

Definition at line 84 of file arcGraphPart.h.

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

onNodeAdded

Signaler1< NodeId > gum::NodeGraphPart::onNodeAdded

inherited

Definition at line 274 of file nodeGraphPart.h.

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

onNodeDeleted

Signaler1< NodeId > gum::NodeGraphPart::onNodeDeleted

inherited

Definition at line 275 of file nodeGraphPart.h.

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

---

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

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