% 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.