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

Arc

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

Edge

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

Digraph

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

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

n (int)

Return type:

DiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

Return type:

dict(int,Set[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

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

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen 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

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

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

Directed Acyclic Graph

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

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

n (int)

Return type:

DiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

Return type:

dict(int,Set[int])

dSeparation(*args)
Return type:

bool

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

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen 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

moralGraph()
Return type:

UndiGraph

moralizedAncestralGraph(*args)
Return type:

UndiGraph

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

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

UndiGraph

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

clear()

Remove all the nodes and edges from the graph.

Return type:

None

static completeGraph(n)
Parameters:

n (int)

Return type:

UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

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

hasUndirectedCycle()

Checks whether the graph contains cycles.

Returns:

True if the graph contains a cycle

Return type:

bool

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

nodes2ConnectedComponent()
Return type:

Dict[int, 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:

pyAgrum.UndiGraph

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

Clique Graph

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

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[int]

Raises:

pyAgrum.NotFound – If the clique does not belong to the clique graph

static completeGraph(n)
Parameters:

n (int)

Return type:

UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

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

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

isJoinTree()
Returns:

True if the graph is a join tree

Return type:

bool

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

nodes2ConnectedComponent()
Return type:

Dict[int, 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:

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[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 (Set[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

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

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

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

node (int)

Return type:

List[int]

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 edges from the graph.

Return type:

None

static completeGraph(n)
Parameters:

n (int)

Return type:

UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

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

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

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen 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)
Parameters:

  • node1 (int)

  • node2 (int)

Return type:

bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

Returns:

True if the graph contains a cycle

Return type:

bool

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

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

nodes2ConnectedComponent()
Return type:

Dict[int, int]

parents(id)
Parameters:

id (int) – The id of the child node

Returns:

the set of the parents 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

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

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()
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

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

cSeparation(*args)
Return type:

bool

chainComponent(node)
Parameters:

node (int)

Return type:

List[int]

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 edges from the graph.

Return type:

None

static completeGraph(n)
Parameters:

n (int)

Return type:

UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

The firstly visited node for each component is called a ‘root’ and is used as a key for the component. This root has been arbitrarily chosen during the algorithm.

Returns:

dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.

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

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

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen 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)
Parameters:

  • node1 (int)

  • node2 (int)

Return type:

bool

hasMixedReallyOrientedPath(n1, n2)
Parameters:

  • n1 (int)

  • n2 (int)

Return type:

bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

Returns:

True if the graph contains a cycle

Return type:

bool

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()
Return type:

UndiGraph

moralizedAncestralGraph(*args)
Return type:

UndiGraph

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

nodes2ConnectedComponent()
Return type:

Dict[int, int]

parents(id)
Parameters:

id (int) – The id of the child node

Returns:

the set of the parents 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

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