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 gum.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
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
(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
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
(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.
-
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
(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
-
hasDirectedPath
(self, _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
Returns: True if the directed path exists
Return type: bool
-
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
-
toDot
(self)¶ Returns: a friendly display of the graph in DOT format Return type: str
-
topologicalOrder
(self, clear=True)¶ 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.
- DAG() -> DAG
- default constructor
- DAG(src) -> DAG
- Parameters:
- src (DAG) – 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 arcgum.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.
-
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
(self, X, Y, Z)¶ dSeparation(self, X, Y, Z) -> bool
-
empty
(self)¶ Check if the graph is empty.
Returns: True if the graph is empty Return type: bool
-
emptyArcs
(self)¶
-
eraseArc
(self, n1, n2)¶
-
eraseChildren
(self, n)¶
-
eraseNode
(self, id)¶ Erase the node and all the related arcs.
Parameters: id (int) – the id of the node
-
eraseParents
(self, n)¶
-
existsArc
(self, n1, n2)¶
-
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
-
hasDirectedPath
(self, _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
Returns: True if the directed path exists
Return type: bool
-
moralGraph
(self)¶
-
moralizedAncestralGraph
(self, nodes)¶
-
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)¶
-
toDot
(self)¶ Returns: a friendly display of the graph in DOT format Return type: str
-
topologicalOrder
(self, clear=True)¶ 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.
- UndiGraph() -> UndiGraph
- default constructor
- UndiGraph(src) -> UndiGraph
- Parameters!
- src (UndiGraph) – the pyAgrum.UndiGraph to copy
-
addEdge
(self, first, second)¶ 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.
-
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
(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
-
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
-
nodes2ConnectedComponent
(self)¶
-
partialUndiGraph
(self, nodes)¶ 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
-
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.
- CliqueGraph() -> CliqueGraph
- default constructor
- CliqueGraph(src) -> CliqueGraph
- Parameter
- 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 existgum.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
-
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
(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
-
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
-
nodes2ConnectedComponent
(self)¶
-
partialUndiGraph
(self, nodes)¶ 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, 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
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
-
toDot
(self)¶ Returns: a friendly display of the graph in DOT format Return type: str
-
toDotWithNames
(bn)¶ Parameters: - bn (pyAgrum.BayesNet) –
- Bayesian network (a) –
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
(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
-
adjacents
(self, id)¶
-
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.
-
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
(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 related arcs and 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
-
hasDirectedPath
(self, _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
Returns: True if the directed path exists
Return type: bool
-
hasUndirectedCycle
(self)¶ Checks whether the graph contains cycles.
Returns: True if the graph contains a cycle Return type: bool
-
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). If no path is found, the returned list is empty.
Return type: List
-
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). If no path is found, the list is empty.
Return type: List
-
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
-
nodes2ConnectedComponent
(self)¶
-
parents
(self, id)¶ Parameters: id – The id of the child node Returns: the set of the parents ids. Return type: Set
-
partialUndiGraph
(self, nodes)¶ 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
-
toDot
(self)¶ Returns: a friendly display of the graph in DOT format Return type: str
-
topologicalOrder
(self, clear=True)¶ Returns: the list of the nodes Ids in a topological order Return type: List Raises: gum.InvalidDirectedCycle
– If this graph contains cycles