aGrUM  0.15.1
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 75 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 39 of file edgeGraphPart.cpp.

39  :
40  __edges(edges_size, edges_resize_policy) {
41  GUM_CONSTRUCTOR(EdgeGraphPart);
42  }
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 44 of file edgeGraphPart.cpp.

References __edges, __neighbours, GUM_EMIT2, and onEdgeAdded.

44  : __edges(s.__edges) {
45  GUM_CONS_CPY(EdgeGraphPart);
46 
47  // copy the set of neighbours
48  __neighbours.resize(s.__neighbours.capacity());
49 
50  for (const auto& elt : s.__neighbours) {
51  NodeSet* newneigh = new NodeSet(*elt.second);
52  __neighbours.insert(elt.first, newneigh);
53  }
54 
55  // send signals to indicate that there are new edges
56  if (onEdgeAdded.hasListener())
57  for (const auto& edge : __edges)
58  GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
59  }
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:42
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:79
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

◆ ~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )
virtual

destructor

Definition at line 61 of file edgeGraphPart.cpp.

References clearEdges().

61  {
62  GUM_DESTRUCTOR(EdgeGraphPart);
63  // be sure to deallocate all the neighbours sets
64  clearEdges();
65  }
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 50 of file edgeGraphPart_inl.h.

References __neighbours.

Referenced by addEdge(), and neighbours().

50  {
51  if (!__neighbours.exists(id)) { __neighbours.insert(id, new NodeSet); }
52  }
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 54 of file edgeGraphPart_inl.h.

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

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

54  {
55  Edge edge(first, second);
56  __edges.insert(edge);
57  __checkNeighbours(first);
58  __checkNeighbours(second);
59  __neighbours[first]->insert(second);
60  __neighbours[second]->insert(first);
61 
62  GUM_EMIT2(onEdgeAdded, first, second);
63  }
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:42
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:79
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
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 67 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().

67  {
68  for (const auto& elt : __neighbours)
69  delete elt.second;
70 
71  __neighbours.clear();
72 
73  if (onEdgeDeleted.hasListener()) {
74  EdgeSet tmp = __edges;
75  __edges.clear();
76 
77  for (const auto& edge : tmp)
78  GUM_EMIT2(onEdgeDeleted, edge.first(), edge.second());
79  } else {
80  __edges.clear();
81  }
82  }
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:42
Signaler2< NodeId, NodeId > onEdgeDeleted
Definition: edgeGraphPart.h:80
void clear()
Removes all the elements, if any, from the set.
Definition: set_tpl.h:375
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 39 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().

39 { 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 35 of file edgeGraphPart_inl.h.

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

35 { return __edges.empty(); }
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
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 65 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().

65  {
66  if (existsEdge(edge)) {
67  // ASSUMING first and second exists in __neighbours (if not, it is an
68  // error)
69  NodeId id1 = edge.first(), id2 = edge.second();
70 
71  __neighbours[id1]->erase(id2);
72  __neighbours[id2]->erase(id1);
73  __edges.erase(edge);
74  GUM_EMIT2(onEdgeDeleted, id1, id2);
75  }
76  }
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:656
#define GUM_EMIT2(signal, arg1, arg2)
Definition: signaler2.h:42
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
Signaler2< NodeId, NodeId > onEdgeDeleted
Definition: edgeGraphPart.h:80
Size NodeId
Type for node ids.
Definition: graphElements.h:98
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 83 of file edgeGraphPart_inl.h.

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

83  {
84  if (__neighbours.exists(id)) {
85  const NodeSet& set = neighbours(id);
86 
87  for (auto iter = set.beginSafe(); iter != set.endSafe();
88  ++iter) { // safe iterator needed here
89  // warning: use this erase so that you actually use the virtualized
90  // edge removal function
91  eraseEdge(Edge(*iter, id));
92  }
93  }
94  }
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 41 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().

41  {
42  return __edges.contains(edge);
43  }
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:581
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 45 of file edgeGraphPart_inl.h.

References __neighbours.

46  {
47  return __neighbours.exists(first) && __neighbours[first]->exists(second);
48  }
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 78 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().

78  {
80  return *(__neighbours[id]);
81  }
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 111 of file edgeGraphPart_inl.h.

References __edges.

111  {
112  return __edges != p.__edges;
113  }
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 84 of file edgeGraphPart.cpp.

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

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

84  {
85  // avoid self assignment
86  if (this != &s) {
87  clearEdges();
88 
89  __edges = s.__edges;
90 
91  // copy the set of neighbours
92  __neighbours.resize(s.__neighbours.capacity());
93 
94  for (const auto& elt : s.__neighbours) {
95  NodeSet* newneigh = new NodeSet(*elt.second);
96  __neighbours.insert(elt.first, newneigh);
97  }
98 
99  if (onEdgeAdded.hasListener())
100  for (const auto& edge : __edges)
101  GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
102  }
103 
104  return *this;
105  }
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:42
Signaler2< NodeId, NodeId > onEdgeAdded
Definition: edgeGraphPart.h:79
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 107 of file edgeGraphPart_inl.h.

References __edges.

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

107  {
108  return __edges == p.__edges;
109  }
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 37 of file edgeGraphPart_inl.h.

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

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

37 { return __edges.size(); }
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701
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 107 of file edgeGraphPart.cpp.

References __edges.

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

107  {
108  std::stringstream s;
109  bool first = true;
110  s << "{";
111 
112  for (const auto edge : __edges) {
113  if (first)
114  first = false;
115  else
116  s << ",";
117 
118  s << edge;
119  }
120 
121  s << "}";
122 
123  return s.str();
124  }
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 127 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().

127  {
128  // not recursive version => use a FIFO for simulating the recursion
129  List< NodeId > nodeFIFO;
130  nodeFIFO.pushBack(n2);
131 
132  // mark[node] = predecessor if visited, else mark[node] does not exist
133  NodeProperty< NodeId > mark;
134  mark.insert(n2, n2);
135 
136  NodeId current;
137 
138  while (!nodeFIFO.empty()) {
139  current = nodeFIFO.front();
140  nodeFIFO.popFront();
141 
142  // check the neighbour
143  for (const auto new_one : neighbours(current)) {
144  if (mark.exists(new_one)) // if this node is already marked, stop
145  continue;
146 
147  mark.insert(new_one, current);
148 
149  if (new_one == n1) {
150  std::vector< NodeId > v;
151 
152  for (current = n1; current != n2; current = mark[current])
153  v.push_back(current);
154 
155  v.push_back(n2);
156 
157  return v;
158  }
159 
160  nodeFIFO.pushBack(new_one);
161  }
162  }
163 
164  GUM_ERROR(NotFound, "no path found");
165  }
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:98
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
+ 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 96 of file edgeGraphPart_inl.h.

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

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

96  {
97  if (__neighbours.exists(id)) {
98  const NodeSet& set = neighbours(id);
99 
100  for (auto iter = set.beginSafe(); iter != set.endSafe();
101  ++iter) { // safe iterator needed here
102  EdgeGraphPart::eraseEdge(Edge(*iter, id));
103  }
104  }
105  }
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 226 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 229 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 79 of file edgeGraphPart.h.

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

◆ onEdgeDeleted

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

Definition at line 80 of file edgeGraphPart.h.

Referenced by clearEdges(), and eraseEdge().


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