Base class for mixed graphs. More...

#include <mixedGraph.h>

Inheritance diagram for gum::MixedGraph:

Collaboration diagram for gum::MixedGraph:

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

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

Public Member Functions

bool hasDirectedPath (NodeId from, NodeId to)

checks whether there exists a directed path from from to to

Constructors / Destructors

MixedGraph (Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)

default constructor

MixedGraph (const UndiGraph &g)

default constructor

MixedGraph (const DiGraph &g)

default constructor

MixedGraph (const MixedGraph &g)

copy constructor

virtual ~MixedGraph ()

destructor

Operators

MixedGraph & operator= (const MixedGraph &g)

copy operator

bool operator== (const MixedGraph &g) const

tests whether two MixedGraphs are identical (same nodes, arcs and edges)

Accessors/Modifiers

void eraseNode (const NodeId node) override

remove a node as well as its adjacent arcs and edges from the graph

void clear () override

removes all the nodes, arcs and edges from the graph

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

returns a mixed edge/directed arc path from node1 to node2 in the arc/edge set

bool hasMixedOrientedPath (NodeId node1, NodeId node2) const

returns true if a mixed edge/directed arc path from node1 to node2 in the arc/edge set exists.

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

returns a mixed/directed path from node1 to node2 in the arc/edge set

std::string toDot () const override

to friendly display mixed graph in DOT format

std::string toString () const override

to friendly display the content of the MixedGraph

NodeSet boundary (NodeId node) const

returns the set of node adjacent to a given node

NodeSet chainComponent (NodeId node) const

returns the set of nodes reachable by undirected path

Operators

bool operator== (const UndiGraph &g) const

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

bool operator!= (const UndiGraph &g) const

tests whether two UndiGraphs are different

Operators

bool operator== (const EdgeGraphPart &p) const

tests whether two EdgeGraphParts contain the same edges

Accessors/Modifiers

void addEdge (NodeId first, NodeId second) override

insert a new edge into the undirected graph

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 > nodes2ConnectedComponent () const

returns a property {node:id of connected component}

Accessors/Modifiers

virtual void eraseEdge (const Edge &edge)

removes an edge from the EdgeGraphPart

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

virtual void clearEdges ()

removes all the edges from the EdgeGraphPart

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

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

returns a possible path from node1 to node2 in the edge set

bool hasUndirectedPath (NodeId n1, NodeId n2) const

return true if n1 and n2 are connected (by an undirected path) in the graph.

bool hasUndirectedPath (NodeId n1, NodeId n2, const NodeSet &except) const

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

bool hasUndirectedPath (const NodeSet &n1, const NodeSet &n2, const NodeSet &except) const

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

Operators

bool operator== (const DiGraph &g) const

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

Operators

bool operator== (const ArcGraphPart &p) const

tests whether two ArcGraphParts contain the same arcs

Accessors/Modifiers

tests whether two DiGraphs are different

Parameters

g	the DiGraph with which "this" is compared

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

insert a new arc into the directed graph

Sequence< NodeId > topologicalOrder () const

Build and return a topological order.

Accessors/Modifiers

virtual void eraseArc (const Arc &arc)

removes an arc from the ArcGraphPart

bool existsArc (const Arc &arc) const

indicates whether a given arc exists

bool existsArc (NodeId tail, NodeId head) const

indicates whether a given arc exists

bool emptyArcs () const

indicates wether the ArcGraphPart contains any arc

void clearArcs ()

removes all the arcs from the ArcGraphPart

Size sizeArcs () const

indicates the number of arcs stored within the ArcGraphPart

const ArcSet & arcs () const

returns the set of arcs stored within the ArcGraphPart

const NodeSet & parents (NodeId id) const

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

NodeSet parents (const NodeSet &ids) const

returns the set of parents of a set of nodes

NodeSet family (NodeId id) const

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

NodeSet family (const NodeSet &ids) const

returns the set of family nodes of a set of nodes

NodeSet descendants (NodeId id) const

returns the set of nodes with directed path outgoing from a given node

NodeSet ancestors (NodeId id) const

returns the set of nodes with directed path ingoing to a given node

NodeSet children (const NodeSet &ids) const

returns the set of children of a set of nodes

const NodeSet & children (NodeId id) const

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

void eraseParents (NodeId id)

erase all the parents of a given node

void unvirtualizedEraseParents (NodeId id)

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

void eraseChildren (NodeId id)

removes all the children of a given node

void unvirtualizedEraseChildren (NodeId id)

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

template<typename VAL>

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

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

template<typename VAL>

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

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

template<typename VAL>

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

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

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

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

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

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

Operators

bool operator== (const NodeGraphPart &p) const

check whether two NodeGraphParts contain the same nodes

bool operator!= (const NodeGraphPart &p) const

check whether two NodeGraphParts contain different 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

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
Constructors / Destructors
static DiGraph	completeGraph (int n)
	Build a complete DiGraph with n nodes.

Public Attributes
Signaler2< NodeId, NodeId >	onEdgeAdded
Signaler2< NodeId, NodeId >	onEdgeDeleted
Signaler2< NodeId, NodeId >	onArcAdded
Signaler2< NodeId, NodeId >	onArcDeleted
Signaler1< NodeId >	onNodeAdded
Signaler1< NodeId >	onNodeDeleted

Protected Member Functions
void	eraseSetOfArcs_ (const ArcSet &set)
	a (virtualized) function to remove a given set of arcs
void	unvirtualizedEraseSetOfArcs_ (const ArcSet &set)
	similar to eraseSetOfArcs_ except that it is unvirtualized

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_ ()
void	_checkParents_ (NodeId id)
	when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entry to parents[id]
void	_checkChildren_ (NodeId id)
	when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set entry to children[id]

Private Attributes
EdgeSet	_edges_
	the set of all the edges contained within the EdgeGraphPart
NodeProperty< NodeSet * >	_neighbours_
	for each node, the set of its adjacent edges
Set< Arc >	_arcs_
	the set of all the arcs contained within the ArcGraphPart
NodeProperty< NodeSet * >	_parents_
	for each arc, the sets of its parents
NodeProperty< NodeSet * >	_children_
	for each arc, the set of its children

Detailed Description

Base class for mixed graphs.

Usage example:: // creating empty graphs

MixedGraph g1,g2;

// adding nodes, arcs and edges to g1

NodeId i1=g1.addNode();

NodeId i2=g1.addNode();

NodeId i3=g1.addNode();

g1.addArc( i1,i2 );

g1.addArc( i1,i3 );

g1.addArc( i2,i3 );

g1.addEdge( i1,i2 );

g1.addEdge( i1,i3 );

g1.addEdge( i2,i3 );

//throw an InvalidNode

// g1.addArc( i1+i2+i3,i1 );

// g1.addEdge( i1+i2+i3,i1 );

// copying graphs

MixedGraph g3 = g1;

g2 = g1;

MixedGraph g4=g1;

