# Computing the probability of a path between two nodes in an undirected probabilistic graph An undirected 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).

## Code We use tabling to avoid non termination:

:- use_module(library(pita)). :- if(current_predicate(use_rendering/1)). :- use_rendering(c3). :- use_rendering(graphviz). :- endif. :- pita.

We declare path/2 as tabled

:- table path/2. :- 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 a path between X and Z and there is an edge between Z and Y

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

Edges are undirected

edge(X,Y):-arc(X,Y). edge(X,Y):-arc(Y,X).

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

arc(a,b):0.2.

Other probabilistic arcs:

arc(b,e):0.5. arc(a,c):0.3. arc(c,d):0.4. arc(d,e):0.4. arc(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,dir=none]), clause(arc(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.