aGrUM 3.1.1
a C++ library for (probabilistic) graphical models
gum::EdgeGraphPart Class Reference

Classes for undirected edge sets. More...

#include <edgeGraphPart.h>

Inheritance diagram for gum::EdgeGraphPart:
Collaboration diagram for gum::EdgeGraphPart:

Public Types

using EdgeIterator = EdgeSetIterator

Public Member Functions

Constructors / Destructors
 EdgeGraphPart (Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
 default constructor
 EdgeGraphPart (const EdgeGraphPart &s)
 copy constructor
 EdgeGraphPart (EdgeGraphPart &&s)
 move constructor
virtual ~EdgeGraphPart ()
 destructor
Operators
EdgeGraphPartoperator= (const EdgeGraphPart &s)
 copy operator
EdgeGraphPartoperator= (EdgeGraphPart &&s)
 move assignment operator
bool operator== (const EdgeGraphPart &p) const
 tests whether two EdgeGraphParts contain the same edges
Accessors/Modifiers
virtual void addEdge (NodeId n1, NodeId n2)
 insert a new edge into the EdgeGraphPart
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 EdgeSetedges () const
 returns the set of edges stored within the EdgeGraphPart
const NodeSetneighbours (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
virtual std::string toString () const
 to friendly display the content of the EdgeGraphPart
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))

Public Attributes

Signaler< NodeId, NodeIdonEdgeAdded
Signaler< NodeId, NodeIdonEdgeDeleted

Private Member Functions

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

Private Attributes

EdgeSet _edges_
 the set of all the edges contained within the EdgeGraphPart
NodeProperty< NodeSet * > _neighbours_
 for each node, the set of its adjacent edges

Detailed Description

Classes for undirected edge sets.

Author
Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
Usage example:
EdgeGraphPart edges1,edges2;
// insert elements into edges1
edges1.addEdge( 2,3 );
Edge edge( 5,3 );
edges1.addEdge( 5,3 );
// copy edges1 into edges2
edges2=edges1;
std::cerr<<"edges2:"<<edges2.toString()<<std::endl;
// remove some elements from edges1
edges1.eraseEdge( Edge (2,3) );
edges1.eraseEdge( edge );
if ( edges1.empty() ) std::cerr<<" edges1 is empty"<<std::endl;
// checks whether a given edge exists
if ( edges2.exists( edge ) )
std::cerr << "set contains " << edge << endl;
if ( edges2.exists( 5,3 ) )
std::cerr << "set contains " << edge << endl;
std::cerr<<edges2.toString()<<std::endl;
std::cerr<<edges2.neighbours( 5 )<<std::endl;
EdgeGraphPart(Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
virtual void addEdge(NodeId n1, NodeId n2)
insert a new edge into the EdgeGraphPart
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart
virtual std::string toString() const
to friendly display the content of the EdgeGraphPart
const NodeSet & neighbours(NodeId id) const
returns the set of node neighbours to a given node
The base class for all undirected edges.

Definition at line 94 of file edgeGraphPart.h.

Member Typedef Documentation

◆ EdgeIterator

Constructor & Destructor Documentation

◆ EdgeGraphPart() [1/3]

gum::EdgeGraphPart::EdgeGraphPart ( Size edges_size = HashTableConst::default_size,
bool edges_resize_policy = true )
explicit

default constructor

Parameters
edges_sizethe size of the hash table used to store all the edges
edges_resize_policythe resizing policy of this hash table

Definition at line 58 of file edgeGraphPart.cpp.

58 :
59 _edges_(edges_size, edges_resize_policy) {
60 GUM_CONSTRUCTOR(EdgeGraphPart);
61 }
EdgeSet _edges_
the set of all the edges contained within the EdgeGraphPart

References EdgeGraphPart(), and _edges_.

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ EdgeGraphPart() [2/3]

gum::EdgeGraphPart::EdgeGraphPart ( const EdgeGraphPart & s)

copy constructor

Parameters
sthe EdgeGraphPart to copy

Definition at line 68 of file edgeGraphPart.cpp.

68 : _edges_(s._edges_) {
69 GUM_CONS_CPY(EdgeGraphPart)
70
71 // copy the set of neighbours
72 _neighbours_.resize(s._neighbours_.capacity());
73
74 for (const auto& [key, nodeset]: s._neighbours_) {
75 NodeSet* newneigh = new NodeSet(*nodeset);
76 _neighbours_.insert(key, newneigh);
77 }
78
79 // send signals to indicate that there are new edges
80 if (onEdgeAdded.hasListener())
81 for (const auto& edge: _edges_)
82 GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
83 }
Signaler< NodeId, NodeId > onEdgeAdded
NodeProperty< NodeSet * > _neighbours_
for each node, the set of its adjacent edges
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
#define GUM_EMIT2(signal, arg1, arg2)
Definition signaler.h:290

References EdgeGraphPart(), _edges_, _neighbours_, GUM_EMIT2, and onEdgeAdded.

Here is the call graph for this function:

◆ EdgeGraphPart() [3/3]

gum::EdgeGraphPart::EdgeGraphPart ( EdgeGraphPart && s)

move constructor

Definition at line 63 of file edgeGraphPart.cpp.

63 :
64 _edges_(std::move(s._edges_)), _neighbours_(std::move(s._neighbours_)) {
65 GUM_CONS_MOV(EdgeGraphPart);
66 }

References EdgeGraphPart(), _edges_, and _neighbours_.

Here is the call graph for this function:

◆ ~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )
virtual

