(* verkko_keha.p SJ *)

program suuntaamattomat;

uses TRA;

(* kehä vai ei *)

(* syvyyssuuntaisessa haussa otetaan lisäparametriksi edellinen
   solmu, jotta vältetään suora paluu *)
function keha_dfs(G : GRAPH; v, ed : GRAPH_VERTEX) : boolean;
	var i : GRAPH_VERTEX_ITERATOR;
		w : GRAPH_VERTEX;
		kehaloydetty : boolean;
begin

  kehaloydetty := false;

  (* väritetään käsiteltävä solmu *)
  GRAPH_ASSIGN_VERTEX_COLOR(G, v, GRAPH_GRAY);

  w := GRAPH_VERTEX_ANY_ADJ(G, v, i);
  while (GRAPH_VERTEX_ITERATING_ADJ(G, v, i) and not kehaloydetty ) do begin

      (* ei palata takaisin edelliseen *)
	  if (w <> ed) then begin

	      (* jos naapuri valkoinen, edetään *)
		  if (GRAPH_VERTEX_COLOR(G, w) = GRAPH_WHITE) then begin
			  kehaloydetty := kehaloydetty or keha_dfs(G, w, v);

		  (* muuten havaittiin kehä *)
		  end else
		      kehaloydetty := true;
	   end;
		  	
	  w := GRAPH_VERTEX_ANOTHER_ADJ(G, v, i);
  end;

  keha_dfs := kehaloydetty;

end; (* keha_dfs() *)

function keha(G : GRAPH) : boolean;
	var v : GRAPH_VERTEX;
		i : GRAPH_VERTEX_ITERATOR;
		kehaloydetty : boolean;
begin
  kehaloydetty := false;

  (* kaikki valkoisiksi *)
  v := GRAPH_VERTEX_ANY(G, i);
  while (GRAPH_VERTEX_ITERATING(G, i)) do begin
	  GRAPH_ASSIGN_VERTEX_COLOR(G, v, GRAPH_WHITE);
	  v := GRAPH_VERTEX_ANOTHER(G, i);
  end; 

  (* syvyyssuuntainen läpikäynti niin, että kehästä
     palautetaan tieto *)

  v := GRAPH_VERTEX_ANY(G, i);
  while (GRAPH_VERTEX_ITERATING(G, i) and not kehaloydetty) do begin
      if (GRAPH_VERTEX_COLOR(G, v) = GRAPH_WHITE) then
		  kehaloydetty := kehaloydetty or keha_dfs(G, v, v);
	  v := GRAPH_VERTEX_ANOTHER(G, i);
  end;

  keha := kehaloydetty;

end; (* keha() *)


(* pääohjelma *)
const MAX = 7;
var
    G : GRAPH;
    V_APU : array[1..MAX] of 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);
	
	writeln('   4     7  ');
	writeln('   |        ');
	writeln('1--2--3  6  ');
	writeln('         |  ');
	writeln('   5-----+  ');

	writeln;
	writeln('Kehä: ', keha(G));
	(* writeln('Euler: ', onkoeuler(G)); *)
	(* writeln('Komponentit ', komponentit(G)); *)
	writeln;


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

	writeln;
	writeln('Kehä: ', keha(G));
	(* writeln('Euler: ', onkoeuler(G)); *)
	(* writeln('Komponentit ', komponentit(G)); *)
	writeln;

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


	writeln;
	writeln('Kehä: ', keha(G));
	(* writeln('Euler: ', onkoeuler(G)); *)
	(* writeln('Komponentit ', komponentit(G)); *)
	writeln;

	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;
	writeln('Kehä: ', keha(G));
	(* writeln('Euler: ', onkoeuler(G)); *)
	(* writeln('Komponentit ', komponentit(G)); *)
	writeln;

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

	writeln;
	writeln('Kehä: ', keha(G));
	(* writeln('Euler: ', onkoeuler(G)); *)
	(* writeln('Komponentit ', komponentit(G)); *)
	writeln;


	GRAPH_FREE(G);

end.