aGrUM  0.14.3
gum::EdgeGraphPart Class Reference

Classes for undirected edge sets. More...

#include <edgeGraphPart.h>

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

Public Attributes

Signaler2< NodeId, NodeIdonEdgeAdded
 
Signaler2< NodeId, NodeIdonEdgeDeleted
 

Public Member Functions

Constructors / Destructors
 EdgeGraphPart (Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
 default constructor More...
 
 EdgeGraphPart (const EdgeGraphPart &s)
 copy constructor More...
 
virtual ~EdgeGraphPart ()
 destructor More...
 
Operators
EdgeGraphPartoperator= (const EdgeGraphPart &s)
 copy operator More...
 
bool operator== (const EdgeGraphPart &p) const
 tests whether two EdgeGraphParts contain the same edges More...
 
bool operator!= (const EdgeGraphPart &p) const
 tests whether two EdgeGraphParts contain different edges More...
 
Accessors/Modifiers
virtual void addEdge (const NodeId n1, const NodeId n2)
 insert a new edge into the EdgeGraphPart More...
 
virtual void eraseEdge (const Edge &edge)
 removes an edge from the EdgeGraphPart More...
 
bool existsEdge (const Edge &edge) const
 indicates whether a given edge exists More...
 
bool existsEdge (const NodeId n1, const NodeId n2) const
 indicates whether a given edge exists More...
 
bool emptyEdges () const
 indicates wether the EdgeGraphPart contains any edge More...
 
virtual void clearEdges ()
 removes all the edges from the EdgeGraphPart More...
 
Size sizeEdges () const
 indicates the number of edges stored within the EdgeGraphPart More...
 
const EdgeSetedges () const
 returns the set of edges stored within the EdgeGraphPart More...
 
const NodeSetneighbours (const NodeId id) const
 returns the set of edges adjacent to a given node More...
 
void eraseNeighbours (const NodeId id)
 erase all the edges adjacent to a given node More...
 
void unvirtualizedEraseNeighbours (const NodeId id)
 same function as eraseNeighbours but without any virtual call to an erase More...
 
const std::string toString () const
 to friendly display the content of the EdgeGraphPart More...
 
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)) More...
 
template<typename VAL >
EdgeProperty< VAL > edgesProperty (const VAL &a, 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) More...
 
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)) More...
 
const std::vector< NodeIdundirectedPath (const NodeId node1, const NodeId node2) const
 returns a possible path from node1 to node2 in the edge set More...
 

Public Types

typedef EdgeSetIterator EdgeIterator
 

Detailed Description

Classes for undirected edge sets.

Author
Pierre-Henri WUILLEMIN and Christophe GONZALES
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;

Definition at line 72 of file edgeGraphPart.h.

Member Typedef Documentation

◆ EdgeIterator

Constructor & Destructor Documentation

◆ EdgeGraphPart() [1/2]

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 36 of file edgeGraphPart.cpp.

