gum::prm::gspan::Pattern Class Reference

This contains all the information we want for a node in a DFSTree. More...

#include <agrum/PRM/gspan/pattern.h>

Inheritance diagram for gum::prm::gspan::Pattern:

Collaboration diagram for gum::prm::gspan::Pattern:

Public Member Functions
Constructor and destructor.
	Pattern ()
	Default constructor. More...
	Pattern (const Pattern &source)
	Copy constructor. More...
	~Pattern ()
	Destructor. More...
Graphical getters and setters.
NodeId	addNodeWithLabel (LabelData &l)
	Insert a node with the given LabelData. More...
LabelData &	label (NodeId node)
	Returns the LabelData assigned to node. More...
const LabelData &	label (NodeId node) const
	Returns the LabelData assigned to node. More...
LabelData &	label (NodeId i, NodeId j)
	Returns the LabelData assigned to arc. More...
const LabelData &	label (NodeId i, NodeId j) const
	Returns the LabelData assigned to arc. More...
LabelData &	label (const Arc &arc)
	Returns the LabelData assigned to arc. More...
const LabelData &	label (const Arc &arc) const
	Returns the LabelData assigned to arc. More...
LabelData &	lastAdded ()
	Insert a node with the given LabelData. More...
const LabelData &	lastAdded () const
	Insert a node with the given LabelData. More...
void	addArc (NodeId i, NodeId j, LabelData &l)
	Add an arc to this Pattern. More...
bool	exists (NodeId id) const
	Returns true if id is a node in this Pattern. More...
bool	exists (NodeId tail, NodeId head) const
	Returns true if (tail, head) is an arc in this Pattern. More...
Size	size () const
	Returns the number of nodes in this Pattern. More...
Size	sizeArcs () const
	Returns the number of arcs in this Pattern. More...
void	rightmostPath (std::list< NodeId > &r_path) const
	Fill r_path with the rightmost path of this Pattern. The list is supposed empty. More...
std::string	toDot (size_t name) const
	Print the pattern in the DOT syntax. More...
Access to topology
const NodeGraphPart &	nodes () const
const ArcSet &	arcs () const
DFSCode related methods.
DFSCode &	code ()
	Returns the DFSCode of this Pattern. More...
const DFSCode &	code () const
	Returns the DFSCode of this Pattern. More...
EdgeCode &	edgeCode (NodeId tail, NodeId head)
	Returns the EdgeCode of an edge of this Pattern. More...
EdgeCode &	edgeCode (const Arc &arc)
	Returns the EdgeCode of an edge of this Pattern. More...
const EdgeCode &	edgeCode (NodeId tail, NodeId head) const
	Returns the EdgeCode of an edge of this Pattern. More...
const EdgeCode &	edgeCode (const Arc &arc) const
	Returns the EdgeCode of an edge of this Pattern. More...
void	pop_back ()
	Remove the last EdgeCode of this pattern. More...
void	remove (NodeId node)
	Remove a node if it has no neighbors, raise an OperationNotAllowed otherwise. More...
bool	isMinimal ()
	Returns the DFSCode of this Pattern. More...

Detailed Description

This contains all the information we want for a node in a DFSTree.

Several rules are used regarding nodes in Pattern::graph. First nodes are added respecting a depth-first search, thus each node is labelled from 1 to n, where n is the number of nodes in Pattern::graph.

Given two nodes id i and j, if i < j then i was discovered before j in the depth first search.

To retrieve the depth first search tree from Pattern::graph simple consider only arcs (u, v) with u < v. The set of arcs { (u,v) | u < v} is called the forward edge set and the set of arcs { (u,v) | u > v} is called the backward edge set.

The orientation in Pattern::graph is only used to differentiate forward edges from backward edges.

Definition at line 72 of file pattern.h.

Member Typedef Documentation

ArcIterator

typedef ArcSetIterator gum::ArcGraphPart::ArcIterator

inherited

Definition at line 80 of file arcGraphPart.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

Pattern() [1/2]

INLINE gum::prm::gspan::Pattern::Pattern

(

)

Default constructor.

Definition at line 34 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

: DiGraph(), last__(0) { GUM_CONSTRUCTOR(Pattern); }

Here is the call graph for this function:

Pattern() [2/2]

gum::prm::gspan::Pattern::Pattern

(

const Pattern &

source

)

Copy constructor.

Definition at line 39 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                                            : DiGraph(), last__(0) {
        GUM_CONS_CPY(Pattern);
        NodeProperty< NodeId > node_map;

        for (NodeId node = 1; node <= source.size(); ++node) {
          node_map.insert(
             node,
             addNodeWithLabel(const_cast< LabelData& >(source.label(node))));
        }

        for (const auto& edge: source.code().codes)
          addArc(node_map[edge->i],
                 node_map[edge->j],
                 const_cast< LabelData& >(
                    source.label(node_map[edge->i], node_map[edge->j])));
      }

Here is the call graph for this function:

~Pattern()

INLINE gum::prm::gspan::Pattern::~Pattern

(

)

Destructor.

Definition at line 37 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ GUM_DESTRUCTOR(Pattern); }

Here is the call graph for this function:

Member Function Documentation

addArc() [1/2]

