gum::UndiGraph Class Reference

Base class for undirected graphs. More...

#include <undiGraph.h>

Inheritance diagram for gum::UndiGraph:

Collaboration diagram for gum::UndiGraph:

Public Attributes
Signaler1< NodeId >	onNodeAdded
Signaler1< NodeId >	onNodeDeleted
Signaler2< NodeId, NodeId >	onEdgeAdded
Signaler2< NodeId, NodeId >	onEdgeDeleted

Public Member Functions
Constructors / Destructors
	UndiGraph (Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
	default constructor More...
	UndiGraph (const UndiGraph &g)
	copy constructor More...
virtual	~UndiGraph ()
	destructor More...
Operators
UndiGraph &	operator= (const UndiGraph &g)
	copy operator More...
bool	operator== (const UndiGraph &g) const
	tests whether two UndiGraphs are identical (same nodes, same edges) More...
bool	operator!= (const UndiGraph &g) const
	tests whether two UndiGraphs are different More...
Accessors/Modifiers
void	addEdge (NodeId first, NodeId second) override
	insert a new edge into the undirected graph More...
void	eraseNode (NodeId id) override
	remove a node and its adjacent edges from the graph More...
void	clear () override
	removes all the nodes and edges from the graph More...
std::string	toString () const override
	to friendly display the content of the graph More...
virtual std::string	toDot () const
	to friendly display graph in DOT format More...
bool	hasUndirectedCycle () const
	checks whether the graph contains cycles More...
virtual UndiGraph	partialUndiGraph (NodeSet nodes)
	returns the partial graph formed by the nodes given in parameter More...
NodeProperty< NodeId >	nodes2ConnectedComponent () const
	returns a property {node:id of connected component} More...
Operators
bool	operator== (const NodeGraphPart &p) const
	check whether two NodeGraphParts contain the same nodes More...
bool	operator!= (const NodeGraphPart &p) const
	check whether two NodeGraphParts contain different nodes More...
Accessors/Modifiers
void	populateNodes (const NodeGraphPart &s)
	populateNodes clears *this and fills it with the same nodes as "s" More...
template<typename T >
void	populateNodesFromProperty (const NodeProperty< T > &h)
	populateNodesFromProperty clears *this and fills it with the keys of "h" More...
NodeId	nextNodeId () const
	returns a new node id, not yet used by any node More...
virtual NodeId	addNode ()
	insert a new node and return its id More...
std::vector< NodeId >	addNodes (Size n)
	insert n nodes More...
virtual void	addNodeWithId (const NodeId id)
	try to insert a node with the given id More...
bool	existsNode (const NodeId id) const
	returns true iff the NodeGraphPart contains the given nodeId More...
bool	exists (const NodeId id) const
	alias for existsNode More...
bool	emptyNodes () const
	indicates whether there exists nodes in the NodeGraphPart More...
bool	empty () const
	alias for emptyNodes More...
virtual void	clearNodes ()
	remove all the nodes from the NodeGraphPart More...
Size	sizeNodes () const
	returns the number of nodes in the NodeGraphPart More...
Size	size () const
	alias for sizeNodes More...
NodeId	bound () const
	returns a number n such that all node ids are strictly lower than n More...
NodeSet	asNodeSet () const
	returns a copy of the set of nodes represented by the NodeGraphPart More...
const NodeGraphPart &	nodes () const
	return *this as a NodeGraphPart More...
node_iterator_safe	beginSafe () const
	a begin iterator to parse the set of nodes contained in the NodeGraphPart More...
const node_iterator_safe &	endSafe () const noexcept
	the end iterator to parse the set of nodes contained in the NodeGraphPart More...
node_iterator	begin () const noexcept
	a begin iterator to parse the set of nodes contained in the NodeGraphPart More...
const node_iterator &	end () const noexcept
	the end iterator to parse the set of nodes contained in the NodeGraphPart More...
template<typename VAL >
NodeProperty< VAL >	nodesProperty (VAL(*f)(const NodeId &), Size size=0) const
	a method to create a HashTable with key:NodeId and value:VAL More...
template<typename VAL >
NodeProperty< VAL >	nodesProperty (const VAL &a, Size size=0) const
	a method to create a hashMap with key:NodeId and value:VAL More...
template<typename VAL >
List< VAL >	listMapNodes (VAL(*f)(const NodeId &)) const
	a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x)) More...
