(* seuraajat.p SJ *)

(* Pelkästään näiden lukemisesta ei ole mitään hyötyä *)
(* Selkeytä algoritmi itsellesi ja piirrä toiminta verkolla *)

program verkkoesimerkki;

uses TRA;

(* seuraajien joukko *)
procedure dfs_seuraajat_rek(G : DIGRAPH; v : DIVERTEX; S : DSET);
	var w : DIVERTEX;
		i : DIGRAPH_VERTEX_ITERATOR;
begin

  (* vaihteeksi joukko-operaatioita käyttäen *)
  w := DIGRAPH_VERTEX_ANY_ADJ(G, v, i);
  while (DIGRAPH_VERTEX_ITERATING_ADJ(G, v, i)) do begin
	  if (not VOIDPTR_DSET_MEMBER(S, w)) then begin
		  VOIDPTR_DSET_INSERT(S, w);
		  dfs_seuraajat_rek(G, w, S);
	  end;
	  w := DIGRAPH_VERTEX_ANOTHER_ADJ(G, v, i);
  end;
end; (* dfs_seuraajat_rek() *)

(* käynnistys *)
function dfs_seuraajat(G : DIGRAPH; v : DIVERTEX) : DSET;
	var S : DSET;
begin
  VOIDPTR_DSET_CREATE(S);

  dfs_seuraajat_rek(G, v, S);

  dfs_seuraajat := S;
end; (* dfs_seuraajat() *)


function seuraajat_lev(G : DIGRAPH; V_alku : DIGRAPH_VERTEX) : DSET;
var
	Q : QUEUE;
	S : DSET;
	vi : DIGRAPH_VERTEX_ITERATOR;
	W, V : DIGRAPH_VERTEX;
begin

	VOIDPTR_QUEUE_CREATE(Q); (* Pidetään käymättömiä solmuja jonossa *)
	VOIDPTR_DSET_CREATE(S); (* Tehdään osoittimia sisältävä joukko *)

	(* for each vertex W in G do *)
	W := DIGRAPH_VERTEX_ANY(G, vi); (* Kaikki valkoisiksi ... *)
	while (DIGRAPH_VERTEX_ITERATING(G, vi)) do begin
		DIGRAPH_ASSIGN_VERTEX_COLOR(G, W, DIGRAPH_WHITE);
		W := DIGRAPH_VERTEX_ANOTHER(G, vi);
	end;

	VOIDPTR_QUEUE_ENQUEUE(Q, V_alku);

	while (not VOIDPTR_QUEUE_EMPTY(Q)) do begin
		V := VOIDPTR_QUEUE_FRONT(Q);
		VOIDPTR_QUEUE_DEQUEUE(Q);

		(* for each white vertex W adjacent to V repeat  *)
		W := DIGRAPH_VERTEX_ANY_ADJ(G, V, vi);
		while (DIGRAPH_VERTEX_ITERATING_ADJ(G, V, vi)) do begin
			if (DIGRAPH_VERTEX_COLOR(G, W) = DIGRAPH_WHITE) then begin
				DIGRAPH_ASSIGN_VERTEX_COLOR(G, W, DIGRAPH_GRAY);
				VOIDPTR_QUEUE_ENQUEUE(Q, W);
				VOIDPTR_DSET_INSERT(S, W);
			end;
			W := DIGRAPH_VERTEX_ANOTHER_ADJ(G, V, vi);
		end;
	end;
	seuraajat_lev := S;

end; (* seuraajat_lev() *)


procedure tulosta_verkko(G : DIGRAPH);
var v, w : DIGRAPH_VERTEX;
	vi, wi : DIGRAPH_VERTEX_ITERATOR;
begin

	(* for each vertex W in G do *)
	v := DIGRAPH_VERTEX_ANY(G, vi);
	while (DIGRAPH_VERTEX_ITERATING(G, vi)) do begin
		write(DIGRAPH_VERTEX_LABEL(G, v), ' -> ');
		w := DIGRAPH_VERTEX_ANY_ADJ(G, v, wi); 
		while (DIGRAPH_VERTEX_ITERATING_ADJ(G, v, wi)) do begin
			write(DIGRAPH_VERTEX_LABEL(G, w), '  ');
			w := DIGRAPH_VERTEX_ANOTHER_ADJ(G, v, wi);
		end;
		writeln;
		v := DIGRAPH_VERTEX_ANOTHER(G, vi);
	end;

