% from Sicstus 3.7.1 manual : ----
% add_vertices(+Graph1, +Vertices, -Graph2) 
% Graph2 is Graph1 with Vertices added to it. 
% :end -----
% Only add Verices that do not appear in the graph.
% Vertices are assumed sorted.

add_vertices( [Vertex-Neighbours|GrT], [V|VcT], GraphOut ) :-
	!,
	( Vertex @< V -> 
		GraphOut = [Vertex-Neighbours|GrOuT],
		NxVs = [V|VcT]
		;
		NxVs = VcT,
		( Vertex == V -> 
			GraphOut = [Vertex-Neighbours|GrOuT]
			;
			GraphOut = [V-[],Vertex-Neighbours|GrOuT]
		)
	),
	add_vertices( GrT, NxVs, GrOuT ).
add_vertices( [], [H|T], [H-[]|GrT] ) :-
	!,
	add_vertices( [], T, GrT ).
add_vertices( Graph, [], Graph ).

reachable( Vertex, Graph, Reaches ) :-
	reachable_1( [Vertex], Graph, [], Reaches ).

reachable_1( [H|T], Graph, Acc, Reaches ) :-
	memberchk( H-Neighbours, Graph ),
	merge_set( [H], Acc, NxtAcc ),
	subtract( Neighbours, NxtAcc, RedNeighbours ),
	merge_set( T, RedNeighbours, NxT ),
	reachable_1( NxT, Graph, NxtAcc, Reaches ).
reachable_1( [], _Graph, Reached, Reached ).

/* 
just_make sure! !
reachable_1( [H|T], Graph, [H|Reaches] ) :-
	( select( Graph, [H-HNeighbours], RedGraph ) ->
		union( T, HNeighbours, NxtVertices )
		;
		NxtVertices = T, 
		RedGraph = Graph
	),
	reachable_1( NxtVertices, RedGraph, Reaches ).
reachable_1( [], _Graph, [] ).
*/

% add_edges( Graph, Edges, NewGraph ).
add_edges( Graph, Edges, NewGraph ) :-
	sort( Edges, Sedges ),
	add_edges_ord( Graph, Sedges, MidGraph ),
	edges_vertices( Sedges, _From, To ),
	add_vertices( MidGraph, To, NewGraph ).

add_edges_ord( Any, [], Any ) :- !.
add_edges_ord( [Vert-Neigh|Rest], [U-V|T], NewGraph ) :-
	( Vert = U -> 
		merge_set( [V], Neigh, NewNeigh ),
		NxtT = T,
		NewGraph = [Vert-NewNeigh|NewRest]
		;
		NxtT = [U-V|T],
		NewGraph = [Vert-Neigh|NewRest]
	),
	add_edges_ord( Rest, NxtT, NewRest ).
add_edges_ord( [], [U-V|T], [U-[V]|NewT] ) :-
	add_edges_ord( [], T, NewT ).
% add_edges_ord( [], [], [] ).


% non sicstus aux predicates.

edges_vertices( [V-U|VcsT], [V|FromT], [U|ToT] ) :-
	edges_vertices( VcsT, FromT, ToT ).
edges_vertices( [], [], [] ).