Partial Ancestral Graph: undirected topology with endpoint marks. More...

#include <PAG.h>

Inheritance diagram for gum::PAG:

Collaboration diagram for gum::PAG:

Public Types
using	EdgeIterator = EdgeSetIterator
using	NodeIterator = NodeGraphPartIterator
using	NodeConstIterator = NodeGraphPartIterator
using	NodeIteratorSafe = NodeGraphPartIteratorSafe
using	NodeConstIteratorSafe = NodeGraphPartIteratorSafe

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

Public Member Functions
Constructors / Destructors
	PAG ()
	PAG (const PAG &)
	PAG (PAG &&) noexcept
	~PAG () override
PAG &	operator= (const PAG &)
PAG &	operator= (PAG &&) noexcept
Edge operations (override UndiGraph/EdgeGraphPart virtuals)
void	addEdge (NodeId x, NodeId y) override
	add edge with Circle-Circle marks
void	addEdge (NodeId x, NodeId y, EdgeMark markAtX, EdgeMark markAtY)
	add edge with explicit endpoint marks
void	eraseEdge (const Edge &e) override
	remove edge and its two mark entries
void	clearEdges () override
	clear all edges (and their marks)
void	eraseNode (NodeId id) override
	remove node and clean up marks for all its adjacent edges
void	clear () override
	remove all nodes, edges, and marks
Mark accessors
EdgeMark	markAt (NodeId src, NodeId dst) const
	mark at dst-endpoint when traversing from src
void	setMarkAt (NodeId src, NodeId dst, EdgeMark m)
	set mark at dst-endpoint when traversing from src
Endpoint-mark predicates
bool	isArrowhead (NodeId src, NodeId dst) const
	true if mark at dst (from src) is Arrowhead
bool	isTail (NodeId src, NodeId dst) const
	true if mark at dst (from src) is Tail
bool	isCircle (NodeId src, NodeId dst) const
	true if mark at dst (from src) is Circle
bool	isDefinitelyDirected (NodeId x, NodeId y) const
	true if edge x-y is definitely directed x→y (Tail@x, Arrowhead@y)
bool	isBidirected (NodeId x, NodeId y) const
	true if edge x-y is bidirected x↔y (Arrowhead on both endpoints)
bool	isDefCollider (NodeId x, NodeId z, NodeId y) const
	true if z is a definite collider on path x-z-y (Arrowhead at z from both sides)
Bulk operations
void	reorientAllWith (EdgeMark m)
	set all endpoint marks to m (used between FCI phases to reset to Circle)
Conversion / display
MixedGraph	toMixedGraph () const
	approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge
std::string	toString () const override
	approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge
std::string	toDot () const override
	approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge
Operators
bool	operator== (const UndiGraph &g) const
	tests whether two UndiGraphs are identical (same nodes, same edges)
Operators
bool	operator== (const EdgeGraphPart &p) const
	tests whether two EdgeGraphParts contain the same edges
Accessors/Modifiers
bool	hasUndirectedCycle () const
	checks whether the graph contains cycles
virtual UndiGraph	partialUndiGraph (NodeSet nodes)
	returns the partial graph formed by the nodes given in parameter
NodeProperty< NodeId >	chainComponents () const
	returns a property {node:id of chain component} (edges only)
NodeProperty< NodeId >	connectedComponents () const
	returns a property {node:id of weakly connected component}
std::optional< std::vector< NodeId > >	undirectedPath (NodeId node1, NodeId node2) const
	returns a shortest undirected path from node1 to node2, or std::nullopt if none
bool	hasUndirectedPath (NodeId n1, NodeId n2) const
	returns true if n1 and n2 are connected by an undirected path
bool	hasUndirectedPath (NodeId n1, NodeId n2, const NodeSet &except) const
	returns true if n1 and n2 are connected by a path avoiding nodes in except
bool	hasUndirectedPath (const NodeSet &n1, const NodeSet &n2, const NodeSet &except) const
	returns true if any node in n1 reaches any node in n2 avoiding except
Accessors/Modifiers
bool	existsEdge (const Edge &edge) const
	indicates whether a given edge exists
bool	existsEdge (NodeId n1, NodeId n2) const
	indicates whether a given edge exists
bool	emptyEdges () const
	indicates wether the EdgeGraphPart contains any edge
Size	sizeEdges () const
	indicates the number of edges stored within the EdgeGraphPart
const EdgeSet &	edges () const
	returns the set of edges stored within the EdgeGraphPart
const NodeSet &	neighbours (NodeId id) const
	returns the set of node neighbours to a given node
void	eraseNeighbours (NodeId id)
	erase all the edges adjacent to a given node
void	unvirtualizedEraseNeighbours (NodeId id)
	same function as eraseNeighbours but without any virtual call to an erase
template<typename VAL>
EdgeProperty< VAL >	edgesProperty (VAL(*f)(const Edge &), Size size=0) const
	a method to create a hashMap of VAL from a set of edges (using for every edge, say x, the VAL f(x))
template<typename VAL>
EdgeProperty< VAL >	edgesProperty (const VAL &val, Size size=0) const
	a method to create a hashMap of VAL from a set of edges (using for every edge, say x, the VAL a)
template<typename VAL>
List< VAL >	listMapEdges (VAL(*f)(const Edge &)) const
	a method to create a list of VAL from a set of edges (using for every edge, say x, the VAL f(x))
Operators
bool	operator== (const NodeGraphPart &p) const
	check whether two NodeGraphParts contain the same nodes
Accessors/Modifiers
void	populateNodes (const NodeGraphPart &s)
	populateNodes clears *this and fills it with the same nodes as "s"
template<typename T>
void	populateNodesFromProperty (const NodeProperty< T > &h)
	populateNodesFromProperty clears *this and fills it with the keys of "h"
NodeId	nextNodeId () const
	returns a new node id, not yet used by any node
virtual NodeId	addNode ()
	insert a new node and return its id
std::vector< NodeId >	addNodes (Size n)
	insert n nodes