INLINE void gum::prm::gspan::Pattern::addArc	(	NodeId	i,
		NodeId	j,
		LabelData &	l
	)

Add an arc to this Pattern.

This create an EdgeCode and check if it respects neighborhood restriction, if not an exception is raised.

Parameters

i	The DFS subscript of the first node in the code.
j	The DFS subscript of the second node in the code.
l	The label data of the added edge.

Exceptions

OperationNotAllowed

Raised if the neighborhood restriction is not respected.

Definition at line 117 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                           {
        if (!(DiGraph::exists(i) && DiGraph::exists(j))) {
          GUM_ERROR(NotFound, "node not found in this pattern");
        }

        EdgeCode* edge
           = new EdgeCode(i, j, node_map__[i]->id, l.id, node_map__[j]->id);

        if ((code().codes.size() == 0)
            || (DFSCode::validNeighbors(code().codes.back(), edge))) {
          DiGraph::addArc(i, j);
          arc_map__.insert(Arc(i, j), std::make_pair(&l, edge));
          code().codes.push_back(edge);
        } else {
          delete edge;
          GUM_ERROR(OperationNotAllowed,
                    "illegal arc considering neighborhood restriction");
        }
      }

Here is the call graph for this function:

addArc() [2/2]

INLINE void gum::DiGraph::addArc ( const NodeId  tail, const NodeId  head  )

virtualinherited

insert a new arc into the directed graph

Parameters

tail	the id of the tail of the new inserted arc
head	the id of the head of the new inserted arc

Warning

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

Exceptions

InvalidNode

if head or tail does not belong to the graph nodes

Reimplemented from gum::ArcGraphPart.

Reimplemented in gum::DAG.

Definition at line 34 of file diGraph_inl.h.

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

                                                                  {
    if (!exists(head)) { GUM_ERROR(InvalidNode, "no head node : " << head); }

    if (!exists(tail)) { GUM_ERROR(InvalidNode, "no tail node : " << tail); }

    ArcGraphPart::addArc(tail, head);
  }

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 252 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 270 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:

addNodeWithLabel()

INLINE NodeId gum::prm::gspan::Pattern::addNodeWithLabel

(

LabelData &

l

)

Insert a node with the given LabelData.

Returns

The id assigned to the inserted node.

Definition at line 40 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                   {
        NodeId n = NodeId(size() + 1);
        DiGraph::addNodeWithId(n);
        node_map__.insert(n, &l);
        last__ = &l;
        return n;
      }

Here is the call graph for this function:

ancestors()

NodeSet gum::ArcGraphPart::ancestors ( NodeId  id ) const

inherited

returns the set of nodes with directed path ingoing to a given node

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is ingoing to the given node.

Parameters

id	the node which is the head of a directed path with the returned nodes

Definition at line 172 of file arcGraphPart.cpp.

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

                                                 {
    NodeSet res;
    NodeSet tmp;
    for (auto next: parents(id))
      tmp.insert(next);

    while (!tmp.empty()) {
      auto current = *(tmp.begin());
      tmp.erase(current);
      res.insert(current);
      for (auto next: parents(current)) {
        if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
      }
    }
    return res;
  }

Here is the call graph for this function:

arcs()

INLINE const ArcSet & gum::prm::gspan::Pattern::arcs

(

)

const

Definition at line 169 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return DiGraph::arcs(); }

Here is the call graph for this function:

arcsProperty() [1/2]

template<typename VAL >

ArcProperty< VAL > gum::ArcGraphPart::arcsProperty ( VAL(*)(const Arc &)  f, Size  size = 0  ) const

inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Parameters

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

arcsProperty() [2/2]

template<typename VAL >

ArcProperty< VAL > gum::ArcGraphPart::arcsProperty ( const VAL &  a, Size  size = 0  ) const

inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL a)

Parameters

a	the default value assigned to each arc 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 arcs. If you do not specify this parameter, the method will assign it for you.

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 360 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 332 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 318 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 307 of file nodeGraphPart_inl.h.

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

{ return boundVal__; }

Here is the call graph for this function:

children() [1/2]

INLINE NodeSet gum::ArcGraphPart::children ( const NodeSet &  ids ) const

inherited

returns the set of children of a set of nodes

Definition at line 68 of file arcGraphPart_inl.h.

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

                                                                {
    NodeSet res;
    for (const auto node: ids)
      res += children(node);
    return res;
  }

Here is the call graph for this function:

children() [2/2]

INLINE const NodeSet & gum::ArcGraphPart::children ( NodeId  id ) const

inherited

returns the set of nodes with arc outgoing from a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is outgoing from the given node.

Parameters

id	the node which is the tail of the arcs returned

Definition at line 91 of file arcGraphPart_inl.h.

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

                                                              {
    checkChildren__(id);
    return *(children__[id]);
  }

Here is the call graph for this function:

clear()

INLINE void gum::DiGraph::clear ( )

virtualinherited

removes all the nodes and arcs from the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 42 of file diGraph_inl.h.

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

                             {
    ArcGraphPart::clearArcs();
    NodeGraphPart::clearNodes();
  }

Here is the call graph for this function:

clearArcs()

void gum::ArcGraphPart::clearArcs ( )

inherited

removes all the arcs from the ArcGraphPart