end; (* tulosta_verkko() *)


(* apualiohjelma *)
procedure Tulosta_solmut_joukosta(G : DIGRAPH; S : DSET);
	var	V : DIGRAPH_VERTEX;
		i : DSET_ITERATOR;
begin
    V := VOIDPTR_DSET_ANY(S, i);
    while (VOIDPTR_DSET_ITERATING(S, i)) do begin
        write(DIGRAPH_VERTEX_LABEL(G, V)); write(' ');
        V := VOIDPTR_DSET_ANOTHER(S, i);
    end;
end; (* Tulosta_solmut_joukosta() *)

(* pääohjelma *)
const MAX = 7;
var
    G : DIGRAPH;
    V_APU : array[1..MAX] of DIVERTEX;
	e : DIEDGE;
	v : DIVERTEX;

begin

	DIGRAPH_CREATE(G);

	V_APU[1] := DIGRAPH_INSERT_VERTEX(G, "Eka",0,DIGRAPH_WHITE);
	V_APU[2] := DIGRAPH_INSERT_VERTEX(G, "Toka",0,DIGRAPH_WHITE);
	V_APU[3] := DIGRAPH_INSERT_VERTEX(G, "Kolmas",0,DIGRAPH_WHITE);
	V_APU[4] := DIGRAPH_INSERT_VERTEX(G, "Neljäs",0,DIGRAPH_WHITE);
	V_APU[5] := DIGRAPH_INSERT_VERTEX(G, "Viides",0,DIGRAPH_WHITE);
	V_APU[6] := DIGRAPH_INSERT_VERTEX(G, "Kuudes",0, DIGRAPH_WHITE);
	V_APU[7] := DIGRAPH_INSERT_VERTEX(G, "Seiska",0, DIGRAPH_WHITE);

	DIGRAPH_INSERT_EDGE(G, V_APU[1], V_APU[2], "Kaari 1-2",5,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[2], V_APU[3], "Kaari 2-3",3,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[2], V_APU[4], "Kaari 2-4",2,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[6], V_APU[5], "Kaari 6-5",2,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[4], V_APU[7], "Kaari 4-7",2,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[3], V_APU[6], "Kaari 3-6",2,DIGRAPH_WHITE);
	DIGRAPH_INSERT_EDGE(G, V_APU[5], V_APU[2], "Kaari 5-2",2,DIGRAPH_WHITE);

	writeln('    4------>7  ');
	writeln('    ^          ');
	writeln('    |          ');
	writeln('1-->2-->3-->6  ');
	writeln('    ^       |  ');
	writeln('    |       |  ');
	writeln('    5<------+  ');

	write(DIGRAPH_VERTEX_LABEL(G, V_APU[3]), ':n seuraajat: ');
	tulosta_solmut_joukosta(G, dfs_seuraajat(G, V_APU[3]));
	writeln;

	writeln;
	tulosta_verkko(G);
	writeln;

	write(DIGRAPH_VERTEX_LABEL(G, V_APU[3]), ':n seuraajat: ');
	tulosta_solmut_joukosta(G, seuraajat_lev(G, V_APU[3]));
	writeln;

	write(DIGRAPH_VERTEX_LABEL(G, V_APU[4]), ':n seuraajat: ');
	tulosta_solmut_joukosta(G, dfs_seuraajat(G, V_APU[4]));
	writeln;

	(* esimerkki head:sta ja tail:sta *)
	e := DIGRAPH_RETRIEVE_EDGE(G, V_APU[1], V_APU[2]);
	v := DIGRAPH_HEAD(G, e);
	writeln(DIGRAPH_VERTEX_LABEL(G, v));
	v := DIGRAPH_TAIL(G, e);
	writeln(DIGRAPH_VERTEX_LABEL(G, v));

	DIGRAPH_FREE(G);
end.