/* seuraajat.c SJ */

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

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

/* seuraajien joukko */
void dfs_seuraajat_rek(DIGRAPH G, DIVERTEX v, DSET S)
{
  DIGRAPH_VERTEX_ITERATOR i;
  DIVERTEX w;

  /* vaihteeksi joukko-operaatioita käyttäen */
  w = DIGRAPH_VERTEX_ANY_ADJ(G, v, i);
  while (DIGRAPH_VERTEX_ITERATING_ADJ(G, v, i)) {
	  if (! VOIDPTR_DSET_MEMBER(S, w)) {
		  VOIDPTR_DSET_INSERT(S, w);
		  dfs_seuraajat_rek(G, w, S);
	  }
	  w = DIGRAPH_VERTEX_ANOTHER_ADJ(G, v, i);
  }
} /* dfs_seuraajat_rek() */

/* käynnistys */
DSET dfs_seuraajat(DIGRAPH G, DIVERTEX v)
{
  DSET S;
  VOIDPTR_DSET_CREATE(S);

  dfs_seuraajat_rek(G, v, S);

  return S;
} /* dfs_seuraajat() */


/* seuraajat leveyssuuntaisella haulla */
DSET seuraajat_lev(DIGRAPH G, DIVERTEX v)
{
  QUEUE Q;
  DSET S;
  DIGRAPH_VERTEX_ITERATOR vi;
  DIVERTEX W, V;

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

  /* for each vertex W in G do */
  W = DG_VERTEX_ANY(G, vi); /* Kaikki valkoisiksi ... */
  while (DG_VERTEX_ITERATING(G, vi)) {
	  DG_ASSIGN_VERTEX_COLOR(G, W, TRA_WHITE);
	  W = DG_VERTEX_ANOTHER(G, vi);
  }

  PQ_ENQUEUE(Q, v);

  while (!PQ_EMPTY(Q)) {
	  V = PQ_FRONT(Q);
	  PQ_DEQUEUE(Q);

	  /* for each white vertex W adjacent to V do  */
	  W = DG_VERTEX_ANY_ADJ(G, V, vi);
	  while (DG_VERTEX_ITERATING_ADJ(G, V, vi)) {

		  if (DG_VERTEX_COLOR(G, W)==TRA_WHITE) {
			  DG_ASSIGN_VERTEX_COLOR(G, W, TRA_GRAY);
			  PQ_ENQUEUE(Q, W);
			  PDS_INSERT(S, W);
		  }
		  W = DG_VERTEX_ANOTHER_ADJ(G, V, vi);
	  }
  }
  return S;
} /* seuraajat_lev() */


void tulosta_verkko(DIGRAPH G)
{
  DIGRAPH_VERTEX v, w;
  DIGRAPH_VERTEX_ITERATOR vi, wi;

  /* for each vertex v in G  */
  v = DIGRAPH_VERTEX_ANY(G, vi);
  while (DIGRAPH_VERTEX_ITERATING(G, vi))  {
	  printf("%s -> ", DIGRAPH_VERTEX_LABEL(G, v));

	  /* for (each vertex w adjacent ; <= v in G  */
	  w = DIGRAPH_VERTEX_ANY_ADJ(G, v, wi); 
	  while (DIGRAPH_VERTEX_ITERATING_ADJ(G, v, wi))  {
		  printf("%s  ", DIGRAPH_VERTEX_LABEL(G, w));
		  w = DIGRAPH_VERTEX_ANOTHER_ADJ(G, v, wi);
	  }

	  printf("\n");
	  v = DIGRAPH_VERTEX_ANOTHER(G, vi);
  }
} /* tulosta_verkko() */


/* apufunktio */
void tulosta_solmut_joukosta(DIGRAPH G, DSET S){
	DIVERTEX V;
	DSET_ITERATOR i;

	V = PDS_ANY(S, i);
	while (PDS_ITERATING(S, i)) {
		printf("%s ",DG_VERTEX_LABEL(G, V));
		V = PDS_ANOTHER(S, i);
	}
}

int main()
{
  DIGRAPH G;
  DIVERTEX V_APU[8];

  DIEDGE e;
  DIVERTEX v;

  DIGRAPH_CREATE(G);

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

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

  printf("    4------>7  \n");
  printf("    ^          \n");
  printf("    |          \n");
  printf("1-->2-->3-->6  \n");
  printf("    ^       |  \n");
  printf("    |       |  \n");
  printf("    5<------+  \n");


  printf("%s:n seuraajat: ", DIGRAPH_VERTEX_LABEL(G, V_APU[3]));
  tulosta_solmut_joukosta(G, dfs_seuraajat(G, V_APU[3]));
  printf("\n");

  printf("%s:n seuraajat (lev): ", DIGRAPH_VERTEX_LABEL(G, V_APU[3]));
  tulosta_solmut_joukosta(G, seuraajat_lev(G, V_APU[3]));
  printf("\n");

  printf("\n");
  tulosta_verkko(G);
  printf("\n");

  printf("%s:n seuraajat: ", DIGRAPH_VERTEX_LABEL(G, V_APU[4]));
  tulosta_solmut_joukosta(G, dfs_seuraajat(G, V_APU[4]));
  printf("\n");


  /* esimerkki */
  e = DIGRAPH_RETRIEVE_EDGE(G, V_APU[1], V_APU[2]);
  v = DIGRAPH_HEAD(G, e);
  printf("%s\n", DIGRAPH_VERTEX_LABEL(G, v));
  v = DIGRAPH_TAIL(G, e);
  printf("%s\n", DIGRAPH_VERTEX_LABEL(G, v));
  DIGRAPH_FREE(G);

  exit(0);
}