/* verkko_keha.c SJ */

#include "TRA.h"
#include <stdio.h>


/* kehä vai ei */

/* syvyyssuuntaisessa haussa otetaan lisäparametriksi edellinen
   solmu, jotta vältetään suora paluu */
int keha_dfs(GRAPH G, GRAPH_VERTEX v, GRAPH_VERTEX ed)
{
	GRAPH_VERTEX_ITERATOR i;
		GRAPH_VERTEX w;
		int kehaloydetty;

  kehaloydetty = 0;

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

  w = GRAPH_VERTEX_ANY_ADJ(G, v, i);
  while (GRAPH_VERTEX_ITERATING_ADJ(G, v, i) &&  ! kehaloydetty )  {

      /* ei palata takaisin edelliseen */
	  if (w != ed)  {

	      /* jos naapuri valkoinen, edetään */
		  if (GRAPH_VERTEX_COLOR(G, w) == TRA_WHITE)  {
			  kehaloydetty = kehaloydetty || keha_dfs(G, w, v);

		  /* muuten havaittiin kehä */
		  } else
		      kehaloydetty = 1;
	   }
		  	
	  w = GRAPH_VERTEX_ANOTHER_ADJ(G, v, i);
  }

  return kehaloydetty;

} /* keha_dfs() */

int keha(GRAPH G)
{
  GRAPH_VERTEX v;
  GRAPH_VERTEX_ITERATOR i;
  int kehaloydetty;

  kehaloydetty = 0;

  /* kaikki valkoisiksi */
  v = GRAPH_VERTEX_ANY(G, i);
  while (GRAPH_VERTEX_ITERATING(G, i))  {
	  GRAPH_ASSIGN_VERTEX_COLOR(G, v, TRA_WHITE);
	  v = GRAPH_VERTEX_ANOTHER(G, i);
  } 

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

  v = GRAPH_VERTEX_ANY(G, i);
  while (GRAPH_VERTEX_ITERATING(G, i) &&  ! kehaloydetty)  {
      if (GRAPH_VERTEX_COLOR(G, v) == TRA_WHITE) 
		  kehaloydetty = kehaloydetty || keha_dfs(G, v, v);
	  v = GRAPH_VERTEX_ANOTHER(G, i);
  }

  return kehaloydetty;

} /* keha() */


/* pääohjelma */

#define MAX 8

int main()
{
    GRAPH G;
    GRAPH_VERTEX V_APU[MAX];

	GRAPH_CREATE(G);

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

	GRAPH_INSERT_EDGE(G, V_APU[1], V_APU[2], "Kaari 1-2",5,TRA_WHITE);
	GRAPH_INSERT_EDGE(G, V_APU[2], V_APU[3], "Kaari 2-3",3,TRA_WHITE);
	GRAPH_INSERT_EDGE(G, V_APU[2], V_APU[4], "Kaari 2-4",2,TRA_WHITE);
	GRAPH_INSERT_EDGE(G, V_APU[6], V_APU[5], "Kaari 6-5",2,TRA_WHITE);
	
	printf("   4     7  \n");
	printf("   |        \n");
	printf("1--2--3  6  \n");
	printf("         |  \n");
	printf("   5-----+  \n");

	printf("\n");
	printf("Kehä: %d\n", keha(G));
	/* printf("Euler: %d\n", onkoeuler(G)); */
	/* printf("Komponentit %d\n", komponentit(G)); */
	printf("\n");


	GRAPH_INSERT_EDGE(G, V_APU[4], V_APU[7], "Kaari 4-7",2,TRA_WHITE);
	printf("   4-----7  \n");
	printf("   |        \n");
	printf("1--2--3  6  \n");
	printf("         |  \n");
	printf("   5-----+  \n");

	printf("\n");
	printf("Kehä: %d\n", keha(G));
	/* printf("Euler: %d\n", onkoeuler(G)); */
	/* printf("Komponentit %d\n", komponentit(G)); */
	printf("\n");

	GRAPH_INSERT_EDGE(G, V_APU[3], V_APU[6], "Kaari 3-6",2,TRA_WHITE);
	printf("   4-----7  \n");
	printf("   |        \n");
	printf("1--2--3--6  \n");
	printf("         |  \n");
	printf("   5-----+  \n");


	printf("\n");
	printf("Kehä: %d\n", keha(G));
	/* printf("Euler: %d\n", onkoeuler(G)); */
	/* printf("Komponentit %d\n", komponentit(G)); */
	printf("\n");

	GRAPH_INSERT_EDGE(G, V_APU[5], V_APU[2], "Kaari 5-2",2,TRA_WHITE);
	printf("   4-----7  \n");
	printf("   |        \n");
	printf("1--2--3--6  \n");
	printf("   |     |  \n");
	printf("   5-----+  \n");

	printf("\n");
	printf("Kehä: %d\n", keha(G));
	/* printf("Euler: %d\n", onkoeuler(G)); */
	/* printf("Komponentit %d\n", komponentit(G)); */
	printf("\n");

	GRAPH_INSERT_EDGE(G, V_APU[1], V_APU[7], "Kaari 1-7",2,TRA_WHITE);
	printf("+--------+  \n");
	printf("|        |  \n");
	printf("|  4-----7  \n");
	printf("|  |        \n");
	printf("1--2--3--6  \n");
	printf("   |     |  \n");
	printf("   5-----+  \n");

	printf("\n");
	printf("Kehä: %d\n", keha(G));
	/* printf("Euler: %d\n", onkoeuler(G)); */
	/* printf("Komponentit %d\n", komponentit(G)); */
	printf("\n");


	GRAPH_FREE(G);

	exit(0);
}