% Copyright (C) 2013 Peter Schueller
%
% minimize 'res' graph diameter
%
#const gmin = res.
% guess number between 1 and #nodes/2+1 for one node
nodecount(G,MD) :- G=gmin, MD = #count { N : gn(G,N) }.
1 { guessnum(G,1..(MD/2+1)) } 1 :- G=gmin, nodecount(G,MD).
% guess node(s) to be reachable with number N
% (multiple nodes because the graph might be disconnected)
{ guessreachable(G,N) } :- G=gmin, gn(G,N).
% compute transitive closure (undirected) from guessreachable nodes
% while decrementing the number until 0
reachable(G,N,Num) :- G=gmin, guessreachable(G,N), guessnum(G,Num).
reachable(G,N2,Num-1) :- G=gmin, reachable(G,N1,Num), ge(G,N1,N2), Num>0.
reachable(G,N1,Num-1) :- G=gmin, reachable(G,N2,Num), ge(G,N1,N2), Num>0.
% require that all nodes are reached (some may not because of <0)
reached(G,N) :- G=gmin, reachable(G,N,_).
:- G=gmin, gn(G,N), not reached(G,N).
print(@concat(("half-diameter ",N))) :- guessnum(gmin,N).
%
% starting points
%
% minimize guessed starting points
% (if we need more than 1 the graph is disconnected and we obtain also an error)
%#minimize { guessreachable(gmin,Node) }.
% check if graph is disconnected (we really want to avoid this)
error("graph disconnected!",G) :- G=gmin, 2 { guessreachable(G,N) }.
% guess exactly one to be reachable (we assume connected graphs!)
:- G=gmin, not 1 { guessreachable(G,N) } 1.
diameter(N) :- guessnum(gmin,N).
%
% optimize
%
% minimize number of steps to reach all vertices (=minimize half diameter of graph)
%#minimize [ diameter(N) = N ].
%#show guessreachable/2.
%#show guessnum/2.