gum::MeekRules Class Reference

#include <MeekRules.h>

Public Member Functions
MixedGraph	propagate (const MixedGraph &mg)
	Propagates the orientation of a MixedGraph (no double-headed arcs) and return a PDAG.
PDAG	propagateToCPDAG (const MixedGraph &mg)
	Propagates the orientation of a MixedGraph (no double-headed arcs) and return a PDAG.
DAG	propagateToDAG (const MixedGraph &mg)
	Propagates the orientation of a MixedGraph and completes it as a DAG.
std::vector< Arc >	choices () const
	Get the Choices object : the list of arcs that the algorithm has to choose from a double arc or a double non-arc.
Constructors / Destructors
	MeekRules ()
	default constructor
virtual	~MeekRules ()
	destructor

Private Member Functions
MixedGraph	_propagates_ (const MixedGraph &graph)
bool	_applyMeekRules_ (MixedGraph &graph, NodeId xj)
	Propagates the orientation from a node to its neighbours.
void	_propagatesOrientationInChainOfRemainingEdges_ (gum::MixedGraph &graph)
	heuristic for remaining edges when everything else has been tried
void	_orientDoubleHeadedArcs_ (MixedGraph &mg)
	Tells us if we can orient the edge xi - xj to xi -> xj.
bool	_isOrientable_ (const gum::MixedGraph &graph, gum::NodeId xi, gum::NodeId xj) const
void	_complete_ (MixedGraph &graph)
gum::Arc	_critereMinParents_ (const gum::MixedGraph &graph, gum::NodeId x, gum::NodeId y)
	When resolving double-headed arcs, prioritize selecting the option that minimizes the number of parent nodes in the graph.

Static Private Member Functions
static bool	_existsDirectedPath_ (const MixedGraph &graph, NodeId n1, NodeId n2)

Private Attributes
std::vector< Arc >	_choices_

Detailed Description

Definition at line 56 of file MeekRules.h.

Constructor & Destructor Documentation

MeekRules()

gum::MeekRules::MeekRules

(

)

default constructor

Definition at line 54 of file MeekRules.cpp.

{ GUM_CONSTRUCTOR(MeekRules); }

References MeekRules().

Referenced by MeekRules(), and ~MeekRules().

Here is the call graph for this function:

Here is the caller graph for this function:

~MeekRules()

gum::MeekRules::~MeekRules ( )

virtual

destructor

Definition at line 57 of file MeekRules.cpp.

{ GUM_DESTRUCTOR(MeekRules); }

References MeekRules().

Here is the call graph for this function:

Member Function Documentation

_applyMeekRules_()

bool gum::MeekRules::_applyMeekRules_ ( MixedGraph & graph, NodeId xj )

private

Propagates the orientation from a node to its neighbours.

Parameters

graph	graph in which to which to propagate arcs
node	node on which neighbours to propagate th orientation
force	: true if an orientation has always to be found.

Definition at line 206 of file MeekRules.cpp.

                                                               {
    bool       res        = false;
    const auto neighbours = graph.neighbours(xj);
    for (auto& xi: neighbours) {
      bool i_j = _isOrientable_(graph, xi, xj);
      bool j_i = _isOrientable_(graph, xj, xi);
      if (i_j || j_i) {
        // GUM_SL_EMIT(xi, xj, "Removing Edge", "line 660")
        graph.eraseEdge(Edge(xi, xj));
        res = true;
      }
      if (i_j) {
        graph.eraseEdge(Edge(xi, xj));
        graph.addArc(xi, xj);
        _applyMeekRules_(graph, xj);
      }
      if (j_i) {
        graph.eraseEdge(Edge(xi, xj));
        graph.addArc(xj, xi);
        _applyMeekRules_(graph, xi);
      }
      if (i_j && j_i) {
        // GUM_TRACE(" + add arc (" << xi << "," << xj << ")")
        _choices_.emplace_back(xi, xj);
      }
    }
    return res;
  }

References _applyMeekRules_(), _choices_, _isOrientable_(), gum::DiGraph::addArc(), gum::EdgeGraphPart::eraseEdge(), and gum::EdgeGraphPart::neighbours().

