gum::graph Namespace Reference

Namespaces
namespace	detail

Functions
template<GUM_DiGraphable G>
NodeSet	requisiteNodes (const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
	Returns the Shachter-requisite nodes for query given evidence.
template<GUM_DiGraphable G>
NodeSet	dConnected (const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
	Returns all nodes d-connected to query given evidence.
template<GUM_DiGraphable G, bool CollectAll>
NodeSet	_bayesBall_ (const G &g, const NodeSet &query, const NodeSet &Zhard, const NodeSet &Zsoft)
template<GUM_DiGraphable G>
Sequence< NodeId >	topologicalOrder (const G &g)
	Returns a topological ordering of the nodes of g (Kahn's algorithm).
template<GUM_UndiGraphable G>
bool	hasUndirectedCycle (const G &g)
	Returns true if g contains at least one undirected cycle.
template<GUM_DiGraphable G>
DAG	markovBlanket (const G &g, NodeId node, int level=1)
	Returns the level-level Markov blanket of node in g as a DAG.
template<GUM_DiGraphable G>
NodeSet	minimalCondSet (const G &g, NodeId target, const NodeSet &soids)
	Returns the minimal subset of soids that d-connects target.
template<GUM_DiGraphable G>
NodeSet	minimalCondSet (const G &g, const NodeSet &targets, const NodeSet &soids)
	Returns the minimal subset of soids that d-connects all targets.
template<GUM_DiGraphable G>
void	_mcsVisitUp_ (const G &g, NodeId node, const NodeSet &soids, NodeSet &minimal, NodeSet &visitedUp, NodeSet &visitedDn)
template<GUM_DiGraphable G>
void	_mcsVisitDn_ (const G &g, NodeId node, const NodeSet &soids, NodeSet &minimal, NodeSet &visitedUp, NodeSet &visitedDn)
template<GUM_DiGraphable G>
UndiGraph	moralGraph (const G &g)
	Returns the moral graph of g.
template<GUM_DiGraphable G>
UndiGraph	moralizedAncestralGraph (const G &g, const NodeSet &query)
	Returns the moralized ancestral graph of query in g.
template<GUM_DiGraphable G>
std::optional< std::vector< NodeId > >	directedPath (const G &g, NodeId n1, NodeId n2)
	Shortest directed path from n1 to n2 (BFS, arc direction).
template<GUM_DiGraphable G>
std::optional< std::vector< NodeId > >	directedUnorientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest path from n1 to n2 ignoring arc orientation (BFS).
template<GUM_DiGraphable G>
bool	hasDirectedPath (const G &g, NodeId from, NodeId to)
	Returns true if there is a directed path from from to to.
template<GUM_UndiGraphable G>
std::optional< std::vector< NodeId > >	undirectedPath (const G &g, NodeId n1, NodeId n2)
	Shortest undirected path from n1 to n2 (BFS).
template<GUM_UndiGraphable G>
bool	hasUndirectedPath (const G &g, NodeId n1, NodeId n2)
	Returns true if an undirected path exists between n1 and n2.
template<GUM_UndiGraphable G>
bool	hasUndirectedPath (const G &g, NodeId n1, NodeId n2, const NodeSet &except)
	Returns true if an undirected path from n1 to n2 exists that avoids all nodes in except.
template<GUM_UndiGraphable G>
bool	hasUndirectedPath (const G &g, const NodeSet &n1, const NodeSet &n2, const NodeSet &except)
	Returns true if an undirected path exists from any node in n1 to any node in n2, avoiding nodes in except.
template<GUM_MixedGraphable G>
std::optional< std::vector< NodeId > >	mixedOrientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest mixed-oriented path from n1 to n2.
template<GUM_MixedGraphable G>
bool	hasMixedOrientedPath (const G &g, NodeId n1, NodeId n2)
	Returns true if a mixed-oriented path from n1 to n2 exists.
template<GUM_MixedGraphable G>
std::optional< std::vector< NodeId > >	mixedUnorientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest path ignoring all orientations in a mixed graph.
template<GUM_DiGraphable G>
NodeSet	ancestors (const G &g, NodeId id)
	Returns the set of all ancestors of id (nodes from which id is reachable following arc direction).
template<GUM_DiGraphable G>
NodeSet	descendants (const G &g, NodeId id)
	Returns the set of all descendants of id (nodes reachable from id following arc direction).
template<GUM_DiGraphable G>
NodeSet	family (const G &g, NodeId id)
	Returns the family of id : { id } ∪ parents(id).
template<GUM_DiGraphable G>
NodeSet	family (const G &g, const NodeSet &ids)
	Returns the union of families of all nodes in ids.
template<GUM_UndiGraphable G>
NodeProperty< NodeId >	chainComponents (const G &g)
	Returns a node-to-component-id mapping for the chain components of g (connected components of the edge-only subgraph).
template<GUM_NodeGraphable G>
NodeProperty< NodeId >	connectedComponents (const G &g)
	Returns a node-to-component-id mapping for the (weakly) connected components of g.
template<GUM_UndiGraphable G>
bool	areConnected (const G &g, const NodeSet &A, const NodeSet &B)
	Returns true iff some node in A can reach some node in B via undirected edges.
template<GUM_MixedGraphable G>
NodeSet	chainComponent (const G &g, NodeId node)
	Returns the chain component of node in g.
template<GUM_MixedGraphable G>
NodeSet	boundary (const G &g, NodeId node)
	Returns the boundary of node: neighbours ∪ parents ∪ children.
template<GUM_DiGraphable G>
bool	dSeparated (const G &g, NodeId X, NodeId Y, const NodeSet &Z)
	Returns true iff X and Y are d-separated by Z in g.
template<GUM_DiGraphable G>
bool	dSeparated (const G &g, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Returns true iff every node in X is d-separated from every node in Y by Z in g.
template<GUM_MixedGraphable G>
bool	cSeparated (const G &g, NodeId X, NodeId Y, const NodeSet &Z)
	Returns true iff X and Y are c-separated by Z in g.
template<GUM_MixedGraphable G>
bool	cSeparated (const G &g, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Returns true iff X and Y are c-separated by Z in g.

Function Documentation

_bayesBall_()

template<GUM_DiGraphable G, bool CollectAll>

NodeSet gum::graph::_bayesBall_	(	const G &	g,
		const NodeSet &	query,
		const NodeSet &	Zhard,
		const NodeSet &	Zsoft )

Definition at line 50 of file bayesBall_tpl.h.

                                                                                                {
    NodeSet result;
 
    static constexpr std::pair< bool, bool > empty_mark{false, false};
    NodeProperty< std::pair< bool, bool > >  marks(g.size());
 
    List< std::pair< NodeId, bool > > to_visit;
    for (const auto node: query)
      to_visit.insert(std::pair{node, true});
 
    while (!to_visit.empty()) {
      const NodeId node       = to_visit.front().first;
      const bool   from_child = to_visit.front().second;
      to_visit.popFront();
 
      auto& [top, bot] = marks.getWithDefault(node, empty_mark);
 
      if (from_child) {
        result.insert(node);                // always requisite on upward visit
        if (Zhard.exists(node)) continue;   // hard evidence blocks upward
 
        if (!top) {
          top = true;
          for (const auto par: g.parents(node))
            to_visit.insert(std::pair{par, true});
        }
        if (!bot) {
          bot = true;
          for (const auto chi: g.children(node))
            to_visit.insert(std::pair{chi, false});
        }
 
      } else {
        if constexpr (CollectAll) result.insert(node);   // dConnected: all visits
 
        const bool is_hard = Zhard.exists(node);
        const bool is_ev   = is_hard || Zsoft.exists(node);
 
        if (is_ev && !top) {
          top = true;
          if constexpr (!CollectAll) result.insert(node);   // requisiteNodes: collider only
          for (const auto par: g.parents(node))
            to_visit.insert(std::pair{par, true});
        }
        if (!is_hard && !bot) {
          bot = true;
          for (const auto chi: g.children(node))
            to_visit.insert(std::pair{chi, false});
        }
      }
    }
 
    return result;
  }

References gum::List< Val >::empty(), gum::Set< Key >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::getWithDefault(), gum::List< Val >::insert(), gum::Set< Key >::insert(), and gum::List< Val >::popFront().

Referenced by dConnected(), and requisiteNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

_mcsVisitDn_()

template<GUM_DiGraphable G>

void gum::graph::_mcsVisitDn_	(	const G &	g,
		NodeId	node,
		const NodeSet &	soids,
		NodeSet &	minimal,
		NodeSet &	visitedUp,
		NodeSet &	visitedDn )

Definition at line 69 of file minimalConditioningSet_tpl.h.

                                              {
    if (visitedDn.contains(node)) return;
    visitedDn << node;
 
    if (soids.contains(node)) {
      minimal << node;
      for (const auto par: g.parents(node))
        _mcsVisitUp_(g, par, soids, minimal, visitedUp, visitedDn);
    } else {
      for (const auto chi: g.children(node))
        _mcsVisitDn_(g, chi, soids, minimal, visitedUp, visitedDn);
    }
  }

References _mcsVisitDn_(), _mcsVisitUp_(), and gum::Set< Key >::contains().

Referenced by _mcsVisitDn_(), _mcsVisitUp_(), and minimalCondSet().

Here is the call graph for this function:

Here is the caller graph for this function:

_mcsVisitUp_()

template<GUM_DiGraphable G>

void gum::graph::_mcsVisitUp_	(	const G &	g,
		NodeId	node,
		const NodeSet &	soids,
		NodeSet &	minimal,
		NodeSet &	visitedUp,
		NodeSet &	visitedDn )

Definition at line 49 of file minimalConditioningSet_tpl.h.

                                              {
    if (visitedUp.contains(node)) return;
    visitedUp << node;
 
    if (soids.contains(node)) {
      minimal << node;
    } else {
      for (const auto par: g.parents(node))
        _mcsVisitUp_(g, par, soids, minimal, visitedUp, visitedDn);
      for (const auto chi: g.children(node))
        _mcsVisitDn_(g, chi, soids, minimal, visitedUp, visitedDn);
    }
  }

References _mcsVisitDn_(), _mcsVisitUp_(), and gum::Set< Key >::contains().

Referenced by _mcsVisitDn_(), _mcsVisitUp_(), and minimalCondSet().

Here is the call graph for this function:

Here is the caller graph for this function:

ancestors()

template<GUM_DiGraphable G>

NodeSet gum::graph::ancestors	(	const G &	g,
		NodeId	id )

Returns the set of all ancestors of id (nodes from which id is reachable following arc direction).

id not included.

Definition at line 57 of file reachability_tpl.h.

                                           {
    NodeSet res;
    NodeSet frontier = g.parents(id);
 
    while (!frontier.empty()) {
      const NodeId current = *frontier.begin();
      frontier.erase(current);
      res.insert(current);
      for (const auto p: g.parents(current))
        if (!res.contains(p)) frontier.insert(p);
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Referenced by gum::DiGraph::ancestors().

Here is the call graph for this function:

Here is the caller graph for this function:

areConnected()

template<GUM_UndiGraphable G>

bool gum::graph::areConnected	(	const G &	g,
		const NodeSet &	A,
		const NodeSet &	B )

Returns true iff some node in A can reach some node in B via undirected edges.

Returns false immediately if A or B is empty, or if both sets share at least one node (trivially connected).

Template Parameters

G	Any GUM_UndiGraphable graph.

Parameters

g	The undirected (or mixed) graph — only edges are traversed.
A	First node set.
B	Second node set.

Returns

true iff there exists an undirected path between some a ∈ A and some b ∈ B in g.

Definition at line 156 of file reachability_tpl.h.

                                                                    {
    if (A.empty() || B.empty()) return false;
    if (!(A * B).empty()) return true;
 
    NodeSet visited;
    NodeSet frontier = A;
    for (const auto s: A)
      visited.insert(s);
 
    while (!frontier.empty()) {
      const NodeId u = *frontier.begin();
      frontier.erase(u);
      for (const auto v: g.neighbours(u)) {
        if (visited.exists(v)) continue;
        if (B.contains(v)) return true;
        visited.insert(v);
        frontier.insert(v);
      }
    }
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::exists(), and gum::Set< Key >::insert().

Referenced by gum::Separation::anyUndirectedConnection().

Here is the call graph for this function:

Here is the caller graph for this function:

boundary()

template<GUM_MixedGraphable G>

NodeSet gum::graph::boundary	(	const G &	g,
		NodeId	node )

Returns the boundary of node: neighbours ∪ parents ∪ children.

Definition at line 195 of file reachability_tpl.h.

                                            {
    return g.neighbours(node) + g.parents(node) + g.children(node);
  }

Referenced by gum::MixedGraph::boundary().

Here is the caller graph for this function:

chainComponent()

template<GUM_MixedGraphable G>

NodeSet gum::graph::chainComponent	(	const G &	g,
		NodeId	node )

Returns the chain component of node in g.

The chain component is the connected component of the undirected subgraph (edges only) containing node. Arc orientations are ignored.

Definition at line 179 of file reachability_tpl.h.

                                                  {
    NodeSet res;
    NodeSet frontier{node};
 
    while (!frontier.empty()) {
      const NodeId n = *frontier.begin();
      frontier.erase(n);
      res.insert(n);
      for (const auto nei: g.neighbours(n))
        if (!res.contains(nei)) frontier.insert(nei);
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Referenced by gum::MixedGraph::chainComponent().

Here is the call graph for this function:

Here is the caller graph for this function:

chainComponents()

template<GUM_UndiGraphable G>

NodeProperty< NodeId > gum::graph::chainComponents

(

const G &

g

)

Returns a node-to-component-id mapping for the chain components of g (connected components of the edge-only subgraph).

Arc orientations are ignored; only edges are traversed. Component ids are assigned in order of first encounter.

Definition at line 103 of file reachability_tpl.h.

                                                     {
    NodeProperty< NodeId > res;
    NodeId                 numCC = 0;
 
    for (const auto node: g.nodes()) {
      if (res.exists(node)) continue;
 
      NodeSet frontier{node};
      while (!frontier.empty()) {
        const NodeId current = *frontier.begin();
        frontier.erase(current);
        res.insert(current, numCC);
        for (const auto nei: g.neighbours(current))
          if (!res.exists(nei)) frontier.insert(nei);
      }
      ++numCC;
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::HashTable< Key, Val >::exists(), gum::HashTable< Key, Val >::insert(), and gum::Set< Key >::insert().

Referenced by gum::MixedGraph::chainComponents(), and gum::UndiGraph::chainComponents().

Here is the call graph for this function:

Here is the caller graph for this function:

connectedComponents()

template<GUM_NodeGraphable G>

NodeProperty< NodeId > gum::graph::connectedComponents

(

const G &

g

)

Returns a node-to-component-id mapping for the (weakly) connected components of g.

For directed graphs, arcs are treated as undirected (weak connectivity). For mixed graphs, both edges and arcs are traversed. Component ids are assigned in order of first encounter.

Template Parameters

G	Must satisfy GUM_DiGraphable, GUM_UndiGraphable, or both.

Definition at line 125 of file reachability_tpl.h.

                                                         {
    NodeProperty< NodeId > res;
    NodeId                 numCC = 0;
 
    for (const auto node: g.nodes()) {
      if (res.exists(node)) continue;
 
      NodeSet frontier{node};
      while (!frontier.empty()) {
        const NodeId current = *frontier.begin();
        frontier.erase(current);
        res.insert(current, numCC);
 
        if constexpr (GUM_DiGraphable< G >) {
          for (const auto n: g.parents(current))
            if (!res.exists(n)) frontier.insert(n);
          for (const auto n: g.children(current))
            if (!res.exists(n)) frontier.insert(n);
        }
        if constexpr (GUM_UndiGraphable< G >) {
          for (const auto n: g.neighbours(current))
            if (!res.exists(n)) frontier.insert(n);
        }
      }
      ++numCC;
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::HashTable< Key, Val >::exists(), gum::HashTable< Key, Val >::insert(), and gum::Set< Key >::insert().

Referenced by gum::DiGraph::connectedComponents(), gum::MixedGraph::connectedComponents(), and gum::UndiGraph::connectedComponents().

Here is the call graph for this function:

Here is the caller graph for this function:

cSeparated() [1/2]

template<GUM_MixedGraphable G>

bool gum::graph::cSeparated	(	const G &	g,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

Returns true iff X and Y are c-separated by Z in g.

Set-valued version: c-separation holds iff every node in X is disconnected from every node in Y after moralization and removal of Z.

Template Parameters

G	Any GUM_MixedGraphable graph (typically a PDAG or chain graph).

Parameters

g	The mixed graph.
X	Source node set (must be disjoint from Y).
Y	Target node set (must be disjoint from X).
Z	Conditioning set.

Returns

true if X ⊥ Y | Z in the c-separation sense.

Exceptions

InvalidArgument

if X and Y are not disjoint.

Definition at line 73 of file separation_tpl.h.

                                                                                    {
    if (!(X * Y).empty()) GUM_ERROR(InvalidArgument, "NodeSets X and Y must be disjoint.")
 
    NodeSet query{Z};
    query += X;
    query += Y;
    auto moral = moralizedAncestralGraph(g, query);
    for (const auto node: Z)
      if (moral.existsNode(node)) moral.eraseNode(node);
 
    const auto cc = moral.chainComponents();
 
    NodeSet Xcc, Ycc;
    for (const auto node: X)
      if (moral.existsNode(node)) Xcc.insert(cc[node]);
    for (const auto node: Y)
      if (moral.existsNode(node)) Ycc.insert(cc[node]);
 
    return (Xcc * Ycc).empty();
  }

References GUM_ERROR, gum::Set< Key >::insert(), and moralizedAncestralGraph().

Here is the call graph for this function:

cSeparated() [2/2]

template<GUM_MixedGraphable G>

bool gum::graph::cSeparated	(	const G &	g,
		NodeId	X,
		NodeId	Y,
		const NodeSet &	Z )

Returns true iff X and Y are c-separated by Z in g.

C-separation generalizes d-separation to mixed graphs (PDAGs / chain graphs). The ancestral subgraph is built by following arcs backward and undirected edges bidirectionally; moralization then marries the parents of each chain component rather than each individual node.

Warning

C-separation is well-defined for any PDAG but is statistically meaningful only for chain graphs (PDAGs with no partially directed cycles).

Template Parameters

G	Any GUM_MixedGraphable graph (typically a PDAG or chain graph).

Parameters

g	The mixed graph.
X	Source node.
Y	Target node.
Z	Conditioning set.

Returns

true if X ⊥ Y | Z in the c-separation sense.

Definition at line 62 of file separation_tpl.h.

                                                                    {
    NodeSet query{Z};
    query.insert(X);
    query.insert(Y);
    auto moral = moralizedAncestralGraph(g, query);
    for (const auto node: Z)
      if (moral.existsNode(node)) moral.eraseNode(node);
    return !moral.hasUndirectedPath(X, Y);
  }

References gum::Set< Key >::insert(), and moralizedAncestralGraph().

Referenced by gum::PDAG::cSeparation(), and gum::PDAG::cSeparation().

Here is the call graph for this function:

Here is the caller graph for this function:

dConnected()

template<GUM_DiGraphable G>

NodeSet gum::graph::dConnected	(	const G &	g,
		const NodeSet &	query,
		const NodeSet &	Zhard = NodeSet(),
		const NodeSet &	Zsoft = NodeSet() )

Returns all nodes d-connected to query given evidence.

Runs the Bayes Ball traversal and collects every visited node (upward or downward), yielding the full d-connected set. Suitable for d-separation testing:

X ⊥ Y | Z iff Y ∉ dConnected(g, {X}, Z)

Template Parameters

G	Any directed graph satisfying GUM_DiGraphable (DAG, DiGraph, …).

Parameters

g	The directed graph.
query	Source nodes from which the ball is launched.
Zhard	Hard-evidence nodes (conditioning set for d-separation).
Zsoft	Soft-evidence nodes: activate colliders without blocking.

Returns

NodeSet of all nodes d-connected to query given the evidence.

Definition at line 112 of file bayesBall_tpl.h.

                                                                                                   {
    return _bayesBall_< G, true >(g, query, Zhard, Zsoft);
  }

References _bayesBall_().

Referenced by dSeparated(), and dSeparated().

Here is the call graph for this function:

Here is the caller graph for this function:

descendants()

template<GUM_DiGraphable G>

NodeSet gum::graph::descendants	(	const G &	g,
		NodeId	id )

Returns the set of all descendants of id (nodes reachable from id following arc direction).

id not included.

Definition at line 73 of file reachability_tpl.h.

                                             {
    NodeSet res;
    NodeSet frontier = g.children(id);
 
    while (!frontier.empty()) {
      const NodeId current = *frontier.begin();
      frontier.erase(current);
      res.insert(current);
      for (const auto c: g.children(current))
        if (!res.contains(c)) frontier.insert(c);
    }
 
    return res;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Referenced by gum::DiGraph::descendants().

Here is the call graph for this function:

Here is the caller graph for this function:

directedPath()

template<GUM_DiGraphable G>

std::optional< std::vector< NodeId > > gum::graph::directedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Shortest directed path from n1 to n2 (BFS, arc direction).

Returns the sequence of nodes [n1, …, n2], or std::nullopt if no directed path exists.

Definition at line 65 of file pathFinding_tpl.h.

                                                                                    {
    List< NodeId > fifo;
    fifo.pushBack(n2);
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto n: g.parents(current)) {
        if (mark.exists(n)) continue;
        mark.insert(n, current);
        if (n == n1) return detail::reconstructPath(mark, n1, n2);
        fifo.pushBack(n);
      }
    }
 
    return std::nullopt;
  }

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), gum::List< Val >::pushBack(), and gum::graph::detail::reconstructPath().

Referenced by gum::DiGraph::directedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

directedUnorientedPath()

template<GUM_DiGraphable G>

std::optional< std::vector< NodeId > > gum::graph::directedUnorientedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Shortest path from n1 to n2 ignoring arc orientation (BFS).

Traverses both parents and children — shortest path in the skeleton. Returns std::nullopt if no path exists.

Definition at line 86 of file pathFinding_tpl.h.

                                                                                              {
    List< NodeId > fifo;
    fifo.pushBack(n2);
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    auto tryVisit = [&](NodeId n, NodeId from) -> bool {
      if (mark.exists(n)) return false;
      mark.insert(n, from);
      if (n == n1) return true;
      fifo.pushBack(n);
      return false;
    };
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto n: g.parents(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
      for (const auto n: g.children(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
    }
 
    return std::nullopt;
  }

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), gum::List< Val >::pushBack(), and gum::graph::detail::reconstructPath().

Referenced by gum::DiGraph::directedUnorientedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

dSeparated() [1/2]

template<GUM_DiGraphable G>

bool gum::graph::dSeparated	(	const G &	g,
		const NodeSet &	X,
		const NodeSet &	Y,
		const NodeSet &	Z )

Returns true iff every node in X is d-separated from every node in Y by Z in g.

Implemented via the Bayes Ball algorithm (O(n+e)): X ⊥ Y | Z iff requisiteNodes(g, X, Z) and Y are disjoint.

Template Parameters

G	Any GUM_DiGraphable graph (typically a DAG).

Parameters

g	The directed graph.
X	Source node set (must be disjoint from Y).
Y	Target node set (must be disjoint from X).
Z	Conditioning set (hard evidence).

Returns

true if X ⊥ Y | Z in the d-separation sense.

Exceptions

InvalidArgument

if X and Y are not disjoint.

Definition at line 56 of file separation_tpl.h.

                                                                                    {
    if (!(X * Y).empty()) GUM_ERROR(InvalidArgument, "NodeSets X and Y must be disjoint.")
    return (graph::dConnected(g, X, Z) * Y).empty();
  }

References dConnected(), and GUM_ERROR.

Here is the call graph for this function:

dSeparated() [2/2]

template<GUM_DiGraphable G>

bool gum::graph::dSeparated	(	const G &	g,
		NodeId	X,
		NodeId	Y,
		const NodeSet &	Z )

Returns true iff X and Y are d-separated by Z in g.

Implemented via the Bayes Ball algorithm (O(n+e)): X ⊥ Y | Z iff Y is not d-connected to X given Z (i.e. Y ∉ requisiteNodes(g, {X}, Z)).

Template Parameters

G	Any GUM_DiGraphable graph (typically a DAG).

Parameters

g	The directed graph.
X	Source node.
Y	Target node.
Z	Conditioning set (hard evidence).

Returns

true if X ⊥ Y | Z in the d-separation sense.

Definition at line 49 of file separation_tpl.h.

                                                                    {
    NodeSet qX;
    qX.insert(X);
    return !graph::dConnected(g, qX, Z).exists(Y);
  }

References dConnected(), gum::Set< Key >::exists(), and gum::Set< Key >::insert().

Referenced by gum::DAG::dSeparation(), and gum::DAG::dSeparation().

Here is the call graph for this function:

Here is the caller graph for this function:

family() [1/2]

template<GUM_DiGraphable G>

NodeSet gum::graph::family	(	const G &	g,
		const NodeSet &	ids )

Returns the union of families of all nodes in ids.

Definition at line 95 of file reachability_tpl.h.

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

References family().

Here is the call graph for this function:

family() [2/2]

template<GUM_DiGraphable G>

NodeSet gum::graph::family	(	const G &	g,
		NodeId	id )

Returns the family of id : { id } ∪ parents(id).

Definition at line 89 of file reachability_tpl.h.

                                        {
    NodeSet res{id};
    return res + g.parents(id);
  }

Referenced by gum::DiGraph::family(), gum::DiGraph::family(), and family().

Here is the caller graph for this function:

hasDirectedPath()

template<GUM_DiGraphable G>

bool gum::graph::hasDirectedPath	(	const G &	g,
		NodeId	from,
		NodeId	to )

Returns true if there is a directed path from from to to.

Returns false immediately if from does not exist in g.

Definition at line 113 of file pathFinding_tpl.h.

                                                           {
    if (!g.existsNode(from)) return false;
 
    List< NodeId > fifo;
    fifo.pushBack(from);
    NodeSet marked{from};
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto chi: g.children(current)) {
        if (chi == to) return true;
        if (!marked.contains(chi)) {
          fifo.pushBack(chi);
          marked.insert(chi);
        }
      }
    }
 
    return false;
  }

References gum::Set< Key >::contains(), gum::List< Val >::empty(), gum::List< Val >::front(), gum::Set< Key >::insert(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by gum::DiGraph::hasDirectedPath(), and gum::learning::StructuralConstraintDAG::setGraphAlone().

Here is the call graph for this function:

Here is the caller graph for this function:

hasMixedOrientedPath()

template<GUM_MixedGraphable G>

bool gum::graph::hasMixedOrientedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Returns true if a mixed-oriented path from n1 to n2 exists.

Definition at line 237 of file pathFinding_tpl.h.

                                                              {
    return mixedOrientedPath(g, n1, n2).has_value();
  }

References mixedOrientedPath().

Referenced by gum::MixedGraph::hasMixedOrientedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

hasUndirectedCycle()

template<GUM_UndiGraphable G>

bool gum::graph::hasUndirectedCycle

(

const G &

g

)

Returns true if g contains at least one undirected cycle.

Uses BFS per connected component, tracking the predecessor to avoid treating the edge we came from as a back-edge.

Definition at line 88 of file cycleDetection_tpl.h.

                                      {
    NodeProperty< bool > visited;
    for (const auto node: g.nodes())
      visited.insert(node, false);
 
    for (const auto node: g.nodes()) {
      if (visited[node]) continue;
      visited[node] = true;
 
      List< std::pair< NodeId, NodeId > > frontier;
      frontier.pushBack({node, node});
 
      while (!frontier.empty()) {
        const auto [current, from] = frontier.front();
        frontier.popFront();
 
        for (const auto next: g.neighbours(current)) {
          if (next == from) continue;
          if (visited[next]) return true;
          visited[next] = true;
          frontier.pushBack({next, current});
        }
      }
    }
 
    return false;
  }

References gum::List< Val >::empty(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by gum::UndiGraph::hasUndirectedCycle().

Here is the call graph for this function:

Here is the caller graph for this function:

hasUndirectedPath() [1/3]

template<GUM_UndiGraphable G>

bool gum::graph::hasUndirectedPath	(	const G &	g,
		const NodeSet &	n1,
		const NodeSet &	n2,
		const NodeSet &	except )

Returns true if an undirected path exists from any node in n1 to any node in n2, avoiding nodes in except.

Definition at line 193 of file pathFinding_tpl.h.

                                                                                                  {
    NodeSet visited;
    NodeSet frontier(n1);
 
    while (!frontier.empty()) {
      const NodeId current = *frontier.begin();
      if (n2.contains(current)) return true;
      frontier.erase(current);
      visited.insert(current);
      for (const auto next: g.neighbours(current))
        if (!visited.contains(next) && !except.contains(next)) frontier.insert(next);
    }
 
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Here is the call graph for this function:

hasUndirectedPath() [2/3]

template<GUM_UndiGraphable G>

bool gum::graph::hasUndirectedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Returns true if an undirected path exists between n1 and n2.

Definition at line 157 of file pathFinding_tpl.h.

                                                           {
    NodeSet visited;
    NodeSet frontier{n1};
 
    while (!frontier.empty()) {
      const NodeId current = *frontier.begin();
      if (current == n2) return true;
      frontier.erase(current);
      visited.insert(current);
      for (const auto next: g.neighbours(current))
        if (!visited.contains(next)) frontier.insert(next);
    }
 
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Referenced by gum::UndiGraph::hasUndirectedPath(), gum::UndiGraph::hasUndirectedPath(), and gum::UndiGraph::hasUndirectedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

hasUndirectedPath() [3/3]

template<GUM_UndiGraphable G>

bool gum::graph::hasUndirectedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2,
		const NodeSet &	except )

Returns true if an undirected path from n1 to n2 exists that avoids all nodes in except.

Definition at line 174 of file pathFinding_tpl.h.

                                                                                  {
    if (except.contains(n2)) return false;
 
    NodeSet visited;
    NodeSet frontier{n1};
 
    while (!frontier.empty()) {
      const NodeId current = *frontier.begin();
      if (current == n2) return true;
      frontier.erase(current);
      visited.insert(current);
      for (const auto next: g.neighbours(current))
        if (!visited.contains(next) && !except.contains(next)) frontier.insert(next);
    }
 
    return false;
  }

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Here is the call graph for this function:

markovBlanket()

template<GUM_DiGraphable G>

DAG gum::graph::markovBlanket	(	const G &	g,
		NodeId	node,
		int	level = 1 )

Returns the level-level Markov blanket of node in g as a DAG.

The level-1 Markov blanket contains:

• all parents of node,
• all children of node,
• all co-parents (other parents of each child of node).

For level k > 1, the same construction is applied iteratively to all newly added nodes at each level, stopping early if no new node is found.

Template Parameters

G	Any GUM_DiGraphable graph (typically a DAG or BayesNet).

Parameters

g	The source directed graph.
node	The node whose Markov blanket is computed.
level	Depth of the blanket (must be >= 1).

Returns

A DAG containing the structural Markov blanket.

Exceptions

InvalidArgument

if node does not exist in g, or level < 1.

Definition at line 49 of file markovBlanket_tpl.h.

                                                        {
    if (!g.exists(node))
      GUM_ERROR(InvalidArgument, "Node " << node << " does not exist in the graph.")
    if (level < 1) GUM_ERROR(InvalidArgument, "level must be >= 1")
 
    DAG mb;
 
    auto step = [&](NodeId n, NodeSet& next_frontier) {
      for (const auto par: g.parents(n)) {
        if (!mb.existsNode(par)) {
          mb.addNodeWithId(par);
          next_frontier.insert(par);
        }
        if (!mb.existsArc(par, n)) mb.addArc(par, n);
      }
      for (const auto chi: g.children(n)) {
        if (!mb.existsNode(chi)) {
          mb.addNodeWithId(chi);
          next_frontier.insert(chi);
        }
        if (!mb.existsArc(n, chi)) mb.addArc(n, chi);
        for (const auto opar: g.parents(chi)) {
          if (opar == n) continue;
          if (!mb.existsNode(opar)) {
            mb.addNodeWithId(opar);
            next_frontier.insert(opar);
          }
          if (!mb.existsArc(opar, chi)) mb.addArc(opar, chi);
        }
      }
    };
 
    mb.addNodeWithId(node);
    NodeSet frontier;
    step(node, frontier);
 
    for (int lv = 1; lv < level && !frontier.empty(); ++lv) {
      NodeSet next;
      for (const auto n: frontier)
        step(n, next);
      frontier = std::move(next);
    }
 
    return mb;
  }

References gum::DAG::addArc(), gum::NodeGraphPart::addNodeWithId(), gum::Set< Key >::empty(), gum::ArcGraphPart::existsArc(), gum::NodeGraphPart::existsNode(), and GUM_ERROR.

Referenced by gum::MarkovBlanket::MarkovBlanket().

Here is the call graph for this function:

Here is the caller graph for this function:

minimalCondSet() [1/2]

template<GUM_DiGraphable G>

NodeSet gum::graph::minimalCondSet	(	const G &	g,
		const NodeSet &	targets,
		const NodeSet &	soids )

Returns the minimal subset of soids that d-connects all targets.

Union of minimalCondSet(g, t, soids) over each t ∈ targets.

Template Parameters

G	Any GUM_DiGraphable graph.

Definition at line 105 of file minimalConditioningSet_tpl.h.

                                                                                   {
    NodeSet res;
    for (const auto node: targets)
      res += minimalCondSet(g, node, soids);
    return res;
  }

References minimalCondSet().

Here is the call graph for this function:

minimalCondSet() [2/2]

template<GUM_DiGraphable G>

NodeSet gum::graph::minimalCondSet	(	const G &	g,
		NodeId	target,
		const NodeSet &	soids )

Returns the minimal subset of soids that d-connects target.

Computes the smallest S ⊆ soids such that P(target | soids) = P(target | S) in the graph g.

Template Parameters

G	Any GUM_DiGraphable graph.

Parameters

g	The directed graph.
target	The query node.
soids	The candidate conditioning set.

Returns

The minimal conditioning subset.

Definition at line 89 of file minimalConditioningSet_tpl.h.

                                                                          {
    if (soids.contains(target)) return NodeSet({target});
 
    NodeSet res, visitedUp, visitedDn;
    visitedUp << target;
    visitedDn << target;
 
    for (const auto par: g.parents(target))
      _mcsVisitUp_(g, par, soids, res, visitedUp, visitedDn);
    for (const auto chi: g.children(target))
      _mcsVisitDn_(g, chi, soids, res, visitedUp, visitedDn);
 
    return res;
  }

References _mcsVisitDn_(), _mcsVisitUp_(), and gum::Set< Key >::contains().

Referenced by gum::DAG::minimalCondSet(), gum::DAG::minimalCondSet(), and minimalCondSet().

Here is the call graph for this function:

Here is the caller graph for this function:

mixedOrientedPath()

template<GUM_MixedGraphable G>

std::optional< std::vector< NodeId > > gum::graph::mixedOrientedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Shortest mixed-oriented path from n1 to n2.

Follows arcs forward and edges in both directions. Returns std::nullopt if no such path exists.

Definition at line 210 of file pathFinding_tpl.h.

                                                                                         {
    List< NodeId > fifo;
    fifo.pushBack(n2);
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    auto tryVisit = [&](NodeId n, NodeId from) -> bool {
      if (mark.exists(n)) return false;
      mark.insert(n, from);
      if (n == n1) return true;
      fifo.pushBack(n);
      return false;
    };
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto n: g.neighbours(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
      for (const auto n: g.parents(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
    }
 
    return std::nullopt;
  }

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), gum::List< Val >::pushBack(), and gum::graph::detail::reconstructPath().

Referenced by hasMixedOrientedPath(), and gum::MixedGraph::mixedOrientedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

mixedUnorientedPath()

template<GUM_MixedGraphable G>

std::optional< std::vector< NodeId > > gum::graph::mixedUnorientedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Shortest path ignoring all orientations in a mixed graph.

Traverses edges (both directions), parents, and children. Returns std::nullopt if no path exists.

Definition at line 242 of file pathFinding_tpl.h.

                                                                                           {
    List< NodeId > fifo;
    fifo.pushBack(n2);
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    auto tryVisit = [&](NodeId n, NodeId from) -> bool {
      if (mark.exists(n)) return false;
      mark.insert(n, from);
      if (n == n1) return true;
      fifo.pushBack(n);
      return false;
    };
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto n: g.neighbours(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
      for (const auto n: g.parents(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
      for (const auto n: g.children(current))
        if (tryVisit(n, current)) return detail::reconstructPath(mark, n1, n2);
    }
 
    return std::nullopt;
  }

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), gum::List< Val >::pushBack(), and gum::graph::detail::reconstructPath().

Referenced by gum::MixedGraph::mixedUnorientedPath().

Here is the call graph for this function:

Here is the caller graph for this function:

moralGraph()

template<GUM_DiGraphable G>

UndiGraph gum::graph::moralGraph

(

const G &

g

)

Returns the moral graph of g.

For a directed graph (DAG):

• every arc u→v becomes edge {u, v}
• for every node v, an edge is added between every pair of parents ("marrying the parents")

For a mixed graph (PDAG / chain graph):

• every arc u→v and every edge u–v become edge {u, v}
• for every chain component (maximal set of nodes connected by undirected edges), an edge is added between every pair of parents of any node in that component

Template Parameters

G	Any GUM_DiGraphable graph.

Parameters

g	The graph to moralize.

Returns

The moral graph as an UndiGraph with the same node set as g.

Definition at line 60 of file moralization_tpl.h.

                                   {
    UndiGraph moral;
    for (const auto node: g.nodes())
      moral.addNodeWithId(node);
 
    if constexpr (GUM_MixedGraphable< G >) {
      for (const auto node: g.nodes()) {
        for (const auto p: g.parents(node))
          moral.addEdge(node, p);
        for (const auto n: g.neighbours(node))
          moral.addEdge(node, n);
      }
 
      NodeSet already;
      for (const auto node: g.nodes()) {
        if (already.contains(node)) continue;
        already.insert(node);
 
        NodeSet par      = g.parents(node);
        NodeSet frontier = g.neighbours(node);
        while (!frontier.empty()) {
          const NodeId nei = frontier.popFirst();
          if (already.contains(nei)) continue;
          already.insert(nei);
          par += g.parents(nei);
          frontier += g.neighbours(nei) - already;
        }
 
        _marryParents_(par, moral);
      }
    } else {
      for (const auto node: g.nodes()) {
        const auto& par = g.parents(node);
        for (const auto p: par)
          moral.addEdge(node, p);
        _marryParents_(par, moral);
      }
    }
    return moral;
  }

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::insert(), and gum::Set< Key >::popFirst().

Referenced by gum::DAG::moralGraph(), gum::PDAG::moralGraph(), and moralizedAncestralGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

moralizedAncestralGraph()

template<GUM_DiGraphable G>

UndiGraph gum::graph::moralizedAncestralGraph	(	const G &	g,
		const NodeSet &	query )

Returns the moralized ancestral graph of query in g.

For a directed graph (DAG): Collects query and all ancestors reachable by following arcs backward, then moralizes the resulting subgraph.

For a mixed graph (PDAG / chain graph): Collects query and all nodes reachable by following arcs backward and undirected edges in both directions, then moralizes with the chain-component rule.

Template Parameters

G	Any GUM_DiGraphable graph.

Parameters

g	The graph.
query	The set of nodes whose moralized ancestral graph is needed.

Returns

The moralized ancestral graph as an UndiGraph.

Definition at line 102 of file moralization_tpl.h.

                                                                      {
    if constexpr (GUM_MixedGraphable< G >) {
      MixedGraph ancestral;
      NodeSet    frontier{query};
      for (const auto n: query)
        ancestral.addNodeWithId(n);
 
      while (!frontier.empty()) {
        const NodeId current = *frontier.begin();
        frontier.erase(current);
 
        for (const auto p: g.parents(current)) {
          if (!ancestral.existsNode(p)) {
            ancestral.addNodeWithId(p);
            frontier.insert(p);
          }
          ancestral.addArc(p, current);
        }
        for (const auto n: g.neighbours(current)) {
          if (!ancestral.existsNode(n)) {
            ancestral.addNodeWithId(n);
            frontier.insert(n);
          }
          ancestral.addEdge(n, current);
        }
      }
      return moralGraph(ancestral);
 
    } else {
      UndiGraph res;
      NodeSet   frontier{query};
 
      while (!frontier.empty()) {
        const NodeId current = *frontier.begin();
        frontier.erase(current);
        res.addNodeWithId(current);
        for (const auto p: g.parents(current))
          if (!res.existsNode(p) && !frontier.contains(p)) frontier.insert(p);
      }
 
      for (const auto node: res.nodes()) {
        const auto& par = g.parents(node);
        for (const auto p: par)
          res.addEdge(node, p);
        _marryParents_(par, res);
      }
      return res;
    }
  }

References gum::DiGraph::addArc(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::NodeGraphPart::existsNode(), gum::Set< Key >::insert(), moralGraph(), and gum::NodeGraphPart::nodes().

Referenced by cSeparated(), cSeparated(), gum::DAG::moralizedAncestralGraph(), and gum::PDAG::moralizedAncestralGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

requisiteNodes()

template<GUM_DiGraphable G>

NodeSet gum::graph::requisiteNodes	(	const G &	g,
		const NodeSet &	query,
		const NodeSet &	Zhard = NodeSet(),
		const NodeSet &	Zsoft = NodeSet() )

Returns the Shachter-requisite nodes for query given evidence.

A node is requisite if it lies on an active path that arrives at a query node from below (upward visit), or if it is evidence that activates a v-structure (collider activation, downward visit). This is the minimal set of nodes whose distributions are needed to compute the posterior of the query.

This is NOT the full d-connected set. Use dConnected when you need all d-connected nodes (e.g. for d-separation testing).

Template Parameters

G	Any directed graph satisfying GUM_DiGraphable (DAG, DiGraph, …).

Parameters

g	The directed graph.
query	Source nodes from which the ball is launched.
Zhard	Hard-evidence nodes: block upward propagation; activate colliders on downward passes.
Zsoft	Soft-evidence nodes: activate colliders without blocking.

Returns

NodeSet of Shachter-requisite nodes.

Definition at line 107 of file bayesBall_tpl.h.

                                                                                                   {
    return _bayesBall_< G, false >(g, query, Zhard, Zsoft);
  }

References _bayesBall_().

Referenced by gum::BayesBall::requisiteNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

topologicalOrder()

template<GUM_DiGraphable G>

Sequence< NodeId > gum::graph::topologicalOrder

(

const G &

g

)

Returns a topological ordering of the nodes of g (Kahn's algorithm).

Nodes are ordered so that every arc goes from an earlier to a later position in the sequence.

Exceptions

InvalidDirectedCycle

if g contains a directed cycle.

Definition at line 49 of file cycleDetection_tpl.h.

                                                  {
    if (g.empty()) return {};
 
    NodeProperty< Size >  indegree;
    std::vector< NodeId > border;
    border.reserve(g.size() / 2);
 
    for (const auto node: g.nodes()) {
      const auto& par = g.parents(node);
      indegree.insert(node, par.size());
      if (par.empty()) border.push_back(node);
    }
 
    if (border.empty())
      GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.")
 
    Sequence< NodeId > result;
    while (!border.empty()) {
      const NodeId root = border.back();
      border.pop_back();
 
      if (result.exists(root))
        GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.")
      result.insert(root);
 
      for (const auto child: g.children(root)) {
        const Size deg = indegree[child];
        if (deg == 0)
          GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.")
        if (deg == 1) border.push_back(child);
        indegree[child] = deg - 1;
      }
    }
 
    GUM_ASSERT(result.size() == g.size());
    return result;
  }

References gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::exists(), GUM_ERROR, gum::HashTable< Key, Val >::insert(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::insert(), and gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::size().

Referenced by gum::DiGraph::topologicalOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

undirectedPath()

template<GUM_UndiGraphable G>

std::optional< std::vector< NodeId > > gum::graph::undirectedPath	(	const G &	g,
		NodeId	n1,
		NodeId	n2 )

Shortest undirected path from n1 to n2 (BFS).

Returns the sequence of nodes [n1, …, n2], or std::nullopt if no path exists.

Definition at line 136 of file pathFinding_tpl.h.

                                                                                      {
    List< NodeId > fifo;
    fifo.pushBack(n2);
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    while (!fifo.empty()) {
      const NodeId current = fifo.front();
      fifo.popFront();
      for (const auto n: g.neighbours(current)) {
        if (mark.exists(n)) continue;
        mark.insert(n, current);
        if (n == n1) return detail::reconstructPath(mark, n1, n2);
        fifo.pushBack(n);
      }
    }
 
    return std::nullopt;
  }

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::popFront(), gum::List< Val >::pushBack(), and gum::graph::detail::reconstructPath().

Referenced by gum::UndiGraph::undirectedPath().

Here is the call graph for this function:

Here is the caller graph for this function: