Path: DBAI > Research > Projects > D-FLAT Project > Software > D-FLAT System > Practice > Minimum Vertex Cover
Tools: Print
Minimum Vertex Cover
%dflat: -d td -n semi --lazy --tables -e vertex -e edge --no-empty-leaves
%add this to command or modeline: --no-empty-root
% Declare atoms passing on information from child rows.
#external childItem(in(X)) : childNode(N), bag(N,X).
#external childItem(out(X)) : childNode(N), bag(N,X).
#external childItem(X) : childNode(N), bag(N,X).
#external childCost(0..C): maxCost(C).
% Only join rows that conincide on vertices belonging to the set.
:- childItem(in(X)), childItem(out(X)).
% Retain relevant information.
item(in(X)) :- childItem(in(X)), current(X).
item(out(X)) :- childItem(out(X)), current(X).
% Guess vertices to be in or out of the vertex cover.
1 { item(in(X)); item(out(X)) } 1 :- introduced(X).
% No adjacent vertices must exist in the set.
:- edge(X,Y), current(X;Y), not item(in(X)), not item(in(Y)).
% Leaf node costs.
cost(C) :- initial, C = #count{ X : item(in(X)) }.
% Exchange node costs
cost(CC + IC) :- childCost(CC),
IC = #count{ X : item(in(X)), introduced(X) }.
% Costs corresponding to current node.
currentCost(C) :- C = #count{ X : item(in(X)) }.
#show item/1. #show auxItem/1.
#show childItem/1. #show childAuxItem/1. #show childCost/1.
Last updated: 2017-08-30 17:51