Operators
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	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...
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 NodeGraphPartIterator	NodeIterator
typedef NodeGraphPartIterator	NodeConstIterator
typedef NodeGraphPartIteratorSafe	NodeIteratorSafe
typedef NodeGraphPartIteratorSafe	NodeConstIteratorSafe
typedef EdgeSetIterator	EdgeIterator
using	node_iterator = NodeGraphPartIterator
	types for STL compliance More...
using	node_const_iterator = NodeGraphPartIterator
	types for STL compliance More...
using	node_iterator_safe = NodeGraphPartIteratorSafe
	types for STL compliance More...
using	node_const_iterator_safe = NodeGraphPartIteratorSafe
	types for STL compliance More...

Detailed Description

Base class for undirected graphs.

This is the base class for graphs containing undirected edges (so-called edges).

Usage example:

// creating empty graphs
UndiGraph g1,g2;

// adding nodes and edges to g1
NodeId i1=g1.addNode();
NodeId i2=g1.addNode();
NodeId i3=g1.addNode();
g1.addEdge( i1,i2 );
g1.addEdge( i1,i3 );
g1.addEdge( i2,i3 );

//throw an InvalidNode
// g1.addEdge( i1+i2+i3,i1 );

// copying graphs
UndiGraph g3 = g1;
g2 = g1;
UndiGraph g4=g1;

// check if a graph has no node
if ( g1.empty() ) cerr << "graph g1 is empty" << endl;

// remove all the nodes (as well as their adjacent edges)
g1.clear();

// remove some edge
g4.eraseEdge( Edge ( i1,i3 ) );

// remove node
g2.eraseNode( i2 );

// parse a graph
for ( const auto node : g3.nodes() )
  cerr << node << endl;

for ( const auto& edge : g3.edges())
  cerr << edge << endl;

const EdgeSet& a=g3.neighbours( 3 );
for ( const auto& edge : a)
  cerr << "  -  "<<edge;

cerr<<endl;

// remove all the edges that are adjacent to a given node
g3.eraseNeighbours( 2 );

Definition at line 108 of file undiGraph.h.

Member Typedef Documentation

EdgeIterator

typedef EdgeSetIterator gum::EdgeGraphPart::EdgeIterator

inherited

Definition at line 76 of file edgeGraphPart.h.

node_const_iterator

using gum::NodeGraphPart::node_const_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 258 of file nodeGraphPart.h.

node_const_iterator_safe

using gum::NodeGraphPart::node_const_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 260 of file nodeGraphPart.h.

node_iterator

using gum::NodeGraphPart::node_iterator = NodeGraphPartIterator

inherited

types for STL compliance

Definition at line 257 of file nodeGraphPart.h.

node_iterator_safe

using gum::NodeGraphPart::node_iterator_safe = NodeGraphPartIteratorSafe

inherited

types for STL compliance

Definition at line 259 of file nodeGraphPart.h.

NodeConstIterator

typedef NodeGraphPartIterator gum::NodeGraphPart::NodeConstIterator

inherited

Definition at line 267 of file nodeGraphPart.h.

NodeConstIteratorSafe

typedef NodeGraphPartIteratorSafe gum::NodeGraphPart::NodeConstIteratorSafe

inherited

Definition at line 269 of file nodeGraphPart.h.

NodeIterator

typedef NodeGraphPartIterator gum::NodeGraphPart::NodeIterator

inherited

Definition at line 266 of file nodeGraphPart.h.

NodeIteratorSafe

typedef NodeGraphPartIteratorSafe gum::NodeGraphPart::NodeIteratorSafe

inherited

Definition at line 268 of file nodeGraphPart.h.

