# 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:
What is the probability that =a= and =e= are connected?
What is the probability that =a= and =e= are connected represented graphically?
## Code We use tabling to avoid non termination:
:- use_module(library(pita)). :- use_module(library(tabling)). :- 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:
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:
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.