gum::prm::gspan::DFSCode Class Reference

Reprensent a Depth First Search coding of a graph. More...

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

Public Attributes
std::vector< EdgeCode *>	codes
	The vector containing the EdgeCode composing this DFSCode. More...

Public Member Functions
	DFSCode ()
	Default constructor. More...
	DFSCode (const DFSCode &source)
	Copy constructor. More...
	~DFSCode ()
	Destructor. More...
DFSCode &	operator= (const DFSCode &source)
	Copy operator. More...
bool	operator== (const DFSCode &code) const
	Equality operator. More...
bool	operator!= (const DFSCode &code) const
	Difference operator. More...
bool	operator< (const DFSCode &code) const
	Lesser than operator. More...
bool	operator<= (const DFSCode &code) const
	Lesser or equal than operator. More...

Static Public Member Functions
static bool	validNeighbors (EdgeCode *e1, EdgeCode *e2)
	Returns true of e2 is a valid neighbor for e1 (i.e. More...

Public Types
typedef std::vector< EdgeCode *>::iterator	iterator
	Code alias. More...
typedef std::vector< EdgeCode *>::const_iterator	const_iterator
	Code alias. More...

Detailed Description

Reprensent a Depth First Search coding of a graph.

A DFSCode is composed of EdgeCode. Each EdgeCode is either a forward edge or a backward edge.

Regarding memory allocation EdgeCode are shared between related DFSCode, so delete DFSCode in a bottom up fashion.

Definition at line 53 of file DFSCode.h.

Member Typedef Documentation

const_iterator

typedef std::vector< EdgeCode* >::const_iterator gum::prm::gspan::DFSCode::const_iterator

Code alias.

Definition at line 131 of file DFSCode.h.

iterator

typedef std::vector< EdgeCode* >::iterator gum::prm::gspan::DFSCode::iterator

Code alias.

Definition at line 128 of file DFSCode.h.

Constructor & Destructor Documentation

DFSCode() [1/2]

INLINE gum::prm::gspan::DFSCode::DFSCode

(

)

Default constructor.

Create an empty DFSCode.

Definition at line 35 of file DFSCode_inl.h.

{ GUM_CONSTRUCTOR(DFSCode); }

DFSCode() [2/2]

INLINE gum::prm::gspan::DFSCode::DFSCode

(

const DFSCode &

source

)

Copy constructor.

Proceeds with a deep copy.

Definition at line 38 of file DFSCode_inl.h.

References codes.

                                            {
        GUM_CONS_CPY(DFSCode);

        for (const auto code : source.codes)
          codes.push_back(new EdgeCode(*code));
      }

~DFSCode()

INLINE gum::prm::gspan::DFSCode::~DFSCode

(

)

Destructor.

This will delete all children of this DFSCode, with their respective EdgeCode.

Definition at line 46 of file DFSCode_inl.h.

References codes.

                        {
        GUM_DESTRUCTOR(DFSCode);

        for (const auto item : codes)
          delete item;
      }

Member Function Documentation

operator!=()

INLINE bool gum::prm::gspan::DFSCode::operator!=

(

const DFSCode &

code

)

const

Difference operator.

Parameters

code	The code tested for difference with this.

Returns

Returns true if this and code are different.

Definition at line 78 of file DFSCode_inl.h.

References codes.

                                                        {
        if (codes.size() == from.codes.size()) {
          for (size_t idx = 0; idx < codes.size(); ++idx) {
            if ((*codes[idx]) != (*codes[idx])) { return true; }
          }

          return false;
        } else {
          return true;
        }
      }

operator<()

INLINE bool gum::prm::gspan::DFSCode::operator<

(

const DFSCode &

code

)

const

Lesser than operator.

Parameters

code	The code on which the test is made.

Returns

Returns true if this is lesser than code.

Definition at line 91 of file DFSCode_inl.h.

References codes, gum::prm::gspan::EdgeCode::i, gum::prm::gspan::EdgeCode::isBackward(), gum::prm::gspan::EdgeCode::isForward(), gum::prm::gspan::EdgeCode::j, gum::prm::gspan::EdgeCode::l_i, gum::prm::gspan::EdgeCode::l_ij, and gum::prm::gspan::EdgeCode::l_j.

                                                       {
        DFSCode::const_iterator iter = codes.begin();
        DFSCode::const_iterator jter = from.codes.begin();

        for (; (iter != codes.end()) && (jter != from.codes.end());
             ++iter, ++jter) {
          if ((**iter) != (**jter)) {
            EdgeCode& alpha = **iter;
            EdgeCode& beta = **jter;

            if (alpha.isBackward()) {
              if (beta.isForward()) {
                return true;
              } else if (alpha.j < beta.j) {
                // beta is a backward edge
                return true;
              } else if ((alpha.j == beta.j) && (alpha.l_ij < beta.l_ij)) {
                return true;
              }

              return false;
            } else {
              // alpha is a forward edge
              if (beta.isBackward()) {
                return false;
              } else if (beta.i < alpha.i) {
                // Beta is a forward edge
                return true;
              } else if (beta.i == alpha.i) {
                if (alpha.l_i < beta.l_i) {
                  return true;
                } else if (alpha.l_i == beta.l_i) {
                  if (alpha.l_ij < beta.l_ij) {
                    return true;
                  } else if (alpha.l_ij == beta.l_ij) {
                    return alpha.l_j < beta.l_j;
                  }
                }
              }

              return false;
            }

            return (**iter) < (**jter);
          }
        }

        return false;
      }

Here is the call graph for this function:

operator<=()

INLINE bool gum::prm::gspan::DFSCode::operator<=

(

const DFSCode &

code

)

const

Lesser or equal than operator.

Parameters

code	The code on which the test is made.

Returns

Returns true if this is lesser than code.

Definition at line 142 of file DFSCode_inl.h.

References codes.

                                                        {
        DFSCode::const_iterator iter = codes.begin();
        DFSCode::const_iterator jter = from.codes.begin();

        for (; (iter != codes.end()) && (jter != from.codes.end());
             ++iter, ++jter) {
          if ((**iter) != (**jter)) { return (**iter) < (**jter); }
        }

        return codes.size() <= from.codes.size();
      }

operator=()

INLINE DFSCode & gum::prm::gspan::DFSCode::operator=

(

const DFSCode &

source

)

Copy operator.

Proceeds with a deep copy.

Definition at line 54 of file DFSCode_inl.h.

References codes.

                                                       {
        for (const auto item : codes)
          delete item;

        for (const auto srcitem : source.codes)
          codes.push_back(new EdgeCode(*srcitem));

        return *this;
      }

operator==()

INLINE bool gum::prm::gspan::DFSCode::operator==

(

const DFSCode &

code

)

const

Equality operator.

Parameters

code	The code tested for equality with this.

Returns

Returns true if this and code are equal.

Definition at line 65 of file DFSCode_inl.h.

References codes.

                                                        {
        if (codes.size() == from.codes.size()) {
          for (size_t idx = 0; idx < codes.size(); ++idx) {
            if ((*codes[idx]) != (*codes[idx])) { return false; }
          }

          return true;
        } else {
          return false;
        }
      }

validNeighbors()

bool gum::prm::gspan::DFSCode::validNeighbors ( EdgeCode *  e1, EdgeCode *  e2  )

inlinestatic

Returns true of e2 is a valid neighbor for e1 (i.e.

it respect the neighborhood restriction) if e1 precedes e2 in a DFSCode.

Parameters

e1	An EdgeCode.
e2	Another EdgeCode.

Returns

Returns true of e2 is a valid neighbor for e1 (i.e. it respect the neighborhood restriction) if e1 precedes e2 in a DFSCode.

Definition at line 142 of file DFSCode.h.

References gum::prm::gspan::EdgeCode::i, gum::prm::gspan::EdgeCode::isBackward(), gum::prm::gspan::EdgeCode::isForward(), and gum::prm::gspan::EdgeCode::j.

Referenced by gum::prm::gspan::Pattern::addArc().

                                                                    {
        if (e1->isBackward()) {
          if (e2->isForward()) {
            return (e2->i <= e1->i) && (e2->j = (e1->i + 1));
          } else {
            return (e2->i == e1->i) && (e1->j < e2->j);
          }
        } else {
          // e1 is a forward edge
          if (e2->isForward()) {
            return (e2->i <= e1->j) && (e2->j == (e1->j + 1));
          } else {
            return (e2->i == e1->j) && (e2->j < e1->i);
          }
        }
      }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

codes

std::vector< EdgeCode* > gum::prm::gspan::DFSCode::codes

The vector containing the EdgeCode composing this DFSCode.

Definition at line 90 of file DFSCode.h.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::__checkGrowth(), gum::prm::gspan::Pattern::__not_rec(), gum::prm::gspan::Pattern::__rec(), gum::prm::GSpan< GUM_SCALAR >::__subgraph_mining(), gum::prm::gspan::Pattern::addArc(), DFSCode(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::prm::gspan::Pattern::isMinimal(), operator!=(), operator<(), gum::prm::gspan::operator<<(), operator<=(), operator=(), operator==(), gum::prm::gspan::Pattern::Pattern(), gum::prm::gspan::Pattern::pop_back(), and ~DFSCode().

---

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

• agrum/PRM/gspan/DFSCode.h
• agrum/PRM/gspan/DFSCode_inl.h