Constructor & Destructor Documentation

UndiGraph() [1/2]

gum::UndiGraph::UndiGraph ( Size  nodes_size = HashTableConst::default_size, bool  nodes_resize_policy = true, Size  edges_size = HashTableConst::default_size, bool  edges_resize_policy = true  )

explicit

default constructor

Parameters

nodes_size	the size of the hash table used to store all the nodes
nodes_resize_policy	the resizing policy of this hash table
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 39 of file undiGraph.cpp.

                                                 :
      NodeGraphPart(nodes_size, nodes_resize_policy),
      EdgeGraphPart(edges_size, edges_resize_policy) {
    GUM_CONSTRUCTOR(UndiGraph);
  }

UndiGraph() [2/2]

gum::UndiGraph::UndiGraph

(

const UndiGraph &

g

)

copy constructor

Parameters

g	the UndiGraph to copy

Definition at line 48 of file undiGraph.cpp.

                                         : NodeGraphPart(g), EdgeGraphPart(g) {
    GUM_CONS_CPY(UndiGraph);
  }

~UndiGraph()

gum::UndiGraph::~UndiGraph ( )

virtual

destructor

Definition at line 52 of file undiGraph.cpp.

                        {
    GUM_DESTRUCTOR(UndiGraph);
    ;
  }

Member Function Documentation

addEdge()

INLINE void gum::UndiGraph::addEdge ( NodeId  first, NodeId  second  )

overridevirtual

insert a new edge into the undirected graph

The order in which the extremal nodes are specified is not important.

Parameters

first	the id of one extremal node of the new inserted edge
second	the id of the other extremal node of the new inserted edge

Warning

if the edge already exists, nothing is done. In particular, no exception is raised.

Exceptions

InvalidNode

if first and/or second do not belong to the graph nodes

Reimplemented from gum::EdgeGraphPart.

Definition at line 34 of file undiGraph_inl.h.

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

                                                                        {
    if (!exists(first)) { GUM_ERROR(InvalidNode, "Node (" << first << ") does not exist.") }

    if (!exists(second)) { GUM_ERROR(InvalidNode, "Node (" << second << ") does not exist.") }

    EdgeGraphPart::addEdge(second, first);
  }

Here is the call graph for this function:

addNode()

INLINE NodeId gum::NodeGraphPart::addNode ( )

virtualinherited

insert a new node and return its id

Returns

the id chosen by the internal idFactory

Reimplemented in gum::CliqueGraph.

Definition at line 238 of file nodeGraphPart_inl.h.

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

                                       {
    NodeId newNode;

    // fill the first hole if holes exist
    if (_holes_ && (!_holes_->empty())) {
      newNode = *(_holes_->begin());
      _eraseHole_(newNode);
    } else {
      newNode = _boundVal_;
      ++_boundVal_;
      _updateEndIteratorSafe_();
    }

    GUM_EMIT1(onNodeAdded, newNode);

    return newNode;
  }

Here is the call graph for this function:

addNodes()

INLINE std::vector< NodeId > gum::NodeGraphPart::addNodes ( Size  n )

inherited

insert n nodes

Parameters

n	the number of nodes to add

Returns

the vector of chosen ids

Definition at line 256 of file nodeGraphPart_inl.h.

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

                                                           {
    std::vector< NodeId > v;
    v.reserve(N);
    for (Idx i = 0; i < N; i++)
      v.push_back(this->addNode());
    return v;
  }

Here is the call graph for this function:

addNodeWithId()

void gum::NodeGraphPart::addNodeWithId ( const NodeId  id )

virtualinherited

try to insert a node with the given id

Warning

This method should be carefully used. Please prefer populateNodes or populateNodesFromProperty when possible

Exceptions

DuplicateElement

exception if the id already exists