Referenced by _applyMeekRules_(), _complete_(), _propagates_(), and _propagatesOrientationInChainOfRemainingEdges_().

Here is the call graph for this function:

Here is the caller graph for this function:

_complete_()

void gum::MeekRules::_complete_ ( MixedGraph & graph )

private

Definition at line 190 of file MeekRules.cpp.

                                              {
    // Propagates existing orientations thanks to rules
    bool newOrientation = true;
    while (newOrientation) {
      newOrientation = false;
      for (NodeId x: graph.nodes()) {
        if (!graph.parents(x).empty()) { newOrientation |= _applyMeekRules_(graph, x); }
      }
    }
 
    // GUM_TRACE(graph.toDot())
    //  Orient remaining edges
    _propagatesOrientationInChainOfRemainingEdges_(graph);
  }

References _applyMeekRules_(), _propagatesOrientationInChainOfRemainingEdges_(), gum::Set< Key >::empty(), gum::NodeGraphPart::nodes(), and gum::ArcGraphPart::parents().

Referenced by propagateToDAG().

Here is the call graph for this function:

Here is the caller graph for this function:

_critereMinParents_()

gum::Arc gum::MeekRules::_critereMinParents_ ( const gum::MixedGraph & graph, gum::NodeId x, gum::NodeId y )

private

When resolving double-headed arcs, prioritize selecting the option that minimizes the number of parent nodes in the graph.

Returns

gum::Arc the arc that should be earased.

Definition at line 236 of file MeekRules.cpp.

                                                                                         {
    // If the number of parents of x is less than the number of parents of y.
    if (graph.parents(x).size() < graph.parents(y).size()) {
      // If the number of parents of x is less than the number of parents of y.
      // We want to keep y->x, so we return x->y for erasure.
      return Arc(x, y);
    } else if (graph.parents(x).size() > graph.parents(y).size()) {
      return Arc(y, x);
    } else {   // If they have the same number of parents, we choose the one with less neighbours.
      if (graph.neighbours(x).size() < graph.neighbours(y).size()) {
        return Arc(x, y);
      } else {
        return Arc(y, x);
      }
    }
  }

References gum::EdgeGraphPart::neighbours(), gum::ArcGraphPart::parents(), and gum::Set< Key >::size().

Referenced by _orientDoubleHeadedArcs_().

Here is the call graph for this function:

Here is the caller graph for this function:

_existsDirectedPath_()

bool gum::MeekRules::_existsDirectedPath_ ( const MixedGraph & graph, NodeId n1, NodeId n2 )

staticprivate

Definition at line 340 of file MeekRules.cpp.

                                                                                                {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    // mark[node] = successor if visited, else mark[node] does not exist
    Set< NodeId > mark;
 
    mark.insert(n2);
    nodeFIFO.pushBack(n2);
 
    NodeId current;
 
    while (!nodeFIFO.empty()) {
      current = nodeFIFO.front();
      nodeFIFO.popFront();
 
      // check the parents
      for (const auto new_one: graph.parents(current)) {
        if (graph.existsArc(current,
                            new_one))   // if there is a double arc, pass
          continue;
 
        if (new_one == n1) { return true; }
 
        if (mark.exists(new_one))   // if this node is already marked, do not
          continue;                 // check it again
 
        mark.insert(new_one);
        nodeFIFO.pushBack(new_one);
      }
    }
 
    return false;
  }