Definition at line 78 of file arcGraphPart.cpp.

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

                               {
    for (const auto& elt: parents__)
      delete elt.second;

    parents__.clear();

    for (const auto& elt: children__)
      delete elt.second;

    children__.clear();

    // we need this copy only if at least one onArcDeleted listener exists
    if (onArcDeleted.hasListener()) {
      ArcSet tmp = arcs__;
      arcs__.clear();

      for (const auto& arc: tmp)
        GUM_EMIT2(onArcDeleted, arc.tail(), arc.head());
    } else {
      arcs__.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 309 of file nodeGraphPart_inl.h.

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

{ clearNodes__(); }

Here is the call graph for this function:

code() [1/2]

INLINE DFSCode & gum::prm::gspan::Pattern::code

(

)

Returns the DFSCode of this Pattern.

Definition at line 172 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return code__; }

Here is the call graph for this function:

code() [2/2]

INLINE const DFSCode & gum::prm::gspan::Pattern::code

(

)

const

Returns the DFSCode of this Pattern.

Definition at line 175 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return code__; }

Here is the call graph for this function:

descendants()

NodeSet gum::ArcGraphPart::descendants ( NodeId  id ) const

inherited

returns the set of nodes with directed path outgoing from a given node

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is outgoing from the given node.

Parameters

id	the node which is the tail of a directed path with the returned nodes

Definition at line 154 of file arcGraphPart.cpp.

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

                                                   {
    NodeSet res;
    NodeSet tmp;
    for (auto next: children(id))
      tmp.insert(next);

    while (!tmp.empty()) {
      auto current = *(tmp.begin());
      tmp.erase(current);
      res.insert(current);
      for (auto next: children(current)) {
        if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
      }
    }
    return res;
  }

Here is the call graph for this function:

directedPath()

std::vector< NodeId > gum::ArcGraphPart::directedPath ( NodeId  node1, NodeId  node2  ) const

inherited

returns a directed path from node1 to node2 belonging to the set of arcs

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 190 of file arcGraphPart.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] = successor 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 parents

      for (const auto new_one: parents(current)) {
        if (mark.exists(new_one))   // if this node is already marked, do not
          continue;                 // check it again

        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:

directedUnorientedPath()

std::vector< NodeId > gum::ArcGraphPart::directedUnorientedPath ( NodeId  node1, NodeId  node2  ) const

inherited

returns an unoriented (directed) path from node1 to node2 in the arc 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 231 of file arcGraphPart.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] = successor 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 parents
      for (const auto new_one: parents(current)) {
        if (mark.exists(new_one))   // the node has already been visited
          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);
      }

      // check the children
      for (const auto new_one: children(current)) {
        if (mark.exists(new_one))   // the node has already been visited
          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:

edgeCode() [1/4]

INLINE EdgeCode & gum::prm::gspan::Pattern::edgeCode	(	NodeId	tail,
		NodeId	head
	)

Returns the EdgeCode of an edge of this Pattern.

Definition at line 178 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                          {
        try {
          return *(arc_map__[Arc(tail, head)].second);
        } catch (NotFound&) { GUM_ERROR(NotFound, "arc not found in Pattern"); }
      }

Here is the call graph for this function:

edgeCode() [2/4]

INLINE EdgeCode & gum::prm::gspan::Pattern::edgeCode

(

const Arc &

arc

)

Returns the EdgeCode of an edge of this Pattern.

Definition at line 185 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                {
        try {
          return *(arc_map__[arc].second);
        } catch (NotFound&) { GUM_ERROR(NotFound, "arc not found in Pattern"); }
      }

Here is the call graph for this function:

edgeCode() [3/4]

INLINE const EdgeCode & gum::prm::gspan::Pattern::edgeCode	(	NodeId	tail,
		NodeId	head
	)		const

Returns the EdgeCode of an edge of this Pattern.

Definition at line 192 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                                      {
        try {
          return *(arc_map__[Arc(tail, head)].second);
        } catch (NotFound&) { GUM_ERROR(NotFound, "arc not found in Pattern"); }
      }

Here is the call graph for this function:

edgeCode() [4/4]

INLINE const EdgeCode & gum::prm::gspan::Pattern::edgeCode

(

const Arc &

arc

)

const

Returns the EdgeCode of an edge of this Pattern.

Definition at line 199 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                            {
        try {
          return *(arc_map__[arc].second);
        } catch (NotFound&) { GUM_ERROR(NotFound, "arc not found in Pattern"); }
      }

Here is the call graph for this function:

empty()

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

inherited

alias for emptyNodes

Definition at line 305 of file nodeGraphPart_inl.h.

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

{ return emptyNodes(); }

Here is the call graph for this function:

emptyArcs()

INLINE bool gum::ArcGraphPart::emptyArcs ( ) const

inherited

indicates wether the ArcGraphPart contains any arc

Definition at line 34 of file arcGraphPart_inl.h.

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

{ return arcs__.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 303 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 338 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 328 of file nodeGraphPart_inl.h.

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

                                                                                {
    return endIteratorSafe__;
  }

Here is the call graph for this function:

eraseArc()

INLINE void gum::ArcGraphPart::eraseArc ( const Arc &  arc )

virtualinherited

removes an arc from the ArcGraphPart

Parameters

arc	the arc to be removed

Warning

if the arc does not exist, nothing is done. In particular, no exception is thrown. However, the signal onArcDeleted is fired only if a node is effectively removed.

Definition at line 108 of file arcGraphPart_inl.h.

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

                                                   {
    // ASSUMING tail and head exists in parents__ anf children__
    // (if not, it is an error)
    if (existsArc(arc)) {
      NodeId tail = arc.tail(), head = arc.head();
      parents__[head]->erase(tail);
      children__[tail]->erase(head);
      arcs__.erase(arc);
      GUM_EMIT2(onArcDeleted, tail, head);
    }
  }

Here is the call graph for this function:

eraseChildren()

INLINE void gum::ArcGraphPart::eraseChildren ( NodeId  id )

inherited

removes all the children of a given node

Parameters

id	the node all the children of which will be removed

Warning

although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseChildren

if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 139 of file arcGraphPart_inl.h.

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

                                                   {
    if (children__.exists(id)) {
      NodeSet& children = *(children__[id]);

      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        // warning: use this erase so that you actually use the vritualized
        // arc removal function
        eraseArc(Arc(id, *iter));
      }
    }
  }

Here is the call graph for this function:

eraseNode()

INLINE void gum::DiGraph::eraseNode ( const NodeId  id )

virtualinherited

remove a node and its adjacent arcs 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.

Reimplemented in gum::MixedGraph.

Definition at line 68 of file diGraph_inl.h.

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

                                                {
    // warning: to remove the arcs adjacent to id, use the unvirtualized
    // versions
    // of arc removals
    ArcGraphPart::unvirtualizedEraseParents(id);
    ArcGraphPart::unvirtualizedEraseChildren(id);

    NodeGraphPart::eraseNode(id);
  }

Here is the call graph for this function:

eraseParents()

INLINE void gum::ArcGraphPart::eraseParents ( NodeId  id )

inherited

erase all the parents of a given node

Parameters

id	the node all the parents of which will be removed

Warning

although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseParents

if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 125 of file arcGraphPart_inl.h.

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

                                                  {
    if (parents__.exists(id)) {
      NodeSet& parents = *(parents__[id]);

      for (auto iter = parents.beginSafe();   // safe iterator needed here
           iter != parents.endSafe();
           ++iter) {
        // warning: use this erase so that you actually use the virtualized
        // arc removal function
        eraseArc(Arc(*iter, id));
      }
    }
  }

Here is the call graph for this function:

eraseSetOfArcs_()

INLINE void gum::ArcGraphPart::eraseSetOfArcs_ ( const ArcSet &  set )

protectedinherited

a (virtualized) function to remove a given set of arcs

Warning

this function uses eraseArc, which is a virtual function. Hence the behaviour of this function is that of a virtual function

Definition at line 120 of file arcGraphPart_inl.h.

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

                                                             {
    for (const auto& arc: set)
      eraseArc(arc);
  }

Here is the call graph for this function:

exists() [1/2]

INLINE bool gum::prm::gspan::Pattern::exists

(

NodeId

id

)

const

Returns true if id is a node in this Pattern.

Definition at line 138 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return DiGraph::exists(id); }