Definition at line 131 of file nodeGraphPart.cpp.

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

                                                   {
    if (id >= _boundVal_) {
      if (id > _boundVal_) {   // we have to add holes
        if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);

        for (NodeId i = _boundVal_; i < id; ++i)
          _holes_->insert(i);
      }

      _boundVal_ = id + 1;

      _updateEndIteratorSafe_();
    } else {
      if (_inHoles_(id)) {   // we fill a hole
        _eraseHole_(id);
      } else {
        GUM_ERROR(DuplicateElement, "Id " << id << " is already used")
      }
    }

    GUM_EMIT1(onNodeAdded, id);
  }

Here is the call graph for this function:

asNodeSet()

INLINE NodeSet gum::NodeGraphPart::asNodeSet ( ) const

inherited

returns a copy of the set of nodes represented by the NodeGraphPart

Warning

this function is o(n) where n is the number of nodes. In space and in time. Usually, when you need to parse the nodes of a NodeGraphPart, prefer using

for(const auto n : nodes()) 

rather than

for(const auto n : asNodeSet()) 

as this is faster and consumes much less memory.

Definition at line 340 of file nodeGraphPart_inl.h.

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

                                                {
    NodeSet son(sizeNodes());

    if (!empty()) {
      for (NodeId n = 0; n < _boundVal_; ++n) {
        if (!_inHoles_(n)) son.insert(n);
      }
    }

    return son;
  }

Here is the call graph for this function:

begin()

INLINE NodeGraphPartIterator gum::NodeGraphPart::begin ( ) const

noexceptinherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 314 of file nodeGraphPart_inl.h.

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

                                                                   {
    NodeGraphPartIterator it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

Here is the call graph for this function:

beginSafe()

INLINE NodeGraphPartIteratorSafe gum::NodeGraphPart::beginSafe ( ) const

inherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 302 of file nodeGraphPart_inl.h.

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

                                                                  {
    NodeGraphPartIteratorSafe it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

Here is the call graph for this function:

bound()

INLINE NodeId gum::NodeGraphPart::bound ( ) const

inherited

returns a number n such that all node ids are strictly lower than n

Definition at line 291 of file nodeGraphPart_inl.h.

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

{ return _boundVal_; }

Here is the call graph for this function:

clear()

INLINE void gum::UndiGraph::clear ( )

overridevirtual

removes all the nodes and edges from the graph

Reimplemented from gum::NodeGraphPart.

Definition at line 42 of file undiGraph_inl.h.

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

                               {
    EdgeGraphPart::clearEdges();
    NodeGraphPart::clearNodes();
  }

Here is the call graph for this function:

clearEdges()

void gum::EdgeGraphPart::clearEdges ( )

virtualinherited

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:

clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )

virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 293 of file nodeGraphPart_inl.h.

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

{ _clearNodes_(); }

Here is the call graph for this function:

edges()

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

inherited

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

inherited

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

inherited

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.

empty()

INLINE bool gum::NodeGraphPart::empty ( ) const

inherited

alias for emptyNodes

Definition at line 289 of file nodeGraphPart_inl.h.

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

{ return emptyNodes(); }

Here is the call graph for this function:

emptyEdges()

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

inherited

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:

emptyNodes()

INLINE bool gum::NodeGraphPart::emptyNodes ( ) const

inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 287 of file nodeGraphPart_inl.h.

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

{ return (sizeNodes() == 0); }

Here is the call graph for this function:

end()

INLINE const NodeGraphPartIterator & gum::NodeGraphPart::end ( ) const

noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 320 of file nodeGraphPart_inl.h.

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

                                                                        {
    return _endIteratorSafe_;
  }

Here is the call graph for this function:

endSafe()

INLINE const NodeGraphPartIteratorSafe & gum::NodeGraphPart::endSafe ( ) const

noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 310 of file nodeGraphPart_inl.h.

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

                                                                                {
    return _endIteratorSafe_;
  }

Here is the call graph for this function:

eraseEdge()

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

virtualinherited

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 )

inherited

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:

eraseNode()

INLINE void gum::UndiGraph::eraseNode ( NodeId  id )

overridevirtual

remove a node and its adjacent edges from the graph

Parameters

id	the id of the node to be removed

