Graphs manipulation

In aGrUM, graphs are undirected (using edges), directed (using arcs) or mixed (using both arcs and edges). Some other types of graphs are described below. Edges and arcs are represented by pairs of int (nodeId), but these pairs are considered as unordered for edges whereas they are ordered for arcs.

For all types of graphs, nodes are int. If a graph of objects is needed (like pyagrum.BayesNet), the objects are mapped to nodeIds.

Quick specification of graphs

Graphs can also be built with a fast dot-like syntax, similar to the one used for graphical models (see Quick specification of (randomly parameterized) graphical models) : '->' denotes a directed arc, '<-' a directed arc in the other direction, '-' an undirected edge, ';' separates independent chains.

pyagrum.fastDiGraph('A->B->C;B->E')
pyagrum.fastDiGraph('A->B<-C')       # both A and C point to B
pyagrum.fastUndiGraph('A-B-C')
pyagrum.fastMixedGraph('A->B-C')

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF() already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. Writing 'A--B' in these functions raises an error rather than being silently misread.

pyagrum.fastDiGraph(desc)

Build a graph from a dot-like syntax : 'A->B->C;B->E'.

'->' denotes a directed arc, '<-' a directed arc in the other direction (e.g. 'A->B<-C' means both A and C point to B), '-' an undirected edge, ';' separates independent chains. If every node token in the description is a non-negative integer, those integers are used directly as node ids ; otherwise every token – including numeric-looking ones – is used as a node name.

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. 'A--B' is therefore rejected here rather than silently misread.

• Raises:
  • pyagrum.InvalidArc – If the description requires a directed arc but the target graph type does not support arcs, or if the description is malformed.
  • pyagrum.InvalidEdge – If the description requires an undirected edge but the target graph type does not support edges.
• Parameters: desc (str) – the string containing the dot-like specification
• Return type: DiGraph

Examples

>>> pyagrum.fastDiGraph('A->B->C;B->E')
>>> pyagrum.fastUndiGraph('A-B-C')
>>> pyagrum.fastMixedGraph('A->B-C')
>>> pyagrum.fastDAG('A->B->C')
>>> pyagrum.fastPDAG('A->B-C')

pyagrum.fastUndiGraph(desc)

Build a graph from a dot-like syntax : 'A->B->C;B->E'.

'->' denotes a directed arc, '<-' a directed arc in the other direction (e.g. 'A->B<-C' means both A and C point to B), '-' an undirected edge, ';' separates independent chains. If every node token in the description is a non-negative integer, those integers are used directly as node ids ; otherwise every token – including numeric-looking ones – is used as a node name.

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. 'A--B' is therefore rejected here rather than silently misread.

• Raises:
  • pyagrum.InvalidArc – If the description requires a directed arc but the target graph type does not support arcs, or if the description is malformed.
  • pyagrum.InvalidEdge – If the description requires an undirected edge but the target graph type does not support edges.
• Parameters: desc (str) – the string containing the dot-like specification
• Return type: UndiGraph

Examples

>>> pyagrum.fastDiGraph('A->B->C;B->E')
>>> pyagrum.fastUndiGraph('A-B-C')
>>> pyagrum.fastMixedGraph('A->B-C')
>>> pyagrum.fastDAG('A->B->C')
>>> pyagrum.fastPDAG('A->B-C')

pyagrum.fastMixedGraph(desc)

Build a graph from a dot-like syntax : 'A->B->C;B->E'.

'->' denotes a directed arc, '<-' a directed arc in the other direction (e.g. 'A->B<-C' means both A and C point to B), '-' an undirected edge, ';' separates independent chains. If every node token in the description is a non-negative integer, those integers are used directly as node ids ; otherwise every token – including numeric-looking ones – is used as a node name.

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. 'A--B' is therefore rejected here rather than silently misread.

• Raises:
  • pyagrum.InvalidArc – If the description requires a directed arc but the target graph type does not support arcs, or if the description is malformed.
  • pyagrum.InvalidEdge – If the description requires an undirected edge but the target graph type does not support edges.
• Parameters: desc (str) – the string containing the dot-like specification
• Return type: MixedGraph

Examples

>>> pyagrum.fastDiGraph('A->B->C;B->E')
>>> pyagrum.fastUndiGraph('A-B-C')
>>> pyagrum.fastMixedGraph('A->B-C')
>>> pyagrum.fastDAG('A->B->C')
>>> pyagrum.fastPDAG('A->B-C')

pyagrum.fastDAG(desc)

Build a graph from a dot-like syntax : 'A->B->C;B->E'.

'->' denotes a directed arc, '<-' a directed arc in the other direction (e.g. 'A->B<-C' means both A and C point to B), '-' an undirected edge, ';' separates independent chains. If every node token in the description is a non-negative integer, those integers are used directly as node ids ; otherwise every token – including numeric-looking ones – is used as a node name.

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. 'A--B' is therefore rejected here rather than silently misread.