Here is the call graph for this function:

exists() [2/2]

INLINE bool gum::prm::gspan::Pattern::exists	(	NodeId	tail,
		NodeId	head
	)		const

Returns true if (tail, head) is an arc in this Pattern.

Definition at line 141 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                         {
        return DiGraph::existsArc(tail, head);
      }

Here is the call graph for this function:

existsArc() [1/2]

INLINE bool gum::ArcGraphPart::existsArc ( const Arc &  arc ) const

inherited

indicates whether a given arc exists

Parameters

arc	the arc we test whether or not it belongs to the ArcGraphPart

Definition at line 40 of file arcGraphPart_inl.h.

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

                                                          {
    return arcs__.contains(arc);
  }

Here is the call graph for this function:

existsArc() [2/2]

INLINE bool gum::ArcGraphPart::existsArc ( NodeId  tail, NodeId  head  ) const

inherited

indicates whether a given arc exists

Parameters

tail	the tail of the arc we test the existence in the ArcGraphPart
head	the head of the arc we test the existence in the ArcGraphPart

Definition at line 44 of file arcGraphPart_inl.h.

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

                                                                    {
    return parents__.exists(head) && parents__[head]->exists(tail);
  }

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

expandCodeIsMinimal__()

bool gum::prm::gspan::Pattern::expandCodeIsMinimal__ ( NodeId  u, NodeId  v  )

private

Returns true if the expand code by adding and edge betwenne u and v is minimal with respect to code__.

Parameters

u	A node in this Pattern.
v	A node in this Pattern.

Returns

true if the expand code by adding and edge betwenne u and v is minimal with respect to code__.

Definition at line 99 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                                                            {
        Bijection< NodeId, NodeId > node_map;
        Pattern                     p;
        node_map.insert(u, p.addNodeWithLabel(label(u)));
        node_map.insert(v, p.addNodeWithLabel(label(v)));

        try {
          p.addArc(1, 2, label(u, v));
        } catch (NotFound&) { p.addArc(1, 2, label(v, u)); }

        for (const auto nei: children(u))
          if (nei != v)
            if (rec__(p, node_map, u, nei)) return true;

        for (const auto nei: parents(u))
          if (nei != v)
            if (rec__(p, node_map, u, nei)) return true;

        for (const auto nei: children(v))
          if (nei != u)
            if (rec__(p, node_map, v, nei)) return true;

        for (const auto nei: parents(v))
          if (nei != u)
            if (rec__(p, node_map, v, nei)) return true;

        return false;
      }