destructor

Definition at line 85 of file edgeGraphPart.cpp.

85 {
86 GUM_DESTRUCTOR(EdgeGraphPart)
87 // be sure to deallocate all the neighbours sets
89 }

References EdgeGraphPart(), and _clearEdges_().

Here is the call graph for this function:

Member Function Documentation

◆ _checkNeighbours_()

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

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

Parameters
idthe node whose neighbours[id] is checked

Definition at line 68 of file edgeGraphPart_inl.h.

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

References _neighbours_.

Referenced by addEdge().

Here is the caller graph for this function:

◆ _clearEdges_()

void gum::EdgeGraphPart::_clearEdges_ ( )
private

Definition at line 93 of file edgeGraphPart.cpp.

93 {
94 for (const auto& elt: _neighbours_)
95 delete elt.second;
96
97 _neighbours_.clear();
98
99 if (onEdgeDeleted.hasListener()) {
100 EdgeSet tmp = _edges_;
101 _edges_.clear();
102
103 for (const auto& edge: tmp)
104 GUM_EMIT2(onEdgeDeleted, edge.first(), edge.second());
105 } else {
106 _edges_.clear();
107 }
108 }
Signaler< NodeId, NodeId > onEdgeDeleted
Set< Edge > EdgeSet
Some typdefs and define for shortcuts ...

References _edges_, _neighbours_, GUM_EMIT2, and onEdgeDeleted.

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

Here is the caller graph for this function:

◆ addEdge()

INLINE void gum::EdgeGraphPart::addEdge ( NodeId n1,
NodeId n2 )
virtual

insert a new edge into the EdgeGraphPart

Parameters
n1the id of one extremity of the new edge to be inserted
n2the id of the other extremity of the new edge to be inserted
Warning
if the edge already exists, nothing is done. In particular, no exception is raised.

Reimplemented in gum::CliqueGraph, gum::PAG, gum::PDAG, and gum::UndiGraph.

Definition at line 72 of file edgeGraphPart_inl.h.

72 {
73 Edge edge(first, second);
74 _edges_.insert(edge);
75 _checkNeighbours_(first);
76 _checkNeighbours_(second);
77 _neighbours_[first]->insert(second);
78 _neighbours_[second]->insert(first);
79
80 GUM_EMIT2(onEdgeAdded, first, second);
81 }
void _checkNeighbours_(NodeId id)
when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set ent...

References _checkNeighbours_(), _edges_, _neighbours_, GUM_EMIT2, and onEdgeAdded.

Referenced by gum::PDAG::addEdge(), and gum::UndiGraph::addEdge().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ clearEdges()