Warning

if the node does not exist, nothing is done. In particular, no exception is raised.

Reimplemented from gum::NodeGraphPart.

Definition at line 57 of file undiGraph_inl.h.

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

                                                  {
    // warning: to remove the edges adjacent to id, use the unvirtualized
    // versions
    // of edge removals
    EdgeGraphPart::unvirtualizedEraseNeighbours(id);
    NodeGraphPart::eraseNode(id);
  }

Here is the call graph for this function:

exists()

INLINE bool gum::NodeGraphPart::exists ( const NodeId  id ) const

inherited

alias for existsNode

Definition at line 277 of file nodeGraphPart_inl.h.

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

{ return existsNode(node); }

Here is the call graph for this function:

existsEdge() [1/2]

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

inherited

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

inherited

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:

existsNode()

INLINE bool gum::NodeGraphPart::existsNode ( const NodeId  id ) const

inherited

returns true iff the NodeGraphPart contains the given nodeId

Definition at line 271 of file nodeGraphPart_inl.h.

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

                                                               {
    if (node >= _boundVal_) return false;

    return (!_inHoles_(node));
  }

Here is the call graph for this function:

hasUndirectedCycle()

bool gum::UndiGraph::hasUndirectedCycle

(

)

const

checks whether the graph contains cycles

Definition at line 57 of file undiGraph.cpp.

                                           {
    List< std::pair< NodeId, NodeId > > open_nodes;
    NodeProperty< bool >                examined_nodes = nodesProperty(false);
    std::pair< NodeId, NodeId >         thePair;
    NodeId                              current, from_current;

    for (const auto node: nodes()) {
      // check if the node has already been examined (if this is not the case,
      // this means that we are on a new connected component)
      if (!examined_nodes[node]) {
        // indicates that we are examining a new node
        examined_nodes[node] = true;

        // check recursively all the nodes of node's connected component
        thePair.first  = node;
        thePair.second = node;
        open_nodes.insert(thePair);

        while (!open_nodes.empty()) {
          // get a node to propagate
          thePair = open_nodes.front();
          open_nodes.popFront();

          current      = thePair.first;
          from_current = thePair.second;

          // check the neighbours
          for (const auto new_node: neighbours(current))

            // avoid to check the node we are coming from
            if (new_node != from_current) {
              if (examined_nodes[new_node])
                return true;
              else {
                examined_nodes[new_node] = true;
                thePair.first            = new_node;
                thePair.second           = current;
                open_nodes.insert(thePair);
              }
            }
        }
      }
    }

    return false;
  }

hasUndirectedPath() [1/3]

bool gum::EdgeGraphPart::hasUndirectedPath ( const NodeId  n1, const NodeId  n2  ) const

inherited

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

inherited

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

inherited

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

inherited

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

listMapNodes()

template<typename VAL >

List< VAL > gum::NodeGraphPart::listMapNodes ( VAL(*)(const NodeId &)  f ) const

inherited

a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))

Parameters

f	a function assigning a VAL to any node

neighbours()

INLINE const NodeSet & gum::EdgeGraphPart::neighbours ( const NodeId  id ) const

inherited

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:

nextNodeId()

INLINE NodeId gum::NodeGraphPart::nextNodeId ( ) const

inherited

returns a new node id, not yet used by any node

Warning

a code like

id=nextNodeId();addNode(id); 

is basically not thread safe !!

Returns

a node id not yet used by any node within the NodeGraphPart

Definition at line 211 of file nodeGraphPart_inl.h.

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

                                                {
    NodeId next = 0;

    // return the first hole if holes exist
    if (_holes_ && (!_holes_->empty()))
      next = *(_holes_->begin());
    else   // in other case
      next = _boundVal_;

    return next;
  }

Here is the call graph for this function:

nodes()

INLINE const NodeGraphPart & gum::NodeGraphPart::nodes ( ) const

inherited

return *this as a NodeGraphPart

Definition at line 352 of file nodeGraphPart_inl.h.

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

                                                         {
    return *(static_cast< const NodeGraphPart* >(this));
  }

