Imprimir Grafos en C

Iniciado por JorgeKun, 12 Junio 2011, 21:59 PM

0 Miembros y 1 Visitante están viendo este tema.

JorgeKun

 :D Buen dia!!
Oigan alguien me podria hechar la mano, tengo un codigo que me crea un grafo, el problema es que necesito imprimirlo graficamente, esta hecho en C.
Estoy tratando con la libreria graphics.h pero me marca el error de que no es compatible en windows, alguien sabe como solucionar esto? o tiene una mejor idea sobre como imprimir?
abajo esta el codigo que solo me imprime el recorrido en forma de listado...#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <conio.h>
#include <string.h>
#define MaxNodos 47

typedef struct nodo_ {
    int etiqueta;
    float peso;
    struct nodo_ *sig;
}Tnodo;

/** variables globales */
Tnodo *Lista[MaxNodos]; //lista de adyacencia
int marca[MaxNodos]; //visitados
int predecesores[MaxNodos]; //ruta
float d[MaxNodos]; // distancia - peso
int Num_Vertices; //numero de vertices
int tipo; //1 no dirigido, 0 dirigido
char uanl[250][250]; //Arreglo de nombres UANL
/** ------------------ */

/* Inicializa la lista de adyacencia a NULL */
void init() {
    int i;
    for (i = 0; i < MaxNodos; i++)
        Lista[i] = NULL;
}

int lista (int tipo)/*FUNCION QUE DESPLIEGA LA LISTA PARA SELECCIONAR LA OPCION DEL USUARIO*/
{
int val=0;
do
{
printf("\n\n\tSeleccione una opcion");
int j=0;
switch(tipo)
{
  case 1: printf("\n\n\tCIUDAD UNIVERSITARIA");

  for(j=1;j<=28;j++)
  printf("%s\n",uanl[j]);

         break;
  case 2:printf("\n\n\tPREPARATORIAS");
  for(j=29;j<=47;j++)
  printf("%s\n",uanl[j]);

         break;
};
printf("\n\n\tIntroduzca el numero de la lista que desee...");
scanf("%d",&val);
clrscr();
}while(val<1 || val > 47);
return val;
}

/* Inserta los vertices en la lista de adyacencia */
void inserta (int Vorigen, int Vfinal, float peso) {
    Tnodo *q;
    q = (Tnodo*) malloc (sizeof(Tnodo) * 1);
    if (!q) return; //hubo un error
    q->etiqueta = Vfinal-1;
    q->peso     = peso;
    q->sig      = NULL;
    if (Lista[Vorigen-1] != NULL)
       q->sig = Lista[Vorigen-1];
    Lista[Vorigen-1] = q;
}

/* Libera la lista de adyacencia */
void liberar_lista (void) {
   Tnodo *q;
   int i;
   for (i = 0; i <  Num_Vertices; i++) {
      if (Lista[i] != NULL) {
         while (Lista[i] != NULL) {
            q = Lista[i];
            Lista[i] = Lista[i]->sig;
            free(q);
         }
      } //--fin si (no necesarias las llaves)
   } //--fin for (no necesaria las llaves)
}

/* Carga el grafo desde un fichero */
void cargar_grafo (char *fn) {
  FILE *fp;
  int v_in, v_fn; //vertice inicial y final
  float peso;
  if ((fp = fopen (fn, "r")) == NULL) {
       printf ("El archivo %s no existe o no se puede abrir\n", fn);
       getche();
       exit(0);
   }
   fscanf (fp, "%d\n", &tipo); //tipo es una vble global
   fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global
   while (!feof(fp)){
         fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
         inserta(v_in, v_fn, peso);
         inserta (v_fn, v_in, peso);
   }
   fclose (fp);
} // fin cargar_grafo
void cargar_nombres (char *fn) {
  FILE *fp;
    if ((fp = fopen (fn, "r")) == NULL) {
       printf ("El archivo %s no existe o no se puede abrir\n", fn);
       getche();
       exit(0);
   }

        int i=1;
        char caracteres[150];

        printf("\nEl contenido del archivo de prueba es \n\n");
        while (feof(fp) == 0)
        {
        fgets(caracteres,100,fp);
                strcpy(uanl[i], caracteres);
                i++;
        }
         fclose (fp);
} // fin cargar_nombres