Here is the call graph for this function:

family() [1/2]

INLINE NodeSet gum::ArcGraphPart::family ( NodeId  id ) const

inherited

returns the set of nodes which consists in the node and its parents

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is outgoing from the given node.

Parameters

id	the node which is the tail of a directed path with the returned nodes

Definition at line 61 of file arcGraphPart_inl.h.

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

                                                     {
    checkParents__(id);
    NodeSet res{id};
    return res + parents(id);
  }

Here is the call graph for this function:

family() [2/2]

INLINE NodeSet gum::ArcGraphPart::family ( const NodeSet &  ids ) const

inherited

returns the set of family nodes of a set of nodes

Definition at line 84 of file arcGraphPart_inl.h.

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

                                                              {
    NodeSet res;
    for (const auto node: ids)
      res += family(node);
    return res;
  }

Here is the call graph for this function:

hasDirectedPath()

bool gum::DiGraph::hasDirectedPath ( const NodeId  from, const NodeId  to  )

inherited

checks whether there exists a directed path from from to to

If from==to, this function checks if a directed cycle containing from exists.

Parameters

from
to

Returns

true if a directed path exists

Definition at line 136 of file diGraph.cpp.

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

                                                                  {
    if (!exists(from)) return false;

    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(from);

    NodeSet marked;
    marked.insert(from);

    NodeId new_one;

    while (!nodeFIFO.empty()) {
      new_one = nodeFIFO.front();
      // std::cout<<new_one<<std::endl;
      nodeFIFO.popFront();

      for (const auto chi: children(new_one)) {
        if (chi == to) return true;

        if (!marked.contains(chi)) {
          nodeFIFO.pushBack(chi);
          marked.insert(chi);
        }
      }
    }

    return false;
  }

Here is the call graph for this function:

isMinimal()

bool gum::prm::gspan::Pattern::isMinimal

(

)

Returns the DFSCode of this Pattern.

Definition at line 56 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                              {
        for (const auto node: nodes()) {
          for (const auto next: parents(node)) {
            Size     u = label(node).id;
            Size     v = label(next).id;
            EdgeCode edge_code(1, 2, u, label(next, node).id, v);

            if (edge_code < *(code().codes.front())) {
              return false;
            } else if (edge_code == (*code().codes.front())) {
              if (expandCodeIsMinimal__(node, next)) { return false; }
            }
          }

          for (const auto next: children(node)) {
            Size     u = label(node).id;
            Size     v = label(next).id;
            EdgeCode edge_code(1, 2, u, label(node, next).id, v);

            if (edge_code < *(code().codes.front())) {
              return false;
            } else if (edge_code == (*code().codes.front())) {
              if (expandCodeIsMinimal__(node, next)) { return false; }
            }
          }
        }

        return true;
      }

Here is the call graph for this function:

label() [1/6]

INLINE LabelData & gum::prm::gspan::Pattern::label

(

NodeId

node

)

Returns the LabelData assigned to node.

Definition at line 49 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                           {
        try {
          return *(node_map__[node]);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "node not found in this Pattern");
        }
      }

Here is the call graph for this function:

label() [2/6]

INLINE const LabelData & gum::prm::gspan::Pattern::label

(

NodeId

node

)

const

Returns the LabelData assigned to node.

Definition at line 58 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                       {
        try {
          return *(node_map__[node]);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "node not found in this Pattern");
        }
      }

Here is the call graph for this function:

label() [3/6]

INLINE LabelData & gum::prm::gspan::Pattern::label	(	NodeId	i,
		NodeId	j
	)

Returns the LabelData assigned to arc.

Definition at line 81 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                  {
        try {
          return *(arc_map__[Arc(i, j)].first);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "arc not found in this Pattern");
        }
      }

Here is the call graph for this function:

label() [4/6]

INLINE const LabelData & gum::prm::gspan::Pattern::label	(	NodeId	i,
		NodeId	j
	)		const

Returns the LabelData assigned to arc.

Definition at line 90 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                              {
        try {
          return *(arc_map__[Arc(i, j)].first);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "arc not found in this Pattern");
        }
      }

Here is the call graph for this function:

label() [5/6]

INLINE LabelData & gum::prm::gspan::Pattern::label

(

const Arc &

arc

)

Returns the LabelData assigned to arc.

Definition at line 99 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                              {
        try {
          return *(arc_map__[arc].first);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "arc not found in this Pattern");
        }
      }

Here is the call graph for this function:

label() [6/6]

INLINE const LabelData & gum::prm::gspan::Pattern::label

(

const Arc &

arc

)

const

Returns the LabelData assigned to arc.

Definition at line 108 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                          {
        try {
          return *(arc_map__[arc].first);
        } catch (NotFound&) {
          GUM_ERROR(NotFound, "arc not found in this Pattern");
        }
      }

