Graph Module

Graphs

All the nodes in the graph are represented by a name and are associated with a non-negative unique index.

The name can be obtained from the unique index using the method name(), while the unique index can be obtained from the index using the method index().

Removing a node invalidates the index of the removed node, while leaving the other nodes unaffected. When adding a node, the graph may reuse previously invalidated indices to avoid wasting too much memory.

If there are not removal of nodes in a graph, the unique indices are in the range [0-num_nodes()). The removal of nodes, can lead to some indices being greater or equal to num_nodes():

>>> from pybnesian.graph import UndirectedGraph
>>> g = UndirectedGraph(["a", "b", "c", "d"])
>>> g.index("a")
0
>>> g.index("b")
1
>>> g.index("c")
2
>>> g.index("d")
3
>>> g.remove_node("a")
>>> g.index("b")
1
>>> g.index("c")
2
>>> g.index("d")
3
>>> assert g.index("d") >= g.num_nodes()

Sometimes, this effect may be undesirable because we want to identify our nodes with a index in a range [0-num_nodes()). For this reason, there is a collapsed_index() method and other related methods index_from_collapsed(), collapsed_from_index() and collapsed_name(). Note that the collapsed index is not unique, because removing a node can change the collapsed index of at most one other node.

>>> from pybnesian.graph import UndirectedGraph
>>> g = UndirectedGraph(["a", "b", "c", "d"])
>>> g.collapsed_index("a")
0
>>> g.collapsed_index("b")
1
>>> g.collapsed_index("c")
2
>>> g.collapsed_index("d")
3
>>> g.remove_node("a")
>>> g.collapsed_index("b")
1
>>> g.collapsed_index("c")
2
>>> g.collapsed_index("d")
0
>>> assert all([g.collapsed_index(n) < g.num_nodes() for n in g.nodes()])

Conditional Graphs

A conditional graph is the underlying graph in a conditional Bayesian networks ([PGM], Section 5.6). In a conditional Bayesian network, only the normal nodes can have a conditional probability density, while the interface nodes are always observed. A conditional graph splits all the nodes in two subsets: normal nodes and interface nodes. In a conditional graph, the interface nodes can not have parents.

In a conditional graph, normal nodes can be returned with nodes(), the interface nodes with interface_nodes() and the joint set of nodes with joint_nodes(). Also, there are many other functions that have the prefix interface and joint to denote the interface and joint sets of nodes. Among them, there is a collapsed index version for only interface nodes, interface_collapsed_index(), and the joint set of nodes, joint_collapsed_index(). Note that the collapsed index for each set of nodes is independent.

Bibliography

dag2pdag

Chickering, M. (2002). Learning Equivalence Classes of Bayesian-Network Structures. Journal of Machine Learning Research, 2, 445-498.

dag2pdag_extra

Chickering, M. (1995). A Transformational Characterization of Equivalent Bayesian Network Structures. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI’95), Montreal.

pdag2dag

Dorit, D. and Tarsi, M. (1992). A simple algorithm to construct a consistent extension of a partially oriented graph (Report No: R-185).

PGM

Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models. MIT press.