(* 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;

(* esimerkki leveyssuuntaisesta läpikäynnistä, tämä palauttaa joukon
   jonkin solmun seuraajista *)

function seuraajat_lev(G : GRAPH; V_alku : GRAPH_VERTEX) : DSET;
var
	Q : QUEUE;
	S : DSET;
	vi : GRAPH_VERTEX_ITERATOR;
	W, V : GRAPH_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 := GRAPH_VERTEX_ANY(G, vi); (* Kaikki valkoisiksi ... *)
	while (GRAPH_VERTEX_ITERATING(G, vi)) do begin
		GRAPH_ASSIGN_VERTEX_COLOR(G, W, GRAPH_WHITE);
		W := GRAPH_VERTEX_ANOTHER(G, vi);
	end;

	VOIDPTR_QUEUE_ENQUEUE(Q, V_alku);
	GRAPH_ASSIGN_VERTEX_COLOR(G, V_alku, GRAPH_GRAY);

	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 := GRAPH_VERTEX_ANY_ADJ(G, V, vi);
		while (GRAPH_VERTEX_ITERATING_ADJ(G, V, vi)) do begin
			if (GRAPH_VERTEX_COLOR(G, W) = GRAPH_WHITE) then begin
				GRAPH_ASSIGN_VERTEX_COLOR(G, W, GRAPH_GRAY);
				VOIDPTR_QUEUE_ENQUEUE(Q, W);
				VOIDPTR_DSET_INSERT(S, W);
			end;
			W := GRAPH_VERTEX_ANOTHER_ADJ(G, V, vi);
		end;
	end;
	seuraajat_lev := S;

end; (* seuraajat_lev() *)


procedure tulosta_verkko(G : GRAPH);
var v, w : GRAPH_VERTEX;
	vi, wi : GRAPH_VERTEX_ITERATOR;
begin

	(* for each vertex v in G do *)
	v := GRAPH_VERTEX_ANY(G, vi);
	while (GRAPH_VERTEX_ITERATING(G, vi)) do begin
		write(GRAPH_VERTEX_LABEL(G, v), ' -> ');

		(* for each vertex w adjacent to v in G do *)
		w := GRAPH_VERTEX_ANY_ADJ(G, v, wi); 
		while (GRAPH_VERTEX_ITERATING_ADJ(G, v, wi)) do begin
			write(GRAPH_VERTEX_LABEL(G, w), '  ');
			w := GRAPH_VERTEX_ANOTHER_ADJ(G, v, wi);
		end;

		writeln;
		v := GRAPH_VERTEX_ANOTHER(G, vi);
	end;

end; (* tulosta_verkko() *)


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

(* pääohjelma *)
const MAX = 7;
var
    G : GRAPH;
    V_APU : array[1..MAX] of GRAPH_VERTEX;
	e : GRAPH_EDGE;
	v : GRAPH_VERTEX;

begin

	GRAPH_CREATE(G);

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

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

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

	writeln;
	tulosta_verkko(G);
	writeln;

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

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

	(* esimerkki head:sta ja tail:sta *)
	e := GRAPH_RETRIEVE_EDGE(G, V_APU[1], V_APU[2]);
	v := GRAPH_HEAD(G, e);
	writeln(GRAPH_VERTEX_LABEL(G, v));
	v := GRAPH_TAIL(G, e);
	writeln(GRAPH_VERTEX_LABEL(G, v));

	GRAPH_FREE(G);
end.