Here is the call graph for this function:

lastAdded() [1/2]

INLINE LabelData & gum::prm::gspan::Pattern::lastAdded

(

)

Insert a node with the given LabelData.

Returns

The id assigned to the inserted node.

Definition at line 67 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                    {
        if (last__) return *last__;

        GUM_ERROR(OperationNotAllowed, "there are no LabelData yet");
      }

Here is the call graph for this function:

lastAdded() [2/2]

INLINE const LabelData & gum::prm::gspan::Pattern::lastAdded

(

)

const

Insert a node with the given LabelData.

Returns

The id assigned to the inserted node.

Definition at line 74 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                {
        if (last__) return *last__;

        GUM_ERROR(OperationNotAllowed, "there are no LabelData yet");
      }

Here is the call graph for this function:

listMapArcs()

template<typename VAL >

List< VAL > gum::ArcGraphPart::listMapArcs ( VAL(*)(const Arc &)  f ) const

inherited

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

Parameters

f	a function assigning a VAL to any arc

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

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 225 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::prm::gspan::Pattern::nodes

(

)

const

Definition at line 165 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                       {
        return DiGraph::nodes();
      }

Here is the call graph for this function:

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.

not_rec__()

bool gum::prm::gspan::Pattern::not_rec__ ( Pattern &  p, Bijection< NodeId, NodeId > &  node_map, NodeId  u, NodeId  v  )

private

A non recursive bugged version of rec__.

Definition at line 189 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                                                                {
        std::vector< std::pair< NodeId, NodeId > > stack;
        std::vector< size_t >                      rec_call;
        stack.push_back(std::make_pair(a_u, a_v));
        NodeId u = 0;
        NodeId v = 0;

        while (!stack.empty()) {
          bool go = true;
          u       = stack.back().first;
          v       = stack.back().second;
          stack.pop_back();

          if ((u == 0) && (v == 0)) {
            p.pop_back();
          } else {
            if (node_map.existsFirst(v)) {
              if (node_map.second(u) < node_map.second(v)) {
                // Invalid forward edge
                go = false;
              } else if ((p.existsArc(node_map.second(u), node_map.second(v)))
                         || (p.existsArc(node_map.second(v),
                                         node_map.second(u)))) {
                // Duplicate arc !
                go = false;
              }
            } else {
              node_map.insert(v, p.addNodeWithLabel(label(v)));
            }

            if (go) {
              // Retrieving arc label data
              LabelData* data = 0;

              try {
                data = &(label(u, v));
              } catch (NotFound&) { data = &(label(v, u)); }

              // Adding arc
              try {
                p.addArc(node_map.second(u), node_map.second(v), *data);
              } catch (OperationNotAllowed&) {
                // Invalid neighbor
                if (node_map.second(u) < node_map.second(v)) {
                  p.remove(node_map.second(v));
                  node_map.eraseFirst(v);
                }

                go = false;
              }

              if (go) {
                // Check if this is minimal or if equal find another growth
                size_t depth = p.code().codes.size() - 1;

                if (*(p.code().codes.back()) < *(code().codes[depth])) {
                  return true;
                } else if (*(p.code().codes.back()) == *(code().codes[depth])) {
                  std::list< NodeId > r_path;
                  p.rightmostPath(r_path);
                  stack.push_back(std::make_pair((NodeId)0, (NodeId)0));

                  for (const auto node: r_path) {
                    for (const auto nei: children(node)) {
                      stack.push_back(std::make_pair(node_map.first(node), nei));
                      ++(rec_call.back());
                    }

                    for (const auto nei: parents(node)) {
                      stack.push_back(std::make_pair(node_map.first(node), nei));
                      ++(rec_call.back());
                    }
                  }
                }

                if (p.code().codes.back()->isForward()) node_map.eraseFirst(v);
              }
            }
          }
        }

        return false;
      }

Here is the call graph for this function:

operator!=() [1/3]

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

inherited

tests whether two ArcGraphParts contain different arcs

Parameters

p	the ArcGraphPart that we compare with this

Definition at line 186 of file arcGraphPart_inl.h.

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

                                                                  {
    return arcs__ != p.arcs__;
  }

Here is the call graph for this function:

operator!=() [2/3]

INLINE bool gum::DiGraph::operator!= ( const DiGraph &  g ) const

inherited

tests whether two DiGraphs are different

Parameters

g	the DiGraph with which "this" is compared

Definition at line 82 of file diGraph_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 356 of file nodeGraphPart_inl.h.

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

                                                                    {
    return !operator==(p);
  }

Here is the call graph for this function:

operator==() [1/3]

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

inherited

tests whether two ArcGraphParts contain the same arcs

Parameters

p	the ArcGraphPart that we compare with this

Definition at line 182 of file arcGraphPart_inl.h.

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

                                                                  {
    return arcs__ == p.arcs__;
  }

Here is the call graph for this function:

operator==() [2/3]

INLINE bool gum::DiGraph::operator== ( const DiGraph &  g ) const

inherited

tests whether two DiGraphs are identical (same nodes, same arcs)

Parameters

g	the DiGraph with which "this" is compared