virtual void	addNodeWithId (const NodeId id)
	try to insert a node with the given id
bool	existsNode (const NodeId id) const
	returns true iff the NodeGraphPart contains the given nodeId
bool	exists (const NodeId id) const
	alias for existsNode
bool	emptyNodes () const
	indicates whether there exists nodes in the NodeGraphPart
bool	empty () const
	alias for emptyNodes
virtual void	clearNodes ()
	remove all the nodes from the NodeGraphPart
Size	sizeNodes () const
	returns the number of nodes in the NodeGraphPart
Size	size () const
	alias for sizeNodes
NodeId	bound () const
	returns a number n such that all node ids are strictly lower than n
NodeSet	asNodeSet () const
	returns a copy of the set of nodes represented by the NodeGraphPart
const NodeGraphPart &	nodes () const
	return *this as a NodeGraphPart
node_iterator_safe	beginSafe () const
	a begin iterator to parse the set of nodes contained in the NodeGraphPart
const node_iterator_safe &	endSafe () const noexcept
	the end iterator to parse the set of nodes contained in the NodeGraphPart
node_iterator	begin () const noexcept
	a begin iterator to parse the set of nodes contained in the NodeGraphPart
const node_iterator &	end () const noexcept
	the end iterator to parse the set of nodes contained in the NodeGraphPart
std::string	nameFromId (NodeId id) const
	returns the name of node id, or "<id>" if no name is set
std::optional< NodeId >	idFromName (const std::string &name) const
	returns the id of the node with the given name, or std::nullopt
void	setName (NodeId id, const std::string &name)
	sets the name of node id
bool	hasName (NodeId id) const
	returns true iff node id has an explicit name
std::string	dotNodeLabel (NodeId id) const
	returns " [label=\"...\"]" with DOT-escaped name, or "" if no name
template<typename VAL>
NodeProperty< VAL >	nodesPropertyFromFunction (VAL(*f)(const NodeId &), Size size=0) const
	a method to create a HashTable with key:NodeId and value:VAL
template<typename VAL>
NodeProperty< VAL >	nodesPropertyFromVal (const VAL &a, Size size=0) const
	a method to create a hashMap with key:NodeId and value:VAL
template<typename VAL>
List< VAL >	listMapNodes (VAL(*f)(const NodeId &)) const
	a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))

Static Public Member Functions
Constructors / Destructors
static UndiGraph	completeGraph (int n)
	create a complete UndiGraph with n nodes

Public Attributes
Signaler< NodeId, NodeId >	onEdgeAdded
Signaler< NodeId, NodeId >	onEdgeDeleted
Signaler< NodeId >	onNodeAdded
Signaler< NodeId >	onNodeDeleted

Private Member Functions
void	_checkNeighbours_ (NodeId id)
	when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set entry to neighbours[id]
void	_clearEdges_ ()

Private Attributes
ArcProperty< EdgeMark >	marks_
	marks_[Arc(x,y)] = mark at y-endpoint of edge x-y
EdgeSet	_edges_
	the set of all the edges contained within the EdgeGraphPart
NodeProperty< NodeSet * >	_neighbours_
	for each node, the set of its adjacent edges

Detailed Description

Partial Ancestral Graph: undirected topology with endpoint marks.

Extends UndiGraph: the edge topology is stored in the base class; each edge carries two EdgeMark values (one per endpoint) stored in marks_.

marks_[Arc(x,y)] = mark at the y-endpoint of edge x-y.

Edge types represented:

o-o (Circle-Circle) : completely uncertain
o-> (Circle-Arrowhead): possibly directed
-> (Tail-Arrowhead) : definitely directed
<-> (Arrowhead-Arrowhead) : bidirected (latent confounder)
– (Tail-Tail) : definitely undirected

Definition at line 90 of file PAG.h.

Member Typedef Documentation

◆ EdgeIterator

using gum::EdgeGraphPart::EdgeIterator = EdgeSetIterator

inherited

Definition at line 96 of file edgeGraphPart.h.

◆ node_const_iterator

using gum::NodeGraphPart::node_const_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 268 of file nodeGraphPart.h.

◆ node_const_iterator_safe

using gum::NodeGraphPart::node_const_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 270 of file nodeGraphPart.h.

◆ node_iterator

using gum::NodeGraphPart::node_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 267 of file nodeGraphPart.h.

◆ node_iterator_safe

using gum::NodeGraphPart::node_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 269 of file nodeGraphPart.h.

◆ NodeConstIterator

using gum::NodeGraphPart::NodeConstIterator = NodeGraphPartIterator

inherited

Definition at line 277 of file nodeGraphPart.h.

◆ NodeConstIteratorSafe

using gum::NodeGraphPart::NodeConstIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 279 of file nodeGraphPart.h.

◆ NodeIterator

using gum::NodeGraphPart::NodeIterator = NodeGraphPartIterator

inherited

Definition at line 276 of file nodeGraphPart.h.

◆ NodeIteratorSafe

using gum::NodeGraphPart::NodeIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 278 of file nodeGraphPart.h.

Constructor & Destructor Documentation

◆ PAG() [1/3]

gum::PAG::PAG ( )

Definition at line 57 of file PAG.cpp.

57{ GUM_CONSTRUCTOR(PAG); }

gum::PAG::PAG

PAG()

Definition PAG.cpp:57

References PAG().

