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 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< NodeId >	undirectedPath (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

typedef EdgeSetIterator gum::EdgeGraphPart::EdgeIterator

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

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

EdgeGraphPart() [2/2]

gum::EdgeGraphPart::EdgeGraphPart

(

const EdgeGraphPart &

s

)

copy constructor

Parameters

s	the EdgeGraphPart to copy

Definition at line 41 of file edgeGraphPart.cpp.

References __edges, __neighbours, GUM_EMIT2, and onEdgeAdded.

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

~EdgeGraphPart()

gum::EdgeGraphPart::~EdgeGraphPart ( )

virtual

destructor

Definition at line 58 of file edgeGraphPart.cpp.

References clearEdges().

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

References __neighbours.

Referenced by addEdge(), and neighbours().

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

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

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

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

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

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

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

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

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(), and gum::SpanningForestPrim::edgesInSpanningForest().

{ return __edges; }

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

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.

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

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

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

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

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

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

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

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

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

                                                              {
    return __edges.contains(edge);
  }

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

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

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

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

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

                                                                       {
    __checkNeighbours(id);
    return *(__neighbours[id]);
  }

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

p	the EdgeGraphPart that we compare with this

Definition at line 108 of file edgeGraphPart_inl.h.

References __edges.

                                                                    {
    return __edges != p.__edges;
  }

operator=()

EdgeGraphPart & gum::EdgeGraphPart::operator=

(

const EdgeGraphPart &

s

)

copy operator

Parameters

s	the 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=().

                                                                {
    // 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:

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

References __edges.

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

                                                                    {
    return __edges == p.__edges;
  }

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

{ return __edges.size(); }

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

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

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

                                                                         {
    // 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 93 of file edgeGraphPart_inl.h.

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

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

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

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:

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