References gum::List< Val >::empty(), gum::Set< Key >::exists(), gum::ArcGraphPart::existsArc(), gum::List< Val >::front(), gum::Set< Key >::insert(), gum::ArcGraphPart::parents(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by _isOrientable_(), and _orientDoubleHeadedArcs_().

Here is the call graph for this function:

Here is the caller graph for this function:

_isOrientable_()

bool gum::MeekRules::_isOrientable_ ( const gum::MixedGraph & graph, gum::NodeId xi, gum::NodeId xj ) const

private

Definition at line 253 of file MeekRules.cpp.

                                                                                    {
    // no cycle
    if (_existsDirectedPath_(graph, xj, xi)) {
      // GUM_TRACE("cycle(" << xi << "-" << xj << ")")
      return false;
    }
    // R1
    if (!(graph.parents(xi) - graph.boundary(xj)).empty()) {
      // GUM_TRACE("R1(" << xi << "-" << xj << ")")
      return true;
    }
    // R2
    if (_existsDirectedPath_(graph, xi, xj)) {
      // GUM_TRACE("R2(" << xi << "-" << xj << ")")
      return true;
    }
    // R3
    int nbr = 0;
    for (const auto p: graph.parents(xj)) {
      if (!graph.mixedOrientedPath(xi, p).empty()) {
        nbr += 1;
        if (nbr == 2) {
          // GUM_TRACE("R3(" << xi << "-" << xj << ")")
          return true;
        }
      }
    }
    return false;
  }

References _existsDirectedPath_(), gum::MixedGraph::boundary(), gum::MixedGraph::mixedOrientedPath(), and gum::ArcGraphPart::parents().

Referenced by _applyMeekRules_().

Here is the call graph for this function:

Here is the caller graph for this function:

_orientDoubleHeadedArcs_()

void gum::MeekRules::_orientDoubleHeadedArcs_ ( MixedGraph & mg )

private

Tells us if we can orient the edge xi - xj to xi -> xj.

Orient double-headed arcs while avoiding cycles.

Parameters

graph	the graph
xi	the tail of the arc
xj	the head of the arc

Returns

true if we can orient xi to xj Gets the orientation probabilities like MIIC for the orientation phase

Parameters

mg	the MixedGraph the graph from which the double headed arcs will be oriented.

Definition at line 112 of file MeekRules.cpp.

                                                         {
    gum::ArcSet L;   // create a set of all double-headed arcs
    for (gum::NodeId x: mg.nodes())
      for (NodeId y: mg.parents(x))
        // If there is a mutual parent-child relationship, add the arc to the set
        if (mg.parents(y).contains(x)) {
          if (x > y) {
            continue;   // Avoid duplicate arcs by considering only one direction
          } else {
            L.insert(gum::Arc(x, y));
          }
        }
 
    // If there are double-headed arcs
    if (not L.empty()) {
      while (true) {
        bool withdrawFlag_L = false;
        for (auto arc: ArcSet(L)) {
          bool tail_head        = _existsDirectedPath_(mg, arc.tail(), arc.head());
          bool head_tail        = _existsDirectedPath_(mg, arc.head(), arc.tail());
          bool withdrawFlag_arc = false;
 
          // Case 1: There is already a path from tail to head and no path from head to tail
          if (tail_head && !head_tail) {
            // Erase the arc from head to tail to avoid cycles
            mg.eraseArc(Arc(arc.head(), arc.tail()));
            withdrawFlag_arc = true;
 
            // Case 2: There is already a path from head to tail and no path from tail to head
          } else if (!tail_head && head_tail) {
            // Erase the arc from tail to head to avoid cycles
            mg.eraseArc(Arc(arc.tail(), arc.head()));
            withdrawFlag_arc = true;
 
            // Case 3: There is no path between tail and head
          } else if (!tail_head && !head_tail) {
            // Choose an arbitrary orientation and erase the corresponding arc
            // mg.eraseArc(Arc(arc.head(), arc.tail()));
            mg.eraseArc(_critereMinParents_(mg, arc.tail(), arc.head()));
            withdrawFlag_arc = true;
          }
 
          // Remove the arc from the set if it was processed
          if (withdrawFlag_arc) {
            L.erase(arc);
            withdrawFlag_L = true;
          }
        }
        // If all double-headed arcs are processed, exit the loop
        if (L.empty()) { break; }
 
        // If no arcs were withdrawn, erase an arbitrary double arc in the graph (the first one in
        // L). Hoping the situation will improve. ┐(￣ヘ￣)┌ If we arrive here, it's because the
        // double-headed arc creates cycles in both directions
        if (!withdrawFlag_L) {
          auto it  = L.begin();
          auto arc = *it;
          mg.eraseArc(Arc(arc.head(), arc.tail()));
          mg.eraseArc(Arc(arc.tail(), arc.head()));
          L.erase(arc);
        }
      }
    }
  }

References _critereMinParents_(), _existsDirectedPath_(), gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::ArcGraphPart::eraseArc(), gum::Set< Key >::insert(), gum::NodeGraphPart::nodes(), and gum::ArcGraphPart::parents().

Referenced by propagateToCPDAG(), and propagateToDAG().

Here is the call graph for this function:

Here is the caller graph for this function:

_propagates_()

MixedGraph gum::MeekRules::_propagates_ ( const MixedGraph & graph )

private

Definition at line 177 of file MeekRules.cpp.

                                                         {
    MixedGraph graph(mg);
    // Propagates existing orientations thanks to Meek rules
    bool newOrientation = true;
    while (newOrientation) {
      newOrientation = false;
      for (NodeId x: graph.nodes()) {
        if (!graph.parents(x).empty()) { newOrientation |= _applyMeekRules_(graph, x); }
      }
    }
    return graph;
  }

References _applyMeekRules_(), gum::Set< Key >::empty(), gum::NodeGraphPart::nodes(), and gum::ArcGraphPart::parents().

Referenced by propagate(), propagateToCPDAG(), and propagateToDAG().

Here is the call graph for this function:

Here is the caller graph for this function:

_propagatesOrientationInChainOfRemainingEdges_()

void gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_ ( gum::MixedGraph & graph )

private

heuristic for remaining edges when everything else has been tried

Arbitrary propagation if we can't propagate thanks to MeekRules.

Parameters

graph	graph in which to which to propagate arcs
_latentCouples_

Definition at line 284 of file MeekRules.cpp.

                                                                                           {
    // then decide the orientation for remaining edges
    while (!essentialGraph.edges().empty()) {
      const auto& edge               = *(essentialGraph.edges().begin());
      NodeId      root               = edge.first();
      Size        size_children_root = essentialGraph.children(root).size();
      NodeSet     visited;
      NodeSet     stack{root};
 
      // check the best root for the set of neighbours
      while (!stack.empty()) {
        NodeId next = *(stack.begin());
        stack.erase(next);
        if (visited.contains(next)) continue;
        if (essentialGraph.children(next).size() > size_children_root) {
          size_children_root = essentialGraph.children(next).size();
          root               = next;
        }
        for (const auto n: essentialGraph.neighbours(next))
          if (!stack.contains(n) && !visited.contains(n)) stack.insert(n);
        visited.insert(next);
      }
 
      // orientation now
      visited.clear();
      stack.clear();
      stack.insert(root);
      while (!stack.empty()) {
        // GUM_TRACE("stack : " << stack)
        NodeId next = *(stack.begin());
        stack.erase(next);
        // GUM_TRACE("next : " << next)
        if (visited.contains(next)) continue;
        const auto nei = essentialGraph.neighbours(next);
        for (const auto n: nei) {
          // GUM_TRACE("n : "<< n)
          if (!stack.contains(n) && !visited.contains(n)) stack.insert(n);
          // GUM_TRACE(" + amap reasonably orientation for " << n << "->" << next);
          if (_applyMeekRules_(essentialGraph, next)) {
            continue;
          } else {
            if (!essentialGraph.existsArc(next,
                                          n)) {   // Checking that we're not creating a
                                                  // doubly-oriented arc by adding a "random" arc.
              essentialGraph.eraseEdge(Edge(n, next));
              essentialGraph.addArc(n, next);
              _choices_.emplace_back(n, next);
              // GUM_TRACE(" + add arc (" << n << "->" << next << ")")
            }
          }
        }
        visited.insert(next);
      }
    }
  }

References _applyMeekRules_(), _choices_, gum::DiGraph::addArc(), gum::Set< Key >::begin(), gum::ArcGraphPart::children(), gum::Set< Key >::clear(), gum::Set< Key >::contains(), gum::EdgeGraphPart::edges(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::EdgeGraphPart::eraseEdge(), gum::ArcGraphPart::existsArc(), gum::Set< Key >::insert(), gum::EdgeGraphPart::neighbours(), and gum::Set< Key >::size().

Referenced by _complete_().

Here is the call graph for this function:

Here is the caller graph for this function:

choices()

std::vector< Arc > gum::MeekRules::choices ( ) const

inline

Get the Choices object : the list of arcs that the algorithm has to choose from a double arc or a double non-arc.

Returns

std::vector< Arc >

Definition at line 95 of file MeekRules.h.

{ return _choices_; };

References _choices_.

propagate()

MixedGraph gum::MeekRules::propagate

(

const MixedGraph &

mg

)

Propagates the orientation of a MixedGraph (no double-headed arcs) and return a PDAG.

Propagates MeekRules in a MixedGraph.

Parameters

graph

the graph in which to which to propagate arcs

Warning

propagates may create double arcs

Definition at line 60 of file MeekRules.cpp.

                                                         {
    _choices_.clear();
    return _propagates_(graph);
  }

References _choices_, and _propagates_().

Here is the call graph for this function:

propagateToCPDAG()

PDAG gum::MeekRules::propagateToCPDAG

(

const MixedGraph &

mg

)

Propagates the orientation of a MixedGraph (no double-headed arcs) and return a PDAG.

Parameters

graph

the graph in which to which to propagate arcs

Warning

propagateToCPDAG may have to select between double arcs created by propagates

Definition at line 66 of file MeekRules.cpp.

                                                       {
    _choices_.clear();
 
    MixedGraph graph = _propagates_(mg);
 
    // Resolve double-headed arc while avoiding cycle creation.
    _orientDoubleHeadedArcs_(graph);
 
    // cycle have been resolved above, so we can safely convert to PDAG
    PDAG pdag;
    for (auto node: graph) {
      pdag.addNodeWithId(node);
    }
    for (const Edge& edge: graph.edges()) {
      pdag.addEdge(edge.first(), edge.second());
    }
    for (const Arc& arc: graph.arcs()) {
      pdag.addArc(arc.tail(), arc.head());
    }
    return pdag;
  }

References _choices_, _orientDoubleHeadedArcs_(), _propagates_(), gum::PDAG::addArc(), gum::PDAG::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::ArcGraphPart::arcs(), and gum::EdgeGraphPart::edges().

Here is the call graph for this function:

propagateToDAG()

DAG gum::MeekRules::propagateToDAG

(

const MixedGraph &

mg

)

Propagates the orientation of a MixedGraph and completes it as a DAG.

Propagates the orientation of a MixedGraph and return a DAG.

Parameters

graph

the graph in which to which to propagate arcs

Warning

propagateToDAG may have to select between double arcs created by propagates

Definition at line 89 of file MeekRules.cpp.

                                                       {
    _choices_.clear();
    // Orient all remaining  edges into arcs
    MixedGraph graph = _propagates_(mg);
 
    // complete remaining edges
    _complete_(graph);
 
    // Resolve double-headed arc while avoiding cycle creation.
    _orientDoubleHeadedArcs_(graph);
 
 
    DAG dag;
    for (auto node: graph.nodes()) {
      dag.addNodeWithId(node);
    }
    for (const Arc& arc: graph.arcs()) {
      dag.addArc(arc.tail(), arc.head());
    }
    return dag;
  }

References _choices_, _complete_(), _orientDoubleHeadedArcs_(), _propagates_(), gum::DAG::addArc(), gum::NodeGraphPart::addNodeWithId(), gum::ArcGraphPart::arcs(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

Member Data Documentation

_choices_

std::vector< Arc > gum::MeekRules::_choices_

private

Definition at line 100 of file MeekRules.h.

Referenced by _applyMeekRules_(), _propagatesOrientationInChainOfRemainingEdges_(), choices(), propagate(), propagateToCPDAG(), and propagateToDAG().

---

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

• agrum/base/graphs/algorithms/MeekRules.h
• agrum/base/graphs/algorithms/MeekRules.cpp