• Raises:
  • pyagrum.InvalidArc – If the description requires a directed arc but the target graph type does not support arcs, or if the description is malformed.
  • pyagrum.InvalidEdge – If the description requires an undirected edge but the target graph type does not support edges.
• Parameters: desc (str) – the string containing the dot-like specification
• Return type: DAG

Examples

>>> pyagrum.fastDiGraph('A->B->C;B->E')
>>> pyagrum.fastUndiGraph('A-B-C')
>>> pyagrum.fastMixedGraph('A->B-C')
>>> pyagrum.fastDAG('A->B->C')
>>> pyagrum.fastPDAG('A->B-C')

pyagrum.fastPDAG(desc)

Build a graph from a dot-like syntax : 'A->B->C;B->E'.

'->' denotes a directed arc, '<-' a directed arc in the other direction (e.g. 'A->B<-C' means both A and C point to B), '-' an undirected edge, ';' separates independent chains. If every node token in the description is a non-negative integer, those integers are used directly as node ids ; otherwise every token – including numeric-looking ones – is used as a node name.

Note

A single '-' (not '--') is used for edges on purpose : pyagrum.fastMRF already uses '--' to list the variables of a single factor (a clique), a different construct from a chain of pairwise edges. 'A--B' is therefore rejected here rather than silently misread.

• Raises:
  • pyagrum.InvalidArc – If the description requires a directed arc but the target graph type does not support arcs, or if the description is malformed.
  • pyagrum.InvalidEdge – If the description requires an undirected edge but the target graph type does not support edges.
• Parameters: desc (str) – the string containing the dot-like specification
• Return type: PDAG

Examples

>>> pyagrum.fastDiGraph('A->B->C;B->E')
>>> pyagrum.fastUndiGraph('A-B-C')
>>> pyagrum.fastMixedGraph('A->B-C')
>>> pyagrum.fastDAG('A->B->C')
>>> pyagrum.fastPDAG('A->B-C')

See also this notebook for a tour of graph construction and algorithms.

Edges and Arcs

class pyagrum.Arc(*args)

pyagrum.Arc is the representation of an arc between two nodes represented by int : the head and the tail.

Arc(tail, head) -> Arc : Parameters: : - tail (int) – the tail - head (int) – the head

Arc(src) -> Arc : Parameters: : - src (Arc) – the pyagrum.Arc to copy

first()

• Returns: the nodeId of the first node of the arc (the tail)
• Return type: int

head()

• Returns: the id of the head node
• Return type: int

other(id)

• Parameters: id (int) – the nodeId of the head or the tail
• Returns: the nodeId of the other node
• Return type: int

second()

• Returns: the nodeId of the second node of the arc (the head)
• Return type: int

tail()

• Returns: the id of the tail node
• Return type: int

class pyagrum.Edge(*args)

pyagrum.Edge is the representation of an arc between two nodes represented by int : the first and the second.

Edge(aN1,aN2) -> Edge : Parameters: : - aN1 (int) – the nodeId of the first node - aN2 (int) – the nodeId of the secondnode

Edge(src) -> Edge : Parameters: : - src (yAgrum.Edge) – the Edge to copy

first()

• Returns: the nodeId of the first node of the arc (the tail)
• Return type: int

other(id)

• Parameters: id (int) – the nodeId of one of the nodes of the Edge
• Returns: the nodeId of the other node
• Return type: int

second()

• Returns: the nodeId of the second node of the arc (the head)
• Return type: int

Directed Graphs

class pyagrum.DiGraph(*args)

DiGraph represents a Directed Graph.

DiGraph() -> DiGraph : default constructor

DiGraph(src) -> DiGraph : Parameters: : - src (pyagrum.DiGraph) – the digraph to copy

addArc(*args)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
• Raises: pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises:
  • pyagrum.DuplicateElement –
  • If the given id is already used –
• Return type: None

addNodes(n)

Add a set of n nodes.

• Parameters: n (int) – the number of nodes to add.
• Returns: the new ids
• Return type: set[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

ancestors(*args)

give the set of nodeid of ancestors of a node

• Parameters: norid (str *|*int) – the name or the id of the node
• Returns: the set of ids of the ancestors of node norid.
• Return type: list[int]

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: set[tuple[int, int]]

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: list[int]

clear()

Remove all the nodes and arcs from the graph.

• Return type: None

static completeGraph(n)

Create a complete directed graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: directed graph where every ordered pair (i, j) with i≠j has arc i→j, with nodes 0..n-1
• Return type: DiGraph

connectedComponents()

Returns the weakly connected components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

descendants(*args)

give the set of nodeid of descendants of a node

• Parameters: norid (str *|*int) – the name or the id of the node
• Returns: the set of ids of the descendants of node norid.
• Return type: list[int]

directedPath(node1, node2)

Return a shortest directed path from node1 to node2, or None if no such path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids along the directed path, or None if node2 is unreachable from node1
• Return type: list[int] | None

directedUnorientedPath(node1, node2)

Return a shortest path from node1 to node2 ignoring arc orientation, or None if no path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids (arcs may be traversed in either direction), or None if unreachable
• Return type: list[int] | None

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading through the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseNode(id)

Erase the node and all the related arcs.

• Parameters: id (int) – the id of the node
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

Check if a node with a certain id exists in the graph.

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

family(*args)

Return the family of a node: the node itself plus all its parents.

• Parameters: norid (int) – id of the node
• Returns: {norid} ∪ parents(norid)
• Return type: list[int]

hasDirectedPath(_from, to)

Check if a directedpath exists between from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

nodes()

• Returns: the set of ids
• Return type: set[int]

parents(id)

• Parameters: id (int) – The id of the child node
• Returns: the set of the parents ids.
• Return type: list[int]

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

• Returns: the list of the nodes Ids in a topological order
• Return type: list[int]
• Raises: pyagrum.InvalidDirectedCycle – If this graph contains cycles

class pyagrum.DAG(*args)

DAG represents a Directed Graph.

DAG() -> DAG : default constructor

DAG(src) -> DAG : Parameters: : - src (pyagrum.DAG) – the DAG to copy

addArc(*args)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
• Raises:
  • pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
  • pyagrum.CycleDetected – If a cycle is detected
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises:
  • pyagrum.DuplicateElement –
  • If the given id is already used –
• Return type: None

addNodes(n)

Add a set of n nodes.

• Parameters: n (int) – the number of nodes to add.
• Returns: the new ids
• Return type: set[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

ancestors(id)

give the set of nodeid of ancestors of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the ancestors of node norid.
• Return type: list[int]

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: set[tuple[int, int]]

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: list[int]

clear()

Remove all the nodes and arcs from the graph.

• Return type: None

static completeGraph(n)

Create a complete directed graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: directed graph where every ordered pair (i, j) with i≠j has arc i→j, with nodes 0..n-1
• Return type: DiGraph

connectedComponents()

Returns the weakly connected components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

dSeparation(*args)

Check if the sets of nodes X and Y are d-separated (by the set of nodes Z if given) in the DAG.

• Parameters:
  • X (int | sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Y (int | sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Z (int | sequence of int *(*optional )) – a sequence of node ids (int) or a single node id (int)
• Returns: True if X and Y are d-separated (by Z if given), False otherwise.
• Return type: bool

descendants(id)

give the set of nodeid of descendants of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the descendants of node norid.
• Return type: list[int]

directedPath(node1, node2)

Return a shortest directed path from node1 to node2, or None if no such path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids along the directed path, or None if node2 is unreachable from node1
• Return type: list[int] | None

directedUnorientedPath(node1, node2)

Return a shortest path from node1 to node2 ignoring arc orientation, or None if no path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids (arcs may be traversed in either direction), or None if unreachable
• Return type: list[int] | None

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading to the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseNode(id)

Erase the node and all the related arcs.

• Parameters: id (int) – the id of the node
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

Check if a node with a certain id exists in the graph.

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

family(*args)

Return the family of a node: the node itself plus all its parents.

• Parameters: norid (int) – id of the node
• Returns: {norid} ∪ parents(norid)
• Return type: list[int]

hasDirectedPath(_from, to)

Check if a directedpath exists between from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

minimalCondSet(*args)

Return a minimal conditioning set of a target given source nodes in the DAG.

• Parameters:
  • target (int | str | list *[*int *|*str ]) – the target node id(s) or name(s)
  • soids (list *[*int *|*str ]) – the list of source node ids or names
• Returns: the minimal conditioning set (as node ids)
• Return type: list[int]

moralGraph()

Returns the moral graph of the DAG, formed by adding edges between all pairs of nodes that have a common child, and then making all edges in the graph undirected.

• Returns: The moral graph
• Return type: UndiGraph

moralizedAncestralGraph(nodes)

Compute the moralized ancestral graph of the nodes from the DAG.

• Parameters: nodes (list[int]) – a sequence of node ids (int) or a single node id (int)
• Returns: the moralized ancestral graph of the nodes from the DAG.
• Return type: UndiGraph

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

nodes()

• Returns: the set of ids
• Return type: set[int]

parents(id)

• Parameters: id (int) – The id of the child node
• Returns: the set of the parents ids.
• Return type: list[int]

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

• Returns: the list of the nodes Ids in a topological order
• Return type: list[int]
• Raises: pyagrum.InvalidDirectedCycle – If this graph contains cycles

Undirected Graphs

class pyagrum.UndiGraph(*args)

UndiGraph represents an Undirected Graph.

UndiGraph() -> UndiGraph : default constructor

UndiGraph(src) -> UndiGraph : Parameters! : - src (UndiGraph) – the pyagrum.UndiGraph to copy

addEdge(*args)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

• Parameters: n (int) – the number of nodes to add.
• Returns: the new ids
• Return type: set[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

chainComponents()

Return the chain components (connected components) of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

Create a complete undirected graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: graph where every pair of distinct nodes is connected by an edge, with nodes 0..n-1
• Return type: UndiGraph

connectedComponents()

Returns the connected components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

edges()

• Returns: the list of the edges
• Return type: set[tuple[int, int]]

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseEdge(n1, n2)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(id)

Erase the node and all the adjacent edges.

• Parameters: id (int) – the id of the node
• Return type: None

existsEdge(n1, n2)

Check if an edge exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

Check if a node with a certain id exists in the graph.

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

hasUndirectedPath(*args)

Check whether two nodes are connected by an undirected path.

• Parameters:
  • n1 (int) – id of the first node
  • n2 (int) – id of the second node
• Returns: True if a path exists between n1 and n2
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: list[int]

nodes()

• Returns: the set of ids
• Return type: set[int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: UndiGraph

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

undirectedPath(node1, node2)

Return a shortest undirected path between two nodes, or None if no path exists.

• Parameters:
  • node1 (int) – id of the first node
  • node2 (int) – id of the second node
• Returns: ordered list of node ids along the path, or None if the nodes are disconnected
• Return type: list[int] | None

class pyagrum.CliqueGraph(*args)

CliqueGraph represents a Clique Graph.

CliqueGraph() -> CliqueGraph : default constructor

CliqueGraph(src) -> CliqueGraph : Parameter : - src (pyagrum.CliqueGraph) – the CliqueGraph to copy

addEdge(first, second)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
  • first (int)
  • second (int)
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode(*args)

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

• Parameters: n (int) – the number of nodes to add.
• Returns: the new ids
• Return type: set[int]

addToClique(clique_id, node_id)

Change the set of nodes included into a given clique and returns the new set

• Parameters:
  • clique_id (int) – the id of the clique
  • node_id (int) – the id of the node
• Raises:
  • pyagrum.NotFound –
  • If clique_id does not exist –
  • pyagrum.DuplicateElement –
  • If clique_id set already contains the ndoe –
• Return type: None

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

chainComponents()

Return the chain components (connected components) of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

clear()

Remove all the nodes and edges from the graph.

• Return type: None

clearEdges()

Remove all edges and their separators

• Return type: None

clique(clique)

• Parameters:
  • idClique (int) – the id of the clique
  • clique (int)
• Returns: The set of nodes included in the clique
• Return type: list[int]
• Raises: pyagrum.NotFound – If the clique does not belong to the clique graph

static completeGraph(n)

Create a complete undirected graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: graph where every pair of distinct nodes is connected by an edge, with nodes 0..n-1
• Return type: UndiGraph

connectedComponents()

Returns the connected components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

container(idNode)

• Parameters: idNode (int) – the id of the node
• Returns: the id of a clique containing the node
• Return type: int
• Raises: pyagrum.NotFound – If no clique contains idNode

containerPath(node1, node2)

• Parameters:
  • node1 (int) – the id of one node
  • node2 (int) – the id of the other node
• Returns: a path from a clique containing node1 to a clique containing node2
• Return type: list[int]
• Raises: pyagrum.NotFound – If such path cannot be found

edges()

• Returns: the list of the edges
• Return type: set[tuple[int, int]]

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseEdge(edge)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
  • edge (Edge)
• Return type: None

eraseFromClique(clique_id, node_id)

Remove a node from a clique

• Parameters:
  • clique_id (int) – the id of the clique
  • node_id (int) – the id of the node
• Raises: pyagrum.NotFound – If clique_id does not exist
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(node)

Erase the node and all the adjacent edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

existsEdge(n1, n2)

Check if an edge exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

Check if a node with a certain id exists in the graph.

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

hasRunningIntersection()

• Returns: True if the running intersection property holds
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

hasUndirectedPath(*args)

Check whether two nodes are connected by an undirected path.

• Parameters:
  • n1 (int) – id of the first node
  • n2 (int) – id of the second node
• Returns: True if a path exists between n1 and n2
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

isJoinTree()

• Returns: True if the graph is a join tree
• Return type: bool

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: list[int]

nodes()

• Returns: the set of ids
• Return type: set[int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: UndiGraph

separator(cliq1, cliq2)

• Parameters:
  • edge (pyagrum.Edge) – the edge to be checked
  • clique1 (int) – one extremity of the edge
  • clique (int) – the other extremity of the edge
  • cliq1 (int)
  • cliq2 (int)
• Returns: the separator included in a given edge
• Return type: list[int]
• Raises: pyagrum.NotFound – If the edge does not belong to the clique graph

setClique(idClique, new_clique)

changes the set of nodes included into a given clique

• Parameters:
  • idClique (int) – the id of the clique
  • new_clique (list[int]) – the new set of nodes to be included in the clique
• Raises: pyagrum.NotFound – If idClique is not a clique of the graph
• Return type: None

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

toDotWithNames(bn)

• Parameters:
  • bn (pyagrum.BayesNet)
  • network (a Bayesian)
• Returns: a friendly display of the graph in DOT format where ids have been changed according to their correspondance in the BN
• Return type: str

undirectedPath(node1, node2)

Return a shortest undirected path between two nodes, or None if no path exists.

• Parameters:
  • node1 (int) – id of the first node
  • node2 (int) – id of the second node
• Returns: ordered list of node ids along the path, or None if the nodes are disconnected
• Return type: list[int] | None

Mixed Graph

class pyagrum.MixedGraph(*args)

MixedGraph represents a graph with both arcs and edges.

MixedGraph() -> MixedGraph : default constructor

MixedGraph(src) -> MixedGraph : Parameters: : - src (pyagrum.MixedGraph) –the MixedGraph to copy

addArc(n1, n2)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
  • n1 (int)
  • n2 (int)
• Raises: pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
• Return type: None

addEdge(n1, n2)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

• Parameters: n (int) – the number of nodes to add.
• Returns: the new ids
• Return type: set[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

ancestors(id)

give the set of nodeid of ancestors of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the ancestors of node norid.
• Return type: list[int]

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: set[tuple[int, int]]

boundary(id)

Boundary are neighbours (not oriented), children and parents

• Parameters: id (int) – the id of the node
• Returns: the set of node ids.
• Return type: list[int]

chainComponent(node)

Return the chain component containing a given node.

The chain component of a node in a mixed graph is the set of nodes reachable via undirected edges from that node.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Returns: the set of node ids in the same chain component
• Return type: list[int]

chainComponents()

Return the chain components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

children(id)

• Parameters: id (int) – the id of the parent node
• Returns: the set of all the children ids
• Return type: list[int]

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

Create a complete undirected graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: graph where every pair of distinct nodes is connected by an edge, with nodes 0..n-1
• Return type: UndiGraph

connectedComponents()

Returns the weakly connected components of the mixed graph (following both arcs and undirected edges in both directions).

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

descendants(id)

give the set of nodeid of descendants of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the descendants of node norid.
• Return type: list[int]

directedPath(node1, node2)

Return a shortest directed path from node1 to node2, or None if no such path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids along the directed path, or None if node2 is unreachable from node1
• Return type: list[int] | None

directedUnorientedPath(node1, node2)

Return a shortest path from node1 to node2 ignoring arc orientation, or None if no path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids (arcs may be traversed in either direction), or None if unreachable
• Return type: list[int] | None

edges()

• Returns: the list of the edges
• Return type: set[tuple[int, int]]

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading through the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseEdge(n1, n2)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(node)

Erase the node and all the related arcs and edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsEdge(n1, n2)

Check if an edge exists between n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

Check if a node with a certain id exists in the graph.

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

family(*args)

Return the family of a node: the node itself plus all its parents.

• Parameters: norid (int) – id of the node
• Returns: {norid} ∪ parents(norid)
• Return type: list[int]

hasDirectedPath(_from, to)

Check if a directedpath exists between from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasMixedOrientedPath(node1, node2)

Check if there is an oriented path from node1 to node2 in the mixed graph (following arc directions).

• Parameters:
  • node1 (int) – the id of the start node
  • node2 (int) – the id of the end node
• Returns: True if such a path exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

hasUndirectedPath(*args)

Check whether two nodes are connected by an undirected path.

• Parameters:
  • n1 (int) – id of the first node
  • n2 (int) – id of the second node
• Returns: True if a path exists between n1 and n2
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

mixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id form which the path begins
  • node2 (int) – the id to witch the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (following the direction of the arcs). If no path is found, the returned list is empty.
• Return type: list[int] | None

mixedUnorientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id from which the path begins
  • node2 (int) – the id to which the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of the arcs). If no path is found, the list is empty.
• Return type: list[int] | None

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: the set of node ids linked to the given node by an edge
• Return type: list[int]

nodes()

• Returns: the set of ids
• Return type: set[int]

parents(id)

• Parameters: id (int) – the id of the child node
• Returns: the set of parent node ids
• Return type: list[int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: UndiGraph

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

• Returns: the list of the nodes Ids in a topological order
• Return type: list[int]
• Raises: pyagrum.InvalidDirectedCycle – If this graph contains cycles

undirectedPath(node1, node2)

Return a shortest undirected path between two nodes, or None if no path exists.

• Parameters:
  • node1 (int) – id of the first node
  • node2 (int) – id of the second node
• Returns: ordered list of node ids along the path, or None if the nodes are disconnected
• Return type: list[int] | None

Partially Directed Graph (DAG)

class pyagrum.PDAG(*args)

PDAG represents a graph with both arcs and edges.

PDAG() -> PDAG : default constructor

PDAG(src) -> PDAG : Parameters: : - src (pyagrum.PDAG) –the PDAG to copy

addArc(*args)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
• Raises:
  • pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
  • PyAgrum.InvalidDirectedCycle – if the arc would create a (mixed) cycle.
• Return type: None

addEdge(*args)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

Add a new node to the graph and return its id.

• Returns: the id of the new node
• Return type: int

addNodeWithId(id)

Add a node with a specific id.

• Parameters: id (int) – the id of the new node
• Raises: pyagrum.DuplicateElement – if a node with this id already exists
• Return type: None

addNodes(n)

Add n new nodes to the graph.

• Parameters: n (int) – the number of nodes to add
• Return type: set[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

ancestors(id)

give the set of nodeid of ancestors of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the ancestors of node norid.
• Return type: list[int]

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: set[tuple[int, int]]

boundary(id)

Boundary of a node: neighbours (via edges), children, and parents.

• Parameters: id (int) – the id of the node
• Returns: the set of adjacent node ids
• Return type: list[int]

cSeparation(*args)

Check if the sets of nodes X and Y are c-separated (by the set of nodes Z if given) in the PDAG.

• Parameters:
  • X (int | sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Y (int | sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Z (int | sequence of int *(*optional )) – a sequence of node ids (int) or a single node id (int)
• Returns: True if X and Y are c-separated (by Z if given), False otherwise.
• Return type: bool

chainComponent(node)

Return the chain component containing a given node.

The chain component of a node in a mixed graph is the set of nodes reachable via undirected edges from that node.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Returns: the set of node ids in the same chain component
• Return type: list[int]

chainComponents()

Return the chain components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

children(id)

• Parameters: id (int) – the id of the parent node
• Returns: the set of all children ids
• Return type: list[int]

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

Create a complete undirected graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: graph where every pair of distinct nodes is connected by an edge, with nodes 0..n-1
• Return type: UndiGraph

connectedComponents()

Returns the weakly connected components of the mixed graph (following both arcs and undirected edges in both directions).

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

descendants(id)

give the set of nodeid of descendants of a node

• Parameters:
  • norid (str *|*int) – the name or the id of the node
  • id (int)
• Returns: the set of ids of the descendants of node norid.
• Return type: list[int]

directedPath(node1, node2)

Return a shortest directed path from node1 to node2, or None if no such path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids along the directed path, or None if node2 is unreachable from node1
• Return type: list[int] | None

directedUnorientedPath(node1, node2)

Return a shortest path from node1 to node2 ignoring arc orientation, or None if no path exists.

• Parameters:
  • node1 (int) – id of the source node
  • node2 (int) – id of the destination node
• Returns: ordered list of node ids (arcs may be traversed in either direction), or None if unreachable
• Return type: list[int] | None

edges()

• Returns: the list of the edges
• Return type: set[tuple[int, int]]

empty()

Check if the graph has no nodes.

• Returns: True if there are no nodes in the graph
• Return type: bool

emptyArcs()

Check if the graph has no arcs.

• Returns: True if the graph contains no arcs
• Return type: bool

emptyEdges()

Check if the graph has no edges.

• Returns: True if the graph contains no edges
• Return type: bool

eraseArc(n1, n2)

Remove an arc from the graph.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
  • n1 (int)
  • n2 (int)
• Raises: pyagrum.InvalidArc – if the arc does not exist
• Return type: None

eraseChildren(n)

Erase all arcs from a node to its children.

• Parameters:
  • id (int) – the id of the node
  • n (int)
• Return type: None

eraseEdge(n1, n2)

Remove an edge from the graph.

• Parameters:
  • n1 (int) – one endpoint of the edge
  • n2 (int) – the other endpoint
• Raises: pyagrum.InvalidEdge – if the edge does not exist
• Return type: None

eraseNeighbours(n)

Erase all edges adjacent to a given node.

• Parameters:
  • id (int) – the id of the node
  • n (int)
• Return type: None

eraseNode(node)

Erase the node and all the related arcs and edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

eraseParents(n)

Erase all arcs incoming to a node from its parents.

• Parameters:
  • id (int) – the id of the node
  • n (int)
• Return type: None

existsArc(n1, n2)

Check whether an arc exists between two nodes.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
  • n1 (int)
  • n2 (int)
• Returns: True if the arc (tail, head) exists
• Return type: bool

existsEdge(n1, n2)

Check whether an edge exists between two nodes.

• Parameters:
  • n1 (int) – one endpoint
  • n2 (int) – the other endpoint
• Returns: True if the edge exists
• Return type: bool

existsNode(id)

Check whether a node exists.

• Parameters: id (int) – the node id to check
• Returns: True if the node exists
• Return type: bool

family(*args)

Return the family of a node: the node itself plus all its parents.

• Parameters: norid (int) – id of the node
• Returns: {norid} ∪ parents(norid)
• Return type: list[int]

hasDirectedPath(_from, to)

Check if a directedpath exists between from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasMixedOrientedPath(node1, node2)

Check if there is an oriented path from node1 to node2 in the mixed graph (following arc directions).

• Parameters:
  • node1 (int) – the id of the start node
  • node2 (int) – the id of the end node
• Returns: True if such a path exists
• Return type: bool

hasMixedReallyOrientedPath(n1, n2)

Check if there is a strictly oriented path from node1 to node2 (all arcs, no edges).

• Parameters:
  • node1 (int) – the start node id
  • node2 (int) – the end node id
  • n1 (int)
  • n2 (int)
• Returns: True if such a path exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

hasUndirectedPath(*args)

Check whether two nodes are connected by an undirected path.

• Parameters:
  • n1 (int) – id of the first node
  • n2 (int) – id of the second node
• Returns: True if a path exists between n1 and n2
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

mixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id form which the path begins
  • node2 (int) – the id to witch the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (following the direction of the arcs). If no path is found, the returned list is empty.
• Return type: list[int] | None

mixedUnorientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id from which the path begins
  • node2 (int) – the id to which the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of the arcs). If no path is found, the list is empty.
• Return type: list[int] | None

moralGraph()

Returns the moral graph of the PDAG, formed by adding edges between all pairs of nodes that have a common child, and then making all edges in the graph undirected.

• Returns: The moral graph
• Return type: UndiGraph

moralizedAncestralGraph(nodes)

Compute the moralized ancestral graph of the nodes from the DAG.

• Parameters: nodes (list[int]) – a sequence of node ids (int) or a single node id (int)
• Returns: the moralized ancestral graph of the nodes from the DAG.
• Return type: UndiGraph

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: the set of node ids linked by an edge to the given node
• Return type: list[int]

nodes()

• Returns: the set of ids
• Return type: set[int]

parents(id)

• Parameters: id (int) – the id of the child node
• Returns: the set of parent node ids
• Return type: list[int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: UndiGraph

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

• Returns: the list of the nodes Ids in a topological order
• Return type: list[int]
• Raises: pyagrum.InvalidDirectedCycle – If this graph contains cycles

undirectedPath(node1, node2)

Return a shortest undirected path between two nodes, or None if no path exists.

• Parameters:
  • node1 (int) – id of the first node
  • node2 (int) – id of the second node
• Returns: ordered list of node ids along the path, or None if the nodes are disconnected
• Return type: list[int] | None

Partial Ancestral Graph (PAG)

class pyagrum.PAG(*args)

PAG represents a Partial Ancestral Graph, the output of the FCI algorithm.

A PAG is an undirected graph whose edges carry endpoint marks. Each edge between nodes x and y has two marks, one at each endpoint:

• EdgeMark_Circle (o): uncertain endpoint
• EdgeMark_Tail (-): definite non-ancestor (tail)
• EdgeMark_Arrowhead (>): definite ancestor (arrowhead)

PAG() -> PAG : default constructor

PAG(src) -> PAG : Parameters: : - src (pyagrum.PAG) – the PAG to copy

Typically obtained via BNLearner.learnPAG() after calling useFCI().

addEdge(*args)

Add an edge between two nodes with specified endpoint marks.

Signatures:

addEdge(x, y) : Adds a Circle-Circle edge (both endpoints uncertain).

addEdge(x, y, markAtX, markAtY) : Adds an edge with explicit marks. markAtX is the mark on x’s side (visible from y), markAtY is the mark on y’s side (visible from x).

• Parameters:
  • x (int) – id of the first node
  • y (int) – id of the second node
  • markAtX (int , optional) – mark at the x endpoint (EdgeMark_Circle, EdgeMark_Tail, or EdgeMark_Arrowhead)
  • markAtY (int , optional) – mark at the y endpoint (EdgeMark_Circle, EdgeMark_Tail, or EdgeMark_Arrowhead)
• Return type: None

addNode()

Add a new node to the PAG and return its id.

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node with a chosen id.

• Parameters: id (int) – the id of the new node
• Raises: pyagrum.DuplicateElement – if the given id is already used
• Return type: None

addNodes(n)

Add n new nodes to the PAG.

• Parameters: n (int) – number of nodes to add
• Returns: the new NodeIds
• Return type: list[int]

adjacencyMatrix()

adjacency matrix from a graph/graphical models

Compute the adjacency matrix of a pyAgrum’s graph or graphical models (more generally an object that has nodes, children/parents or neighbours methods)

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

chainComponents()

Return the chain components (connected components) of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

clear()

Remove all the nodes and edges from the graph.

• Return type: None

clearEdges()

Remove all edges and their endpoint marks from the PAG.

Nodes are preserved; only edges and their associated marks are removed.

• Return type: None

static completeGraph(n)

Create a complete undirected graph with n nodes.

• Parameters: n (int) – number of nodes
• Returns: graph where every pair of distinct nodes is connected by an edge, with nodes 0..n-1
• Return type: UndiGraph

connectedComponents()

Returns the connected components of the graph.

Each node is mapped to the id of its component root (an arbitrarily chosen node from the same component).

• Returns: mapping node id → component root id
• Return type: dict[int, int]

SEE ALSO

connectedComponentsList : returns a dict[int, set[int]] grouping nodes by component

connectedComponentsCount : returns the number of components

connectedComponentsCount()

number of connected components

• Returns: the number of connected components in the graph.
• Return type: int

connectedComponentsList()

connected components as a dict of sets

• Returns: dict of connected components (as sets of nodeIds) keyed by an arbitrary root nodeId per component.
• Return type: dict(int, set[int])

edges()

• Returns: the list of the edges
• Return type: set[tuple[int, int]]

empty()

Check whether the PAG has no nodes.

• Returns: True if the PAG contains no nodes
• Return type: bool

emptyEdges()

Check whether the PAG has no edges.

• Returns: True if the PAG contains no edges
• Return type: bool

eraseEdge(*args)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Remove all edges adjacent to a given node (and their marks).

• Parameters: n (int) – id of the node
• Return type: None

eraseNode(id)

Erase the node and all the adjacent edges.

• Parameters: id (int) – the id of the node
• Return type: None

existsEdge(n1, n2)

Check whether an edge exists between two nodes.

• Parameters:
  • n1 (int) – id of one endpoint
  • n2 (int) – id of the other endpoint
• Returns: True if the edge exists
• Return type: bool

existsNode(id)

Check whether a node with the given id exists in the PAG.

• Parameters: id (int) – the id to check
• Returns: True if the node exists
• Return type: bool

hasName(id)

Check whether a node has an explicitly assigned name.

• Parameters: id (int) – the node id
• Returns: True if a name has been assigned to this node via setName
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

hasUndirectedPath(*args)

Check whether two nodes are connected by an undirected path.

• Parameters:
  • n1 (int) – id of the first node
  • n2 (int) – id of the second node
• Returns: True if a path exists between n1 and n2
• Return type: bool

idFromName(name)

Return the id of the node with the given name, or None if no such name exists.

• Parameters: name (str) – the name to look up
• Returns: the node id, or None if the name is not found
• Return type: int | None

isArrowhead(src, dst)

Return True if the mark at dst (seen from src) is an arrowhead.

• Parameters:
  • src (int)
  • dst (int)
• Return type: bool

isBidirected(x, y)

Return True if both endpoints of edge (x, y) are arrowheads (bidirected edge).

• Parameters:
  • x (int)
  • y (int)
• Return type: bool

isCircle(src, dst)

Return True if the mark at dst (seen from src) is a circle.

• Parameters:
  • src (int)
  • dst (int)
• Return type: bool

isDefCollider(x, z, y)

Return True if z is a definite collider on the path x-z-y.

z is a definite collider when both marks at z (from x and from y) are arrowheads.

• Parameters:
  • x (int)
  • z (int)
  • y (int)
• Return type: bool

isDefinitelyDirected(x, y)

Return True if the edge x-y is definitely directed from x to y.

An edge is definitely directed from x to y when x has a tail and y has an arrowhead.

• Parameters:
  • x (int)
  • y (int)
• Return type: bool

isTail(src, dst)

Return True if the mark at dst (seen from src) is a tail.

• Parameters:
  • src (int)
  • dst (int)
• Return type: bool

markAt(*args)

Return the endpoint mark on the dst side of edge (src, dst).

The mark at dst indicates what the edge says about dst from src’s perspective: marks_[Arc(src,dst)] = mark at the dst endpoint.

• Parameters:
  • src (int) – id of the source node
  • dst (int) – id of the destination node
• Returns: EdgeMark_Circle (0), EdgeMark_Tail (1), or EdgeMark_Arrowhead (2)
• Return type: int

nameFromId(id)

Return the name of a node, or its id as a string if no name was set.

• Parameters: id (int) – the node id
• Returns: the name associated with the node, or str(id) if the node has no name
• Return type: str

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: list[int]

nodes()

• Returns: the set of ids
• Return type: set[int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: UndiGraph

reorientAllWith(*args)

Set all endpoint marks in the PAG to the given mark.

• Parameters: m (int) – mark to set everywhere: EdgeMark_Circle (0), EdgeMark_Tail (1), or EdgeMark_Arrowhead (2)
• Return type: None

setMarkAt(*args)

Set the endpoint mark on the dst side of edge (src, dst).

• Parameters:
  • src (int) – id of the source node
  • dst (int) – id of the destination node
  • m (int) – new mark: EdgeMark_Circle (0), EdgeMark_Tail (1), or EdgeMark_Arrowhead (2)
• Return type: None

setName(id, name)

Assign a name to a node.

If the node already has a name, it is replaced. The name must not already be used by another node.

• Parameters:
  • id (int) – the node id
  • name (str) – the name to assign
• Raises:
  • pyagrum.InvalidNode – If the node does not exist.
  • pyagrum.DuplicateElement – If the name is already used by a different node.
• Return type: None

size()

Return the number of nodes in the PAG.

• Returns: number of nodes
• Return type: int

sizeEdges()

Return the number of edges in the PAG.

• Returns: number of edges
• Return type: int

toDot()

Return a Graphviz dot representation of the PAG.

Endpoint marks are rendered as:

• Circle: odot
• Tail: none
• Arrowhead: normal

• Returns: dot-format string
• Return type: str

toMixedGraph()

Convert the PAG to a MixedGraph by interpreting definite edge orientations.

• Definitely directed edges become arcs.
• Bidirected edges become two arcs (one in each direction).
• Undirected or circle edges become undirected edges.

• Return type: MixedGraph

undirectedPath(node1, node2)

Return a shortest undirected path between two nodes, or None if no path exists.

• Parameters:
  • node1 (int) – id of the first node
  • node2 (int) – id of the second node
• Returns: ordered list of node ids along the path, or None if the nodes are disconnected
• Return type: list[int] | None