Referenced by PAG(), PAG(), PAG(), ~PAG(), operator=(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PAG() [2/3]

gum::PAG::PAG ( const PAG & other )

Definition at line 59 of file PAG.cpp.

                           : NodeGraphPart(other), UndiGraph(other), marks_(other.marks_) {
    GUM_CONS_CPY(PAG);
  }

References PAG(), gum::UndiGraph::UndiGraph(), and marks_.

Here is the call graph for this function:

◆ PAG() [3/3]

gum::PAG::PAG ( PAG && other )

noexcept

Definition at line 63 of file PAG.cpp.

                               :
      NodeGraphPart(std::move(other)), UndiGraph(std::move(other)),
      marks_(std::move(other.marks_)) {
    GUM_CONS_MOV(PAG);
  }

References PAG(), gum::UndiGraph::UndiGraph(), and marks_.

Here is the call graph for this function:

◆ ~PAG()

gum::PAG::~PAG ( )

override

Definition at line 69 of file PAG.cpp.

69{ GUM_DESTRUCTOR(PAG); }

References PAG().

Here is the call graph for this function:

Member Function Documentation

◆ _checkNeighbours_()

INLINE void gum::EdgeGraphPart::_checkNeighbours_ ( NodeId id )

privateinherited

when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set entry to neighbours[id]

Parameters

id	the node whose neighbours[id] is checked

Definition at line 68 of file edgeGraphPart_inl.h.

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

References _neighbours_.

Referenced by addEdge().

Here is the caller graph for this function:

◆ _clearEdges_()

void gum::EdgeGraphPart::_clearEdges_ ( )

privateinherited

Definition at line 93 of file edgeGraphPart.cpp.

                                   {
    for (const auto& elt: _neighbours_)
      delete elt.second;
 
    _neighbours_.clear();
 
    if (onEdgeDeleted.hasListener()) {
      EdgeSet tmp = _edges_;
      _edges_.clear();
 
      for (const auto& edge: tmp)
        GUM_EMIT2(onEdgeDeleted, edge.first(), edge.second());
    } else {
      _edges_.clear();
    }
  }

References _edges_, _neighbours_, GUM_EMIT2, and onEdgeDeleted.

Referenced by ~EdgeGraphPart(), and clearEdges().

Here is the caller graph for this function:

◆ addEdge() [1/2]

void gum::PAG::addEdge	(	NodeId	x,
		NodeId	y )

overridevirtual

add edge with Circle-Circle marks

Reimplemented from gum::EdgeGraphPart.

Definition at line 91 of file PAG.cpp.

91{ addEdge(x, y, EdgeMark::Circle, EdgeMark::Circle); }

gum::PAG::addEdge

void addEdge(NodeId x, NodeId y) override

add edge with Circle-Circle marks

Definition PAG.cpp:91

gum::EdgeMark::Circle

@ Circle

Definition PAG.h:65

References addEdge(), and gum::Circle.

Referenced by addEdge(), and gum::learning::FCI::learnPAG().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addEdge() [2/2]

void gum::PAG::addEdge	(	NodeId	x,
		NodeId	y,
		EdgeMark	markAtX,
		EdgeMark	markAtY )

add edge with explicit endpoint marks

Definition at line 93 of file PAG.cpp.

                                                                          {
    if (existsEdge(x, y)) { return; }
    UndiGraph::addEdge(x, y);
    // marks_[Arc(x,y)] = mark at y; marks_[Arc(y,x)] = mark at x
    marks_.insert(Arc(x, y), markAtY);
    marks_.insert(Arc(y, x), markAtX);
  }

References gum::UndiGraph::addEdge(), gum::EdgeGraphPart::existsEdge(), and marks_.

Here is the call graph for this function:

◆ addNode()

INLINE NodeId gum::NodeGraphPart::addNode ( )

virtualinherited

insert a new node and return its id

Returns: the id chosen by the internal idFactory

Reimplemented in gum::CliqueGraph.

Definition at line 269 of file nodeGraphPart_inl.h.

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

References _boundVal_, _eraseHole_(), _holes_, _updateEndIteratorSafe_(), GUM_EMIT1, and onNodeAdded.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::StructuredInference< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot(), and populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addNodes()

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

inherited

insert n nodes

Parameters

n	the number of nodes to add

Returns: the vector of chosen ids

Definition at line 287 of file nodeGraphPart_inl.h.

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

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

Here is the caller graph for this function:

◆ addNodeWithId()

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

virtualinherited

try to insert a node with the given id

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

Exceptions

DuplicateElement exception if the id already exists

Reimplemented in gum::CliqueGraph.

Definition at line 214 of file nodeGraphPart.cpp.

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

References _boundVal_, _eraseHole_(), _holes_, _holes_resize_policy_, _holes_size_, _inHoles_(), _updateEndIteratorSafe_(), GUM_EMIT1, GUM_ERROR, and onNodeAdded.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::Separation::isForwardSeparated(), gum::learning::IBNLearner::learnDag_(), gum::learning::FCI::learnPAG(), gum::learning::SimpleMiic::learnStructure(), gum::graph::markovBlanket(), gum::graph::moralGraph(), gum::graph::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), populateNodesFromProperty(), gum::learning::IBNLearner::prepareFCI_(), gum::learning::IBNLearner::prepareMiic_(), gum::learning::IBNLearner::preparePC_(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), gum::learning::StructuralConstraintDAG::setGraphAlone(), gum::EssentialGraph::skeleton(), and gum::PAG::toMixedGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ asNodeSet()

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

inherited

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

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

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

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

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

as this is faster and consumes much less memory.

Definition at line 367 of file nodeGraphPart_inl.h.

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

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin()

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

noexceptinherited

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

Definition at line 346 of file nodeGraphPart_inl.h.

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

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ beginSafe()

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

inherited

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

Definition at line 334 of file nodeGraphPart_inl.h.

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

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

Referenced by populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bound()

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

inherited

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

Definition at line 323 of file nodeGraphPart_inl.h.

323{ return _boundVal_; }

References _boundVal_.

Referenced by _clearNodes_(), and populateNodesFromProperty().

Here is the caller graph for this function:

◆ chainComponents()

INLINE NodeProperty< NodeId > gum::UndiGraph::chainComponents ( ) const

inherited

returns a property {node:id of chain component} (edges only)

Definition at line 123 of file undiGraph_inl.h.

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

References gum::graph::chainComponents().

Here is the call graph for this function:

◆ clear()

void gum::PAG::clear ( )

overridevirtual

remove all nodes, edges, and marks

Reimplemented from gum::NodeGraphPart.

Definition at line 125 of file PAG.cpp.

                  {
    marks_.clear();
    UndiGraph::clear();
  }

