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
virtual	~EdgeGraphPart ()
	destructor
Operators
EdgeGraphPart &	operator= (const EdgeGraphPart &s)
	copy 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 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
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))
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.

Public Attributes
Signaler2< NodeId, NodeId >	onEdgeAdded
Signaler2< NodeId, NodeId >	onEdgeDeleted

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;

Definition at line 94 of file edgeGraphPart.h.

Member Typedef Documentation

EdgeIterator

using gum::EdgeGraphPart::EdgeIterator = EdgeSetIterator

Definition at line 96 of file edgeGraphPart.h.

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

                                                                        :
      _edges_(edges_size, edges_resize_policy) {
    GUM_CONSTRUCTOR(EdgeGraphPart);
  }

References EdgeGraphPart(), and _edges_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

EdgeGraphPart() [2/2]

gum::EdgeGraphPart::EdgeGraphPart

(

const EdgeGraphPart &

s

)

copy constructor

Parameters

s	the EdgeGraphPart to copy

Definition at line 63 of file edgeGraphPart.cpp.

                                                     : _edges_(s._edges_) {
    GUM_CONS_CPY(EdgeGraphPart)
 
    // copy the set of neighbours
    _neighbours_.resize(s._neighbours_.capacity());
 
    for (const auto& [key, nodeset]: s._neighbours_) {
      NodeSet* newneigh = new NodeSet(*nodeset);
      _neighbours_.insert(key, newneigh);
    }
 
    // send signals to indicate that there are new edges
    if (onEdgeAdded.hasListener())
      for (const auto& edge: _edges_)
        GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
  }

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

Here is the call graph for this function:

~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )

virtual

destructor

Definition at line 80 of file edgeGraphPart.cpp.

                                {
    GUM_DESTRUCTOR(EdgeGraphPart)
    // be sure to deallocate all the neighbours sets
    _clearEdges_();
  }

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

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:

_clearEdges_()

void gum::EdgeGraphPart::_clearEdges_ ( )

private

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:

addEdge()

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

virtual

insert a new edge into the EdgeGraphPart

Parameters

n1	the id of one extremity of the new edge to be inserted
n2	the 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::PDAG, and gum::UndiGraph.

Definition at line 71 of file edgeGraphPart_inl.h.

                                                                {
    Edge edge(first, second);
    _edges_.insert(edge);
    _checkNeighbours_(first);
    _checkNeighbours_(second);
    _neighbours_[first]->insert(second);
    _neighbours_[second]->insert(first);
 
    GUM_EMIT2(onEdgeAdded, first, second);
  }

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.

Definition at line 86 of file edgeGraphPart.cpp.

{ _clearEdges_(); }

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:

edges()

INLINE const EdgeSet & gum::EdgeGraphPart::edges

(

)

const

returns the set of edges stored within the EdgeGraphPart

Definition at line 59 of file edgeGraphPart_inl.h.

{ 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

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

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.

emptyEdges()

INLINE bool gum::EdgeGraphPart::emptyEdges

(

)

const

indicates wether the EdgeGraphPart contains any edge

Definition at line 55 of file edgeGraphPart_inl.h.

{ return _edges_.empty(); }

References _edges_.

eraseEdge()

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

virtual

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

Referenced by gum::MeekRules::_applyMeekRules_(), gum::learning::Miic::_orientingVstructureMiic_(), gum::learning::SimpleMiic::_orientingVstructureMiic_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::learning::Miic::_propagatingOrientationMiic_(), gum::learning::SimpleMiic::_propagatingOrientationMiic_(), gum::prm::GSpan< GUM_SCALAR >::discoverPatterns(), eraseNeighbours(), gum::learning::Miic::initiation_(), gum::learning::SimpleMiic::initiation_(), gum::learning::Miic::iteration_(), gum::learning::SimpleMiic::iteration_(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::learning::SimpleMiic::propagatesRemainingOrientableEdges_(), 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

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:

existsEdge() [1/2]

INLINE bool gum::EdgeGraphPart::existsEdge

(

const Edge &

edge

)

const

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.

{ 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

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

hasUndirectedPath() [1/3]

bool gum::EdgeGraphPart::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.

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

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

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:

listMapEdges()

template<typename VAL>

List< VAL > gum::EdgeGraphPart::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))

Parameters

f	a 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

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_().

operator=()

EdgeGraphPart & gum::EdgeGraphPart::operator=

(

const EdgeGraphPart &

s

)

copy operator

Parameters

s	the EdgeGraphPart to copy

Definition at line 105 of file edgeGraphPart.cpp.

                                                              {
    // avoid self assignment
    if (this != &s) {
      clearEdges();
 
      _edges_ = s._edges_;
 
      // copy the set of neighbours
      _neighbours_.resize(s._neighbours_.capacity());
 
      for (const auto& [key, nodeset]: s._neighbours_) {
        NodeSet* newneigh = new NodeSet(*nodeset);
        _neighbours_.insert(key, newneigh);
      }
 
      if (onEdgeAdded.hasListener())
        for (const auto& edge: _edges_)
          GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
    }
 
    return *this;
  }

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

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

INLINE bool gum::EdgeGraphPart::operator==

(

const EdgeGraphPart &

p

)

const

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:

sizeEdges()

INLINE Size gum::EdgeGraphPart::sizeEdges

(

)

const

indicates the number of edges stored within the EdgeGraphPart

Definition at line 57 of file edgeGraphPart_inl.h.

{ 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, and gum::UndiGraph.

Definition at line 128 of file edgeGraphPart.cpp.

                                          {
    std::stringstream s;
    bool              first = true;
    s << "{";
 
    for (const auto& edge: _edges_) {
      if (first) first = false;
      else s << ",";
 
      s << edge;
    }
 
    s << "}";
 
    return s.str();
  }

References _edges_.

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

Here is the caller graph for this function:

undirectedPath()

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

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:

unvirtualizedEraseNeighbours()

INLINE void gum::EdgeGraphPart::unvirtualizedEraseNeighbours

(

NodeId

id

)

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:

Member Data Documentation

_edges_

EdgeSet gum::EdgeGraphPart::_edges_

private

the set of all the edges contained within the EdgeGraphPart

Definition at line 266 of file edgeGraphPart.h.

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

_neighbours_

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

private

for each node, the set of its adjacent edges

Definition at line 269 of file edgeGraphPart.h.

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

onEdgeAdded

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

Definition at line 98 of file edgeGraphPart.h.

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

onEdgeDeleted

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

• agrum/base/graphs/parts/edgeGraphPart.h
• agrum/base/graphs/parts/edgeGraphPart.cpp
• agrum/base/graphs/parts/edgeGraphPart_inl.h