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

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

arcs()
Returns

the list of the arcs

Return type

List

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

connectedComponents()

connected components from a graph/BN

Compute the connected components of a pyAgrum’s graph or Bayesian Network (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(clear=True)
Returns

the list of the nodes Ids in a topological order

Return type

List

Raises

pyAgrum.InvalidDirectedCycle – If this graph contains cycles

Parameters

clear (bool) –

Directed Acyclic Graph

class pyAgrum.DAG(*args)

DAG represents a Directed Acyclic Graph.

DAG() -> DAG

default constructor

DAG(src) -> DAG
Parameters:
  • src (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.InvalidDirectedCircle – If any (directed) cycle is created by this arc

  • pyAgrum.InvalidNode – If head or tail does not belong to the graph nodes

Return type

None

addNode()
Returns

the new NodeId

Return type

int

addNodeWithId(id)

Add a node by choosing a new NodeId.

Parameters

id (int) – The id of the new node

Raises

pyAgrum.DuplicateElement – If the given id is already used

Return type

None

addNodes(n)

Add n nodes.

Parameters

n (int) – the number of nodes to add.

Returns

the new ids

Return type

Set of int

arcs()
Returns

the list of the arcs

Return type

List

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

connectedComponents()

connected components from a graph/BN

Compute the connected components of a pyAgrum’s graph or Bayesian Network (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

pyAgrum.UndiGraph

moralizedAncestralGraph(nodes)
Parameters

nodes (List[int]) –

Return type

pyAgrum.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(clear=True)
Returns

the list of the nodes Ids in a topological order

Return type

List

Raises

pyAgrum.InvalidDirectedCycle – If this graph contains cycles

Parameters

clear (bool) –

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

clear()

Remove all the nodes and edges from the graph.

Return type

None

connectedComponents()

connected components from a graph/BN

Compute the connected components of a pyAgrum’s graph or Bayesian Network (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

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

connectedComponents()

connected components from a graph/BN

Compute the connected components of a pyAgrum’s graph or Bayesian Network (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 (pyAgrum.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

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

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

adjacents(*args)

adjacents nodes are neighbours (not oriented), children and parents

Parameters

id (int) – the id of the node

Returns

the set of node ids.

Return type

set

arcs()
Returns

the list of the arcs

Return type

List

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

connectedComponents()

connected components from a graph/BN

Compute the connected components of a pyAgrum’s graph or Bayesian Network (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(id)

Erase the node and all the related arcs and edges.

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

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

hasUndirectedCycle()

Checks whether the graph contains cycles.

Returns

True if the graph contains a cycle

Return type

bool

mixedOrientedPath(*args)
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(*args)
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(clear=True)
Returns

the list of the nodes Ids in a topological order

Return type

List

Raises

pyAgrum.InvalidDirectedCycle – If this graph contains cycles

Parameters

clear (bool) –