Definition at line 78 of file diGraph_inl.h.

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

                                                        {
    return ArcGraphPart::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 342 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:

parents() [1/2]

INLINE const NodeSet & gum::ArcGraphPart::parents ( NodeId  id ) const

inherited

returns the set of nodes with arc ingoing to a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is ingoing into the given node.

Parameters

id	the node toward which the arcs returned are pointing

Definition at line 56 of file arcGraphPart_inl.h.

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

                                                             {
    checkParents__(id);
    return *(parents__[id]);
  }

Here is the call graph for this function:

parents() [2/2]

INLINE NodeSet gum::ArcGraphPart::parents ( const NodeSet &  ids ) const

inherited

returns the set of parents of a set of nodes

Definition at line 76 of file arcGraphPart_inl.h.

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

                                                               {
    NodeSet res;
    for (const auto node: ids)
      res += parents(node);
    return res;
  }

Here is the call graph for this function:

pop_back()

INLINE void gum::prm::gspan::Pattern::pop_back

(

)

Remove the last EdgeCode of this pattern.

Definition at line 206 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                             {
        EdgeCode* edge = code__.codes.back();
        code__.codes.pop_back();

        if (edge->isForward()) {
          node_map__.erase(edge->j);
          arc_map__.erase(Arc(edge->i, edge->j));
          DiGraph::eraseArc(Arc(edge->i, edge->j));
          DiGraph::eraseNode(edge->j);
        } else {
          arc_map__.erase(Arc(edge->i, edge->j));
          DiGraph::eraseArc(Arc(edge->i, edge->j));
        }

        delete edge;
      }

Here is the call graph for this function:

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.

rec__()

bool gum::prm::gspan::Pattern::rec__ ( Pattern &  p, Bijection< NodeId, NodeId > &  node_map, NodeId  u, NodeId  v  )

private

Recurisve method used by expandCodeIsMinimal__.

Parameters

p	A Pattern.
node_map	A bijection.
u	A node in this Pattern.
v	A node in this Pattern.

Returns

true if the expansion is minimal.

Definition at line 128 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                                                          {
        if (node_map.existsFirst(v)) {
          if (node_map.second(u) < node_map.second(v)) {
            // Invalid forward edge
            return false;
          } else if ((p.existsArc(node_map.second(u), node_map.second(v)))
                     || (p.existsArc(node_map.second(v), node_map.second(u)))) {
            // Duplicate arc !
            return false;
          }
        } else {
          node_map.insert(v, p.addNodeWithLabel(label(v)));
        }

        // Retrieving arc label data
        LabelData* data = 0;

        try {
          data = &(label(u, v));
        } catch (NotFound&) { data = &(label(v, u)); }

        // Adding arc
        try {
          p.addArc(node_map.second(u), node_map.second(v), *data);
        } catch (OperationNotAllowed&) {
          // Invalid neighbor
          if (node_map.second(u) < node_map.second(v)) {
            p.remove(node_map.second(v));
            node_map.eraseFirst(v);
          }

          return false;
        }

        // Check if this is minimal or if equal find another growth
        size_t depth = p.code().codes.size() - 1;

        if (*(p.code().codes.back()) < *(code().codes[depth])) {
          return true;
        } else if (*(p.code().codes.back()) == *(code().codes[depth])) {
          std::list< NodeId > r_path;
          p.rightmostPath(r_path);

          for (const auto node: r_path) {
            for (const auto nei: children(node_map.first(node)))
              if (rec__(p, node_map, node_map.first(node), nei)) return true;

            for (const auto nei: parents(node_map.first(node)))
              if (rec__(p, node_map, node_map.first(node), nei)) return true;
          }
        }

        if (p.code().codes.back()->isForward()) node_map.eraseFirst(v);

        p.pop_back();
        return false;
      }

Here is the call graph for this function:

remove()

INLINE void gum::prm::gspan::Pattern::remove

(

NodeId

node

)

Remove a node if it has no neighbors, raise an OperationNotAllowed otherwise.

Definition at line 224 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                      {
        if (DiGraph::parents(node).empty() && DiGraph::children(node).empty()) {
          DiGraph::eraseNode(node);
          node_map__.erase(node);
        } else {
          GUM_ERROR(OperationNotAllowed, "the given node has neighbors");
        }
      }

Here is the call graph for this function:

rightmostPath()

INLINE void gum::prm::gspan::Pattern::rightmostPath

(

std::list< NodeId > &

r_path

)

const

Fill r_path with the rightmost path of this Pattern. The list is supposed empty.

Definition at line 152 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

                                                                 {
        r_path.push_back(NodeId(size()));

        while (r_path.front() != 1) {
          for (const auto par: parents(r_path.front())) {
            if (par < r_path.front()) {
              r_path.push_front(par);
              break;
            }
          }
        }
      }

Here is the call graph for this function:

size()

INLINE Size gum::prm::gspan::Pattern::size

(

)

const

Returns the number of nodes in this Pattern.

Definition at line 146 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return DiGraph::size(); }

Here is the call graph for this function:

sizeArcs()

INLINE Size gum::prm::gspan::Pattern::sizeArcs

(

)

const

Returns the number of arcs in this Pattern.

Definition at line 149 of file pattern_inl.h.

References gum::prm::gspan::operator<<().

{ return DiGraph::sizeArcs(); }

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 279 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() [1/2]