Here is the call graph for this function:

nodes2ConnectedComponent()

NodeProperty< NodeId > gum::UndiGraph::nodes2ConnectedComponent

(

)

const

returns a property {node:id of connected component}

Definition at line 152 of file undiGraph.cpp.

                                                                   {
    NodeProperty< NodeId > res;

    NodeId numCC = 0;
    for (const auto node: nodes()) {
      if (res.exists(node)) continue;
      NodeSet nodes{node};
      while (!nodes.empty()) {
        auto actual = *(nodes.begin());
        nodes.erase(actual);
        res.insert(actual, numCC);
        for (const auto nei: neighbours(actual)) {
          if (!res.exists(nei))
            if (!nodes.exists(nei)) nodes.insert(nei);
        }
      }
      numCC += 1;
    }

    return res;
  }

nodesProperty() [1/2]

template<typename VAL >

NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( VAL(*)(const NodeId &)  f, Size  size = 0  ) const

inherited

a method to create a HashTable with key:NodeId and value:VAL

VAL are computed from the nodes using for all node x, VAL f(x). This method is a wrapper of the same method in HashTable.

See also

HashTable::map.

Parameters

f	a function assigning a VAL to any node
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 nodes. If you do not specify this parameter, the method will assign it for you.

nodesProperty() [2/2]

template<typename VAL >

NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( const VAL &  a, Size  size = 0  ) const

inherited

a method to create a hashMap with key:NodeId and value:VAL

for all nodes, the value stored is a. This method is a wrapper of the same method in HashTable.

See also

HashTable::map.

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 nodes. If you do not specify this parameter, the method will assign it for you.

operator!=() [1/3]

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

inherited

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!=() [2/3]

INLINE bool gum::UndiGraph::operator!=

(

const UndiGraph &

g

)

const

tests whether two UndiGraphs are different

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 69 of file undiGraph_inl.h.

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

{ return !operator==(p); }

Here is the call graph for this function:

operator!=() [3/3]

INLINE bool gum::NodeGraphPart::operator!= ( const NodeGraphPart &  p ) const

inherited

check whether two NodeGraphParts contain different nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 338 of file nodeGraphPart_inl.h.

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

{ return !operator==(p); }

Here is the call graph for this function:

operator=()

INLINE UndiGraph & gum::UndiGraph::operator=

(

const UndiGraph &

g

)

copy operator

Parameters

g	the DiGraph to copy

Definition at line 47 of file undiGraph_inl.h.

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

                                                           {
    if (this != &g) {
      UndiGraph::clear();
      NodeGraphPart::operator=(g);
      EdgeGraphPart::operator=(g);
    }

    return *this;
  }

Here is the call graph for this function:

operator==() [1/3]

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

inherited

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:

operator==() [2/3]

INLINE bool gum::UndiGraph::operator==

(

const UndiGraph &

g

)

const

tests whether two UndiGraphs are identical (same nodes, same edges)

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 65 of file undiGraph_inl.h.

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

                                                            {
    return EdgeGraphPart::operator==(p) && NodeGraphPart::operator==(p);
  }

Here is the call graph for this function:

operator==() [3/3]

INLINE bool gum::NodeGraphPart::operator== ( const NodeGraphPart &  p ) const

inherited

check whether two NodeGraphParts contain the same nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 324 of file nodeGraphPart_inl.h.

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

                                                                    {
    if (_boundVal_ != p._boundVal_) return false;

    if (_holes_)
      if (p._holes_)
        return (*_holes_ == *p._holes_);
      else
        return false;
    else if (p._holes_)
      return false;

    return true;
  }

Here is the call graph for this function:

partialUndiGraph()

UndiGraph gum::UndiGraph::partialUndiGraph ( NodeSet  nodes )

virtual

returns the partial graph formed by the nodes given in parameter

