# Computing the probability of a path between two nodes in a probabilistic graph A probabilistic graph is a graph where each edge has a probability of being present. Consider the probabilistic graph:

graph(G).

What is the probability that =a= and =e= are connected?

prob(path(a,e),Prob).

What is the probability that =a= and =e= are connected represented graphically?

prob(path(a,e),Prob),bar(Prob,C).

What is the BDD for query path(a,e)?

bdd_dot_string(path(a,e),BDD,Var).

A solid edge indicates a 1-child, a dashed edge indicates a 0-child and a dotted edge indicates a negated 0-child. Each level of the BDD is associated to a variable of the form XI_J indicated on the left: I indicates the multivalued variable index and J the index of the Boolean variable of I. The table =Var= contains the associations between the rule groundings and the multivalued variables: the first column contains the multivalued variable index, the second column contains the rule index, corresponding to its position in the program, and the last column contains the list of constants grounding the rule, each replacing a variable in the order of appearance in the rule. ## Code Preamble:

:- use_module(library(pita)). :- if(current_predicate(use_rendering/1)). :- use_rendering(c3). :- use_rendering(graphviz). :- use_rendering(table,[header(['Multivalued variable index','Rule index','Grounding substitution'])]). :- endif. :- pita. :- begin_lpad.

path(X,Y) is true if there is a path between nodes =X= and =Y= edge(a,b) indicates that there is an edge between =a= and =b= There is surely a path between a node and itself:

path(X,X).

There is surely a path between X and Y if there is another node Z such that there is an edge between X and Z and there is a path between Z and Y

path(X,Y):- edge(X,Z),path(Z,Y).

There is an edge between =a= and =b= with probability 0.2:

edge(a,b):0.2.

Other probabilistic edges:

edge(b,e):0.5. edge(a,c):0.3. edge(c,d):0.4. edge(d,e):0.4. edge(a,e):0.1.

End of probabilistic part:

:- end_lpad.

Clause for drawing the graph using the integration with Graphviz:

graph(digraph([rankdir='LR'|G])):- findall(edge(A -> B,[label=P]), clause(edge(A,B,_,_),(get_var_n(_,_,_,_,[P|_],_),_)), G).

## References L. De Raedt, A. Kimmig, and H. Toivonen. ProbLog: A probabilistic Prolog and its application in link discovery. In International Joint Conference on Artificial Intelligence, pages 2462-2467, 2007.