// check if a graph has no node

if ( g1.empty() ) cerr << "graph g1 is empty" << endl;

// remove all the nodes (as well as their adjacent arcs and edges)

g1.clear();

// remove some arc

g4.eraseArc( Arc ( i1,i3 ) );

// remove some edge

g4.eraseEdge( Edge ( i1,i3 ) );

// remove node

g2.eraseNode( i2 );

// parse a graph

for ( const auto nod : g3.nodes() )

cerr << nod << endl;

for ( const auto arc : g3.arcs() )

cerr << arc << endl;

for ( const auto edg : g3.edges()) )

cerr << edg << endl;

const NodeSet& a=g3.parents( 3 );

for ( const auto iter : a)

cerr << " - "<<iter;

cerr<<endl;

const NodeSet& a=g3.neighbours( 3 );

for ( NodeSetIterator iter = a.begin( ); iter != a.end(); ++iter )

cerr << " - "<<*iter;

cerr<<endl;

// remove all the arcs that are parent of a given node

g3.eraseParents( 2 );

// remove all the edges that are adjacent to a given node

g3.eraseNeighbours( 2 );

gum::ArcGraphPart::parents
const NodeSet & parents(NodeId id) const
returns the set of nodes with arc ingoing to a given node
Definition arcGraphPart_inl.h:75

gum::ArcGraphPart::eraseParents
void eraseParents(NodeId id)
erase all the parents of a given node
Definition arcGraphPart_inl.h:144

gum::ArcGraphPart::eraseArc
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
Definition arcGraphPart_inl.h:126

gum::ArcGraphPart::arcs
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart
Definition arcGraphPart_inl.h:59

gum::Arc
The base class for all directed edges.
Definition graphElements.h:261

gum::DiGraph::addArc
virtual void addArc(const NodeId tail, const NodeId head)
insert a new arc into the directed graph
Definition diGraph_inl.h:55

gum::EdgeGraphPart::eraseEdge
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart
Definition edgeGraphPart_inl.h:82

gum::EdgeGraphPart::eraseNeighbours
void eraseNeighbours(NodeId id)
erase all the edges adjacent to a given node
Definition edgeGraphPart_inl.h:101

gum::EdgeGraphPart::edges
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart
Definition edgeGraphPart_inl.h:59

gum::EdgeGraphPart::neighbours
const NodeSet & neighbours(NodeId id) const
returns the set of node neighbours to a given node
Definition edgeGraphPart_inl.h:96

gum::Edge
The base class for all undirected edges.
Definition graphElements.h:164

gum::MixedGraph::eraseNode
void eraseNode(const NodeId node) override
remove a node as well as its adjacent arcs and edges from the graph
Definition mixedGraph_inl.h:74

gum::MixedGraph::clear
void clear() override
removes all the nodes, arcs and edges from the graph
Definition mixedGraph_inl.h:68

gum::MixedGraph::MixedGraph
MixedGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
Definition mixedGraph.cpp:56

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

gum::NodeGraphPart::empty
bool empty() const
alias for emptyNodes
Definition nodeGraphPart_inl.h:308

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

gum::Set::begin
iterator begin() const
The usual unsafe begin iterator to parse the set.
Definition set_tpl.h:438

gum::Set::end
const iterator & end() const noexcept
The usual unsafe end iterator to parse the set.
Definition set_tpl.h:450

gum::UndiGraph::addEdge
void addEdge(NodeId first, NodeId second) override
insert a new edge into the undirected graph
Definition undiGraph_inl.h:55

gum::NodeId
Size NodeId
Type for node ids.
Definition graphElements.h:117

gum::NodeSetIterator
NodeSet::const_iterator NodeSetIterator
Some typdefs and define for shortcuts ...
Definition graphElements.h:385

gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition graphElements.h:380

Definition at line 146 of file mixedGraph.h.

Member Typedef Documentation

◆ ArcIterator

using gum::ArcGraphPart::ArcIterator = ArcSetIterator

inherited

Definition at line 100 of file arcGraphPart.h.

using gum::NodeGraphPart::NodeConstIterator = NodeGraphPartIterator

inherited

Definition at line 285 of file nodeGraphPart.h.

◆ NodeConstIteratorSafe

using gum::NodeGraphPart::NodeConstIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 287 of file nodeGraphPart.h.

◆ NodeIterator

using gum::NodeGraphPart::NodeIterator = NodeGraphPartIterator

inherited

Definition at line 284 of file nodeGraphPart.h.

◆ NodeIteratorSafe

using gum::NodeGraphPart::NodeIteratorSafe = NodeGraphPartIteratorSafe

inherited

Definition at line 286 of file nodeGraphPart.h.

Constructor & Destructor Documentation

◆ MixedGraph() [1/4]

gum::MixedGraph::MixedGraph	(	Size	nodes_size = HashTableConst::default_size,
		bool	nodes_resize_policy = true,
		Size	arcs_size = HashTableConst::default_size,
		bool	arcs_resize_policy = true,
		Size	edges_size = HashTableConst::default_size,
		bool	edges_resize_policy = true )

explicit

default constructor

Parameters

nodes_size	the size of the hash table used to store all the nodes
nodes_resize_policy	the resizing policy of this hash table
arcs_size	the size of the hash table used to store all the arcs
arcs_resize_policy	the resizing policy of this hash table
edges_size	the size of the hash table used to store all the edges
edges_resize_policy	the resizing policy of this hash table

Definition at line 56 of file mixedGraph.cpp.

                                                   :
      // Note that we need to initialize the NodeGraphPart by ourselves
      // because
      // it is a virtual inherited class (see C++ FAQ Lite #25.12 for details)
      NodeGraphPart(nodes_size, nodes_resize_policy), UndiGraph(edges_size, edges_resize_policy),
      DiGraph(arcs_size, arcs_resize_policy) {   // for debugging purposes
    GUM_CONSTRUCTOR(MixedGraph);
  }

References gum::DiGraph::DiGraph(), MixedGraph(), and gum::UndiGraph::UndiGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MixedGraph() [2/4]

gum::MixedGraph::MixedGraph ( const UndiGraph & g )

explicit

default constructor

Parameters

nodes_size	the size of the hash table used to store all the nodes
nodes_resize_policy	the resizing policy of this hash table
arcs_size	the size of the hash table used to store all the arcs
arcs_resize_policy	the resizing policy of this hash table
edges_size	the size of the hash table used to store all the edges
edges_resize_policy	the resizing policy of this hash table

Definition at line 70 of file mixedGraph.cpp.

                                           : NodeGraphPart(g), UndiGraph(g), DiGraph() {
    GUM_CONSTRUCTOR(MixedGraph);
  }

References gum::DiGraph::DiGraph(), MixedGraph(), and gum::UndiGraph::UndiGraph().

Here is the call graph for this function:

◆ MixedGraph() [3/4]

