BN State Space
Since a Bayesian network is a directed acyclical graph, it can be represented as a series of ordered nodes connected by directed arcs. The nodes are ordered in a hierarchy where a node cannot be the parent of another node higher in the hierarchy. In other words, the nodes are topologically ordered.
- BNStateSpace.py
import math def C(n, r): '''C(n, r)->Integer representing the combination of n things taken r at a time. n: Number of things in "bag" r: Number of things taken from the "bag"''' return math.factorial(n)/(math.factorial(n - r)*math.factorial(r)); def bnStateSpace(n): '''bnStateSpace(n)->Integer representing a rough approximation of the number of possible BN configurations n: The number of nodes in the Bayesian network''' sumSS = 0; # A BN with n nodes can have n-1 to n*(n - 1)/2 arcs # Thus, a BN with 5 nodes can have 4 to 10 arcs for i in range(n - 1, n*(n - 1)/2 + 1): # Combinations of max arcs taken i at a time # representing the number of legal BN configurations with i arcs sumSS += C(n*(n - 1)/2, i); return sumSS # Print out BN state space for BNs with 1 to 10 nodes for i in range(1, 11): print '%i: %12.0f' % (i, bnStateSpace(i)); # Calculate BN state space from user input print 'BN state space: %12.0f' % (bnStateSpace(input("Number of nodes in BN: "))); # Pause before ending execution raw_input();