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, NodeId >	onEdgeAdded
Signaler2< NodeId, NodeId >	onEdgeDeleted

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
EdgeGraphPart &	operator= (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 EdgeSet &	edges () const
	returns the set of edges stored within the EdgeGraphPart More...
const NodeSet &	neighbours (const NodeId id) const
	returns the set of node neighbours 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...
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< NodeId >	undirectedPath (const NodeId node1, const NodeId node2) const
	returns a possible path from node1 to node2 in the edge set More...
bool	hasUndirectedPath (const NodeId n1, const NodeId n2) const
	return true if n1 and n2 are connected (by an undirected path) in the graph. More...
bool	hasUndirectedPath (const NodeId n1, const 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. More...
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. More...

Public Types
typedef EdgeSetIterator	EdgeIterator

Detailed Description

Classes for undirected edge sets.

Author

Pierre-Henri WUILLEMIN() & 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 74 of file edgeGraphPart.h.

Member Typedef Documentation

EdgeIterator

typedef EdgeSetIterator gum::EdgeGraphPart::EdgeIterator

Definition at line 76 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 38 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

EdgeGraphPart() [2/2]

gum::EdgeGraphPart::EdgeGraphPart

(

const EdgeGraphPart &

s

)

copy constructor

Parameters

s	the EdgeGraphPart to copy

Definition at line 43 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                     : _edges_(s._edges_) {
    GUM_CONS_CPY(EdgeGraphPart);

    // copy the set of neighbours
    _neighbours_.resize(s._neighbours_.capacity());

    for (const auto& elt: s._neighbours_) {
      NodeSet* newneigh = new NodeSet(*elt.second);
      _neighbours_.insert(elt.first, 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());
  }

Here is the call graph for this function:

~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )

virtual

destructor

Definition at line 60 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

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

id	the node whose neighbours[id] is checked

Definition at line 46 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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

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

Definition at line 50 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

    GUM_EMIT2(onEdgeAdded, first, second);
  }

Here is the call graph for this function:

clearEdges()

void gum::EdgeGraphPart::clearEdges ( )

virtual

removes all the edges from the EdgeGraphPart

Reimplemented in gum::CliqueGraph.

Definition at line 66 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

edges()

INLINE const EdgeSet & gum::EdgeGraphPart::edges

(

)

const

returns the set of edges stored within the EdgeGraphPart

Definition at line 38 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return _edges_; }

Here is the call 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

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.

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

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.

emptyEdges()

INLINE bool gum::EdgeGraphPart::emptyEdges

(

)

const

indicates wether the EdgeGraphPart contains any edge

Definition at line 34 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return _edges_.empty(); }

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

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

References gum::Set< Key, Alloc >::emplace().

                                                       {
    if (existsEdge(edge)) {
      // ASSUMING first and second exists in  _neighbours_ (if not, it is an
      // error)
      NodeId id1 = edge.first(), id2 = edge.second();

      _neighbours_[id1]->erase(id2);
      _neighbours_[id2]->erase(id1);
      _edges_.erase(edge);
      GUM_EMIT2(onEdgeDeleted, id1, id2);
    }
  }

Here is the call graph for this function:

eraseNeighbours()

INLINE void gum::EdgeGraphPart::eraseNeighbours

(

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

References gum::Set< Key, Alloc >::emplace().

                                                            {
    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 erase so that you actually use the virtualized
        // edge removal function
        eraseEdge(Edge(*iter, id));
      }
    }
  }

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

References gum::Set< Key, Alloc >::emplace().

{ return _edges_.contains(edge); }

Here is the call 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

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

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

hasUndirectedPath() [1/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	const NodeId	n1,
		const 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 166 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

hasUndirectedPath() [2/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	const NodeId	n1,
		const 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 183 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

hasUndirectedPath() [3/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 203 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

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

f	a function assigning a VAL to any edge

neighbours()

INLINE const NodeSet & gum::EdgeGraphPart::neighbours

(

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

References gum::Set< Key, Alloc >::emplace().

                                                                       {
    _checkNeighbours_(id);
    return *(_neighbours_[id]);
  }

Here is the call graph for this function:

operator!=()

INLINE bool gum::EdgeGraphPart::operator!=

(

const EdgeGraphPart &

p

)

const

tests whether two EdgeGraphParts contain different edges

Parameters

p	the EdgeGraphPart that we compare with this

Definition at line 107 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                    {
    return _edges_ != p._edges_;
  }

Here is the call graph for this function:

operator=()

EdgeGraphPart & gum::EdgeGraphPart::operator=

(

const EdgeGraphPart &

s

)

copy operator

Parameters

s	the EdgeGraphPart to copy

Definition at line 83 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                {
    // avoid self assignment
    if (this != &s) {
      clearEdges();

      _edges_ = s._edges_;

      // copy the set of neighbours
      _neighbours_.resize(s._neighbours_.capacity());

      for (const auto& elt: s._neighbours_) {
        NodeSet* newneigh = new NodeSet(*elt.second);
        _neighbours_.insert(elt.first, newneigh);
      }

      if (onEdgeAdded.hasListener())
        for (const auto& edge: _edges_)
          GUM_EMIT2(onEdgeAdded, edge.first(), edge.second());
    }

    return *this;
  }

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

p	the EdgeGraphPart that we compare with this

Definition at line 103 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                    {
    return _edges_ == p._edges_;
  }

Here is the call graph for this function:

sizeEdges()

INLINE Size gum::EdgeGraphPart::sizeEdges

(

)

const

indicates the number of edges stored within the EdgeGraphPart

Definition at line 36 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return _edges_.size(); }

Here is the call graph for this function:

toString()

std::string gum::EdgeGraphPart::toString

(

)

const

to friendly display the content of the EdgeGraphPart

Definition at line 106 of file edgeGraphPart.cpp.

References gum::Set< Key, Alloc >::emplace().

                                          {
    std::stringstream s;
    bool              first = true;
    s << "{";

    for (const auto& edge: _edges_) {
      if (first)
        first = false;
      else
        s << ",";

      s << edge;
    }

    s << "}";

    return s.str();
  }

Here is the call 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

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

References gum::Set< Key, Alloc >::emplace().

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

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

id	the node whose ingoing arcs will be removed

Definition at line 92 of file edgeGraphPart_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

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

_neighbours_

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

mutableprivate

for each node, the set of its adjacent edges

Definition at line 254 of file edgeGraphPart.h.

onEdgeAdded

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

Definition at line 78 of file edgeGraphPart.h.

onEdgeDeleted

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

Definition at line 79 of file edgeGraphPart.h.

---

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

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