gum::MixedGraph::MixedGraph ( const DiGraph & g )

explicit

default constructor

Parameters

nodes_size	the size of the hash table used to store all the nodes
nodes_resize_policy	the resizing policy of this hash table
arcs_size	the size of the hash table used to store all the arcs
arcs_resize_policy	the resizing policy of this hash table
edges_size	the size of the hash table used to store all the edges
edges_resize_policy	the resizing policy of this hash table

Definition at line 74 of file mixedGraph.cpp.

                                         : NodeGraphPart(g), UndiGraph(), DiGraph(g) {
    GUM_CONSTRUCTOR(MixedGraph);
  }

References gum::DiGraph::DiGraph(), MixedGraph(), and gum::UndiGraph::UndiGraph().

Here is the call graph for this function:

◆ MixedGraph() [4/4]

gum::MixedGraph::MixedGraph ( const MixedGraph & g )

copy constructor

Parameters

g	the MixedGraph to copy

Definition at line 78 of file mixedGraph.cpp.

                                            :
      NodeGraphPart(g), UndiGraph(g), DiGraph(g) {   // for debugging purposes
    GUM_CONS_CPY(MixedGraph);
  }

References gum::DiGraph::DiGraph(), MixedGraph(), and gum::UndiGraph::UndiGraph().

Here is the call graph for this function:

◆ ~MixedGraph()

gum::MixedGraph::~MixedGraph ( )

virtual

destructor

Definition at line 83 of file mixedGraph.cpp.

                          {   // for debugging purposes
    GUM_DESTRUCTOR(MixedGraph);
  }

References MixedGraph().

Here is the call graph for this function:

Member Function Documentation

◆ _checkChildren_()

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

privateinherited

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

Parameters

id	the node whose children[id] is checked

Definition at line 71 of file arcGraphPart_inl.h.

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

References _children_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _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 67 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:

◆ _checkParents_()

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

privateinherited

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

Parameters

id	the node whose parents[id] is checked

Definition at line 67 of file arcGraphPart_inl.h.

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

References _parents_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _clearEdges_()

void gum::EdgeGraphPart::_clearEdges_ ( )

privateinherited

Definition at line 88 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:

◆ 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, gum::PDAG, and gum::prm::gspan::Pattern.

Definition at line 55 of file diGraph_inl.h.

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

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

