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.

Available ructors:

Arc(tail, head) -> Arc

Arc(src) -> Arc

Parameters:
  • tail (int) – the tail
  • head (int) – the head
  • src – the Arc to copy
first(self)
Returns:the nodeId of the first node of the arc (the tail)
Return type:int
head(self)
Returns:the id of the head node
Return type:int
other(self, id)
Parameters:id (int) – the nodeId of the head or the tail
Returns:the nodeId of the other node
Return type:int
second(self)
Returns:the nodeId of the second node of the arc (the head)
Return type:int
tail(self)
Returns:the id of the tail node
Return type:int
thisown

The membership flag

Edge

class pyAgrum.Edge(*args)

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

Available ructors :

Edge(aN1,aN2) -> Edge

Edge(src) -> Edge

Parameters:
  • aN1 (int) – the nodeId of the first node
  • aN2 (int) – the nodeId of the secondnode
  • src (pyAgrum.Edge) – the Edge to copy
first(self)
Returns:the nodeId of the first node of the arc (the tail)
Return type:int
other(self, 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(self)
Returns:the nodeId of the second node of the arc (the head)
Return type:int
thisown

The membership flag

Directed Graphs

Digraph

class pyAgrum.DiGraph(*args)

DiGraph represents a Directed Graph.

Available ructors:

DiGraph() -> DiGraph

DiGraph(src) -> DiGraph

Parameters:src (pyAgrum.DiGraph) – the digraph to copy
addArc(self, tail, head)

addArc(self, 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
Raises:

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

addNode(self)
Returns:the new NodeId
Return type:int
addNodeWithId(self, id)

Add a node by choosing a new NodeId.

Parameters:id (int) – The id of the new node
Raises:gum.DuplicateElement – If the given id is already used
addNodes(self, n)

Add n nodes.

Parameters:n (int) – the number of nodes to add.
Returns:the new ids
Return type:Set of int
arcs(self)
Returns:the list of the arcs
Return type:List
children(self, id)
Parameters:id (int) – the id of the parent
Returns:the set of all the children
Return type:Set
clear(self)

Remove all the nodes and arcs from the graph.

empty(self)

Check if the graph is empty.

Returns:True if the graph is empty
Return type:bool
emptyArcs(self)

Check if the graph doesn’t contains arcs.

Returns:True if the graph doesn’t contains arcs
Return type:bool
eraseArc(self, 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
eraseChildren(self, n)

Erase the arcs heading through the node’s children.

Parameters:n (int) – the id of the parent node
eraseNode(self, id)

Erase the node and all the related arcs.

Parameters:id (int) – the id of the node
eraseParents(self, n)

Erase the arcs coming to the node.

Parameters:n (int) – the id of the child node
existsArc(self, 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(self, 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
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

nodes(self)
Returns:the set of ids
Return type:set
parents(self, id)
Parameters:id – The id of the child node
Returns:the set of the parents ids.
Return type:Set
size(self)
Returns:the number of nodes in the graph
Return type:int
sizeArcs(self)
Returns:the number of arcs in the graph
Return type:int
thisown

The membership flag

toDot(self)
Returns:a friendly display of the graph in DOT format
Return type:str
topologicalOrder(self, clear=True)

topologicalOrder(self) -> pyAgrum.Sequence< int >

Returns:the list of the nodes Ids in a topological order
Return type:List
Raises:gum.InvalidDirectedCycle – If this graph contains cycles

Directed Acyclic Graph

class pyAgrum.DAG(*args)

DAG represents a Directed Acyclic Graph.

Available ructors:

DAG() -> DAG

DAG(src) -> DAG

Parameters:src – the DAG to copy
addArc(self, tail, head)

addArc(self, 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
Raises:
  • gum.InvalidDirectedCircle – If any (directed) cycle is created by this arc
  • gum.InvalidNode – If head or tail does not belong to the graph nodes
addNode(self)
Returns:the new NodeId
Return type:int
addNodeWithId(self, id)

Add a node by choosing a new NodeId.

Parameters:id (int) – The id of the new node
Raises:gum.DuplicateElement – If the given id is already used
addNodes(self, n)
arcs(self)
Returns:the list of the arcs
Return type:List
children(self, id)
Parameters:id (int) – the id of the parent
Returns:the set of all the children
Return type:Set
clear(self)

Remove all the nodes and arcs from the graph.

empty(self)

Check if the graph is empty.

Returns:True if the graph is empty
Return type:bool
emptyArcs(self)

Check if the graph doesn’t contains arcs.

Returns:True if the graph doesn’t contains arcs
Return type:bool
eraseArc(self, 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
eraseChildren(self, n)

Erase the arcs heading through the node’s children.

Parameters:n (int) – the id of the parent node
eraseNode(self, id)

Erase the node and all the related arcs.

Parameters:id (int) – the id of the node
eraseParents(self, n)

Erase the arcs coming to the node.

Parameters:n (int) – the id of the child node
existsArc(self, 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(self, 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
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

nodes(self)
Returns:the set of ids
Return type:set
parents(self, id)
Parameters:id – The id of the child node
Returns:the set of the parents ids.
Return type:Set
size(self)
Returns:the number of nodes in the graph
Return type:int
sizeArcs(self)
Returns:the number of arcs in the graph
Return type:int
thisown

The membership flag

toDot(self)
Returns:a friendly display of the graph in DOT format
Return type:str
topologicalOrder(self, clear=True)

topologicalOrder(self) -> pyAgrum.Sequence< int >

Returns:the list of the nodes Ids in a topological order
Return type:List
Raises:gum.InvalidDirectedCycle – If this graph contains cycles

Undirected Graphs

UndiGraph

class pyAgrum.UndiGraph(*args)

UndiGraph represents an Undirected Graph.

Available ructors:

UndiGraph() -> UndiGraph

UndiGraph(src) -> UndiGraph

Parameters:src – the UndiGraph to copy
addEdge(self, 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:

gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.

addNode(self)
Returns:the new NodeId
Return type:int
addNodeWithId(self, id)

Add a node by choosing a new NodeId.

Parameters:id (int) – The id of the new node
Raises:gum.DuplicateElement – If the given id is already used
addNodes(self, n)

Add n nodes.

Parameters:n (int) – the number of nodes to add.
Returns:the new ids
Return type:Set of int
clear(self)

Remove all the nodes and edges from the graph.

edges(self)
Returns:the list of the edges
Return type:List
empty(self)

Check if the graph is empty.

Returns:True if the graph is empty
Return type:bool
emptyEdges(self)

Check if the graph doesn’t contains edges.

Returns:True if the graph doesn’t contains edges
Return type:bool
eraseEdge(self, 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
eraseNeighbours(self, n)

Erase all the edges adjacent to a given node.

Parameters:n (int) – the id of the node
eraseNode(self, id)

Erase the node and all the adjacent edges.

Parameters:id (int) – the id of the node
existsEdge(self, 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(self, 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(self)

Checks whether the graph contains cycles.

Returns:True if the graph contains a cycle
Return type:bool
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

neighbours(self, id)
Parameters:id (int) – the id of the checked node
Returns:The set of edges adjacent to the given node
Return type:Set
nodes(self)
Returns:the set of ids
Return type:set
partialUndiGraph(self, nodesSet)
Parameters:nodesSet (Set) – The set of nodes composing the partial graph
Returns:The partial graph formed by the nodes given in parameter
Return type:pyAgrum.UndiGraph
size(self)
Returns:the number of nodes in the graph
Return type:int
sizeEdges(self)
Returns:the number of edges in the graph
Return type:int
thisown

The membership flag

toDot(self)
Returns:a friendly display of the graph in DOT format
Return type:str

Clique Graph

class pyAgrum.CliqueGraph(*args)

CliqueGraph represents a Clique Graph.

Available ructors:

CliqueGraph() -> CliqueGraph

CliqueGraph(src) -> CliqueGraph

Parameters:src (pyAgrum.CliqueGraph) – the CliqueGraph to copy
addEdge(self, 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
Raises:

gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.

addNode(self, clique)

addNode(self) -> int addNode(self, id, clique) addNode(self, id)

Returns:the new NodeId
Return type:int
addNodeWithId(self, id)

Add a node by choosing a new NodeId.

Parameters:id (int) – The id of the new node
Raises:gum.DuplicateElement – If the given id is already used
addNodes(self, n)

Add n nodes.

Parameters:n (int) – the number of nodes to add.
Returns:the new ids
Return type:Set of int
addToClique(self, 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:
  • gum.NotFound – If clique_id does not exist
  • gum.DuplicateElement – If clique_id set already contains the ndoe
clear(self)

Remove all the nodes and edges from the graph.

clearEdges(self)

Remove all edges and their separators

clique(self, clique)
Parameters:idClique (int) – the id of the clique
Returns:The set of nodes included in the clique
Return type:Set
Raises:gum.NotFound – If the clique does not belong to the clique graph
container(self, idNode)
Parameters:idNode (int) – the id of the node
Returns:the id of a clique containing the node
Return type:int
Raises:gum.NotFound – If no clique contains idNode
containerPath(self, 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:

gum.NotFound – If such path cannot be found

edges(self)
Returns:the list of the edges
Return type:List
empty(self)

Check if the graph is empty.

Returns:True if the graph is empty
Return type:bool
emptyEdges(self)

Check if the graph doesn’t contains edges.

Returns:True if the graph doesn’t contains edges
Return type:bool
eraseEdge(self, 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
eraseFromClique(self, 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:

gum.NotFound – If clique_id does not exist

eraseNeighbours(self, n)

Erase all the edges adjacent to a given node.

Parameters:n (int) – the id of the node
eraseNode(self, node)

Erase the node and all the adjacent edges.

Parameters:id (int) – the id of the node
existsEdge(self, 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(self, 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(self)
Returns:True if the running intersection property holds
Return type:bool
hasUndirectedCycle(self)

Checks whether the graph contains cycles.

Returns:True if the graph contains a cycle
Return type:bool
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

isJoinTree(self)
Returns:True if the graph is a join tree
Return type:bool
neighbours(self, id)
Parameters:id (int) – the id of the checked node
Returns:The set of edges adjacent to the given node
Return type:Set
nodes(self)
Returns:the set of ids
Return type:set
partialUndiGraph(self, nodesSet)
Parameters:nodesSet (Set) – The set of nodes composing the partial graph
Returns:The partial graph formed by the nodes given in parameter
Return type:pyAgrum.UndiGraph
separator(self, edge)

separator(self, clique1, clique) -> Set

Parameters:
  • edge (pyAgrum.Edge) – the edge to be checked
  • clique1 (int) – one extremity of the edge
  • clique (int) – the other extremity of the edge
Returns:

the separator included in a given edge

Return type:

Set

Raises:

gum.NotFound – If the edge does not belong to the clique graph

setClique(self, 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:

gum.NotFound – If idClique is not a clique of the graph

size(self)
Returns:the number of nodes in the graph
Return type:int
sizeEdges(self)
Returns:the number of edges in the graph
Return type:int
thisown

The membership flag

toDot(self)
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 Clique Graph.

Available ructors:

MixedGraph() -> MixedGraph

MixedGraph(src) -> MixedGraph

Parameters:src (pyAgrum.MixedGraph) – the MixedGraph to copy
addArc(self, tail, head)

addArc(self, 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
Raises:

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

addEdge(self, 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:

gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.

addNode(self)
Returns:the new NodeId
Return type:int
addNodeWithId(self, id)

Add a node by choosing a new NodeId.

Parameters:id (int) – The id of the new node
Raises:gum.DuplicateElement – If the given id is already used
addNodes(self, n)

Add n nodes.

Parameters:n (int) – the number of nodes to add.
Returns:the new ids
Return type:Set of int
arcs(self)
Returns:the list of the arcs
Return type:List
children(self, id)
Parameters:id (int) – the id of the parent
Returns:the set of all the children
Return type:Set
clear(self)

Remove all the nodes and edges from the graph.

edges(self)
Returns:the list of the edges
Return type:List
empty(self)

Check if the graph is empty.

Returns:True if the graph is empty
Return type:bool
emptyArcs(self)

Check if the graph doesn’t contains arcs.

Returns:True if the graph doesn’t contains arcs
Return type:bool
emptyEdges(self)

Check if the graph doesn’t contains edges.

Returns:True if the graph doesn’t contains edges
Return type:bool
eraseArc(self, 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
eraseChildren(self, n)

Erase the arcs heading through the node’s children.

Parameters:n (int) – the id of the parent node
eraseEdge(self, 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
eraseNeighbours(self, n)

Erase all the edges adjacent to a given node.

Parameters:n (int) – the id of the node
eraseNode(self, id)

Erase the node and all the adjacent edges.

Parameters:id (int) – the id of the node
eraseParents(self, n)

Erase the arcs coming to the node.

Parameters:n (int) – the id of the child node
existsArc(self, 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(self, 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(self, 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(self)

Checks whether the graph contains cycles.

Returns:True if the graph contains a cycle
Return type:bool
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

mixedOrientedPath(self, 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)

Return type:

List

Raises:

gum.NotFound – If no path can be found between the two nodes

mixedUnorientedPath(self, 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)

Return type:

List

Raises:

gum.NotFound – If no path can be found between the two nodes

neighbours(self, id)
Parameters:id (int) – the id of the checked node
Returns:The set of edges adjacent to the given node
Return type:Set
nodes(self)
Returns:the set of ids
Return type:set
parents(self, id)
Parameters:id – The id of the child node
Returns:the set of the parents ids.
Return type:Set
partialUndiGraph(self, nodesSet)
Parameters:nodesSet (Set) – The set of nodes composing the partial graph
Returns:The partial graph formed by the nodes given in parameter
Return type:pyAgrum.UndiGraph
size(self)
Returns:the number of nodes in the graph
Return type:int
sizeArcs(self)
Returns:the number of arcs in the graph
Return type:int
sizeEdges(self)
Returns:the number of edges in the graph
Return type:int
thisown

The membership flag

toDot(self)
Returns:a friendly display of the graph in DOT format
Return type:str
topologicalOrder(self, clear=True)

topologicalOrder(self) -> pyAgrum.Sequence< int >

Returns:the list of the nodes Ids in a topological order
Return type:List
Raises:gum.InvalidDirectedCycle – If this graph contains cycles