36  :
37  __edges(edges_size, edges_resize_policy) {
38  GUM_CONSTRUCTOR(EdgeGraphPart);
39  }
EdgeGraphPart(Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

◆ EdgeGraphPart() [2/2]

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

copy constructor

Parameters
sthe EdgeGraphPart to copy

Definition at line 41 of file edgeGraphPart.cpp.

References __edges, __neighbours, GUM_EMIT2, and onEdgeAdded.

41  : __edges(s.__edges) {
42  GUM_CONS_CPY(EdgeGraphPart);
43 
44  // copy the set of neighbours
45  __neighbours.resize(s.__neighbours.capacity());
46 
47  for (const auto& elt : s.__neighbours) {
48  NodeSet* newneigh = new NodeSet(*elt.second);
49  __neighbours.insert(elt.first, newneigh);
50  }
51 
52  // send signals to indicate that there are new edges
53  if (onEdgeAdded.hasListener())
54  for (const auto& edge : __edges)
55  GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
56  }
EdgeGraphPart(Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:76
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

◆ ~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )
virtual

destructor

Definition at line 58 of file edgeGraphPart.cpp.

References clearEdges().

58  {
59  GUM_DESTRUCTOR(EdgeGraphPart);
60  // be sure to deallocate all the neighbours sets
61  clearEdges();
62  }
EdgeGraphPart(Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
virtual void clearEdges()
removes all the edges from the EdgeGraphPart
+ Here is the call graph for this function:

Member Function Documentation

◆ __checkNeighbours()

INLINE void gum::EdgeGraphPart::__checkNeighbours ( const NodeId  id) const
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 47 of file edgeGraphPart_inl.h.

References __neighbours.

Referenced by addEdge(), and neighbours().

47  {
48  if (!__neighbours.exists(id)) { __neighbours.insert(id, new NodeSet); }
49  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
+ Here is the caller graph for this function:

◆ addEdge()

INLINE void gum::EdgeGraphPart::addEdge ( const NodeId  n1,
const 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::UndiGraph, and gum::CliqueGraph.

Definition at line 51 of file edgeGraphPart_inl.h.

References __checkNeighbours(), __edges, __neighbours, GUM_EMIT2, gum::Set< Key, Alloc >::insert(), and onEdgeAdded.

Referenced by gum::UndiGraph::addEdge().

51  {
52  Edge edge(first, second);
53  __edges.insert(edge);
54  __checkNeighbours(first);
55  __checkNeighbours(second);
56  __neighbours[first]->insert(second);
57  __neighbours[second]->insert(first);
58 
59  GUM_EMIT2(onEdgeAdded, first, second);
60  }
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
void __checkNeighbours(const NodeId id) const
when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set ent...
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:76
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:610
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ 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.

Definition at line 64 of file edgeGraphPart.cpp.

References __edges, __neighbours, gum::Set< Key, Alloc >::clear(), GUM_EMIT2, and onEdgeDeleted.

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

64  {
65  for (const auto& elt : __neighbours)
66  delete elt.second;
67 
68  __neighbours.clear();
69 
70  if (onEdgeDeleted.hasListener()) {
71  EdgeSet tmp = __edges;
72  __edges.clear();
73 
74  for (const auto& edge : tmp)
75  GUM_EMIT2(onEdgeDeleted, edge.first(), edge.second());
76  } else {
77  __edges.clear();
78  }
79  }
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
Set< Edge > EdgeSet
Some typdefs and define for shortcuts ...
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
Signaler2< NodeId, NodeId > onEdgeDeleted
Definition: edgeGraphPart.h:77
void clear()
Removes all the elements, if any, from the set.
Definition: set_tpl.h:372
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ edges()

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

returns the set of edges stored within the EdgeGraphPart

Definition at line 36 of file edgeGraphPart_inl.h.

References __edges.

Referenced by gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::learning::Miic::_initiation(), gum::BarrenNodesFinder::barrenNodes(), gum::EssentialGraph::edges(), gum::SpanningForestPrim::edgesInSpanningForest(), and gum::learning::genericBNLearner::setPossibleSkeleton().

36 { return __edges; }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the caller graph for this function:

◆ edgesProperty() [1/2]

template<typename VAL >
EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty ( VAL(*)(const Edge &)  f,
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.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree().

+ Here is the caller graph for this function:

◆ edgesProperty() [2/2]

template<typename VAL >
EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty ( const VAL &  a,
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.

◆ emptyEdges()

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

indicates wether the EdgeGraphPart contains any edge

Definition at line 32 of file edgeGraphPart_inl.h.

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

32 { return __edges.empty(); }
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:704
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:

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

Definition at line 62 of file edgeGraphPart_inl.h.

References __edges, __neighbours, gum::Set< Key, Alloc >::erase(), existsEdge(), gum::Edge::first(), GUM_EMIT2, onEdgeDeleted, and gum::Edge::second().

Referenced by gum::learning::Miic::_initiation(), gum::learning::Miic::_iteration(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_latents(), gum::learning::Miic::_orientation_miic(), gum::learning::Miic::_propagatesHead(), eraseNeighbours(), and unvirtualizedEraseNeighbours().

62  {
63  if (existsEdge(edge)) {
64  // ASSUMING first and second exists in __neighbours (if not, it is an
65  // error)
66  NodeId id1 = edge.first(), id2 = edge.second();
67 
68  __neighbours[id1]->erase(id2);
69  __neighbours[id2]->erase(id1);
70  __edges.erase(edge);
71  GUM_EMIT2(onEdgeDeleted, id1, id2);
72  }
73  }
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
void erase(const Key &k)
Erases an element from the set.
Definition: set_tpl.h:653
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
Signaler2< NodeId, NodeId > onEdgeDeleted
Definition: edgeGraphPart.h:77
Size NodeId
Type for node ids.
Definition: graphElements.h:97
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ eraseNeighbours()

INLINE void gum::EdgeGraphPart::eraseNeighbours ( const 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 80 of file edgeGraphPart_inl.h.

References __neighbours, eraseEdge(), and neighbours().

80  {
81  if (__neighbours.exists(id)) {
82  const NodeSet& set = neighbours(id);
83 
84  for (auto iter = set.beginSafe(); iter != set.endSafe();
85  ++iter) { // safe iterator needed here
86  // warning: use this erase so that you actually use the virtualized
87  // edge removal function
88  eraseEdge(Edge(*iter, id));
89  }
90  }
91  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart
+ Here is the call graph for this function:

◆ existsEdge() [1/2]

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

indicates whether a given edge exists

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

Definition at line 38 of file edgeGraphPart_inl.h.

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

Referenced by gum::StaticTriangulation::__computeMaxPrimeMergings(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::EssentialGraph::__strongly_protected(), gum::StaticTriangulation::__triangulate(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_miic(), eraseEdge(), gum::StaticTriangulation::fillIns(), and gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph().

38  {
39  return __edges.contains(edge);
40  }
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:578
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ existsEdge() [2/2]

INLINE bool gum::EdgeGraphPart::existsEdge ( const NodeId  n1,
const 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 42 of file edgeGraphPart_inl.h.

References __neighbours.

43  {
44  return __neighbours.exists(first) && __neighbours[first]->exists(second);
45  }
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges

◆ listMapEdges()

template<typename VAL >
List< VAL > gum::EdgeGraphPart::listMapEdges ( VAL(*)(const Edge &)  f) 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 ( const NodeId  id) const

returns the set of edges adjacent to a given node

Note that the set of edges 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 75 of file edgeGraphPart_inl.h.

References __checkNeighbours(), and __neighbours.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::StaticTriangulation::__computeMaxPrimeMergings(), gum::BinaryJoinTreeConverterDefault::__convertClique(), gum::BinaryJoinTreeConverterDefault::__convertConnectedComponent(), gum::SpanningForestPrim::__exploreNode(), gum::prm::gspan::DFSTree< GUM_SCALAR >::__initialiaze_root(), gum::BinaryJoinTreeConverterDefault::__markConnectedComponent(), gum::prm::StructuredInference< GUM_SCALAR >::__removeBarrenNodes(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::EssentialGraph::__strongly_protected(), gum::StaticTriangulation::__triangulate(), gum::learning::Miic::_propagatesHead(), eraseNeighbours(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::UndiGraph::hasUndirectedCycle(), gum::learning::Miic::learnStructure(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::EssentialGraph::neighbours(), gum::prm::gspan::DFSTree< GUM_SCALAR >::NeighborDegreeSort::operator()(), gum::UndiGraph::partialUndiGraph(), gum::EssentialGraph::toDot(), gum::UndiGraph::toDot(), gum::MixedGraph::toDot(), undirectedPath(), and unvirtualizedEraseNeighbours().

75  {
77  return *(__neighbours[id]);
78  }
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
void __checkNeighbours(const NodeId id) const
when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set ent...
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ operator!=()

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

tests whether two EdgeGraphParts contain different edges

Parameters
pthe EdgeGraphPart that we compare with this

Definition at line 108 of file edgeGraphPart_inl.h.

References __edges.

108  {
109  return __edges != p.__edges;
110  }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

◆ operator=()

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

copy operator

Parameters
sthe EdgeGraphPart to copy

Definition at line 81 of file edgeGraphPart.cpp.

References __edges, __neighbours, clearEdges(), GUM_EMIT2, and onEdgeAdded.

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

81  {
82  // avoid self assignment
83  if (this != &s) {
84  clearEdges();
85 
86  __edges = s.__edges;
87 
88  // copy the set of neighbours
89  __neighbours.resize(s.__neighbours.capacity());
90 
91  for (const auto& elt : s.__neighbours) {
92  NodeSet* newneigh = new NodeSet(*elt.second);
93  __neighbours.insert(elt.first, newneigh);
94  }
95 
96  if (onEdgeAdded.hasListener())
97  for (const auto& edge : __edges)
98  GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
99  }
100 
101  return *this;
102  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
virtual void clearEdges()
removes all the edges from the EdgeGraphPart
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:40
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:76
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:
+ Here is the caller 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 104 of file edgeGraphPart_inl.h.

References __edges.

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

104  {
105  return __edges == p.__edges;
106  }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ 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 34 of file edgeGraphPart_inl.h.

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

Referenced by gum::EssentialGraph::sizeEdges().

34 { return __edges.size(); }
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:698
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ toString()

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

to friendly display the content of the EdgeGraphPart

Definition at line 104 of file edgeGraphPart.cpp.

References __edges.

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

104  {
105  std::stringstream s;
106  bool first = true;
107  s << "{";
108 
109  for (const auto edge : __edges) {
110  if (first)
111  first = false;
112  else
113  s << ",";
114 
115  s << edge;
116  }
117 
118  s << "}";
119 
120  return s.str();
121  }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
+ Here is the caller graph for this function:

◆ undirectedPath()

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

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

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

Definition at line 124 of file edgeGraphPart.cpp.

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

124  {
125  // not recursive version => use a FIFO for simulating the recursion
126  List< NodeId > nodeFIFO;
127  nodeFIFO.pushBack(n2);
128 
129  // mark[node] = predecessor if visited, else mark[node] does not exist
130  NodeProperty< NodeId > mark;
131  mark.insert(n2, n2);
132 
133  NodeId current;
134 
135  while (!nodeFIFO.empty()) {
136  current = nodeFIFO.front();
137  nodeFIFO.popFront();
138 
139  // check the neighbour
140  for (const auto new_one : neighbours(current)) {
141  if (mark.exists(new_one)) // if this node is already marked, stop
142  continue;
143 
144  mark.insert(new_one, current);
145 
146  if (new_one == n1) {
147  std::vector< NodeId > v;
148 
149  for (current = n1; current != n2; current = mark[current])
150  v.push_back(current);
151 
152  v.push_back(n2);
153 
154  return v;
155  }
156 
157  nodeFIFO.pushBack(new_one);
158  }
159  }
160 
161  GUM_ERROR(NotFound, "no path found");
162  }
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
Size NodeId
Type for node ids.
Definition: graphElements.h:97
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
+ Here is the call graph for this function:

◆ unvirtualizedEraseNeighbours()

INLINE void gum::EdgeGraphPart::unvirtualizedEraseNeighbours ( const 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 93 of file edgeGraphPart_inl.h.

References __neighbours, eraseEdge(), and neighbours().

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

93  {
94  if (__neighbours.exists(id)) {
95  const NodeSet& set = neighbours(id);
96 
97  for (auto iter = set.beginSafe(); iter != set.endSafe();
98  ++iter) { // safe iterator needed here
99  EdgeGraphPart::eraseEdge(Edge(*iter, id));
100  }
101  }
102  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet *> __neighbours
for each node, the set of its adjacent edges
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart
+ 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

the set of all the edges contained within the EdgeGraphPart

Definition at line 223 of file edgeGraphPart.h.

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

◆ __neighbours

NodeProperty< NodeSet* > gum::EdgeGraphPart::__neighbours
mutableprivate

for each node, the set of its adjacent edges

Definition at line 226 of file edgeGraphPart.h.

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

◆ onEdgeAdded

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

Definition at line 76 of file edgeGraphPart.h.

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

◆ onEdgeDeleted

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

Definition at line 77 of file edgeGraphPart.h.

Referenced by clearEdges(), and eraseEdge().


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