Referenced by gum::MeekRules::_applyMeekRules_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::learning::Miic::_orientingVstructureMiic_(), gum::learning::SimpleMiic::_orientingVstructureMiic_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::learning::Miic::_propagatingOrientationMiic_(), gum::learning::SimpleMiic::_propagatingOrientationMiic_(), gum::DAG::addArc(), gum::PDAG::addArc(), gum::prm::gspan::Pattern::addArc(), completeGraph(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::IBNLearner::prepareMiic_(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), and gum::learning::SimpleMiic::propagatesRemainingOrientableEdges_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addEdge()

INLINE void gum::UndiGraph::addEdge	(	NodeId	first,
		NodeId	second )

overridevirtualinherited

insert a new edge into the undirected graph

The order in which the extremal nodes are specified is not important.

Parameters

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

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

Exceptions

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

Reimplemented from gum::EdgeGraphPart.

Definition at line 55 of file undiGraph_inl.h.

                                                                        {
    if (!exists(first)) { GUM_ERROR(InvalidNode, "Node (" << first << ") does not exist.") }
 
    if (!exists(second)) { GUM_ERROR(InvalidNode, "Node (" << second << ") does not exist.") }
 
    EdgeGraphPart::addEdge(second, first);
  }

References gum::EdgeGraphPart::addEdge(), gum::NodeGraphPart::exists(), and GUM_ERROR.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::StructuredInference< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::StaticTriangulation::_triangulate_(), completeGraph(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::InfluenceDiagram< GUM_SCALAR >::moralGraph_(), gum::DAG::moralizedAncestralGraph(), partialUndiGraph(), gum::learning::IBNLearner::prepareMiic_(), and gum::EssentialGraph::skeleton().

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 258 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_(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot().

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 276 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(), and gum::UndiGraph::completeGraph().

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 151 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::learning::StructuralConstraintDAG::StructuralConstraintDAG(), gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::learning::IBNLearner::learnDag_(), gum::learning::SimpleMiic::learnStructure(), gum::InfluenceDiagram< GUM_SCALAR >::moralGraph_(), gum::DAG::moralizedAncestralGraph(), gum::PDAG::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), gum::learning::IBNLearner::prepareMiic_(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), gum::rec_ancestral(), and gum::EssentialGraph::skeleton().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ancestors()

NodeSet gum::ArcGraphPart::ancestors ( NodeId id ) const

inherited

returns the set of nodes with directed path ingoing to a given node

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is ingoing to the given node.

Parameters

id	the node which is the head of a directed path with the returned nodes

Definition at line 191 of file arcGraphPart.cpp.

                                                 {
    NodeSet res;
    NodeSet tmp;
    for (auto next: parents(id))
      tmp.insert(next);
 
    while (!tmp.empty()) {
      auto current = *(tmp.begin());
      tmp.erase(current);
      res.insert(current);
      for (auto next: parents(current)) {
        if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
      }
    }
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::insert(), and parents().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ arcs()

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

inherited

returns the set of arcs stored within the ArcGraphPart

Definition at line 59 of file arcGraphPart_inl.h.

59{ return _arcs_; }

gum::ArcGraphPart::_arcs_

Set< Arc > _arcs_

the set of all the arcs contained within the ArcGraphPart

Definition arcGraphPart.h:316

References _arcs_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::ClassBayesNet< GUM_SCALAR >::_init_(), gum::prm::gspan::Pattern::arcs(), gum::learning::SimpleMiic::learnStructure(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), and gum::DiGraph::toDot().

Here is the caller graph for this function:

◆ arcsProperty() [1/2]

template<typename VAL>

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

inherited

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

Parameters

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

◆ arcsProperty() [2/2]

template<typename VAL>

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

inherited

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

Parameters

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

◆ asNodeSet()

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

inherited

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

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

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

as this is faster and consumes much less memory.

Definition at line 356 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(), 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 333 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(), 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 321 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_().

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

310{ return _boundVal_; }

References _boundVal_.

Referenced by _clearNodes_().

Here is the caller graph for this function:

◆ boundary()

INLINE NodeSet gum::MixedGraph::boundary ( NodeId node ) const

returns the set of node adjacent to a given node

Note that the set of node returned may be empty.

Parameters

id	the node to which the edges are adjacent

Definition at line 86 of file mixedGraph_inl.h.

                                                       {
    return neighbours(node) + parents(node) + children(node);
  }

References gum::ArcGraphPart::children(), gum::EdgeGraphPart::neighbours(), and gum::ArcGraphPart::parents().

Referenced by gum::MeekRules::_isOrientable_(), and gum::learning::SimpleMiic::isOrientable_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ chainComponent()

NodeSet gum::MixedGraph::chainComponent ( NodeId node ) const

returns the set of nodes reachable by undirected path

Note that the set of node returned may be empty.

Parameters

id	the node to which the edges are adjacent

Definition at line 260 of file mixedGraph.cpp.

                                                      {
    NodeSet res;
    NodeSet stack{node};
 
    while (!stack.empty()) {
      const NodeId n = *(stack.begin());
      stack.erase(n);
      if (!res.exists(n)) {
        res.insert(n);
        stack += neighbours(n);
      }
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::exists(), gum::Set< Key >::insert(), and gum::EdgeGraphPart::neighbours().

Referenced by gum::PDAG::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ children() [1/2]

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

inherited

returns the set of children of a set of nodes

Definition at line 86 of file arcGraphPart_inl.h.

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

References children().

Referenced by ArcGraphPart(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::_addArcs_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::gspan::Pattern::_expandCodeIsMinimal_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::DAG::_minimalCondSetVisitDn_(), gum::DAG::_minimalCondSetVisitUp_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::BarrenNodesFinder::barrenNodes(), gum::MixedGraph::boundary(), children(), descendants(), directedUnorientedPath(), eraseChildren(), gum::DiGraph::hasDirectedPath(), gum::PDAG::hasMixedReallyOrientedPath(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::initialize_(), gum::prm::PRMClassElementContainer< double >::isInputNode(), gum::prm::gspan::Pattern::isMinimal(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::makeInferenceNodeToNeighbours_(), gum::DAG::minimalCondSet(), gum::MixedGraph::mixedUnorientedPath(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::rec_hasMixedReallyOrientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and unvirtualizedEraseChildren().

Here is the call graph for this function:

◆ children() [2/2]

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

inherited

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

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

Parameters

id	the node which is the tail of the arcs returned

Definition at line 109 of file arcGraphPart_inl.h.

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

References _children_, and gum::emptyNodeSet.

◆ clear()

INLINE void gum::MixedGraph::clear ( )

overridevirtual

removes all the nodes, arcs and edges from the graph

Reimplemented from gum::NodeGraphPart.

Definition at line 68 of file mixedGraph_inl.h.

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

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

Here is the call graph for this function:

◆ clearArcs()

void gum::ArcGraphPart::clearArcs ( )

inherited

removes all the arcs from the ArcGraphPart

Definition at line 98 of file arcGraphPart.cpp.

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

References _arcs_, _children_, _parents_, GUM_EMIT2, and onArcDeleted.

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

Here is the caller graph for this function:

◆ clearEdges()

void gum::EdgeGraphPart::clearEdges ( )

virtualinherited

removes all the edges from the EdgeGraphPart

Reimplemented in gum::CliqueGraph.

Definition at line 86 of file edgeGraphPart.cpp.

86{ _clearEdges_(); }

gum::EdgeGraphPart::_clearEdges_

void _clearEdges_()

Definition edgeGraphPart.cpp:88

References _clearEdges_().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )

virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 312 of file nodeGraphPart_inl.h.

312{ _clearNodes_(); }

gum::NodeGraphPart::_clearNodes_

void _clearNodes_()

code for clearing nodes (called twice)

Definition nodeGraphPart.cpp:174

References _clearNodes_().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ completeGraph() [1/2]

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

staticinherited

Build a complete DiGraph with n nodes.

Parameters

int n

Returns: the complete DiGraph

Definition at line 57 of file diGraph.cpp.

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

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

Here is the call graph for this function:

◆ completeGraph() [2/2]

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

staticinherited

create a complete UndiGraph with n nodes

Parameters

n int

Returns: the complete UndiGraph

Definition at line 60 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:

◆ descendants()

NodeSet gum::ArcGraphPart::descendants ( NodeId id ) const

inherited

returns the set of nodes with directed path outgoing from a given node

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

Parameters

id	the node which is the tail of a directed path with the returned nodes

Definition at line 174 of file arcGraphPart.cpp.

                                                   {
    NodeSet res;
    NodeSet tmp;
    for (auto next: children(id))
      tmp.insert(next);
 
    while (!tmp.empty()) {
      auto current = *(tmp.begin());
      tmp.erase(current);
      res.insert(current);
      for (auto next: children(current)) {
        if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
      }
    }
    return res;
  }

References gum::Set< Key >::begin(), children(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ directedPath()

std::vector< NodeId > gum::ArcGraphPart::directedPath	(	NodeId	node1,
		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 208 of file arcGraphPart.cpp.

                                                                           {
    // 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")
  }

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

Referenced by gum::learning::SimpleMiic::orientationLatents_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ directedUnorientedPath()

std::vector< NodeId > gum::ArcGraphPart::directedUnorientedPath	(	NodeId	node1,
		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 249 of file arcGraphPart.cpp.

                                                                                     {
    // 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")
  }

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

Here is the call 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 59 of file edgeGraphPart_inl.h.

59{ return _edges_; }

References _edges_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::BarrenNodesFinder::barrenNodes(), gum::learning::Miic::initiation_(), gum::learning::SimpleMiic::initiation_(), gum::PDAG::moralGraph(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::MeekRules::propagateToCPDAG(), and gum::learning::IBNLearner::setPossibleSkeleton().

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

308{ return emptyNodes(); }

gum::NodeGraphPart::emptyNodes

bool emptyNodes() const

indicates whether there exists nodes in the NodeGraphPart

Definition nodeGraphPart_inl.h:306

References emptyNodes().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emptyArcs()

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

inherited

indicates wether the ArcGraphPart contains any arc

Definition at line 55 of file arcGraphPart_inl.h.

55{ return _arcs_.empty(); }

References _arcs_.

◆ emptyEdges()

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

inherited

indicates wether the EdgeGraphPart contains any edge

Definition at line 55 of file edgeGraphPart_inl.h.

55{ return _edges_.empty(); }

References _edges_.

◆ emptyNodes()

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

inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 306 of file nodeGraphPart_inl.h.

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

References sizeNodes().

Referenced by empty().

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

                                                                        {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIterator.

Referenced by gum::Estimator< GUM_SCALAR >::Estimator(), 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 329 of file nodeGraphPart_inl.h.

                                                                                {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIteratorSafe.

Here is the call graph for this function:

◆ eraseArc()

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

virtualinherited

removes an arc from the ArcGraphPart

Parameters

arc	the arc to be removed

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

Definition at line 126 of file arcGraphPart_inl.h.

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

References _arcs_, _children_, _parents_, existsArc(), GUM_EMIT2, gum::Arc::head(), onArcDeleted, and gum::Arc::tail().

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::BarrenNodesFinder::barrenNodes(), eraseChildren(), eraseParents(), eraseSetOfArcs_(), gum::learning::IBNLearner::learnDag_(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::prm::gspan::Pattern::pop_back(), unvirtualizedEraseChildren(), unvirtualizedEraseParents(), and unvirtualizedEraseSetOfArcs_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseChildren()

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

inherited

removes all the children of a given node

Parameters

id	the node all the children of which will be removed

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

Definition at line 158 of file arcGraphPart_inl.h.

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

References _children_, children(), and eraseArc().

Here is the call graph for this function:

◆ eraseEdge()

INLINE void gum::EdgeGraphPart::eraseEdge ( const Edge & edge )

virtualinherited

removes an edge from the EdgeGraphPart

Parameters

edge	the edge to be removed

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

Reimplemented in gum::CliqueGraph.

Definition at line 82 of file edgeGraphPart_inl.h.

                                                       {
    if (existsEdge(edge)) {
      // ASSUMING first and second exists in  _neighbours_ (if not, it is an
      // error)
      NodeId id1 = edge.first();
      NodeId id2 = edge.second();
 
      _neighbours_[id1]->erase(id2);
      _neighbours_[id2]->erase(id1);
      _edges_.erase(edge);
      GUM_EMIT2(onEdgeDeleted, id1, id2);
    }
  }

References _edges_, _neighbours_, existsEdge(), gum::Edge::first(), GUM_EMIT2, onEdgeDeleted, and gum::Edge::second().

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 101 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()

INLINE void gum::MixedGraph::eraseNode ( const NodeId node )

overridevirtual

remove a node as well as its adjacent arcs and edges 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.

Definition at line 74 of file mixedGraph_inl.h.

                                                     {
    EdgeGraphPart::unvirtualizedEraseNeighbours(node);
    ArcGraphPart::unvirtualizedEraseParents(node);
    ArcGraphPart::unvirtualizedEraseChildren(node);
    NodeGraphPart::eraseNode(node);
  }

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

Here is the call graph for this function:

◆ eraseParents()

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

inherited

erase all the parents of a given node

Parameters

id	the node all the parents of which will be removed

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

Definition at line 144 of file arcGraphPart_inl.h.

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

References _parents_, eraseArc(), and parents().

Here is the call graph for this function:

◆ eraseSetOfArcs_()

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

protectedinherited

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

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

Definition at line 139 of file arcGraphPart_inl.h.

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

References eraseArc().

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

296{ return existsNode(node); }

gum::NodeGraphPart::existsNode

bool existsNode(const NodeId id) const

returns true iff the NodeGraphPart contains the given nodeId

Definition nodeGraphPart_inl.h:290

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::DiGraph::hasDirectedPath(), gum::learning::IBNLearner::learnDag_(), and gum::DAG::moralizedAncestralGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ existsArc() [1/2]

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

inherited

indicates whether a given arc exists

Parameters

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

Definition at line 61 of file arcGraphPart_inl.h.

61{ return _arcs_.contains(arc); }

References _arcs_.

Referenced by gum::learning::Miic::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::learning::Miic::_existsNonTrivialDirectedPath_(), gum::learning::SimpleMiic::_existsNonTrivialDirectedPath_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::gspan::Pattern::_not_rec_(), gum::learning::Miic::_orientingVstructureMiic_(), gum::learning::SimpleMiic::_orientingVstructureMiic_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::EssentialGraph::_strongly_protected_(), eraseArc(), gum::prm::gspan::Pattern::exists(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::updateProbaTriples_(), and gum::learning::SimpleMiic::updateProbaTriples_().

Here is the caller graph for this function:

◆ existsArc() [2/2]

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

inherited

indicates whether a given arc exists

Parameters

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

Definition at line 63 of file arcGraphPart_inl.h.

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

References _parents_.

◆ 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 61 of file edgeGraphPart_inl.h.

61{ return _edges_.contains(edge); }

References _edges_.

Referenced by gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::EssentialGraph::_strongly_protected_(), gum::StaticTriangulation::_triangulate_(), eraseEdge(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::Miic::unshieldedTriples_(), gum::learning::SimpleMiic::unshieldedTriples_(), gum::learning::Miic::unshieldedTriplesMiic_(), and gum::learning::SimpleMiic::unshieldedTriplesMiic_().

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

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

References _boundVal_, and _inHoles_().

Referenced by eraseNode(), exists(), gum::PDAG::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), and gum::rec_ancestral().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ family() [1/2]

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

inherited

returns the set of family nodes of a set of nodes

Definition at line 102 of file arcGraphPart_inl.h.

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

References family().

Here is the call graph for this function:

◆ family() [2/2]

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

inherited

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

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

Parameters

id	the node which is the tail of a directed path with the returned nodes

Definition at line 80 of file arcGraphPart_inl.h.

                                                     {
    NodeSet res{id};
    return res + parents(id);
  }

References parents().

Referenced by family().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasDirectedPath()

bool gum::DiGraph::hasDirectedPath	(	NodeId	from,
		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 151 of file diGraph.cpp.

                                                                  {
    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();
      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;
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasMixedOrientedPath()

bool gum::MixedGraph::hasMixedOrientedPath	(	NodeId	node1,
		NodeId	node2 ) const

returns true if a mixed edge/directed arc path from node1 to node2 in the arc/edge set exists.

Parameters

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

Definition at line 149 of file mixedGraph.cpp.

                                                                  {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > node_fifo;
    node_fifo.pushBack(n2);
 
    // mark[node] = successor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    NodeId current;
    while (!node_fifo.empty()) {
      current = node_fifo.front();
      node_fifo.popFront();
 
      // check the neighbours
      for (const auto new_one: neighbours(current)) {
        if (mark.exists(new_one))   // if the node has already been visited
          continue;                 // do not check it again
 
        mark.insert(new_one, current);
 
        if (new_one == n1) { return true; }
 
        node_fifo.pushBack(new_one);
      }
 
      // 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) { return true; }
 
        node_fifo.pushBack(new_one);
      }
    }
 
    return false;
  }

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

Here is the call graph for this function:

◆ hasUndirectedCycle()

bool gum::UndiGraph::hasUndirectedCycle ( ) const

inherited

checks whether the graph contains cycles

Definition at line 90 of file undiGraph.cpp.

                                           {
    List< std::pair< NodeId, NodeId > > open_nodes;
    NodeProperty< bool >                examined_nodes = nodesPropertyFromVal(false);
    std::pair< NodeId, NodeId >         thePair;
    NodeId                              current, from_current;
 
    for (const auto node: nodes()) {
      // check if the node has already been examined (if this is not the case,
      // this means that we are on a new connected component)
      if (!examined_nodes[node]) {
        // indicates that we are examining a new node
        examined_nodes[node] = true;
 
        // check recursively all the nodes of node's connected component
        thePair.first  = node;
        thePair.second = node;
        open_nodes.insert(thePair);
 
        while (!open_nodes.empty()) {
          // get a node to propagate
          thePair = open_nodes.front();
          open_nodes.popFront();
 
          current      = thePair.first;
          from_current = thePair.second;
 
          // check the neighbours
          for (const auto new_node: neighbours(current))
 
            // avoid to check the node we are coming from
            if (new_node != from_current) {
              if (examined_nodes[new_node]) return true;
              else {
                examined_nodes[new_node] = true;
                thePair.first            = new_node;
                thePair.second           = current;
                open_nodes.insert(thePair);
              }
            }
        }
      }
    }
 
    return false;
  }

References gum::List< Val >::empty(), gum::List< Val >::front(), gum::List< Val >::insert(), gum::EdgeGraphPart::neighbours(), gum::NodeGraphPart::nodes(), gum::NodeGraphPart::nodesPropertyFromVal(), and gum::List< Val >::popFront().

Here is the call graph for this function:

◆ hasUndirectedPath() [1/3]

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

inherited

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

Parameters

n1	NodeSet
n2	NodeSet
except	NodeSet

Returns: bool

Definition at line 222 of file edgeGraphPart.cpp.

                                                                     {
    NodeSet visited;
    NodeSet temp;
 
    for (auto n: n1)
      temp.insert(n);
 
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (n2.contains(current)) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next) && !except.contains(next))
          temp.insert(next);
      }
    }
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::insert(), and neighbours().

Here is the call graph for this function:

◆ hasUndirectedPath() [2/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	NodeId	n1,
		NodeId	n2 ) const

inherited

return true if n1 and n2 are connected (by an undirected path) in the graph.

Parameters

n1	NodeId
n2	NodeId

Returns: bool

Definition at line 185 of file edgeGraphPart.cpp.

                                                                  {
    NodeSet visited;
    NodeSet temp;
 
    temp.insert(n1);
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (current == n2) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next)) temp.insert(next);
      }
    }
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::insert(), and neighbours().

Referenced by gum::UGmodel::isIndependent(), and gum::UGmodel::isIndependent().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasUndirectedPath() [3/3]

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

inherited

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

Parameters

n1	NodeId
n2	NodeId
except	NodeSet

Warning: n1 in except has no repercussion. However n2 in except naturally leads to 'false'

Returns: bool

Definition at line 202 of file edgeGraphPart.cpp.

                                                                                               {
    NodeSet visited;
    NodeSet temp;
 
    if (except.contains(n2)) return false;
 
    temp.insert(n1);
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (current == n2) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next) && !except.contains(next))
          temp.insert(next);
      }
    }
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::insert(), and neighbours().

Here is the call graph for this function:

◆ listMapArcs()

template<typename VAL>

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

inherited

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

Parameters

f	a function assigning a VAL to any arc

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

◆ mixedOrientedPath()

std::vector< NodeId > gum::MixedGraph::mixedOrientedPath	(	NodeId	node1,
		NodeId	node2 ) const

returns a mixed edge/directed arc path from node1 to node2 in the arc/edge set

This function returns, if any, a path from node1 to node2, using edges and/or arcs (wrt the direction of th arcs)

Parameters

node1	the id from which the path begins
node2	the id to which the path ends if no path can be found between the two nodes, the returned vector is empty

Definition at line 96 of file mixedGraph.cpp.

                                                                              {
    std::vector< NodeId > v;
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > node_fifo;
    node_fifo.pushBack(n2);
 
    // mark[node] = successor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    NodeId current;
    while (!node_fifo.empty()) {
      current = node_fifo.front();
      node_fifo.popFront();
 
      // check the neighbours
      for (const auto new_one: neighbours(current)) {
        if (mark.exists(new_one))   // if the node has already been visited
          continue;                 // do not check it again
 
        mark.insert(new_one, current);
 
        if (new_one == n1) {
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
          v.push_back(n2);
          return v;
        }
 
        node_fifo.pushBack(new_one);
      }
 
      // 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) {
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
          v.push_back(n2);
          return v;
        }
 
        node_fifo.pushBack(new_one);
      }
    }
 
    return v;
  }

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

Referenced by gum::MeekRules::_isOrientable_(), and gum::learning::SimpleMiic::isOrientable_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mixedUnorientedPath()

std::vector< NodeId > gum::MixedGraph::mixedUnorientedPath	(	NodeId	node1,
		NodeId	node2 ) const

returns a mixed/directed path from node1 to node2 in the arc/edge set

This function returns, if any, a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of th arcs)

Parameters

node1	the id from which the path begins
node2	the id to which the path ends if no path can be found between the two nodes, the returned vector is empty.

Definition at line 191 of file mixedGraph.cpp.

                                                                                {
    std::vector< NodeId > v;
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > node_fifo;
    node_fifo.pushBack(n2);
 
    // mark[node] = successor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    NodeId current;
 
    while (!node_fifo.empty()) {
      current = node_fifo.front();
      node_fifo.popFront();
 
      // check the neighbours
      for (const auto new_one: neighbours(current)) {
        if (mark.exists(new_one))   // if the node has already been visited
          continue;                 // do not check it again
 
        mark.insert(new_one, current);
 
        if (new_one == n1) {
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
          v.push_back(n2);
          return v;
        }
 
        node_fifo.pushBack(new_one);
      }
 
      // 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) {
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
          v.push_back(n2);
          return v;
        }
        node_fifo.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) {
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
          v.push_back(n2);
          return v;
        }
 
        node_fifo.pushBack(new_one);
      }
    }
 
    return v;
  }

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

Here is the call 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 96 of file edgeGraphPart_inl.h.

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

References _neighbours_, and gum::emptyNodeSet.

Referenced by gum::MeekRules::_applyMeekRules_(), gum::BinaryJoinTreeConverterDefault::_convertClique_(), gum::BinaryJoinTreeConverterDefault::_convertConnectedComponent_(), gum::MeekRules::_critereMinParents_(), gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::StructuredInference< GUM_SCALAR >::_removeBarrenNodes_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::StaticTriangulation::_triangulate_(), gum::MixedGraph::boundary(), gum::MixedGraph::chainComponent(), gum::MixedGraph::hasMixedOrientedPath(), gum::PDAG::hasMixedReallyOrientedPath(), gum::UndiGraph::hasUndirectedCycle(), hasUndirectedPath(), hasUndirectedPath(), hasUndirectedPath(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::PDAG::moralGraph(), gum::UndiGraph::nodes2ConnectedComponent(), gum::UndiGraph::partialUndiGraph(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::learning::SimpleMiic::propagatesRemainingOrientableEdges_(), gum::rec_ancestral(), gum::rec_hasMixedReallyOrientedPath(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), gum::UndiGraph::toDot(), undirectedPath(), gum::learning::Miic::unshieldedTriples_(), gum::learning::SimpleMiic::unshieldedTriples_(), gum::learning::Miic::unshieldedTriplesMiic_(), and gum::learning::SimpleMiic::unshieldedTriplesMiic_().

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

is basically not thread safe !!

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

Definition at line 232 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_.

◆ nodes()

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

inherited

return *this as a NodeGraphPart

Definition at line 368 of file nodeGraphPart_inl.h.

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

References NodeGraphPart().

Referenced by gum::MeekRules::_complete_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::ClassBayesNet< GUM_SCALAR >::_init_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::MeekRules::_propagates_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::PRMFactory< GUM_SCALAR >::addAttribute(), gum::UndiGraph::hasUndirectedCycle(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::DAG::moralizedAncestralGraph(), gum::PDAG::moralizedAncestralGraph(), gum::prm::gspan::Pattern::nodes(), gum::UndiGraph::nodes2ConnectedComponent(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::UndiGraph::partialUndiGraph(), gum::learning::IBNLearner::prepareMiic_(), gum::MeekRules::propagateToDAG(), gum::DiGraph::toDot(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nodes2ConnectedComponent()

NodeProperty< NodeId > gum::UndiGraph::nodes2ConnectedComponent ( ) const

inherited

returns a property {node:id of connected component}

Definition at line 184 of file undiGraph.cpp.

                                                                   {
    NodeProperty< NodeId > res;
 
    NodeId numCC = 0;
    for (const auto node: nodes()) {
      if (res.exists(node)) continue;
      NodeSet nodes{node};
      while (!nodes.empty()) {
        auto actual = *(nodes.begin());
        nodes.erase(actual);
        res.insert(actual, numCC);
        for (const auto nei: neighbours(actual)) {
          if (!res.exists(nei))
            if (!nodes.exists(nei)) nodes.insert(nei);
        }
      }
      numCC += 1;
    }
 
    return res;
  }

References gum::HashTable< Key, Val >::exists(), gum::HashTable< Key, Val >::insert(), gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::nodes().

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(), gum::UndiGraph::hasUndirectedCycle(), and nodesPropertyFromVal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator!=() [1/2]

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

354{ return !operator==(p); }

gum::NodeGraphPart::operator==

bool operator==(const NodeGraphPart &p) const

check whether two NodeGraphParts contain the same nodes

Definition nodeGraphPart_inl.h:343

References NodeGraphPart(), and operator==().

Here is the call graph for this function:

◆ operator!=() [2/2]

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

inherited

tests whether two UndiGraphs are different

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 90 of file undiGraph_inl.h.

90{ return !operator==(p); }

gum::UndiGraph::operator==

bool operator==(const UndiGraph &g) const

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

Definition undiGraph_inl.h:86

References UndiGraph(), and operator==().

Here is the call graph for this function:

◆ operator=()

INLINE MixedGraph & gum::MixedGraph::operator= ( const MixedGraph & g )

copy operator

Parameters

g	the MixedGraph to copy

Definition at line 51 of file mixedGraph_inl.h.

                                                            {
    // avoid self assignment
    if (this != &g) {
      // remove the old graph properly
      EdgeGraphPart::clearEdges();
      ArcGraphPart::clearArcs();
      NodeGraphPart::clearNodes();
 
      // fill the new graph
      NodeGraphPart::operator=(g);
      EdgeGraphPart::operator=(g);
      ArcGraphPart::operator=(g);
    }
 
    return *this;
  }

References MixedGraph(), gum::ArcGraphPart::clearArcs(), gum::EdgeGraphPart::clearEdges(), gum::NodeGraphPart::clearNodes(), gum::ArcGraphPart::operator=(), gum::EdgeGraphPart::operator=(), and gum::NodeGraphPart::operator=().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [1/6]

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

201{ return _arcs_ == p._arcs_; }

References ArcGraphPart(), and _arcs_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [2/6]

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

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

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

Here is the call graph for this function:

◆ operator==() [3/6]

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 125 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==() [4/6]

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

tests whether two MixedGraphs are identical (same nodes, arcs and edges)

Parameters

g	the MixedGraph with which "this" is compared

Definition at line 81 of file mixedGraph_inl.h.

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

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

Here is the call graph for this function:

◆ operator==() [5/6]

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.

                                                                  {
    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 operator!=(), 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==() [6/6]

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 86 of file undiGraph_inl.h.

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

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

Referenced by operator!=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ parents() [1/2]

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

inherited

returns the set of parents of a set of nodes

Definition at line 94 of file arcGraphPart_inl.h.

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

References parents().

Here is the call graph for this function:

◆ parents() [2/2]

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

inherited

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

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

Parameters

id	the node toward which the arcs returned are pointing

Definition at line 75 of file arcGraphPart_inl.h.

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

References _parents_, and gum::emptyNodeSet.

Referenced by gum::MeekRules::_complete_(), gum::MeekRules::_critereMinParents_(), gum::learning::Miic::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::learning::Miic::_existsNonTrivialDirectedPath_(), gum::learning::SimpleMiic::_existsNonTrivialDirectedPath_(), gum::prm::gspan::Pattern::_expandCodeIsMinimal_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClass_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClasses_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateCluster_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::prm::SVED< GUM_SCALAR >::_initLiftedNodes_(), gum::MeekRules::_isOrientable_(), gum::DAG::_minimalCondSetVisitDn_(), gum::DAG::_minimalCondSetVisitUp_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::MeekRules::_propagates_(), gum::learning::Miic::_propagatingOrientationMiic_(), gum::learning::SimpleMiic::_propagatingOrientationMiic_(), gum::prm::gspan::Pattern::_rec_(), gum::EssentialGraph::_strongly_protected_(), ancestors(), gum::BarrenNodesFinder::barrenNodes(), gum::MixedGraph::boundary(), directedPath(), directedUnorientedPath(), eraseParents(), family(), gum::MixedGraph::hasMixedOrientedPath(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::initialize_(), gum::prm::PRMClassElementContainer< double >::isInputNode(), gum::learning::Miic::isMaxIndegree_(), gum::prm::gspan::Pattern::isMinimal(), gum::learning::SimpleMiic::isOrientable_(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::makeInferenceNodeToNeighbours_(), gum::DAG::minimalCondSet(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::DAG::moralizedAncestralGraph(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), parents(), gum::rec_ancestral(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::prm::gspan::Pattern::rightmostPath(), gum::DAGCycleDetector::setDAG(), and unvirtualizedEraseParents().

◆ partialUndiGraph()

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

virtualinherited

returns the partial graph formed by the nodes given in parameter

Definition at line 171 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 83 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_);
 
    _boundVal_ = s._boundVal_;
 
    _updateEndIteratorSafe_();
  }

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

Referenced by gum::DAG::moralGraph(), gum::PDAG::moralGraph(), and 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(), begin(), end(), and toString().

Here is the call graph for this function:

◆ size()

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

inherited

alias for sizeNodes

Definition at line 288 of file nodeGraphPart_inl.h.

288{ return sizeNodes(); }

References sizeNodes().

Referenced by gum::StaticTriangulation::StaticTriangulation(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::StaticTriangulation::_triangulate_(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), nodesPropertyFromFunction(), nodesPropertyFromVal(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::StaticTriangulation::setGraph(), gum::DAGmodel::size(), gum::prm::gspan::Pattern::size(), gum::UGmodel::size(), and gum::UndiGraph::toDot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sizeArcs()

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

inherited

indicates the number of arcs stored within the ArcGraphPart

Definition at line 57 of file arcGraphPart_inl.h.

57{ return _arcs_.size(); }

References _arcs_.

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

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 57 of file edgeGraphPart_inl.h.

57{ return _edges_.size(); }

References _edges_.

◆ sizeNodes()

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

inherited

returns the number of nodes in the NodeGraphPart

Definition at line 284 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(), and size().

Here is the caller graph for this function:

◆ toDot()

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

overridevirtual

to friendly display mixed graph in DOT format

Reimplemented from gum::UndiGraph.

Reimplemented in gum::PDAG.

Definition at line 276 of file mixedGraph.cpp.

                                    {
    std::stringstream output;
    std::stringstream nodeStream;
    std::stringstream edgeStream;
 
    NodeSet treatedNodes;
 
    output << "digraph \""
           << "no_name\" {" << std::endl;
    nodeStream << "node [shape = ellipse];" << std::endl;
    std::string tab = "  ";
 
    for (const auto node: nodes()) {
      nodeStream << tab << node << ";";
 
      for (const auto nei: neighbours(node))
        if (!treatedNodes.exists(nei))
          edgeStream << tab << node << " -> " << nei << " [dir=none];" << std::endl;
 
      for (const auto chi: children(node))
        edgeStream << tab << node << " -> " << chi << ";" << std::endl;
 
      treatedNodes.insert(node);
    }
 
    output << nodeStream.str() << std::endl << edgeStream.str() << std::endl << "}" << std::endl;
 
    return output.str();
  }

References gum::ArcGraphPart::children(), gum::Set< Key >::exists(), gum::Set< Key >::insert(), gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

◆ topologicalOrder()

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

inherited

Build and return a topological order.

Exceptions

InvalidDirectedCycle Raised if this DiGraph contains cycles.

Definition at line 111 of file diGraph.cpp.

                                                     {
    Sequence< NodeId > topologicalOrder;
    const auto&        dag = *this;
 
    if (dag.empty()) return topologicalOrder;
 
    auto border = std::vector< NodeId >();
    border.reserve(dag.size() / 2);
    auto count = dag.nodesPropertyFromVal< Size >(0, dag.size());
    for (const auto node: dag.nodes()) {
      if (dag.parents(node).empty()) { border.push_back(node); }
      count[node] = dag.parents(node).size();
    }
 
    if (border.empty()) {
      GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
    }
 
    while (!border.empty()) {
      const auto root = border.back();
      border.pop_back();
 
      if (topologicalOrder.exists(root)) {
        GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
      }
      topologicalOrder.insert(root);
 
      for (const auto child: dag.children(root)) {
        if (count[child] == 1) { border.push_back(child); }
        if (count[child] == 0) {
          GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
        }
        count[child]--;
      }
    }
 
    GUM_ASSERT(topologicalOrder.size() == dag.size());
    return topologicalOrder;
  }

References GUM_ERROR, and topologicalOrder().

Referenced by gum::IBayesNet< double >::arcs(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), and topologicalOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toString()

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

overridevirtual

to friendly display the content of the MixedGraph

Reimplemented from gum::NodeGraphPart.

Definition at line 87 of file mixedGraph.cpp.

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

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

Referenced by gum::operator<<().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ undirectedPath()

std::vector< NodeId > gum::EdgeGraphPart::undirectedPath	(	NodeId	node1,
		NodeId	node2 ) const

inherited

returns a possible path from node1 to node2 in the edge 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 145 of file edgeGraphPart.cpp.

                                                                              {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(n2);
 
    // mark[node] = predecessor 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 neighbour
      for (const auto new_one: neighbours(current)) {
        if (mark.exists(new_one))   // if this node is already marked, stop
          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")
  }

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

Here is the call graph for this function:

◆ unvirtualizedEraseChildren()

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

inherited

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

Parameters

id	the node whose outgoing arcs will be removed

Definition at line 189 of file arcGraphPart_inl.h.

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

References _children_, children(), and eraseArc().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

◆ unvirtualizedEraseParents()

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

inherited

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

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 177 of file arcGraphPart_inl.h.

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

References _parents_, eraseArc(), and parents().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unvirtualizedEraseSetOfArcs_()

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

protectedinherited

similar to eraseSetOfArcs_ except that it is unvirtualized

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

Definition at line 172 of file arcGraphPart_inl.h.

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

Signaler1< NodeId > gum::NodeGraphPart::onNodeDeleted

inherited

Definition at line 290 of file nodeGraphPart.h.

Referenced by _clearNodes_(), and eraseNode().

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

agrum/base/graphs/mixedGraph.h
agrum/base/graphs/mixedGraph.cpp
agrum/base/graphs/mixedGraph_inl.h

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ArcIterator

◆ EdgeIterator

◆ node_const_iterator

◆ node_const_iterator_safe

◆ node_iterator

◆ node_iterator_safe

◆ NodeConstIterator

◆ NodeConstIteratorSafe

◆ NodeIterator

◆ NodeIteratorSafe

Constructor & Destructor Documentation

◆ MixedGraph() [1/4]

◆ MixedGraph() [2/4]

◆ MixedGraph() [3/4]

◆ MixedGraph() [4/4]

◆ ~MixedGraph()

Member Function Documentation

◆ _checkChildren_()

◆ _checkNeighbours_()

◆ _checkParents_()

◆ _clearEdges_()

◆ addArc()

◆ addEdge()

◆ addNode()

◆ addNodes()

◆ addNodeWithId()

◆ ancestors()

◆ arcs()

◆ arcsProperty() [1/2]

◆ arcsProperty() [2/2]

◆ asNodeSet()

◆ begin()

◆ beginSafe()

◆ bound()

◆ boundary()

◆ chainComponent()

◆ children() [1/2]

◆ children() [2/2]

◆ clear()

◆ clearArcs()

◆ clearEdges()

◆ clearNodes()

◆ completeGraph() [1/2]

◆ completeGraph() [2/2]

◆ descendants()

◆ directedPath()

◆ directedUnorientedPath()

◆ edges()

◆ edgesProperty() [1/2]

◆ edgesProperty() [2/2]

◆ empty()

◆ emptyArcs()

◆ emptyEdges()

◆ emptyNodes()

◆ end()

◆ endSafe()

◆ eraseArc()

◆ eraseChildren()

◆ eraseEdge()

◆ eraseNeighbours()

◆ eraseNode()

◆ eraseParents()

◆ eraseSetOfArcs_()

◆ exists()

◆ existsArc() [1/2]

◆ existsArc() [2/2]

◆ existsEdge() [1/2]

◆ existsEdge() [2/2]

◆ existsNode()

◆ family() [1/2]

◆ family() [2/2]