/* Retorna el peso de la arista que une dos nodos */
float return_peso (int origen, int destino) {
   Tnodo *p;
   int encontrado;

   encontrado = 0;
   p = Lista[origen];
   while (p != NULL && !encontrado) {
      if (p->etiqueta == destino)
        encontrado = 1;
      else
        p = p->sig;
   }
   return p->peso;
}


int menor_valor() {
   int i, verticeMenor;
   float menor;
   menor = INT_MAX;
   for (i = 0; i < Num_Vertices; i++) {
      if (marca[i] == 0 )
         if (menor > d[i]) {
            menor = d[i];
            verticeMenor = i;
         }
   } // fin for
   return verticeMenor;
}

/* Dijkstra */
void dijkstra (int origen, int destino)
{
   int i, last, x;
   Tnodo *p;
   // inicializacion
   for (i = 0; i < MaxNodos; i++) {
      d[i] = INT_MAX; //"infinito"
      marca[i] = 0;
      predecesores[i] = -1;
   }
   // --
   d[origen] = 0;
   marca[origen] = 1;
   last = origen;
   while (marca[destino] == 0) { //hasta que no lleguemos al destino
      p = Lista[last];
      while (p != NULL){   //para todos los nodos adyacendes
          if (marca[p->etiqueta] == 0) //si no ha sido visitado
          if (d[p->etiqueta] > d[last] + return_peso(last, p->etiqueta))
              {
              d[p->etiqueta] = d[last] + return_peso(last, p->etiqueta);
              predecesores[p->etiqueta] = last;
          } // fin si
           p = p->sig;
      } // fin mientras
      x = menor_valor();
      marca[x] = 1;
      last = x;
   } // fin mientras
}

/* Imprime la ruta por pantalla */
void ImprimirCamino(int v) {
   if (v != -1)
      ImprimirCamino(predecesores[v]);
   if (v != -1) //evitamos que se imprima el -1
      {

                 printf("%s\n",uanl[v+1]);

      }
}

/* Menu de opciones */
int menu() {
    int opcion;
    do {
        printf ("\n\n\t[0] Salir\n\t");
        printf ("[1] Calcular ruta\n\n");
        printf ("Opcion:_");
        scanf("%d", &opcion);
    }while (opcion < 0 || opcion > 1);
    return opcion;
}

/* Funcion principal */
int main () {
    char file[25];
    int origen, destino,opi,tipo=0;
    int salir = 0;
    printf("\n\n\n\tBIENVENIDO\n\n\t...Presione cualquier tecla para comenzar..._");
    getche();
    init();
    cargar_grafo("GrafoUANL.txt");
    cargar_nombres("ListadoUANL.txt");
    clrscr();
    printf("\n\n\tSeleccione una opcion...");
    do {
        switch(menu())
        {
            case 0:
                  salir = 1;
                  break;
            case 1:
                     while(tipo!=1&&tipo!=2)
      {
      clrscr();
                           printf("\n\tSi desea partir de una facultad introduzca 1\n\tSi desea partir de una preparatoria introduca 2....._");
                           scanf("%d",&tipo);

      }
                        origen = lista (tipo);
      tipo=0;
while(tipo!=1&&tipo!=2)
      {
      clrscr();
printf("\n\tSi desea llegar de una facultad introduzca 1\n\tSi desea llegar de una preparatoria introduca 2....._");
                           scanf("%d",&tipo);
                        }
                      destino= lista (tipo);
                     dijkstra(origen-1, destino-1);
                    printf("\n\n\tLA RUTA MAS RAPIDA ES....\n\n");
                  ImprimirCamino(destino-1);
                  break;
        }; //final switch
    tipo=0;
    }while(!salir);
    liberar_lista();

    }