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

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

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

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 a set of n nodes.

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

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: Set

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: Set

clear()

Remove all the nodes and arcs from the graph.

• Return type: None

static completeGraph(n)

• Parameters: n (int)
• Return type: DiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading through the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseNode(id)

Erase the node and all the related arcs.

• Parameters: id (int) – the id of the node
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

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

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

nodes()

• Returns: the set of ids
• Return type: set

parents(id)

• Parameters: id (int) – The id of the child node
• Returns: the set of the parents ids.
• Return type: Set

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

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

class pyagrum.DAG(*args)

DAG represents a Directed Graph.

DAG() -> DAG : default constructor

DAG(src) -> DAG : Parameters: : - src (pyagrum.DAG) – the DAG to copy

addArc(*args)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
• Raises:
  • pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
  • pyagrum.CycleDetected – If a cycle is detected
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises:
  • pyagrum.DuplicateElement –
  • If the given id is already used –
• Return type: None

addNodes(n)

Add a set of n nodes.

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

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: Set

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: Set

clear()

Remove all the nodes and arcs from the graph.

• Return type: None

static completeGraph(n)

• Parameters: n (int)
• Return type: DiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

dSeparation(*args)

Check if the sets of nodes X and Y are d-separated (by the set of nodes Z if given) in the DAG.

