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.

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:
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 of 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:

set

arcs()

Returns the set of arcs in the graph.

Returns:

the set of the arcs

Return type:

Set

children(id)
Parameters:

id (int) – the id of the parent

Returns:

the set of all the children

Return type:

Set

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:

set

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] or 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] or 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:

set[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 or 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

parents(id)
Parameters:

id (int) – The id of the child node

Returns:

the set of the parents ids.

Return type:

Set

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:
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

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:
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 of 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:

set

arcs()

Returns the set of arcs in the graph.

Returns:

the set of the arcs

Return type:

Set

children(id)
Parameters:

id (int) – the id of the parent

Returns:

the set of all the children

Return type:

Set

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:

set

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] or 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] or 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:

set[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 or 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:

set[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:

pyagrum.UndiGraph

moralizedAncestralGraph(nodes)

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

Parameters:

nodes (int | sequence of 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:

pyagrum.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

parents(id)
Parameters:

id (int) – The id of the child node

Returns:

the set of the parents ids.

Return type:

Set

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:
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

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 of 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:

List

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 or 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:

Set

nodes()
Returns:

the set of ids

Return type:

set

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:

pyagrum.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:
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] or 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 of 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:
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:

set

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

Raises:

pyagrum.NotFound – If such path cannot be found

edges()
Returns:

the list of the edges

Return type:

List

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 or 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:

Set

nodes()
Returns:

the set of ids

Return type:

set

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:

pyagrum.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:

set

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 (set) – 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:
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:
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] or 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 of 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:

set

arcs()

Returns the set of arcs in the graph.

Returns:

the set of the arcs

Return type:

set

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:

set

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:

set[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:

Set

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:

set

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] or 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] or None

edges()
Returns:

the list of the edges

Return type:

List

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:

set[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 or 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

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

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:

Set

nodes()
Returns:

the set of ids

Return type:

set

parents(id)
Parameters:

id (int) – the id of the child node

Returns:

the set of parent node ids

Return type:

Set

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:

pyagrum.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:
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

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] or 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:

set

arcs()

Returns the set of arcs in the graph.

Returns:

the set of the arcs

Return type:

set

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:

set

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:

set[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:

Set

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:

set

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] or 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] or None

edges()
Returns:

the list of the edges

Return type:

List

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:

set[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 or 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

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

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:

pyagrum.UndiGraph

moralizedAncestralGraph(nodes)

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

Parameters:

nodes (int | sequence of 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:

pyagrum.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:

Set

nodes()
Returns:

the set of ids

Return type:

set

parents(id)
Parameters:

id (int) – the id of the child node

Returns:

the set of parent node ids

Return type:

Set

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:

pyagrum.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:
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

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] or 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 of 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:

List

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 or 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:

Set

nodes()
Returns:

the set of ids

Return type:

set

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:

pyagrum.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:
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:

pyagrum.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] or None