gum::MeekRules Class Reference

Applies Meek's orientation rules to propagate arc directions in a mixed graph. More...

#include <MeekRules.h>

Public Member Functions
MixedGraph	propagate (const MixedGraph &mg)
	Applies Meek rules to a MixedGraph and returns the partially oriented result.
PDAG	propagateToCPDAG (const MixedGraph &mg)
	Applies Meek rules and returns a CPDAG (completed PDAG).
DAG	propagateToDAG (const MixedGraph &mg)
	Applies Meek rules and completes the result into a DAG.
const std::vector< Arc > &	choices () const
	Returns the arcs for which the algorithm made an arbitrary orientation choice.
Constructors / Destructors
	MeekRules ()
	default constructor
virtual	~MeekRules ()
	destructor

Private Member Functions
MixedGraph	_propagates_ (const MixedGraph &graph)
	Applies Meek rules R1–R4 exhaustively and returns the resulting graph.
bool	_applyMeekRules_ (MixedGraph &graph, NodeId xj)
	Tries to orient edges incident to xj using Meek rules R1–R4.
void	_propagatesOrientationInChainOfRemainingEdges_ (MixedGraph &graph)
	Arbitrarily orients remaining undirected edges when no Meek rule applies.
void	_complete_ (MixedGraph &graph)
	Orients all remaining undirected edges, applying Meek rules then a chain heuristic.

Static Private Member Functions
static void	_orientDoubleHeadedArcs_ (MixedGraph &mg)
	Resolves double-headed arcs (x→y and y→x simultaneously) to avoid cycles.
static bool	_isOrientable_ (const MixedGraph &graph, NodeId xi, NodeId xj)
	Returns true if the edge xi–xj can be oriented as xi→xj under Meek rules R1–R3.
static bool	_existsDirectedPath_ (const MixedGraph &graph, NodeId n1, NodeId n2)
	Returns true if there is a directed path from n1 to n2 (BFS, double arcs ignored).
static Arc	_selectArcToEraseByMinParents_ (const MixedGraph &graph, NodeId x, NodeId y)
	Returns the arc to erase when resolving a double-headed arc, using a min-parents heuristic.

Private Attributes
std::vector< Arc >	_choices_

Detailed Description

Applies Meek's orientation rules to propagate arc directions in a mixed graph.

Given a MixedGraph (containing both directed arcs and undirected edges, with no double-headed arcs in the input), this class applies rules R1–R4 exhaustively to orient as many undirected edges as possible without introducing new v-structures. Three output flavours are available: MixedGraph (partial orientation), PDAG (completed PDAG / CPDAG), and DAG (fully oriented).

When the rules alone cannot resolve all undirected edges, an arbitrary orientation is chosen using a min-parents heuristic; the affected arcs are recorded and accessible via choices().

Definition at line 67 of file MeekRules.h.

Constructor & Destructor Documentation

MeekRules()

gum::MeekRules::MeekRules

(

)

default constructor

Definition at line 58 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 61 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

Tries to orient edges incident to xj using Meek rules R1–R4.

Propagates the orientation from a node to its neighbours.

Parameters

graph	the graph (modified in place)
xj	the node whose incident undirected edges are examined

Returns

true if at least one edge was oriented

Definition at line 212 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.addArc(xi, xj);
        _applyMeekRules_(graph, xj);
      }
      if (j_i) {
        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_, and _isOrientable_().

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

Orients all remaining undirected edges, applying Meek rules then a chain heuristic.

Definition at line 196 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_(), and _propagatesOrientationInChainOfRemainingEdges_().

Referenced by propagateToDAG().

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

Returns true if there is a directed path from n1 to n2 (BFS, double arcs ignored).

Definition at line 361 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::List< Val >::front(), gum::Set< Key >::insert(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by _isOrientable_(), _orientDoubleHeadedArcs_(), and _propagatesOrientationInChainOfRemainingEdges_().

Here is the call graph for this function:

Here is the caller graph for this function:

_isOrientable_()

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

staticnodiscardprivate

Returns true if the edge xi–xj can be oriented as xi→xj under Meek rules R1–R3.

Parameters

graph	the graph
xi	candidate tail
xj	candidate head

Definition at line 258 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: orient xi-xj if two non-adjacent parents of xj are both direct undirected
    //     neighbors of xi (classical Meek R3: chains xi-k->xj and xi-l->xj, k not adj l)
    {
      std::vector< NodeId > qualifying;
      for (const auto p: graph.parents(xj)) {
        if (graph.neighbours(xi).contains(p)) { qualifying.push_back(p); }
      }
      for (std::size_t i = 0; i < qualifying.size(); ++i)
        for (std::size_t j = i + 1; j < qualifying.size(); ++j)
          if (!graph.boundary(qualifying[i]).contains(qualifying[j])) {
            // GUM_TRACE("R3(" << xi << "-" << xj << ")")
            return true;
          }
    }
    // R4: orient xi-xj if there is a purely directed path from xi to some node xk,
    //     xk is an undirected neighbor of xj, and xi is not adjacent to xk
    for (const auto xk: graph.neighbours(xj)) {
      if (graph.boundary(xi).contains(xk)) continue;
      if (graph.existsArc(xi, xk) || graph.existsArc(xk, xi)) continue;
      if (_existsDirectedPath_(graph, xi, xk)) {
        // GUM_TRACE("R4(" << xi << "-" << xj << ")")
        return true;
      }
    }
    return false;
  }

References _existsDirectedPath_().

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 )