• Parameters:
  • X (int sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Y (int sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Z (int sequence of int (**optional )) – a sequence of node ids (int) or a single node id (int)
• Returns: True if X and Y are d-separated (by Z if given), False otherwise.
• 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

minimalCondSet(*args)

• Return type: list[int]

moralGraph()

• Return type: UndiGraph

moralizedAncestralGraph(*args)

Compute the moralized ancestral graph of the nodes from the DAG.

• Parameters: nodes (int sequence of int) – a sequence of node ids (int) or a single node id (int)
• Returns: the moralized ancestral graph of the nodes from the DAG.
• 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()

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

Undirected Graphs

class pyagrum.UndiGraph(*args)

UndiGraph represents an Undirected Graph.

UndiGraph() -> UndiGraph : default constructor

UndiGraph(src) -> UndiGraph : Parameters! : - src (UndiGraph) – the pyagrum.UndiGraph to copy

addEdge(*args)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

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

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

• Parameters: n (int)
• Return type: UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

edges()

• Returns: the list of the edges
• Return type: List

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseEdge(n1, n2)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(id)

Erase the node and all the adjacent edges.

• Parameters: id (int) – the id of the node
• Return type: None

existsEdge(n1, n2)

Check if an edge exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

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

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: Set

nodes()

• Returns: the set of ids
• Return type: set

nodes2ConnectedComponent()

• Return type: dict[int, int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: pyagrum.UndiGraph

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

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:
  • pyagrum.NotFound –
  • If clique_id does not exist –
  • pyagrum.DuplicateElement –
  • If clique_id set already contains the ndoe –
• Return type: None

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

clear()

Remove all the nodes and edges from the graph.

• Return type: None

clearEdges()

Remove all edges and their separators

• Return type: None

clique(clique)

• Parameters:
  • idClique (int) – the id of the clique
  • clique (int)
• Returns: The set of nodes included in the clique
• Return type: Set[int]
• Raises: pyagrum.NotFound – If the clique does not belong to the clique graph

static completeGraph(n)

• Parameters: n (int)
• Return type: UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

container(idNode)

• Parameters: idNode (int) – the id of the node
• Returns: the id of a clique containing the node
• Return type: int
• Raises: pyagrum.NotFound – If no clique contains idNode

containerPath(node1, node2)

• Parameters:
  • node1 (int) – the id of one node
  • node2 (int) – the id of the other node
• Returns: a path from a clique containing node1 to a clique containing node2
• Return type: List
• Raises: pyagrum.NotFound – If such path cannot be found

edges()

• Returns: the list of the edges
• Return type: List

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseEdge(edge)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
  • edge (Edge)
• Return type: None

eraseFromClique(clique_id, node_id)

Remove a node from a clique

• Parameters:
  • clique_id (int) – the id of the clique
  • node_id (int) – the id of the node
• Raises: pyagrum.NotFound – If clique_id does not exist
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(node)

Erase the node and all the adjacent edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

existsEdge(n1, n2)

Check if an edge exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

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

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasRunningIntersection()

• Returns: True if the running intersection property holds
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

isJoinTree()

• Returns: True if the graph is a join tree
• Return type: bool

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: Set

nodes()

• Returns: the set of ids
• Return type: set

nodes2ConnectedComponent()

• Return type: dict[int, int]

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: pyagrum.UndiGraph

separator(cliq1, cliq2)

• Parameters:
  • edge (pyagrum.Edge) – the edge to be checked
  • clique1 (int) – one extremity of the edge
  • clique (int) – the other extremity of the edge
  • cliq1 (int)
  • cliq2 (int)
• Returns: the separator included in a given edge
• Return type: Set[int]
• Raises: pyagrum.NotFound – If the edge does not belong to the clique graph

setClique(idClique, new_clique)

changes the set of nodes included into a given clique

• Parameters:
  • idClique (int) – the id of the clique
  • new_clique (Set [**int ]) – the new set of nodes to be included in the clique
• Raises: pyagrum.NotFound – If idClique is not a clique of the graph
• Return type: None

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

toDotWithNames(bn)

• Parameters:
  • bn (pyagrum.BayesNet)
  • network (a Bayesian)
• Returns: a friendly display of the graph in DOT format where ids have been changed according to their correspondance in the BN
• Return type: str

Mixed Graph

class pyagrum.MixedGraph(*args)

MixedGraph represents a graph with both arcs and edges.

MixedGraph() -> MixedGraph : default constructor

MixedGraph(src) -> MixedGraph : Parameters: : - src (pyagrum.MixedGraph) –the MixedGraph to copy

addArc(n1, n2)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
  • n1 (int)
  • n2 (int)
• Raises: pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
• Return type: None

addEdge(n1, n2)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

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

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: Set

boundary(id)

Boundary are neighbours (not oriented), children and parents

• Parameters: id (int) – the id of the node
• Returns: the set of node ids.
• Return type: set

chainComponent(node)

• Parameters: node (int)
• Return type: list[int]

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: Set

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

• Parameters: n (int)
• Return type: UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

edges()

• Returns: the list of the edges
• Return type: List

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading through the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseEdge(n1, n2)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(node)

Erase the node and all the related arcs and edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsEdge(n1, n2)

Check if an edge exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

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

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasMixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int)
  • node2 (int)
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

mixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id form which the path begins
  • node2 (int) – the id to witch the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (following the direction of the arcs). If no path is found, the returned list is empty.
• Return type: List

mixedUnorientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id from which the path begins
  • node2 (int) – the id to which the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of the arcs). If no path is found, the list is empty.
• Return type: List

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: Set

nodes()

• Returns: the set of ids
• Return type: set

nodes2ConnectedComponent()

• Return type: dict[int, int]

parents(id)

• Parameters: id (int) – The id of the child node
• Returns: the set of the parents ids.
• Return type: Set

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: pyagrum.UndiGraph

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

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

Partially Directed Graph (DAG)

class pyagrum.PDAG(*args)

PDAG represents a graph with both arcs and edges.

PDAG() -> PDAG : default constructor

PDAG(src) -> PDAG : Parameters: : - src (pyagrum.PDAG) –the PDAG to copy

addArc(*args)

Add an arc from tail to head.

• Parameters:
  • tail (int) – the id of the tail node
  • head (int) – the id of the head node
• Raises:
  • pyagrum.InvalidNode – If head or tail does not belong to the graph nodes.
  • PyAgrum.InvalidDirectedCycle – if the arc would create a (mixed) cycle.
• Return type: None

addEdge(*args)

Insert a new edge into the graph.

• Parameters:
  • n1 (int) – the id of one node of the new inserted edge
  • n2 (int) – the id of the other node of the new inserted edge
• Raises: pyagrum.InvalidNode – If n1 or n2 does not belong to the graph nodes.
• Return type: None

addNode()

• Returns: the new NodeId
• Return type: int

addNodeWithId(id)

Add a node by choosing a new NodeId.

• Parameters: id (int) – The id of the new node
• Raises: pyagrum.DuplicateElement – If the given id is already used
• Return type: None

addNodes(n)

Add n nodes.

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

adjacencyMatrix()

adjacency matrix from a graph/graphical models

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

• Returns: adjacency matrix (as numpy.ndarray) with nodeId as key.
• Return type: numpy.ndarray

arcs()

Returns the set of arcs in the graph.

• Returns: the set of the arcs
• Return type: Set

boundary(id)

Boundary are neighbours (not oriented), children and parents

• Parameters: id (int) – the id of the node
• Returns: the set of node ids.
• Return type: set

cSeparation(*args)

Check if the sets of nodes X and Y are c-separated (by the set of nodes Z if given) in the PDAG.

• Parameters:
  • X (int sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Y (int sequence of int) – a sequence of node ids (int) or a single node id (int)
  • Z (int sequence of int (**optional )) – a sequence of node ids (int) or a single node id (int)
• Returns: True if X and Y are c-separated (by Z if given), False otherwise.
• Return type: bool

chainComponent(node)

• Parameters: node (int)
• Return type: list[int]

children(id)

• Parameters: id (int) – the id of the parent
• Returns: the set of all the children
• Return type: Set

clear()

Remove all the nodes and edges from the graph.

• Return type: None

static completeGraph(n)

• Parameters: n (int)
• Return type: UndiGraph

connectedComponents()

connected components from a graph/graphical models

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

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

• Returns: dict of connected components (as set of nodeIds (int)) with a nodeId (root) of each component as key.
• Return type: dict(int,Set[int])

edges()

• Returns: the list of the edges
• Return type: List

empty()

Check if the graph is empty.

• Returns: True if the graph is empty
• Return type: bool

emptyArcs()

Check if the graph doesn’t contains arcs.

• Returns: True if the graph doesn’t contains arcs
• Return type: bool

emptyEdges()

Check if the graph doesn’t contains edges.

• Returns: True if the graph doesn’t contains edges
• Return type: bool

eraseArc(n1, n2)

Erase the arc between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseChildren(n)

Erase the arcs heading through the node’s children.

• Parameters: n (int) – the id of the parent node
• Return type: None

eraseEdge(n1, n2)

Erase the edge between n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Return type: None

eraseNeighbours(n)

Erase all the edges adjacent to a given node.

• Parameters: n (int) – the id of the node
• Return type: None

eraseNode(node)

Erase the node and all the related arcs and edges.

• Parameters:
  • id (int) – the id of the node
  • node (int)
• Return type: None

eraseParents(n)

Erase the arcs coming to the node.

• Parameters: n (int) – the id of the child node
• Return type: None

existsArc(n1, n2)

Check if an arc exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of the tail node
  • n2 (int) – the id of the head node
• Returns: True if the arc exists
• Return type: bool

existsEdge(n1, n2)

Check if an edge exists bewteen n1 and n2.

• Parameters:
  • n1 (int) – the id of one extremity of the edge
  • n2 (int) – the id of the other extremity if tge edge
• Returns: True if the arc exists
• Return type: bool

existsNode(id)

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

• Parameters: id (int) – the checked id
• Returns: True if the node exists
• Return type: bool

hasDirectedPath(_from, to)

Check if a directedpath exists bewteen from and to.

• Parameters:
  • from (int) – the id of the first node of the (possible) path
  • to (int) – the id of the last node of the (possible) path
  • _from (int)
• Returns: True if the directed path exists
• Return type: bool

hasMixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int)
  • node2 (int)
• Return type: bool

hasMixedReallyOrientedPath(n1, n2)

• Parameters:
  • n1 (int)
  • n2 (int)
• Return type: bool

hasUndirectedCycle()

Checks whether the graph contains cycles.

• Returns: True if the graph contains a cycle
• Return type: bool

mixedOrientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id form which the path begins
  • node2 (int) – the id to witch the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (following the direction of the arcs). If no path is found, the returned list is empty.
• Return type: List

mixedUnorientedPath(node1, node2)

• Parameters:
  • node1 (int) – the id from which the path begins
  • node2 (int) – the id to which the path ends
• Returns: a path from node1 to node2, using edges and/or arcs (not necessarily following the direction of the arcs). If no path is found, the list is empty.
• Return type: List

moralGraph()

• Return type: UndiGraph

moralizedAncestralGraph(*args)

Compute the moralized ancestral graph of the nodes from the DAG.

• Parameters: nodes (int sequence of int) – a sequence of node ids (int) or a single node id (int)
• Returns: the moralized ancestral graph of the nodes from the DAG.
• Return type: “pyagrum.UndiGraph”

neighbours(id)

• Parameters: id (int) – the id of the checked node
• Returns: The set of edges adjacent to the given node
• Return type: Set

nodes()

• Returns: the set of ids
• Return type: set

nodes2ConnectedComponent()

• Return type: dict[int, int]

parents(id)

• Parameters: id (int) – The id of the child node
• Returns: the set of the parents ids.
• Return type: Set

partialUndiGraph(nodes)

• Parameters:
  • nodesSet (Set) – The set of nodes composing the partial graph
  • nodes (list[int])
• Returns: The partial graph formed by the nodes given in parameter
• Return type: pyagrum.UndiGraph

size()

• Returns: the number of nodes in the graph
• Return type: int

sizeArcs()

• Returns: the number of arcs in the graph
• Return type: int

sizeEdges()

• Returns: the number of edges in the graph
• Return type: int

toDot()

• Returns: a friendly display of the graph in DOT format
• Return type: str

topologicalOrder()

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