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

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung