/* ic: library used for CSP declaration and solve*/
:-lib(ic).
/* branch and bound: lirary used to optimize solution */
:-lib(branch_and_bound).


 /*
  *	write the edges' list that create_graph returned.
  */
writelist([]).
writelist([X1-X2],0):-
	write(', '),write(X1),write('-'),write(X2),write(']'),!.
writelist([ X1 - X2 | T],0):-
	write(', '),write(X1),write('-'),write(X2),
	writelist(T,0).
writelist([ X1 - X2 | T],1):-
	write('['),write(X1),write('-'),write(X2),
	writelist(T,0).
 /* 
  *	Create variable set.
  *	Variables for this CSP are the vetrexes of the graph. 
  */
vars(N,G):-
	length(G,N).

 /*
  *	Declare domain set for each variable.
  *	Eacg variable can have either 0 nor 1 for value,where
  *		0 stands for: is not used in graph cover.
  *		1 stands for: is used uin graph cover.
  */
domains(G):-
	G :: 0..1.

 /*
  *	Constraints declaration.
  *		Each edge in graph must have at least one
  *		vertex in solution set.
  *		This gets done if the sum of the variables
  *		that abstract these vertexes in csp
  *		is greater or equal to 1.
  */
constraints(_,[]).
constraints(G,[ X1 - X2 | T]):-
	find(G,X1,R1),
	find(G,X2,R2),
	R1 + R2 #>= 1,
	constraints(G,T).


 /*
  *	find predicate returns the n-th element
  *	from the list of vertexes.
  */
find([H|_],1,H):-!.
find([_|T],CUR,R):-
	N is CUR-1,
	find(T,N,R).

 /*
  *	When the csp gets solved then variables
  *	list will be a sequence of 0 and 1.
  *	1 means that the vertex belongs in solution set
  *	and 0 means it doesn't.
  *	So reading this list and append the positions
  *	where 1 exists will give as the exact solution.
  *	This is what optimal prediacte does for us.
  */
optimal([],[],_):- !.
optimal([1 | T1],[POS | T2],POS):-
	Cur is POS+1,
	optimal(T1,T2,Cur),!.
optimal([0 | T],G,POS):-
	Cur is POS+1,
	optimal(T,G,Cur).

report(_, _, _, _).


 /*
  *	create_graph will create a graph
  *	and return a list of its edges.
  */
create_graph(NNodes, Density, Graph) :-
   cr_gr(1, 2, NNodes, Density, [], Graph).

cr_gr(NNodes, _, NNodes, _, Graph, Graph).
cr_gr(N1, N2, NNodes, Density, SoFarGraph, Graph) :-
   N1 < NNodes,
   N2 > NNodes,
   NN1 is N1 + 1,
   NN2 is NN1 + 1,
   cr_gr(NN1, NN2, NNodes, Density, SoFarGraph, Graph).
cr_gr(N1, N2, NNodes, Density, SoFarGraph, Graph) :-
   N1 < NNodes,
   N2 =< NNodes,
   rand(1, 100, Rand),
   (Rand =< Density ->
      append(SoFarGraph, [N1 - N2], NewSoFarGraph) ;
      NewSoFarGraph = SoFarGraph),
   NN2 is N2 + 1,
   cr_gr(N1, NN2, NNodes, Density, NewSoFarGraph, Graph).

rand(N1, N2, R) :-
   random(R1),
   R is R1 mod (N2 - N1 + 1) + N1.


 /*
  *	Main predicate.
  *		creates a graph,
  *		declare the csp by declaring its variables,variables' domains and constraints,
  *		call bb_min to search for the optimal solution in csp,
  *		return the optimal solution set.
  */
vertexcover(N,DENSITY,GRAPH):-
	create_graph(N,DENSITY,GG),
%	write('G= '),
%	writelist(GG,1),
%	nl,
	vars(N,G),
	domains(G),
	constraints(G,GG),
	COST #= sum(G),
  	bb_min(search(G, 0, input_order, indomain, complete, []), COST ,bb_options{report_success:report(_), report_failure:report(_)}),
	optimal(G,GRAPH,1).