Definition at line 139 of file undiGraph.cpp.

                                                     {
    UndiGraph partialGraph;

    for (const auto node: nodes) {
      partialGraph.addNodeWithId(node);

      for (const auto nei: neighbours(node))
        if (nodes.contains(nei) && partialGraph.existsNode(nei)) partialGraph.addEdge(node, nei);
    }

    return partialGraph;
  }

populateNodes()

void gum::NodeGraphPart::populateNodes ( const NodeGraphPart &  s )

inherited

populateNodes clears *this and fills it with the same nodes as "s"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

Parameters

s	the NodeGraphPart to be copied

Definition at line 63 of file nodeGraphPart.cpp.

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

                                                          {
    clear();   // "virtual" flush of the nodes set
    _holes_size_          = s._holes_size_;
    _holes_resize_policy_ = s._holes_resize_policy_;

    if (s._holes_) _holes_ = new NodeSet(*s._holes_);

    _boundVal_ = s._boundVal_;

    _updateEndIteratorSafe_();
  }

Here is the call graph for this function:

populateNodesFromProperty()

template<typename T >

void gum::NodeGraphPart::populateNodesFromProperty ( const NodeProperty< T > &  h )

inherited

populateNodesFromProperty clears *this and fills it with the keys of "h"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

size()

INLINE Size gum::NodeGraphPart::size ( ) const

inherited

alias for sizeNodes

Definition at line 269 of file nodeGraphPart_inl.h.

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

{ return sizeNodes(); }

Here is the call graph for this function:

sizeEdges()

INLINE Size gum::EdgeGraphPart::sizeEdges ( ) const

inherited

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:

sizeNodes()

INLINE Size gum::NodeGraphPart::sizeNodes ( ) const

inherited

returns the number of nodes in the NodeGraphPart

Definition at line 265 of file nodeGraphPart_inl.h.

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

                                             {
    return (_holes_) ? (_boundVal_ - _holes_->size()) : _boundVal_;
  }

Here is the call graph for this function:

toDot()

std::string gum::UndiGraph::toDot ( ) const

virtual

to friendly display graph in DOT format

Reimplemented in gum::CliqueGraph, and gum::MixedGraph.

Definition at line 111 of file undiGraph.cpp.

                                   {
    std::stringstream output;
    std::stringstream nodeStream;
    std::stringstream edgeStream;
    List< NodeId >    treatedNodes;
    output << "digraph \""
           << "no_name\" {" << std::endl
           << "edge [dir=none]" << std::endl;
    nodeStream << "node [shape = ellipse];" << std::endl;
    std::string tab = "  ";

    for (const auto node: nodes()) {
      nodeStream << tab << node << ";";

      if (neighbours(node).size() > 0)
        for (const auto nei: neighbours(node))
          if (!treatedNodes.exists(nei))
            edgeStream << tab << node << " -> " << nei << ";" << std::endl;

      treatedNodes.insert(node);
    }

    output << nodeStream.str() << std::endl << edgeStream.str() << std::endl << "}" << std::endl;

    return output.str();
  }

toString()

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

overridevirtual

to friendly display the content of the graph

Reimplemented from gum::NodeGraphPart.

Definition at line 104 of file undiGraph.cpp.

                                      {
    std::string s = NodeGraphPart::toString();
    s += " , ";
    s += EdgeGraphPart::toString();
    return s;
  }

undirectedPath()

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

inherited

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 )

inherited

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

onEdgeAdded

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

inherited

Definition at line 78 of file edgeGraphPart.h.

onEdgeDeleted

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

inherited

Definition at line 79 of file edgeGraphPart.h.

onNodeAdded

Signaler1< NodeId > gum::NodeGraphPart::onNodeAdded

inherited

Definition at line 271 of file nodeGraphPart.h.

onNodeDeleted

Signaler1< NodeId > gum::NodeGraphPart::onNodeDeleted

inherited

Definition at line 272 of file nodeGraphPart.h.

---

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

• agrum/tools/graphs/undiGraph.h
• agrum/tools/graphs/undiGraph.cpp
• agrum/tools/graphs/undiGraph_inl.h