References gum::UndiGraph::clear(), and marks_.

Here is the call graph for this function:

◆ clearEdges()

void gum::PAG::clearEdges ( )

overridevirtual

clear all edges (and their marks)

Reimplemented from gum::EdgeGraphPart.

Definition at line 108 of file PAG.cpp.

                       {
    marks_.clear();
    EdgeGraphPart::clearEdges();
  }

References gum::EdgeGraphPart::clearEdges(), and marks_.

Here is the call graph for this function:

◆ clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )

virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 325 of file nodeGraphPart_inl.h.

325{ _clearNodes_(); }

gum::NodeGraphPart::_clearNodes_

void _clearNodes_()

code for clearing nodes (called twice)

Definition nodeGraphPart.cpp:237

References _clearNodes_().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ completeGraph()

UndiGraph gum::UndiGraph::completeGraph ( int n )

staticinherited

create a complete UndiGraph with n nodes

Parameters

n int

Returns: the complete UndiGraph

Definition at line 61 of file undiGraph.cpp.

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

References UndiGraph(), addEdge(), and gum::NodeGraphPart::addNodes().

Here is the call graph for this function:

◆ connectedComponents()

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

inherited

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

Definition at line 127 of file undiGraph_inl.h.

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

References gum::graph::connectedComponents().

Here is the call graph for this function:

◆ dotNodeLabel()

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

inherited

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

Definition at line 188 of file nodeGraphPart.cpp.

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

References _names_, and hasName().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ edges()

INLINE const EdgeSet & gum::EdgeGraphPart::edges ( ) const

inherited

returns the set of edges stored within the EdgeGraphPart

Definition at line 60 of file edgeGraphPart_inl.h.

60{ return _edges_; }