std::string gum::prm::gspan::Pattern::toDot

(

size_t

name

)

const

Print the pattern in the DOT syntax.

Definition at line 86 of file pattern.cpp.

References gum::prm::gspan::operator<<().

                                                {
        std::stringstream sBuff;
        sBuff << "digraph " << name << " {\n";

        for (const auto& arc: arcs()) {
          sBuff << label(arc.tail()).id << " -> ";
          sBuff << label(arc.head()).id << ";\n";
        }

        sBuff << "}\n";
        return sBuff.str();
      }

Here is the call graph for this function:

toDot() [2/2]

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

virtualinherited

to friendly display the content of the graph in the DOT syntax

Parameters

name	The graph name in the dot syntax. Default is G.

Returns

Returns a string describing the graph in the dot syntax

Reimplemented in gum::MixedGraph.

Definition at line 67 of file diGraph.cpp.

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

                                 {
    std::stringstream strBuff;
    std::string       tab = "     ";
    strBuff << "digraph {" << std::endl;

    for (const auto node: nodes())
      strBuff << tab << node << ";" << std::endl;

    strBuff << std::endl;

    for (const auto& arc: arcs())
      strBuff << tab << arc.tail() << " -> " << arc.head() << ";" << std::endl;

    strBuff << "}" << std::endl << std::endl;
    return strBuff.str();
  }

Here is the call graph for this function:

topologicalOrder()

const Sequence< NodeId > & gum::DiGraph::topologicalOrder ( bool  clear = true ) const

inherited

The topological order stays the same as long as no variable or arcs are added or erased src the topology.

Parameters

clear

If false returns the previously created topology.

Exceptions

InvalidDirectedCycle

Raised if this DiGraph contains cycles.

Definition at line 90 of file diGraph.cpp.

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

                                                                      {
    if (clear
        || (mutableTopologicalOrder__
            == nullptr)) {   // we have to call topologicalOrder_
      if (mutableTopologicalOrder__ == nullptr) {
        mutableTopologicalOrder__ = new Sequence< NodeId >();
      } else {
        // clear is True
        mutableTopologicalOrder__->clear();
      }

      topologicalOrder__();
    }

    return *mutableTopologicalOrder__;
  }

Here is the call graph for this function:

toString()

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

virtualinherited

to friendly display the content of the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 60 of file diGraph.cpp.

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

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

Here is the call graph for this function:

unvirtualizedEraseChildren()

INLINE void gum::ArcGraphPart::unvirtualizedEraseChildren ( NodeId  id )

inherited

same function as eraseChildren but without any virtual call to an erase

Parameters

id	the node whose outgoing arcs will be removed

Definition at line 170 of file arcGraphPart_inl.h.

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

                                                                {
    if (children__.exists(id)) {
      NodeSet& children = *(children__[id]);

      for (auto iter = children.beginSafe();   // safe iterator needed here
           iter != children.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(id, *iter));
      }
    }
  }

Here is the call graph for this function:

unvirtualizedEraseParents()

INLINE void gum::ArcGraphPart::unvirtualizedEraseParents ( NodeId  id )

inherited

same function as eraseParents but without any virtual call to an erase

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 158 of file arcGraphPart_inl.h.

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

                                                               {
    if (parents__.exists(id)) {
      NodeSet& parents = *(parents__[id]);

      for (auto iter = parents.beginSafe();   // safe iterator needed here
           iter != parents.endSafe();
           ++iter) {
        ArcGraphPart::eraseArc(Arc(*iter, id));
      }
    }
  }

Here is the call graph for this function:

unvirtualizedEraseSetOfArcs_()

INLINE void gum::ArcGraphPart::unvirtualizedEraseSetOfArcs_ ( const ArcSet &  set )

protectedinherited

similar to eraseSetOfArcs_ except that it is unvirtualized

Warning

this function uses ArcGraphPart::eraseArc, hence, as compared with eraseSetOfArcs_, it removes the arcs without calling a virtual eraseArc

Definition at line 153 of file arcGraphPart_inl.h.

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

                                                                          {
    for (const auto& arc: set)
      ArcGraphPart::eraseArc(arc);
  }

Here is the call graph for this function:

Member Data Documentation

arc_map__

ArcProperty< std::pair< LabelData*, EdgeCode* > > gum::prm::gspan::Pattern::arc_map__

private

Mapping between edges in this Pattern and their respective LabelData.

Definition at line 212 of file pattern.h.

code__

DFSCode gum::prm::gspan::Pattern::code__

private

The DFSCode of this Pattern.

Definition at line 204 of file pattern.h.

last__

LabelData* gum::prm::gspan::Pattern::last__

private

The last LabelData added to this pattern.

Definition at line 215 of file pattern.h.

node_map__

NodeProperty< LabelData* > gum::prm::gspan::Pattern::node_map__

private

Mapping between nodes in this Pattern and their respective LabelData.

Definition at line 208 of file pattern.h.

onArcAdded

Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcAdded

inherited

Definition at line 82 of file arcGraphPart.h.

onArcDeleted

Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcDeleted

inherited

Definition at line 83 of file arcGraphPart.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/PRM/gspan/pattern.h
• agrum/PRM/gspan/pattern.cpp
• agrum/PRM/gspan/pattern_inl.h