staticprivate

Resolves double-headed arcs (x→y and y→x simultaneously) to avoid cycles.

Orient double-headed arcs while avoiding cycles.

For each double-headed arc, erases one direction based on existing directed paths; if neither direction creates a cycle, applies the min-parents heuristic.

Parameters

mg	the graph (modified in place)

Definition at line 116 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 (!L.empty()) {
      while (true) {
        bool withdrawFlag_L = false;
        for (auto& arc: ArcSet(L)) {
          const bool tail_head        = _existsDirectedPath_(mg, arc.tail(), arc.head());
          const 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(_selectArcToEraseByMinParents_(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 _existsDirectedPath_(), _selectArcToEraseByMinParents_(), 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

Applies Meek rules R1–R4 exhaustively and returns the resulting graph.

Definition at line 183 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_().

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_ ( MixedGraph & graph )

private

Arbitrarily orients remaining undirected edges when no Meek rule applies.

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

Uses a BFS-based heuristic: picks the node with the most children as a local root and orients edges away from it.

Parameters

graph

the graph (modified in place)

Definition at line 302 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)) {
              essentialGraph.eraseEdge(Edge(n, next));
              if (!_existsDirectedPath_(essentialGraph, next, n)) {
                essentialGraph.addArc(n, next);
                _choices_.emplace_back(n, next);
              } else {
                // n→next would create a cycle; reverse is safe
                essentialGraph.addArc(next, n);
                _choices_.emplace_back(next, n);
              }
            }
          }
        }
        visited.insert(next);
      }
    }
  }

References _applyMeekRules_(), _choices_, _existsDirectedPath_(), 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:

_selectArcToEraseByMinParents_()

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

staticprivate

Returns the arc to erase when resolving a double-headed arc, using a min-parents heuristic.

Prefers to keep the direction whose head already has more parents. Ties are broken by neighbor count.

Parameters

graph	the graph
x	one endpoint
y	the other endpoint

Returns

the arc (x→y or y→x) that should be erased

Definition at line 239 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 {x, y};
    } else if (graph.parents(x).size() > graph.parents(y).size()) {
      return {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 {x, y};
      } else {
        return {y, x};
      }
    }
  }

Referenced by _orientDoubleHeadedArcs_().

Here is the caller graph for this function:

choices()

INLINE const std::vector< Arc > & gum::MeekRules::choices

(

)

const

Returns the arcs for which the algorithm made an arbitrary orientation choice.

An arc is recorded here when no Meek rule could determine its direction and the algorithm had to pick one arbitrarily (e.g. to break a double-headed arc or to orient a residual undirected edge).

Returns

the list of arbitrarily chosen arcs, in order of selection

Definition at line 57 of file MeekRules_inl.h.

{ return _choices_; }

References _choices_.

propagate()

MixedGraph gum::MeekRules::propagate

(

const MixedGraph &

mg

)

Applies Meek rules to a MixedGraph and returns the partially oriented result.

Propagates MeekRules in a MixedGraph.

Meek rules R1–R4 are applied exhaustively; remaining undirected edges are left as-is. Double-headed arcs may appear in the output if two rules fire in opposite directions on the same edge.

Parameters

mg	the mixed graph to orient (arcs and undirected edges, no double-headed arcs)

Returns

the partially oriented graph; may still contain undirected edges or double-headed arcs

Definition at line 64 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

)

Applies Meek rules and returns a CPDAG (completed PDAG).

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

Meek rules R1–R4 are applied exhaustively, then any double-headed arcs are resolved using a min-parents heuristic to avoid cycles. The result is a valid PDAG with no double-headed arcs.

Parameters

mg	the mixed graph to orient

Returns

a PDAG representing the essential graph

Definition at line 70 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(), and gum::NodeGraphPart::addNodeWithId().

Here is the call graph for this function:

propagateToDAG()

DAG gum::MeekRules::propagateToDAG

(

const MixedGraph &

mg

)

Applies Meek rules and completes the result into a DAG.

Propagates the orientation of a MixedGraph and return a DAG.

Meek rules R1–R4 are applied, remaining undirected edges are arbitrarily oriented, and double-headed arcs are resolved to ensure an acyclic result.

Parameters

mg	the mixed graph to orient

Returns

a DAG consistent with the orientations implied by the input

Definition at line 93 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(), and gum::NodeGraphPart::addNodeWithId().

Here is the call graph for this function:

Member Data Documentation

_choices_

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

private

Definition at line 121 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
• agrum/base/graphs/algorithms/MeekRules_inl.h