void gum::EdgeGraphPart::clearEdges ( )
virtual

removes all the edges from the EdgeGraphPart

Reimplemented in gum::CliqueGraph, and gum::PAG.

Definition at line 91 of file edgeGraphPart.cpp.

91{ _clearEdges_(); }

References _clearEdges_().

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ edges()

◆ edgesProperty() [1/2]

template<typename VAL>
EdgeProperty< VAL > gum::EdgeGraphPart::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)

Parameters
athe default value assigned to each edge in the returned Property
sizean optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of 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(* )(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))

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

◆ emptyEdges()

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

indicates wether the EdgeGraphPart contains any edge

Definition at line 56 of file edgeGraphPart_inl.h.

56{ return _edges_.empty(); }

References _edges_.

◆ eraseEdge()

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

removes an edge from the EdgeGraphPart

Parameters
edgethe 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, and gum::PAG.

Definition at line 83 of file edgeGraphPart_inl.h.

83 {
84 if (existsEdge(edge)) {
85 // ASSUMING first and second exists in _neighbours_ (if not, it is an
86 // error)
87 NodeId id1 = edge.first();
88 NodeId id2 = edge.second();
89
90 _neighbours_[id1]->erase(id2);
91 _neighbours_[id2]->erase(id1);
92 _edges_.erase(edge);
93 GUM_EMIT2(onEdgeDeleted, id1, id2);
94 }
95 }
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
Size NodeId
Type for node ids.

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

Referenced by gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::PAG::eraseEdge(), eraseNeighbours(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), and unvirtualizedEraseNeighbours().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ eraseNeighbours()

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

erase all the edges adjacent to a given node

Parameters
idthe node the adjacent edges of which will be removed
Warning
if no edge is adjacent to id, nothing is done. In particular, no exception is thrown.
although this method is not virtual, it calls method eraseEdge( const Edge& edge ) and, as such, has a "virtual" behaviour

Definition at line 102 of file edgeGraphPart_inl.h.

102 {
103 if (_neighbours_.exists(id)) {
104 const NodeSet& set = *(_neighbours_[id]);
105
106 for (auto iter = set.beginSafe(); iter != set.endSafe();
107 ++iter) { // safe iterator needed here
108 // warning: use this erases so that you actually use the virtualized
109 // edge removal function
110 eraseEdge(Edge(*iter, id));
111 }
112 }
113 }

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

Here is the call graph for this function:

◆ existsEdge() [1/2]

◆ existsEdge() [2/2]

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

indicates whether a given edge exists

Parameters
n1the id of one extremity of the edge we test the existence in the EdgeGraphPart
n2the id of the other extremity of the edge we test the existence in the EdgeGraphPart

Definition at line 64 of file edgeGraphPart_inl.h.

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

References _neighbours_.

◆ listMapEdges()

template<typename VAL>
List< VAL > gum::EdgeGraphPart::listMapEdges ( VAL(* )(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))

Parameters
fa function assigning a VAL to any edge

◆ neighbours()

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

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
idthe node to which the edges are adjacent

Definition at line 97 of file edgeGraphPart_inl.h.

97 {
98 if (_neighbours_.exists(id)) return *(_neighbours_[id]);
99 else return emptyNodeSet;
100 }
const NodeSet emptyNodeSet
Some typdefs and define for shortcuts ...

References _neighbours_, and gum::emptyNodeSet.

