/*
*************************************************************************
* A Modified Dijkstra algorithm
* to determine one-to-all shortest paths in a directed unweighted graph
*
* A graph to analyze is specified by a list of its vertices and
* by a set of adjacency lists, for each of the vertices.
* For example, the following facts
* vertices([a,b,c,d,e,f]).
* adjacent(a,[b,d,f]).
* adjacent(b,[c,f]).
* specify a graph with 6 vertices and _directed_ edges a->b, a->d,
* a->f, b->c, b->f. All edges are directed and have a weight ("length",
* "cost", etc) of one.
*
* A predicate shortest_paths(a,ShPaths) would find all shortest paths
* from a to all the other vertices of the graph (if accessible) and
* return the list ShPaths of structures shortest_path(dest,path,length).
* Each structure shortest_path(dest,path,lenth) describes a shortest
* path from vertex 'a' to a vertex 'dest'. For example,
* shortest_path(b,[b,c,a],3)
* tells that the shortest path from 'a' to 'b' goes through 'c'
* and has the length of 3.
*
* As all the edges have the same weight, an edge between two vertices
* is the shortest path between these two vertices. Thus to find shortest
* paths from a given vertex to the others we merely need to perform
* a breadth-first search.
*
* Time complexity
* For every vertex that is accessible from the origin we analyze
* all its neighbors in the adjacency list. We thus look at every directed edge
* in the graph, at most once. Therefore, the time complexity is
* O(e), e being the no. of (directed) edges.
*
*************************************************************************
*/
/* Given below is an example of the graph */
/* to work with */
vertices([a,b,c,d,e,f]).
adjacent(a,[b,d,f]).
adjacent(b,[c,f]).
adjacent(c,[d]).
adjacent(d,[]).
adjacent(e,[f,d]).
adjacent(f,[d]).
/*
*------------------------------------------------------------------------
* Root predicate
* Note, that the global data base is dynamically updated with the
* following facts
* to_handle(x).
* This fact tells a name of a vertex to handle. At first
* it is the vertex-origin. Once a vertex is handled, all its
* neighbors will have to be handled in turn. Note, to_handle(x)
* facts have to form a queue: the facts are picked for processing
* from the top, new facts are added at the bottom.
* This guarantees the breadth-first search.
* free(x).
* This fact tells a vertex a shortest path to which
* hasn't been determined yet.
* shortest_path(x,[x,y,...],size).
* gives the shortest path from the Origin to x
* once established.
*
*/
shortest_path(A,ShPaths) :-
/* Make all the vertices but the initial free */
vertices(Vertices),
make_free(Vertices),
retract(free(A)),
assert(shortest_path(A,[A],0)),
assert(to_handle(A)), /* Start with A */
loop,
setof(shortest_path(X,L,D),shortest_path(X,L,D),ShPaths).
make_free([]).
make_free([X|Y]) :- assert(free(X)), make_free(Y).
loop :- /* Handling the vertices, i.e. extend the path */
retract(to_handle(A)),
adjacent(A,AdjList),
nl,write('Handling the vertex '),write(A),nl,
handle(A,AdjList),
loop.
loop.
/* Extend the path from the Origin through A */
handle(A,[]).
handle(A,[B|Y]) :-
retract(free(B)),
shortest_path(A,Path,Dist), /* Path that has lead to A from origin*/
Dist1 is Dist + 1,
assert(shortest_path(B,[B|Path],Dist1)), /* Extend the path to B */
write(' extending to '),write(B),nl,
assertz(to_handle(B)), /* add to the bottom of queue */
handle(A,Y). /* And handle other neighbors */
handle(A,[_|Y]) :- handle(A,Y). /* If B wasn't free */
% Try it out...
?- print('all shortest pathes from a vertex a'),shortest_path(a,ShPaths),
print(ShPaths).