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
Arc(src) -> Arc
Parameters:
• src (Arc) – the gum.Arc to copy
first(Arc self)
Returns: the nodeId of the first node of the arc (the tail) int
Returns: the id of the head node int
other(Arc self, int id)
Parameters: id (int) – the nodeId of the head or the tail the nodeId of the other node int
second(Arc self)
Returns: the nodeId of the second node of the arc (the head) int
tail(Arc self)
Returns: the id of the tail node 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(Edge self)
Returns: the nodeId of the first node of the arc (the tail) int
other(Edge self, int id)
Parameters: id (int) – the nodeId of one of the nodes of the Edge the nodeId of the other node int
second(Edge self)
Returns: the nodeId of the second node of the arc (the head) 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(DiGraph self, int n1, int 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 gum.InvalidNode – If head or tail does not belong to the graph nodes.
Returns: the new NodeId int
addNodeWithId(DiGraph self, int id)

Add a node by choosing a new NodeId.

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

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

Remove all the nodes and arcs from the 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.

Parameters: graph (pyAgrum's graph) – A graph, a Bayesian network, more generally an object that has nodes, children/parents or neighbours methods in which the search will take place dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key. dict(int,Set[int])
empty(DiGraph self)

Check if the graph is empty.

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

Check if the graph doesn’t contains arcs.

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

Erase the arcs heading through the node’s children.

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

Erase the node and all the related arcs.

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

Erase the arcs coming to the node.

Parameters: n (int) – the id of the child node
existsArc(DiGraph self, int n1, int 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 True if the arc exists bool
existsNode(DiGraph self, int id)

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

Parameters: id (int) – the checked id True if the node exists bool
hasDirectedPath(DiGraph self, int _from, int 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 True if the directed path exists bool
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

nodes(DiGraph self)
Returns: the set of ids set
parents(DiGraph self, int id)
Parameters: id – The id of the child node the set of the parents ids. Set
size(DiGraph self)
Returns: the number of nodes in the graph int
sizeArcs(DiGraph self)
Returns: the number of arcs in the graph int
toDot(DiGraph self)
Returns: a friendly display of the graph in DOT format str
topologicalOrder(DiGraph self, bool clear=True)
Returns: the list of the nodes Ids in a topological order List gum.InvalidDirectedCycle – If this graph contains cycles

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

Add a node by choosing a new NodeId.

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

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

Remove all the nodes and arcs from the 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.

Parameters: graph (pyAgrum's graph) – A graph, a Bayesian network, more generally an object that has nodes, children/parents or neighbours methods in which the search will take place dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key. dict(int,Set[int])
empty(DiGraph self)

Check if the graph is empty.

Returns: True if the graph is empty bool
emptyArcs(DAG self)
eraseArc(DAG self, int n1, int n2)
eraseChildren(DAG self, int n)
eraseNode(DiGraph self, int id)

Erase the node and all the related arcs.

Parameters: id (int) – the id of the node
eraseParents(DAG self, int n)
existsArc(DAG self, int n1, int n2)
existsNode(DiGraph self, int id)

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

Parameters: id (int) – the checked id True if the node exists bool
hasDirectedPath(DiGraph self, int _from, int 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 True if the directed path exists bool
ids()

Deprecated method in pyAgrum>0.12.0. See nodes instead.

moralGraph(DAG self)
nodes(DiGraph self)
Returns: the set of ids set
parents(DiGraph self, int id)
Parameters: id – The id of the child node the set of the parents ids. Set
size(DiGraph self)
Returns: the number of nodes in the graph int
sizeArcs(DAG self)
toDot(DiGraph self)
Returns: a friendly display of the graph in DOT format str
topologicalOrder(DiGraph self, bool clear=True)
Returns: the list of the nodes Ids in a topological order List gum.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(UndiGraph self, int n1, int 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 gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
Returns: the new NodeId int
addNodeWithId(UndiGraph self, int id)

Add a node by choosing a new NodeId.

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

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

Remove all the nodes and edges from the 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.

Parameters: graph (pyAgrum's graph) – A graph, a Bayesian network, more generally an object that has nodes, children/parents or neighbours methods in which the search will take place dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key. dict(int,Set[int])
edges(UndiGraph self)
Returns: the list of the edges List
empty(UndiGraph self)

Check if the graph is empty.

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

Check if the graph doesn’t contains edges.

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

Erase all the edges adjacent to a given node.

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

Erase the node and all the adjacent edges.

Parameters: id (int) – the id of the node
existsEdge(UndiGraph self, int n1, int 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 True if the arc exists bool
existsNode(UndiGraph self, int id)

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

Parameters: id (int) – the checked id True if the node exists bool
hasUndirectedCycle(UndiGraph self)

Checks whether the graph contains cycles.

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

Deprecated method in pyAgrum>0.12.0. See nodes instead.

neighbours(UndiGraph self, int id)
Parameters: id (int) – the id of the checked node The set of edges adjacent to the given node Set
nodes(UndiGraph self)
Returns: the set of ids set
partialUndiGraph(UndiGraph self, Set nodesSet)
Parameters: nodesSet (Set) – The set of nodes composing the partial graph The partial graph formed by the nodes given in parameter pyAgrum.UndiGraph
size(UndiGraph self)
Returns: the number of nodes in the graph int
sizeEdges(UndiGraph self)
Returns: the number of edges in the graph int
toDot(UndiGraph self)
Returns: a friendly display of the graph in DOT format 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(CliqueGraph self, int first, int 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 gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
addNode(CliqueGraph self, Set clique)

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

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

Add a node by choosing a new NodeId.

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

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

Remove all the nodes and edges from the graph.

clearEdges(CliqueGraph self)

Remove all edges and their separators

clique(CliqueGraph self, int clique)
Parameters: idClique (int) – the id of the clique The set of nodes included in the clique Set gum.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.

Parameters: graph (pyAgrum's graph) – A graph, a Bayesian network, more generally an object that has nodes, children/parents or neighbours methods in which the search will take place dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key. dict(int,Set[int])
container(CliqueGraph self, int idNode)
Parameters: idNode (int) – the id of the node the id of a clique containing the node int gum.NotFound – If no clique contains idNode
containerPath(CliqueGraph self, int node1, int node2)
Parameters: node1 (int) – the id of one node node2 (int) – the id of the other node a path from a clique containing node1 to a clique containing node2 List gum.NotFound – If such path cannot be found
edges(UndiGraph self)
Returns: the list of the edges List
empty(UndiGraph self)

Check if the graph is empty.

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

Check if the graph doesn’t contains edges.

Returns: True if the graph doesn’t contains edges bool
eraseEdge(CliqueGraph self, Edge 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(CliqueGraph self, int clique_id, int 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 gum.NotFound – If clique_id does not exist
eraseNeighbours(UndiGraph self, int n)

Erase all the edges adjacent to a given node.

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

Erase the node and all the adjacent edges.

Parameters: id (int) – the id of the node
existsEdge(UndiGraph self, int n1, int 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 True if the arc exists bool
existsNode(UndiGraph self, int id)

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

Parameters: id (int) – the checked id True if the node exists bool
hasRunningIntersection(CliqueGraph self)
Returns: True if the running intersection property holds bool
hasUndirectedCycle(UndiGraph self)

Checks whether the graph contains cycles.

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

Deprecated method in pyAgrum>0.12.0. See nodes instead.

isJoinTree(CliqueGraph self)
Returns: True if the graph is a join tree bool
neighbours(UndiGraph self, int id)
Parameters: id (int) – the id of the checked node The set of edges adjacent to the given node Set
nodes(UndiGraph self)
Returns: the set of ids set
partialUndiGraph(UndiGraph self, Set nodesSet)
Parameters: nodesSet (Set) – The set of nodes composing the partial graph The partial graph formed by the nodes given in parameter pyAgrum.UndiGraph
separator(CliqueGraph self, int cliq1, int 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 the separator included in a given edge Set gum.NotFound – If the edge does not belong to the clique graph
setClique(CliqueGraph self, int idClique, Set 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 gum.NotFound – If idClique is not a clique of the graph
size(UndiGraph self)
Returns: the number of nodes in the graph int
sizeEdges(UndiGraph self)
Returns: the number of edges in the graph int
toDot(CliqueGraph self)
Returns: a friendly display of the graph in DOT format str
toDotWithNames(bn)
Parameters: bn (pyAgrum.BayesNet) – Bayesian network (a) – a friendly display of the graph in DOT format where ids have been changed according to their correspondance in the BN 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(MixedGraph self, int n1, int 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 gum.InvalidNode – If head or tail does not belong to the graph nodes.
addEdge(MixedGraph self, int n1, int 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 gum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
Returns: the new NodeId int
addNodeWithId(MixedGraph self, int id)

Add a node by choosing a new NodeId.

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

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

Remove all the nodes and edges from the 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.

Parameters: graph (pyAgrum's graph) – A graph, a Bayesian network, more generally an object that has nodes, children/parents or neighbours methods in which the search will take place dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key. dict(int,Set[int])
edges(UndiGraph self)
Returns: the list of the edges List
empty(MixedGraph self)

Check if the graph is empty.

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

Check if the graph doesn’t contains arcs.

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

Check if the graph doesn’t contains edges.

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

Erase the arcs heading through the node’s children.

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

Erase all the edges adjacent to a given node.

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

Erase the node and all the related arcs and edges.

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

Erase the arcs coming to the node.

Parameters: n (int) – the id of the child node
existsArc(MixedGraph self, int n1, int 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 True if the arc exists bool
existsEdge(MixedGraph self, int n1, int 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 True if the arc exists bool
existsNode(MixedGraph self, int id)

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

Parameters: id (int) – the checked id True if the node exists bool
hasDirectedPath(DiGraph self, int _from, int 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 True if the directed path exists bool
hasUndirectedCycle(UndiGraph self)

Checks whether the graph contains cycles.

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

Deprecated method in pyAgrum>0.12.0. See nodes instead.

mixedOrientedPath(MixedGraph self, int node1, int node2)
Parameters: node1 (int) – the id form which the path begins node2 (int) – the id to witch the path ends a path from node1 to node2, using edges and/or arcs (following the direction of the arcs) List gum.NotFound – If no path can be found between the two nodes
mixedUnorientedPath(MixedGraph self, int node1, int node2)
Parameters: node1 (int) – the id from which the path begins node2 (int) – the id to which the path ends a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of the arcs) List gum.NotFound – If no path can be found between the two nodes
neighbours(UndiGraph self, int id)
Parameters: id (int) – the id of the checked node The set of edges adjacent to the given node Set
nodes(UndiGraph self)
Returns: the set of ids set
parents(DiGraph self, int id)
Parameters: id – The id of the child node the set of the parents ids. Set
partialUndiGraph(UndiGraph self, Set nodesSet)
Parameters: nodesSet (Set) – The set of nodes composing the partial graph The partial graph formed by the nodes given in parameter pyAgrum.UndiGraph
size(MixedGraph self)
Returns: the number of nodes in the graph int
sizeArcs(MixedGraph self)
Returns: the number of arcs in the graph int
sizeEdges(MixedGraph self)
Returns: the number of edges in the graph int
toDot(MixedGraph self)
Returns: a friendly display of the graph in DOT format str
topologicalOrder(DiGraph self, bool clear=True)
Returns: the list of the nodes Ids in a topological order List gum.InvalidDirectedCycle – If this graph contains cycles