References _edges_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::BarrenNodesFinder::barrenNodes(), gum::learning::ConstraintBasedLearning::initGraph_(), gum::learning::FCI::learnPAG(), gum::learning::FCI::possibleDSepPhase_(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::PAG::reorientAllWith(), gum::learning::IBNLearner::setPossibleSkeleton(), gum::PAG::toDot(), gum::PAG::toMixedGraph(), and gum::PAG::toString().

Here is the caller graph for this function:

◆ edgesProperty() [1/2]

template<typename VAL>

EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty	(	const VAL &	val,
		Size	size = 0 ) const

inherited

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

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 edges. If you do not specify this parameter, the method will assign it for you.

◆ edgesProperty() [2/2]

template<typename VAL>

EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty	(	VAL(*	f )(const Edge &),
		Size	size = 0 ) const

inherited

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

Parameters

f	a function assigning a VAL to any edge
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 edges. If you do not specify this parameter, the method will assign it for you.

◆ empty()

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

inherited

alias for emptyNodes

Definition at line 321 of file nodeGraphPart_inl.h.

321{ return emptyNodes(); }

gum::NodeGraphPart::emptyNodes

bool emptyNodes() const

indicates whether there exists nodes in the NodeGraphPart

Definition nodeGraphPart_inl.h:319

References emptyNodes().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emptyEdges()

INLINE bool gum::EdgeGraphPart::emptyEdges ( ) const

inherited

indicates wether the EdgeGraphPart contains any edge

Definition at line 56 of file edgeGraphPart_inl.h.

56{ return _edges_.empty(); }

References _edges_.

◆ emptyNodes()

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

inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 319 of file nodeGraphPart_inl.h.

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

References sizeNodes().

Referenced by empty(), and populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ end()

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

noexceptinherited

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

Definition at line 352 of file nodeGraphPart_inl.h.

                                                                        {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIterator.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ endSafe()

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

noexceptinherited

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

Definition at line 342 of file nodeGraphPart_inl.h.

                                                                                {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIteratorSafe.

Referenced by populateNodesFromProperty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseEdge()

void gum::PAG::eraseEdge ( const Edge & e )

overridevirtual

remove edge and its two mark entries

Reimplemented from gum::EdgeGraphPart.

Definition at line 101 of file PAG.cpp.

                                   {
    if (!existsEdge(e)) { return; }
    if (marks_.exists(Arc(e.first(), e.second()))) { marks_.erase(Arc(e.first(), e.second())); }
    if (marks_.exists(Arc(e.second(), e.first()))) { marks_.erase(Arc(e.second(), e.first())); }
    EdgeGraphPart::eraseEdge(e);
  }

References gum::EdgeGraphPart::eraseEdge(), gum::EdgeGraphPart::existsEdge(), gum::Edge::first(), marks_, and gum::Edge::second().

Referenced by gum::learning::FCI::possibleDSepPhase_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseNeighbours()

INLINE void gum::EdgeGraphPart::eraseNeighbours ( NodeId id )

inherited

erase all the edges adjacent to a given node

Parameters

id	the node the adjacent edges of which will be removed

Warning: if no edge is adjacent to id, nothing is done. In particular, no exception is thrown.; although this method is not virtual, it calls method eraseEdge( const Edge& edge ) and, as such, has a "virtual" behaviour

Definition at line 102 of file edgeGraphPart_inl.h.

                                                      {
    if (_neighbours_.exists(id)) {
      const NodeSet& set = *(_neighbours_[id]);
 
      for (auto iter = set.beginSafe(); iter != set.endSafe();
           ++iter) {   // safe iterator needed here
        // warning: use this erases so that you actually use the virtualized
        // edge removal function
        eraseEdge(Edge(*iter, id));
      }
    }
  }

References _neighbours_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), and eraseEdge().

Here is the call graph for this function:

◆ eraseNode()

void gum::PAG::eraseNode ( NodeId id )

overridevirtual

remove node and clean up marks for all its adjacent edges

Reimplemented from gum::NodeGraphPart.

Definition at line 113 of file PAG.cpp.

                               {
    if (existsNode(id)) {
      // unvirtualizedEraseNeighbours (called by UndiGraph::eraseNode) bypasses
      // PAG::eraseEdge, so we clean marks manually before delegating
      for (const NodeId nb: neighbours(id)) {
        if (marks_.exists(Arc(id, nb))) { marks_.erase(Arc(id, nb)); }
        if (marks_.exists(Arc(nb, id))) { marks_.erase(Arc(nb, id)); }
      }
    }
    UndiGraph::eraseNode(id);
  }

References gum::UndiGraph::eraseNode(), gum::NodeGraphPart::existsNode(), marks_, and gum::EdgeGraphPart::neighbours().

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

307{ return existsNode(node); }

References existsNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ existsEdge() [1/2]

INLINE bool gum::EdgeGraphPart::existsEdge ( const Edge & edge ) const

inherited

indicates whether a given edge exists

Parameters

edge	the edge we test whether or not it belongs to the EdgeGraphPart

Definition at line 62 of file edgeGraphPart_inl.h.

62{ return _edges_.contains(edge); }

References _edges_.

Here is the caller graph for this function:

◆ existsEdge() [2/2]

INLINE bool gum::EdgeGraphPart::existsEdge	(	NodeId	n1,
		NodeId	n2 ) const

inherited

indicates whether a given edge exists

Parameters

n1	the id of one extremity of the edge we test the existence in the EdgeGraphPart
n2	the id of the other extremity of the edge we test the existence in the EdgeGraphPart

Definition at line 64 of file edgeGraphPart_inl.h.

                                                                         {
    return _neighbours_.exists(first) && _neighbours_[first]->exists(second);
  }

References _neighbours_.

◆ existsNode()

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

inherited

returns true iff the NodeGraphPart contains the given nodeId

Definition at line 301 of file nodeGraphPart_inl.h.

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

References _boundVal_, and _inHoles_().

Referenced by eraseNode(), gum::PAG::eraseNode(), exists(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::Separation::isForwardSeparated(), gum::graph::markovBlanket(), gum::graph::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), populateNodesFromProperty(), gum::Separation::reduceForDSeparation(), and setName().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasName()

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

inherited

returns true iff node id has an explicit name

Definition at line 186 of file nodeGraphPart.cpp.

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

References _names_.

Referenced by dotNodeLabel(), and populateNodesFromProperty().

Here is the caller graph for this function:

◆ hasUndirectedCycle()

INLINE bool gum::UndiGraph::hasUndirectedCycle ( ) const

inherited

checks whether the graph contains cycles

Definition at line 131 of file undiGraph_inl.h.

131{ return graph::hasUndirectedCycle(*this); }

gum::graph::hasUndirectedCycle

bool hasUndirectedCycle(const G &g)

Returns true if g contains at least one undirected cycle.

Definition cycleDetection_tpl.h:88

References gum::graph::hasUndirectedCycle().

Here is the call graph for this function:

◆ hasUndirectedPath() [1/3]

INLINE bool gum::UndiGraph::hasUndirectedPath	(	const NodeSet &	n1,
		const NodeSet &	n2,
		const NodeSet &	except ) const

inherited

returns true if any node in n1 reaches any node in n2 avoiding except

Definition at line 117 of file undiGraph_inl.h.

                                                                        {
    return graph::hasUndirectedPath(*this, n1, n2, except);
  }

References gum::graph::hasUndirectedPath().

Here is the call graph for this function:

◆ hasUndirectedPath() [2/3]

INLINE bool gum::UndiGraph::hasUndirectedPath	(	NodeId	n1,
		NodeId	n2 ) const

inherited

returns true if n1 and n2 are connected by an undirected path

Definition at line 109 of file undiGraph_inl.h.

                                                                     {
    return graph::hasUndirectedPath(*this, n1, n2);
  }

References gum::graph::hasUndirectedPath().

Here is the call graph for this function:

◆ hasUndirectedPath() [3/3]

INLINE bool gum::UndiGraph::hasUndirectedPath	(	NodeId	n1,
		NodeId	n2,
		const NodeSet &	except ) const

inherited

returns true if n1 and n2 are connected by a path avoiding nodes in except

n2 in except naturally leads to false

Definition at line 113 of file undiGraph_inl.h.

                                                                                            {
    return graph::hasUndirectedPath(*this, n1, n2, except);
  }

References gum::graph::hasUndirectedPath().

Here is the call graph for this function:

◆ idFromName()

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

inherited

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

Definition at line 165 of file nodeGraphPart.cpp.

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

References _names_.

Referenced by populateNodesFromProperty().

Here is the caller graph for this function:

◆ isArrowhead()

bool gum::PAG::isArrowhead	(	NodeId	src,
		NodeId	dst ) const

true if mark at dst (from src) is Arrowhead

Definition at line 142 of file PAG.cpp.

                                                    {
    return markAt(src, dst) == EdgeMark::Arrowhead;
  }

References gum::Arrowhead, and markAt().

Referenced by isBidirected(), isDefCollider(), isDefinitelyDirected(), gum::learning::FCI::ruleR10_(), gum::learning::FCI::ruleR1_(), gum::learning::FCI::ruleR2_(), gum::learning::FCI::ruleR3_(), gum::learning::FCI::ruleR4_(), gum::learning::FCI::ruleR8_(), gum::learning::FCI::ruleR9_(), toDot(), and toMixedGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isBidirected()

bool gum::PAG::isBidirected	(	NodeId	x,
		NodeId	y ) const

true if edge x-y is bidirected x↔y (Arrowhead on both endpoints)

Definition at line 155 of file PAG.cpp.

                                                 {
    return isArrowhead(x, y) && isArrowhead(y, x);
  }

References isArrowhead().

Referenced by gum::learning::FCI::learnPAG().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isCircle()

bool gum::PAG::isCircle	(	NodeId	src,
		NodeId	dst ) const

true if mark at dst (from src) is Circle

Definition at line 148 of file PAG.cpp.

148{ return markAt(src, dst) == EdgeMark::Circle; }

References gum::Circle, and markAt().

Referenced by gum::learning::FCI::ruleR10_(), gum::learning::FCI::ruleR1_(), gum::learning::FCI::ruleR2_(), gum::learning::FCI::ruleR3_(), gum::learning::FCI::ruleR4_(), gum::learning::FCI::ruleR5_(), gum::learning::FCI::ruleR6_(), gum::learning::FCI::ruleR7_(), gum::learning::FCI::ruleR8_(), gum::learning::FCI::ruleR9_(), and toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isDefCollider()

bool gum::PAG::isDefCollider	(	NodeId	x,
		NodeId	z,
		NodeId	y ) const

true if z is a definite collider on path x-z-y (Arrowhead at z from both sides)

Definition at line 159 of file PAG.cpp.

                                                            {
    // z is a definite collider on x-z-y iff both endpoints at z are Arrowhead
    return isArrowhead(x, z) && isArrowhead(y, z);
  }

References isArrowhead().

Referenced by gum::learning::FCI::computePossibleDSep_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isDefinitelyDirected()

bool gum::PAG::isDefinitelyDirected	(	NodeId	x,
		NodeId	y ) const

true if edge x-y is definitely directed x→y (Tail@x, Arrowhead@y)

Definition at line 150 of file PAG.cpp.

                                                         {
    // Tail at x (from y's perspective) and Arrowhead at y (from x's perspective)
    return isTail(y, x) && isArrowhead(x, y);
  }

References isArrowhead(), and isTail().

Here is the call graph for this function:

◆ isTail()

bool gum::PAG::isTail	(	NodeId	src,
		NodeId	dst ) const

true if mark at dst (from src) is Tail

Definition at line 146 of file PAG.cpp.

146{ return markAt(src, dst) == EdgeMark::Tail; }

gum::EdgeMark::Tail

@ Tail

Definition PAG.h:65

References markAt(), and gum::Tail.

Referenced by isDefinitelyDirected(), gum::learning::FCI::ruleR10_(), gum::learning::FCI::ruleR1_(), gum::learning::FCI::ruleR2_(), gum::learning::FCI::ruleR4_(), gum::learning::FCI::ruleR6_(), gum::learning::FCI::ruleR7_(), and gum::learning::FCI::ruleR8_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ listMapEdges()

template<typename VAL>

List< VAL > gum::EdgeGraphPart::listMapEdges ( VAL(* f )(const Edge &) ) const

inherited

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

Parameters

f	a function assigning a VAL to any edge

◆ listMapNodes()

template<typename VAL>

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

inherited

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

Parameters

f	a function assigning a VAL to any node

References listMapNodes().

Referenced by listMapNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ markAt()

EdgeMark gum::PAG::markAt	(	NodeId	src,
		NodeId	dst ) const

mark at dst-endpoint when traversing from src

Definition at line 134 of file PAG.cpp.

134{ return marks_[Arc(src, dst)]; }

References marks_.

Referenced by isArrowhead(), isCircle(), isTail(), and toString().

Here is the caller graph for this function:

◆ nameFromId()

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

inherited

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

Definition at line 160 of file nodeGraphPart.cpp.

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

References _names_.

Referenced by populateNodesFromProperty().

Here is the caller graph for this function:

◆ neighbours()

INLINE const NodeSet & gum::EdgeGraphPart::neighbours ( NodeId id ) const

inherited

returns the set of node neighbours to a given node

Note that the set of nodes returned may be empty if no edge within the EdgeGraphPart is adjacent the given node.

Parameters

id	the node to which the edges are adjacent

Definition at line 97 of file edgeGraphPart_inl.h.

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

References _neighbours_, and gum::emptyNodeSet.

Here is the caller graph for this function:

◆ nextNodeId()

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

inherited

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

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

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

gum::NodeGraphPart::addNode
virtual NodeId addNode()
insert a new node and return its id
Definition nodeGraphPart_inl.h:269

is basically not thread safe !!

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

Definition at line 243 of file nodeGraphPart_inl.h.

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

References _boundVal_, and _holes_.

Referenced by populateNodesFromProperty().

Here is the caller graph for this function:

◆ nodes()

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

inherited

return *this as a NodeGraphPart

Definition at line 379 of file nodeGraphPart_inl.h.

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

References NodeGraphPart().

Here is the call graph for this function:

◆ nodesPropertyFromFunction()

template<typename VAL>

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

inherited

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

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

See also: HashTable::map.

Parameters

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

References nodesPropertyFromFunction(), and size().

Referenced by nodesPropertyFromFunction().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nodesPropertyFromVal()

template<typename VAL>

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

inherited

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

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

See also: HashTable::map.

Parameters

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

References nodesPropertyFromVal(), and size().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator=() [1/2]

PAG & gum::PAG::operator= ( const PAG & other )

Definition at line 71 of file PAG.cpp.

                                    {
    if (this != &other) {
      UndiGraph::operator=(other);
      marks_ = other.marks_;
    }
    return *this;
  }

References PAG(), marks_, and gum::UndiGraph::operator=().

Here is the call graph for this function:

◆ operator=() [2/2]

PAG & gum::PAG::operator= ( PAG && other )

noexcept

Definition at line 79 of file PAG.cpp.

                                        {
    if (this != &other) {
      UndiGraph::operator=(std::move(other));
      marks_ = std::move(other.marks_);
    }
    return *this;
  }

References PAG(), marks_, and gum::UndiGraph::operator=().

Here is the call graph for this function:

◆ operator==() [1/3]

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

inherited

tests whether two EdgeGraphParts contain the same edges

Parameters

p	the EdgeGraphPart that we compare with this

Definition at line 126 of file edgeGraphPart_inl.h.

                                                                  {
    return _edges_ == p._edges_;
  }

References EdgeGraphPart(), and _edges_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [2/3]

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

inherited

check whether two NodeGraphParts contain the same nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 356 of file nodeGraphPart_inl.h.

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

References NodeGraphPart(), _boundVal_, and _holes_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [3/3]

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

inherited

tests whether two UndiGraphs are identical (same nodes, same edges)

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 100 of file undiGraph_inl.h.

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

References UndiGraph(), gum::EdgeGraphPart::operator==(), and gum::NodeGraphPart::operator==().

Here is the call graph for this function:

◆ partialUndiGraph()

UndiGraph gum::UndiGraph::partialUndiGraph ( NodeSet nodes )

virtualinherited

returns the partial graph formed by the nodes given in parameter

Definition at line 127 of file undiGraph.cpp.

                                                     {
    UndiGraph partialGraph;
 
    for (const auto node: nodes) {
      partialGraph.addNodeWithId(node);
 
      for (const auto nei: neighbours(node))
        if (nodes.contains(nei) && partialGraph.existsNode(nei)) partialGraph.addEdge(node, nei);
    }
 
    return partialGraph;
  }

References UndiGraph(), addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::NodeGraphPart::existsNode(), gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

◆ populateNodes()

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

inherited

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

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

Parameters

s	the NodeGraphPart to be copied

Definition at line 97 of file nodeGraphPart.cpp.

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

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

Referenced by operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ populateNodesFromProperty()

template<typename T>

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

inherited

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

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

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

Here is the call graph for this function:

◆ reorientAllWith()

void gum::PAG::reorientAllWith ( EdgeMark m )

set all endpoint marks to m (used between FCI phases to reset to Circle)

Definition at line 168 of file PAG.cpp.

                                      {
    for (const Edge& e: edges()) {
      setMarkAt(e.first(), e.second(), m);
      setMarkAt(e.second(), e.first(), m);
    }
  }

References gum::EdgeGraphPart::edges(), and setMarkAt().

Referenced by gum::learning::FCI::learnPAG().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setMarkAt()

void gum::PAG::setMarkAt	(	NodeId	src,
		NodeId	dst,
		EdgeMark	m )

set mark at dst-endpoint when traversing from src

Definition at line 136 of file PAG.cpp.

136{ marks_.set(Arc(src, dst), m); }

References marks_.

Referenced by gum::learning::FCI::doDdpOrientation_(), gum::learning::FCI::learnPAG(), gum::learning::FCI::orientCollidersOnPAG_(), reorientAllWith(), gum::learning::FCI::ruleR10_(), gum::learning::FCI::ruleR1_(), gum::learning::FCI::ruleR2_(), gum::learning::FCI::ruleR3_(), gum::learning::FCI::ruleR5_(), gum::learning::FCI::ruleR6_(), gum::learning::FCI::ruleR7_(), gum::learning::FCI::ruleR8_(), and gum::learning::FCI::ruleR9_().

Here is the caller graph for this function:

◆ setName()

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

inherited

sets the name of node id

Exceptions

DuplicateElement if name is already used by another node

Definition at line 170 of file nodeGraphPart.cpp.

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

References _names_, existsNode(), and GUM_ERROR.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

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

inherited

alias for sizeNodes

Definition at line 299 of file nodeGraphPart_inl.h.

299{ return sizeNodes(); }

References sizeNodes().

Referenced by gum::StaticTriangulation::StaticTriangulation(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::StaticTriangulation::_triangulate_(), nodesPropertyFromFunction(), nodesPropertyFromVal(), populateNodesFromProperty(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::dSeparationAlgorithm::requisiteNodes(), gum::prm::gspan::Pattern::size(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sizeEdges()

INLINE Size gum::EdgeGraphPart::sizeEdges ( ) const

inherited

indicates the number of edges stored within the EdgeGraphPart

Definition at line 58 of file edgeGraphPart_inl.h.

58{ return _edges_.size(); }

References _edges_.

◆ sizeNodes()

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

inherited

returns the number of nodes in the NodeGraphPart

Definition at line 295 of file nodeGraphPart_inl.h.

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

References _boundVal_, and _holes_.

Referenced by gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_(), asNodeSet(), gum::BinaryJoinTreeConverterDefault::convert(), emptyNodes(), populateNodesFromProperty(), and size().

Here is the caller graph for this function:

◆ toDot()

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

overridevirtual

approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge

Reimplemented from gum::UndiGraph.

Definition at line 230 of file PAG.cpp.

                             {
    std::ostringstream out;
    out << "digraph PAG {\n";
    out << "  node [shape=ellipse];\n";
 
    for (const NodeId n: nodes()) {
      out << std::format("  {}{};\n", n, dotNodeLabel(n));
    }
 
    for (const Edge& e: edges()) {
      const NodeId x       = e.first();
      const NodeId y       = e.second();
      const bool   xArrow  = isArrowhead(y, x);
      const bool   yArrow  = isArrowhead(x, y);
      const bool   xCircle = isCircle(y, x);
      const bool   yCircle = isCircle(x, y);
 
      const std::string arrowhead = yArrow ? "normal" : (yCircle ? "odot" : "none");
      const std::string arrowtail = xArrow ? "normal" : (xCircle ? "odot" : "none");
 
      out << std::format("  {} -> {} [dir=both, arrowhead={}, arrowtail={}];\n",
                         x,
                         y,
                         arrowhead,
                         arrowtail);
    }
    out << "}\n";
    return out.str();
  }

References gum::NodeGraphPart::dotNodeLabel(), gum::EdgeGraphPart::edges(), isArrowhead(), isCircle(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

◆ toMixedGraph()

MixedGraph gum::PAG::toMixedGraph ( ) const

approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge

Definition at line 179 of file PAG.cpp.

                                     {
    MixedGraph g;
    for (const NodeId n: nodes()) {
      g.addNodeWithId(n);
    }
 
    for (const Edge& e: edges()) {
      const NodeId x      = e.first();
      const NodeId y      = e.second();
      const bool   xArrow = isArrowhead(y, x);   // arrowhead at x-endpoint
      const bool   yArrow = isArrowhead(x, y);   // arrowhead at y-endpoint
      if (xArrow && yArrow) {
        g.addArc(x, y);
        g.addArc(y, x);
      } else if (yArrow) {
        g.addArc(x, y);
      } else if (xArrow) {
        g.addArc(y, x);
      } else {
        g.addEdge(x, y);
      }
    }
    return g;
  }

References gum::DiGraph::addArc(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::EdgeGraphPart::edges(), isArrowhead(), and gum::NodeGraphPart::nodes().

Referenced by gum::learning::FCI::learnMixedStructure(), and gum::learning::FCI::learnPAG().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toString()

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

overridevirtual

approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; anything else → undirected edge

Reimplemented from gum::NodeGraphPart.

Definition at line 215 of file PAG.cpp.

                                {
    std::ostringstream s;
    s << std::format("PAG{{nodes: {}, edges: [", NodeGraphPart::toString());
    bool first = true;
    for (const Edge& e: edges()) {
      if (!first) { s << ", "; }
      first          = false;
      const NodeId x = e.first();
      const NodeId y = e.second();
      s << std::format("{} {}--{} {}", x, markChar(markAt(y, x)), markChar(markAt(x, y)), y);
    }
    s << "]}";
    return s.str();
  }

References gum::EdgeGraphPart::edges(), markAt(), and gum::NodeGraphPart::toString().

Referenced by gum::operator<<().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ undirectedPath()

INLINE std::optional< std::vector< NodeId > > gum::UndiGraph::undirectedPath	(	NodeId	node1,
		NodeId	node2 ) const

inherited

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

Definition at line 104 of file undiGraph_inl.h.

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

References gum::graph::undirectedPath().

Here is the call graph for this function:

◆ unvirtualizedEraseNeighbours()

INLINE void gum::EdgeGraphPart::unvirtualizedEraseNeighbours ( NodeId id )

inherited

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

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 115 of file edgeGraphPart_inl.h.

                                                                   {
    if (_neighbours_.exists(id)) {
      const NodeSet& set = *(_neighbours_[id]);
 
      for (auto iter = set.beginSafe(); iter != set.endSafe();
           ++iter) {   // safe iterator needed here
        EdgeGraphPart::eraseEdge(Edge(*iter, id));
      }
    }
  }

References _neighbours_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), and eraseEdge().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ _edges_

EdgeSet gum::EdgeGraphPart::_edges_

privateinherited

the set of all the edges contained within the EdgeGraphPart

Definition at line 238 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), EdgeGraphPart(), EdgeGraphPart(), _clearEdges_(), addEdge(), edges(), emptyEdges(), eraseEdge(), existsEdge(), operator=(), operator=(), operator==(), sizeEdges(), and toString().

◆ _neighbours_

NodeProperty< NodeSet* > gum::EdgeGraphPart::_neighbours_

privateinherited

for each node, the set of its adjacent edges

Definition at line 241 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), EdgeGraphPart(), _checkNeighbours_(), _clearEdges_(), addEdge(), eraseEdge(), eraseNeighbours(), existsEdge(), neighbours(), operator=(), operator=(), and unvirtualizedEraseNeighbours().

◆ marks_

ArcProperty< EdgeMark > gum::PAG::marks_

private

marks_[Arc(x,y)] = mark at y-endpoint of edge x-y

Definition at line 197 of file PAG.h.

Referenced by PAG(), PAG(), addEdge(), clear(), clearEdges(), eraseEdge(), eraseNode(), markAt(), operator=(), operator=(), and setMarkAt().

◆ onEdgeAdded

Signaler< NodeId, NodeId > gum::EdgeGraphPart::onEdgeAdded

inherited

Definition at line 98 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), addEdge(), operator=(), and operator=().

◆ onEdgeDeleted

Signaler< NodeId, NodeId > gum::EdgeGraphPart::onEdgeDeleted

inherited

Definition at line 99 of file edgeGraphPart.h.

Referenced by _clearEdges_(), and eraseEdge().

◆ onNodeAdded

Signaler< NodeId > gum::NodeGraphPart::onNodeAdded

inherited

Definition at line 281 of file nodeGraphPart.h.

Referenced by addNode(), and addNodeWithId().

◆ onNodeDeleted

Signaler< NodeId > gum::NodeGraphPart::onNodeDeleted

inherited

Definition at line 282 of file nodeGraphPart.h.

Referenced by _clearNodes_(), and eraseNode().

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

agrum/base/graphs/PAG.h
agrum/base/graphs/PAG.cpp

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ EdgeIterator

◆ node_const_iterator

◆ node_const_iterator_safe

◆ node_iterator

◆ node_iterator_safe

◆ NodeConstIterator

◆ NodeConstIteratorSafe

◆ NodeIterator

◆ NodeIteratorSafe

Constructor & Destructor Documentation

◆ PAG() [1/3]

◆ PAG() [2/3]

◆ PAG() [3/3]

◆ ~PAG()

Member Function Documentation

◆ _checkNeighbours_()

◆ _clearEdges_()

◆ addEdge() [1/2]

◆ addEdge() [2/2]

◆ addNode()

◆ addNodes()

◆ addNodeWithId()

◆ asNodeSet()

◆ begin()

◆ beginSafe()

◆ bound()

◆ chainComponents()

◆ clear()

◆ clearEdges()

◆ clearNodes()

◆ completeGraph()

◆ connectedComponents()

◆ dotNodeLabel()

◆ edges()

◆ edgesProperty() [1/2]

◆ edgesProperty() [2/2]

◆ empty()

◆ emptyEdges()

◆ emptyNodes()

◆ end()

◆ endSafe()

◆ eraseEdge()

◆ eraseNeighbours()

◆ eraseNode()

◆ exists()

◆ existsEdge() [1/2]

◆ existsEdge() [2/2]

◆ existsNode()

◆ hasName()

◆ hasUndirectedCycle()

◆ hasUndirectedPath() [1/3]

◆ hasUndirectedPath() [2/3]

◆ hasUndirectedPath() [3/3]

◆ idFromName()

◆ isArrowhead()

◆ isBidirected()

◆ isCircle()

◆ isDefCollider()

◆ isDefinitelyDirected()

◆ isTail()

◆ listMapEdges()

◆ listMapNodes()

◆ markAt()

◆ nameFromId()

◆ neighbours()

◆ nextNodeId()

◆ nodes()

◆ nodesPropertyFromFunction()

◆ nodesPropertyFromVal()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==() [1/3]