Referenced by gum::BinaryJoinTreeConverterDefault::_convertClique_(), gum::BinaryJoinTreeConverterDefault::_convertConnectedComponent_(), 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::learning::FCI::computePossibleDSep_(), gum::PAG::eraseNode(), gum::PDAG::hasMixedReallyOrientedPath(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::UndiGraph::partialUndiGraph(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::rec_hasMixedReallyOrientedPath(), gum::learning::FCI::ruleR10_(), gum::learning::FCI::ruleR1_(), gum::learning::FCI::ruleR2_(), gum::learning::FCI::ruleR3_(), gum::learning::FCI::ruleR4_(), gum::learning::FCI::ruleR5_(), gum::learning::FCI::ruleR6_(), gum::learning::FCI::ruleR7_(), gum::learning::FCI::ruleR8_(), gum::learning::FCI::ruleR9_(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the caller graph for this function:

◆ operator=() [1/2]

EdgeGraphPart & gum::EdgeGraphPart::operator= ( const EdgeGraphPart & s)

copy operator

Parameters
sthe EdgeGraphPart to copy

Definition at line 110 of file edgeGraphPart.cpp.

110 {
111 // avoid self assignment
112 if (this != &s) {
113 clearEdges();
114
115 _edges_ = s._edges_;
116
117 // copy the set of neighbours
118 _neighbours_.resize(s._neighbours_.capacity());
119
120 for (const auto& [key, nodeset]: s._neighbours_) {
121 NodeSet* newneigh = new NodeSet(*nodeset);
122 _neighbours_.insert(key, newneigh);
123 }
124
125 if (onEdgeAdded.hasListener())
126 for (const auto& edge: _edges_)
127 GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
128
129 GUM_OP_CPY(EdgeGraphPart);
130 }
131
132 return *this;
133 }
virtual void clearEdges()
removes all the edges from the EdgeGraphPart

References EdgeGraphPart(), _edges_, _neighbours_, clearEdges(), GUM_EMIT2, and onEdgeAdded.

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator=() [2/2]

EdgeGraphPart & gum::EdgeGraphPart::operator= ( EdgeGraphPart && s)

move assignment operator

Definition at line 135 of file edgeGraphPart.cpp.

135 {
136 if (this != &s) {
137 clearEdges();
138 _edges_ = std::move(s._edges_);
139 _neighbours_ = std::move(s._neighbours_);
140 if (onEdgeAdded.hasListener()) {
141 for (const auto& edge: _edges_) {
142 GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
143 }
144 }
145 GUM_OP_MOV(EdgeGraphPart);
146 }
147 return *this;
148 }

References EdgeGraphPart(), _edges_, _neighbours_, clearEdges(), GUM_EMIT2, and onEdgeAdded.

Here is the call graph for this function:

◆ operator==()

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

tests whether two EdgeGraphParts contain the same edges

Parameters
pthe EdgeGraphPart that we compare with this

Definition at line 126 of file edgeGraphPart_inl.h.

126 {
127 return _edges_ == p._edges_;
128 }

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:

◆ sizeEdges()

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

indicates the number of edges stored within the EdgeGraphPart

Definition at line 58 of file edgeGraphPart_inl.h.

58{ return _edges_.size(); }

References _edges_.

◆ toString()

std::string gum::EdgeGraphPart::toString ( ) const
virtual

to friendly display the content of the EdgeGraphPart

Reimplemented in gum::CliqueGraph, gum::MixedGraph, gum::PAG, and gum::UndiGraph.

Definition at line 150 of file edgeGraphPart.cpp.

150 {
151 std::stringstream s;
152 bool first = true;
153 s << "{";
154
155 for (const auto& edge: _edges_) {
156 if (first) first = false;
157 else s << ",";
158
159 s << edge;
160 }
161
162 s << "}";
163
164 return s.str();
165 }

References _edges_.

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

Here is the caller graph for this function:

◆ unvirtualizedEraseNeighbours()

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

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

Parameters
idthe node whose ingoing arcs will be removed

Definition at line 115 of file edgeGraphPart_inl.h.

115 {
116 if (_neighbours_.exists(id)) {
117 const NodeSet& set = *(_neighbours_[id]);
118
119 for (auto iter = set.beginSafe(); iter != set.endSafe();
120 ++iter) { // safe iterator needed here
121 EdgeGraphPart::eraseEdge(Edge(*iter, id));
122 }
123 }
124 }

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

Member Data Documentation

◆ _edges_

EdgeSet gum::EdgeGraphPart::_edges_
private

◆ _neighbours_

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

◆ onEdgeAdded

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

Definition at line 98 of file edgeGraphPart.h.

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

◆ onEdgeDeleted

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

Definition at line 99 of file edgeGraphPart.h.

Referenced by _clearEdges_(), and eraseEdge().


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