#-----------------------------------CUT HERE-----------------------------------
#! /bin/sh
#
# This is a shell archive.  Save this into a file, edit it
# and delete all lines above this comment.  Then give this
# file to sh by executing the command "sh file".  The files
# will be extracted into the currecnt directory owned by you
# with default permissions.
#
# The files contained herein are:
#
# -rw-r--r--   1 alberto  user        2902 Jan 14  1993 search0.c
# -rw-r--r--   1 alberto  user        4494 Jan 14  1993 search1.c
# -rw-r--r--   1 alberto  user        5137 Jan 14  1993 search2.c
# -rw-r--r--   1 alberto  user        4758 Jan 14  1993 search3.c
# -rw-r--r--   1 alberto  user        5448 Jan 14  1993 search4.c
# -rw-r--r--   1 alberto  user          97 Jan 14  1993 link.dat
# -rw-r--r--   1 alberto  user         536 Jan 14  1993 test
# -rw-r--r--   1 alberto  user        1612 Jan 14  1993 search.doc
# -rw-r--r--   1 alberto  user         295 Jan 14  1993 makefile
#
echo 'x - search0.c'
if test -f search0.c; then echo 'shar: not overwriting search0.c'; else
sed 's/^X//' > search0.c << '________This_Is_The_END________'
X#include <stdio.h>
X
X#define MAX 50
X
Xstruct VL
X{
X  char from[20];
X  char to[20];
X  int cost;
X  char checked;
X};
X
Xstruct VL vuelos[MAX];
X
Xint pos_ult = 0;
Xint encuentra_pos = 0;
X
Xint head_stack = 0;
X
Xstruct stack
X{
X  char from[20];
X  char to[20];
X  int cost;
X};
X
Xstruct stack pila_rt[MAX];
X
Xload_ack();
Xload();
Xdump();
Xlink();
Xfind();
Xdepth();
Xput_to_stack();
Xget_from_stack();
X  
Xmain()
X{
X  char from[20], to[20];
X
X  load_ack();
X
X  printf("From: ");
X  gets(from);
X  printf("To: ");
X  gets(to);
X
X  depth(from, to);
X
X  dump(to);
X}
X
Xload_ack()
X{
X  load("NewYork", "Chicago", 1000);
X  load("Chicago", "Denver", 1000);
X  load("NewYork", "Toronto", 800);
X  load("NewYork", "Denver", 1900);
X  load("Toronto", "Calgary", 1500);
X  load("Toronto", "LosAngeles", 1800);
X  load("Toronto", "Chicago", 500);
X  load("Denver", "Urbana", 1000);
X  load("Denver", "Houston", 1500);
X  load("Houston", "LosAngeles", 1500);
X  load("Denver", "LosAngeles", 1000);
X}
X
Xload(from, to, cost)
X  char *from, *to;
X  int cost;
X{
X  if (pos_ult < MAX)
X  {
X    strcpy(vuelos[pos_ult].from, from);
X    strcpy(vuelos[pos_ult].to, to);
X    vuelos[pos_ult].cost = cost;
X    vuelos[pos_ult].checked = 0;
X    pos_ult++;
X  }
X  else
X    printf("\nFull Ack");
X}
X
Xdump(to)
X  char *to;
X{
X  int cost, t;
X
X  cost = 0;
X  t = 0;
X
X  while (t <  head_stack)
X  {
X    printf("%s --> ", pila_rt[t].from);
X    cost += pila_rt[t].cost;
X    t++;
X  }
X  printf("%s\n", to);
X
X  printf("The cost is %d\n", cost);
X}
X
Xlink(from, to)
X  char *from, *to;
X{
X  int t;
X
X  for (t = pos_ult-1; t > -1; t--)
X    if (!strcmp(vuelos[t].from, from) && !strcmp(vuelos[t].to, to))
X      return (vuelos[t].cost);
X
X  return (0);
X}
X
Xfind(from, x)
X  char *from, *x;
X{
X  encuentra_pos = 0;
X  while (encuentra_pos < pos_ult)
X  {
X    if (!strcmp(vuelos[encuentra_pos].from, from) && 
X        !vuelos[encuentra_pos].checked)
X    {
X      strcpy(x, vuelos[encuentra_pos].to);
X      vuelos[encuentra_pos].checked = 1;
X
X      return (vuelos[encuentra_pos].cost);
X    }
X    encuentra_pos++;
X  }
X
X  return (0);
X}
X
Xdepth(from, to)
X  char *from, *to;
X{
X  int c, cost;
X  char x[20];
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find(from, x))
X  {
X    put_to_stack(from, to, cost);
X    depth(x, to);
X  }
X  else if (head_stack > 0)
X  {
X    get_from_stack(from, to, &cost);
X    depth(from, to);
X  }
X}
X
Xput_to_stack(from, to, cost)
X  char *from, *to;
X  int cost;
X{
X  if (head_stack < MAX)
X  {
X    strcpy(pila_rt[head_stack].from, from);
X    strcpy(pila_rt[head_stack].to, to);
X    pila_rt[head_stack].cost = cost;
X    head_stack++;
X  }
X  else
X    printf("\nFull Stack\n");
X}
X
Xget_from_stack(from, to, cost)
X  char *from, *to;
X  int *cost;
X{
X
X  if (head_stack > 0)
X  {
X    head_stack--;
X    strcpy(pila_rt[head_stack].from, from);
X    strcpy(pila_rt[head_stack].to, to);
X    *cost = pila_rt[head_stack].cost;
X  }
X  else
X    printf("\nEmpty Stack\n");
X}
X  
________This_Is_The_END________
if test `wc -l < search0.c` -ne 190; then
  echo 'shar: search0.c was damaged during transit (should have been 190 lines)'
fi
fi
echo 'x - search1.c'
if test -f search1.c; then echo 'shar: not overwriting search1.c'; else
sed 's/^X//' > search1.c << '________This_Is_The_END________'
X#include <stdio.h>
X
Xtypedef struct _database * ACKPTR;
Xtypedef struct _stack    * STKPTR;
X
Xstruct _database
X{
X  int from;
X  int to;
X  int cost;
X  int checked;
X
X  ACKPTR nextack;
X};
X
Xstruct _stack
X{
X  int from;
X  int to;
X  int cost;
X
X  STKPTR nextstk;
X};
X
XACKPTR ack = NULL;
XSTKPTR stk = NULL;
X
Xload_ack();
Xdump();
Xlink();
Xfind();
Xsearch();
Xdepth();
Xbreadth();
Xput_to_stack();
Xget_from_stack();
X
X  
Xmain(argc, argv)
X  int argc;
X  char *argv[];
X{
X  int type, from, to;
X
X  if (argc != 5)
X  {
X    printf("\nUsage: trip <file> <type> <from> <out>\n");
X    printf("Type 1 is depth first.\n");
X    printf("Type 2 is breadth first.\n");
X    printf("Range from, to, cost: 0 < x < 32767.\n");
X    exit(1);
X  }
X
X  type = atoi(argv[2]);
X  from = atoi(argv[3]);  
X  to = atoi(argv[4]);
X  if (!to || !from || to < 0 || from < 0 || type < 0 || type > 2)
X  {
X    printf("\nBad parameters\n");
X    exit(1);
X  }
X
X  load_ack(argv[1]);
X  search(type, from, to);
X  dump(from, to);
X}
X
Xload_ack(file)
X  char *file;
X{
X  FILE *fp;
X  int from, to, cost;
X  ACKPTR acktmp, acklist;
X  
X  if ((fp = fopen(file, "r")) == NULL)
X  {
X    printf("\nCannot open file %s\n", file);
X    exit(1);
X  }
X
X  while (fscanf(fp, "%d %d %d", &from, &to, &cost) != EOF)
X  {
X    acktmp = (ACKPTR)malloc(sizeof(struct _database));
X    if (!acktmp)
X    {
X      printf("\nCannot allocate memory\n");
X      exit(1);
X    }
X
X    if (!ack)
X      ack = acktmp;
X    else
X    {
X      acklist = ack;
X      while (acklist->nextack)
X        acklist = acklist->nextack;
X	
X      acklist->nextack = acktmp;
X    }
X    acktmp->nextack = NULL;  
X    acktmp->to      = to;
X    acktmp->from    = from;
X    acktmp->cost    = cost;
X    acktmp->checked = 0;
X  }
X
X  fclose(fp);            
X}
X
Xdump(from, to)
X  int from, to;
X{
X  STKPTR stklist;
X  int cost = 0;
X
X  if (from == to)
X  {
X    printf("It is a self link\n");
X    return;
X  }
X
X  stklist = stk;
X  while (stklist)
X  {
X    printf("%d --> ", stklist->from);
X    cost += stklist->cost;
X    stklist = stklist->nextstk;
X  }
X  if (cost == 0)
X  {
X    printf("There is not a link from %d to %d\n", from, to);
X    return;
X  }
X
X  printf("%d\n", to);
X  printf("The cost is %d\n", cost);
X}
X
Xlink(from, to)
X  int from, to;
X{
X  ACKPTR acklist;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->to == to)
X      return (acklist->cost);
X    acklist = acklist->nextack;
X  }
X     
X  return (0);
X}
X
Xfind(from, x)
X  int from, *x;
X{
X  ACKPTR acklist;
X 
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->checked == 0)
X    {
X      *x = acklist->to;
X      acklist->checked = 1;
X
X      return (acklist->cost);
X    }
X
X    acklist = acklist->nextack;
X  }
X
X  return (0);
X}
X
Xsearch(type, from, to)
X  int type, from, to;
X{
X  switch (type)
X  {
X    case 1: depth(from, to); break;
X    case 2: breadth(from, to); break;
X  }
X}
X
Xdepth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    depth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    depth(from, to);
X  }
X}
X
Xbreadth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  while (cost = find(from, &x))
X  {
X    if (c = link(x, to))
X    {
X      put_to_stack(from, to, cost);
X      put_to_stack(x, to, c);
X      return;
X    }
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    breadth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    breadth(from, to);
X  }
X}
X
Xput_to_stack(from, to, cost)
X  int from, to, cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = (STKPTR)malloc(sizeof(struct _stack));
X  if (!stktmp)
X  {
X    printf("\nCannot allocate memory\n");
X    exit(1);
X  }
X
X  if (!stk)
X    stk = stktmp;
X  else
X  {
X    stklist = stk;
X    while (stklist->nextstk)
X      stklist = stklist->nextstk;
X	
X    stklist->nextstk = stktmp;
X  }
X  stktmp->nextstk = NULL;  
X  stktmp->to      = to;
X  stktmp->from    = from;
X  stktmp->cost    = cost;
X}
X
Xget_from_stack(from, to, cost)
X  int *from, *to, *cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = NULL;
X  stklist = stk;
X  while (stklist)
X  {
X    if (stklist->nextstk == NULL)
X    {
X      if (stktmp)
X        stktmp->nextstk = stklist->nextstk;
X      else
X        stk = stklist->nextstk;
X
X      *from = stklist->from;
X      *to   = stklist->to;
X      *cost = stklist->cost;
X  
X      free(stklist);
X
X      break;
X    }
X
X    stktmp = stklist;
X    stklist = stklist->nextstk;
X  }
X}
X  
________This_Is_The_END________
if test `wc -l < search1.c` -ne 294; then
  echo 'shar: search1.c was damaged during transit (should have been 294 lines)'
fi
fi
echo 'x - search2.c'
if test -f search2.c; then echo 'shar: not overwriting search2.c'; else
sed 's/^X//' > search2.c << '________This_Is_The_END________'
X#include <stdio.h>
X
Xtypedef struct _database * ACKPTR;
Xtypedef struct _stack    * STKPTR;
X
Xstruct _database
X{
X  int from;
X  int to;
X  int cost;
X  int checked;
X
X  ACKPTR nextack;
X};
X
Xstruct _stack
X{
X  int from;
X  int to;
X  int cost;
X
X  STKPTR nextstk;
X};
X
XACKPTR ack = NULL;
XSTKPTR stk = NULL;
X
Xload_ack();
Xdump();
Xlink();
Xfind1();
Xfind2();
Xsearch();
Xhillclimber();
Xlesscost();
Xput_to_stack();
Xget_from_stack();
X
X  
Xmain(argc, argv)
X  int argc;
X  char *argv[];
X{
X  int type, from, to;
X
X  if (argc != 5)
X  {
X    printf("\nUsage: trip <file> <type> <from> <out>\n");
X    printf("Type 1 is hill climber.\n");
X    printf("Type 2 is less cost.\n");
X    printf("Range from, to, cost: 0 < x < 32767.\n");
X    exit(1);
X  }
X
X  type = atoi(argv[2]);
X  from = atoi(argv[3]);  
X  to = atoi(argv[4]);
X  if (!to || !from || to < 0 || from < 0 || type < 0 || type > 2)
X  {
X    printf("\nBad parameters\n");
X    exit(1);
X  }
X
X  load_ack(argv[1]);
X  search(type, from, to);
X  dump(from, to);
X}
X
Xload_ack(file)
X  char *file;
X{
X  FILE *fp;
X  int from, to, cost;
X  ACKPTR acktmp, acklist;
X  
X  if ((fp = fopen(file, "r")) == NULL)
X  {
X    printf("\nCannot open file %s\n", file);
X    exit(1);
X  }
X
X  while (fscanf(fp, "%d %d %d", &from, &to, &cost) != EOF)
X  {
X    acktmp = (ACKPTR)malloc(sizeof(struct _database));
X    if (!acktmp)
X    {
X      printf("\nCannot allocate memory\n");
X      exit(1);
X    }
X
X    if (!ack)
X      ack = acktmp;
X    else
X    {
X      acklist = ack;
X      while (acklist->nextack)
X        acklist = acklist->nextack;
X	
X      acklist->nextack = acktmp;
X    }
X    acktmp->nextack = NULL;  
X    acktmp->to      = to;
X    acktmp->from    = from;
X    acktmp->cost    = cost;
X    acktmp->checked = 0;
X  }
X
X  fclose(fp);            
X}
X
Xdump(from, to)
X  int from, to;
X{
X  STKPTR stklist;
X  int cost = 0;
X
X  if (from == to)
X  {
X    printf("It is a self link\n");
X    return;
X  }
X
X  stklist = stk;
X  while (stklist)
X  {
X    printf("%d --> ", stklist->from);
X    cost += stklist->cost;
X    stklist = stklist->nextstk;
X  }
X  if (cost == 0)
X  {
X    printf("There is not a link from %d to %d\n", from, to);
X    return;
X  }
X
X  printf("%d\n", to);
X  printf("The cost is %d\n", cost);
X}
X
Xlink(from, to)
X  int from, to;
X{
X  ACKPTR acklist;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->to == to)
X      return (acklist->cost);
X    acklist = acklist->nextack;
X  }
X     
X  return (0);
X}
X
Xfind1(from, x)
X  int from, *x;
X{
X  ACKPTR acklist;
X  int cost = 0;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->checked == 0)
X      if (acklist->cost > cost)
X        cost = acklist->cost;
X
X    acklist = acklist->nextack;
X  }
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->cost == cost)
X    {
X      *x = acklist->to;
X      acklist->checked = 1;
X
X      return (acklist->cost);
X    }
X
X    acklist = acklist->nextack;
X  }
X
X  return (0);
X}
X
Xfind2(from, x)
X  int from, *x;
X{
X  ACKPTR acklist;
X  int cost = 32767;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->checked == 0)
X      if (acklist->cost < cost)
X        cost = acklist->cost;
X
X    acklist = acklist->nextack;
X  }
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->cost == cost)
X    {
X      *x = acklist->to;
X      acklist->checked = 1;
X
X      return (acklist->cost);
X    }
X
X    acklist = acklist->nextack;
X  }
X
X  return (0);
X}
X
Xsearch(type, from, to)
X  int type, from, to;
X{
X  switch (type)
X  {
X    case 1: hillclimber(from, to); break;
X    case 2: lesscost(from, to); break;
X  }
X}
X
Xhillclimber(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find1(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    hillclimber(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    hillclimber(from, to);
X  }
X}
X
Xlesscost(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find2(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    hillclimber(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    hillclimber(from, to);
X  }
X}
X
Xput_to_stack(from, to, cost)
X  int from, to, cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = (STKPTR)malloc(sizeof(struct _stack));
X  if (!stktmp)
X  {
X    printf("\nCannot allocate memory\n");
X    exit(1);
X  }
X
X  if (!stk)
X    stk = stktmp;
X  else
X  {
X    stklist = stk;
X    while (stklist->nextstk)
X      stklist = stklist->nextstk;
X	
X    stklist->nextstk = stktmp;
X  }
X  stktmp->nextstk = NULL;  
X  stktmp->to      = to;
X  stktmp->from    = from;
X  stktmp->cost    = cost;
X}
X
Xget_from_stack(from, to, cost)
X  int *from, *to, *cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = NULL;
X  stklist = stk;
X  while (stklist)
X  {
X    if (stklist->nextstk == NULL)
X    {
X      if (stktmp)
X        stktmp->nextstk = stklist->nextstk;
X      else
X        stk = stklist->nextstk;
X
X      *from = stklist->from;
X      *to   = stklist->to;
X      *cost = stklist->cost;
X  
X      free(stklist);
X
X      break;
X    }
X
X    stktmp = stklist;
X    stklist = stklist->nextstk;
X  }
X}
X  
________This_Is_The_END________
if test `wc -l < search2.c` -ne 335; then
  echo 'shar: search2.c was damaged during transit (should have been 335 lines)'
fi
fi
echo 'x - search3.c'
if test -f search3.c; then echo 'shar: not overwriting search3.c'; else
sed 's/^X//' > search3.c << '________This_Is_The_END________'
X#include <stdio.h>
X
Xtypedef struct _database * ACKPTR;
Xtypedef struct _stack    * STKPTR;
X
Xstruct _database
X{
X  int from;
X  int to;
X  int cost;
X  int checked;
X
X  ACKPTR nextack;
X};
X
Xstruct _stack
X{
X  int from;
X  int to;
X  int cost;
X
X  STKPTR nextstk;
X};
X
XACKPTR ack = NULL;
XSTKPTR stk = NULL;
X
Xload_ack();
Xdump();
Xlink();
Xfind();
Xsearch();
Xdepth();
Xbreadth();
Xput_to_stack();
Xget_from_stack();
Xfreestk();
X  
Xmain(argc, argv)
X  int argc;
X  char *argv[];
X{
X  int type, from, to;
X
X  if (argc != 5)
X  {
X    printf("\nUsage: trip <file> <type> <from> <out>\n");
X    printf("Type 1 is depth first - multiple solutions.\n");
X    printf("Type 2 is breadth first - multiple solutions.\n");
X    printf("Range from, to, cost: 0 < x < 32767.\n");
X    exit(1);
X  }
X
X  type = atoi(argv[2]);
X  from = atoi(argv[3]);  
X  to = atoi(argv[4]);
X  if (!to || !from || to < 0 || from < 0 || type < 0 || type > 2)
X  {
X    printf("\nBad parameters\n");
X    exit(1);
X  }
X
X  load_ack(argv[1]);
X
X  for (;;)
X  {
X    search(type, from, to);
X    dump(from, to);
X    freestk();
X  } 
X}
X
Xload_ack(file)
X  char *file;
X{
X  FILE *fp;
X  int from, to, cost;
X  ACKPTR acktmp, acklist;
X  
X  if ((fp = fopen(file, "r")) == NULL)
X  {
X    printf("\nCannot open file %s\n", file);
X    exit(1);
X  }
X
X  while (fscanf(fp, "%d %d %d", &from, &to, &cost) != EOF)
X  {
X    acktmp = (ACKPTR)malloc(sizeof(struct _database));
X    if (!acktmp)
X    {
X      printf("\nCannot allocate memory\n");
X      exit(1);
X    }
X
X    if (!ack)
X      ack = acktmp;
X    else
X    {
X      acklist = ack;
X      while (acklist->nextack)
X        acklist = acklist->nextack;
X	
X      acklist->nextack = acktmp;
X    }
X    acktmp->nextack = NULL;  
X    acktmp->to      = to;
X    acktmp->from    = from;
X    acktmp->cost    = cost;
X    acktmp->checked = 0;
X  }
X
X  fclose(fp);            
X}
X
Xdump(from, to)
X  int from, to;
X{
X  STKPTR stklist;
X  int cost = 0;
X
X  if (from == to)
X  {
X    printf("It is a self link\n");
X    return;
X  }
X
X  stklist = stk;
X  while (stklist)
X  {
X    printf("%d --> ", stklist->from);
X    cost += stklist->cost;
X    stklist = stklist->nextstk;
X  }
X  if (cost == 0)
X  {
X    printf("There is not a link from %d to %d\n", from, to);
X    exit(1);
X  }
X
X  printf("%d\n", to);
X  printf("The cost is %d\n", cost);
X}
X
Xlink(from, to)
X  int from, to;
X{
X  ACKPTR acklist;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->to == to)
X      return (acklist->cost);
X    acklist = acklist->nextack;
X  }
X     
X  return (0);
X}
X
Xfind(from, x)
X  int from, *x;
X{
X  ACKPTR acklist;
X 
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->checked == 0)
X    {
X      *x = acklist->to;
X      acklist->checked = 1;
X
X      return (acklist->cost);
X    }
X
X    acklist = acklist->nextack;
X  }
X
X  return (0);
X}
X
Xsearch(type, from, to)
X  int type, from, to;
X{
X  switch (type)
X  {
X    case 1: depth(from, to); break;
X    case 2: breadth(from, to); break;
X  }
X}
X
Xdepth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    depth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    depth(from, to);
X  }
X}
X
Xbreadth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  while (cost = find(from, &x))
X  {
X    if (c = link(x, to))
X    {
X      put_to_stack(from, to, cost);
X      put_to_stack(x, to, c);
X      return;
X    }
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    breadth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    breadth(from, to);
X  }
X}
X
Xput_to_stack(from, to, cost)
X  int from, to, cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = (STKPTR)malloc(sizeof(struct _stack));
X  if (!stktmp)
X  {
X    printf("\nCannot allocate memory\n");
X    exit(1);
X  }
X
X  if (!stk)
X    stk = stktmp;
X  else
X  {
X    stklist = stk;
X    while (stklist->nextstk)
X      stklist = stklist->nextstk;
X	
X    stklist->nextstk = stktmp;
X  }
X  stktmp->nextstk = NULL;  
X  stktmp->to      = to;
X  stktmp->from    = from;
X  stktmp->cost    = cost;
X}
X
Xget_from_stack(from, to, cost)
X  int *from, *to, *cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = NULL;
X  stklist = stk;
X  while (stklist)
X  {
X    if (stklist->nextstk == NULL)
X    {
X      if (stktmp)
X        stktmp->nextstk = stklist->nextstk;
X      else
X        stk = stklist->nextstk;
X
X      *from = stklist->from;
X      *to   = stklist->to;
X      *cost = stklist->cost;
X  
X      free(stklist);
X
X      break;
X    }
X
X    stktmp = stklist;
X    stklist = stklist->nextstk;
X  }
X}
X  
Xfreestk()
X{
X  STKPTR stktmp, stklist;
X
X  stklist = stk;
X  while (stklist)
X  {
X    stktmp = stklist->nextstk;
X    free(stklist);
X    stklist = stktmp;
X  }
X
X  stk = NULL;
X}
________This_Is_The_END________
if test `wc -l < search3.c` -ne 313; then
  echo 'shar: search3.c was damaged during transit (should have been 313 lines)'
fi
fi
echo 'x - search4.c'
if test -f search4.c; then echo 'shar: not overwriting search4.c'; else
sed 's/^X//' > search4.c << '________This_Is_The_END________'
X#include <stdio.h>
X
Xtypedef struct _database * ACKPTR;
Xtypedef struct _stack    * STKPTR;
X
Xstruct _database
X{
X  int from;
X  int to;
X  int cost;
X  int checked;
X
X  ACKPTR nextack;
X};
X
Xstruct _stack
X{
X  int from;
X  int to;
X  int cost;
X
X  STKPTR nextstk;
X};
X
XACKPTR ack = NULL;
XSTKPTR stk = NULL;
X
Xload_ack();
Xfreechecked();
Xget_from_ack();
Xdump();
Xlink();
Xfind();
Xsearch();
Xdepth();
Xbreadth();
Xput_to_stack();
Xget_from_stack();
Xfreestk();
X  
Xmain(argc, argv)
X  int argc;
X  char *argv[];
X{
X  int type, from, to;
X  int tmp1, tmp2, tmp3;
X
X  if (argc != 5)
X  {
X    printf("\nUsage: trip <file> <type> <from> <out>\n");
X    printf("Type 1 is depth first - multiple solutions.\n");
X    printf("Type 2 is breadth first - multiple solutions.\n");
X    printf("Range from, to, cost: 0 < x < 32767.\n");
X    exit(1);
X  }
X
X  type = atoi(argv[2]);
X  from = atoi(argv[3]);  
X  to = atoi(argv[4]);
X  if (!to || !from || to < 0 || from < 0 || type < 0 || type > 2)
X  {
X    printf("\nBad parameters\n");
X    exit(1);
X  }
X
X  load_ack(argv[1]);
X
X  for (;;)
X  {
X    search(type, from, to);
X    dump(from, to);
X    freechecked();
X    if (stk)
X      get_from_stack(&tmp1, &tmp2, &tmp3);
X    get_from_ack(tmp1, tmp2);
X    freestk();
X  } 
X}
X
Xfreechecked()
X{
X  ACKPTR acklist;
X
X  acklist = ack;
X  while (acklist)
X  {
X    acklist->checked = 0;
X    acklist = acklist->nextack;
X  }
X}
X
Xget_from_ack(from, to)
X  int from, to;
X{
X  ACKPTR acktmp, acklist;
X
X  acktmp = NULL;
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->to == to)
X    {
X      if (acktmp)
X        acktmp->nextack = acklist->nextack;
X      else
X        ack = acklist->nextack;
X
X      free(acklist);
X
X      break;
X    }
X
X    acktmp = acklist;
X    acklist = acklist->nextack;
X  }
X}
X
Xload_ack(file)
X  char *file;
X{
X  FILE *fp;
X  int from, to, cost;
X  ACKPTR acktmp, acklist;
X  
X  if ((fp = fopen(file, "r")) == NULL)
X  {
X    printf("\nCannot open file %s\n", file);
X    exit(1);
X  }
X
X  while (fscanf(fp, "%d %d %d", &from, &to, &cost) != EOF)
X  {
X    acktmp = (ACKPTR)malloc(sizeof(struct _database));
X    if (!acktmp)
X    {
X      printf("\nCannot allocate memory\n");
X      exit(1);
X    }
X
X    if (!ack)
X      ack = acktmp;
X    else
X    {
X      acklist = ack;
X      while (acklist->nextack)
X        acklist = acklist->nextack;
X	
X      acklist->nextack = acktmp;
X    }
X    acktmp->nextack = NULL;  
X    acktmp->to      = to;
X    acktmp->from    = from;
X    acktmp->cost    = cost;
X    acktmp->checked = 0;
X  }
X
X  fclose(fp);            
X}
X
Xdump(from, to)
X  int from, to;
X{
X  STKPTR stklist;
X  int cost = 0;
X
X  if (from == to)
X  {
X    printf("It is a self link\n");
X    return;
X  }
X
X  stklist = stk;
X  while (stklist)
X  {
X    printf("%d --> ", stklist->from);
X    cost += stklist->cost;
X    stklist = stklist->nextstk;
X  }
X  if (cost == 0)
X  {
X    printf("There is not a link from %d to %d\n", from, to);
X    exit(1);
X  }
X
X  printf("%d\n", to);
X  printf("The cost is %d\n", cost);
X}
X
Xlink(from, to)
X  int from, to;
X{
X  ACKPTR acklist;
X
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->to == to)
X      return (acklist->cost);
X    acklist = acklist->nextack;
X  }
X     
X  return (0);
X}
X
Xfind(from, x)
X  int from, *x;
X{
X  ACKPTR acklist;
X 
X  acklist = ack;
X  while (acklist)
X  {
X    if (acklist->from == from && acklist->checked == 0)
X    {
X      *x = acklist->to;
X      acklist->checked = 1;
X
X      return (acklist->cost);
X    }
X
X    acklist = acklist->nextack;
X  }
X
X  return (0);
X}
X
Xsearch(type, from, to)
X  int type, from, to;
X{
X  switch (type)
X  {
X    case 1: depth(from, to); break;
X    case 2: breadth(from, to); break;
X  }
X}
X
Xdepth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  if (c = link(from, to))
X  {
X    put_to_stack(from, to, c);
X    return;
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    depth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    depth(from, to);
X  }
X}
X
Xbreadth(from, to)
X  int from, to;
X{
X  int c, cost, x;
X
X  while (cost = find(from, &x))
X  {
X    if (c = link(x, to))
X    {
X      put_to_stack(from, to, cost);
X      put_to_stack(x, to, c);
X      return;
X    }
X  }
X
X  if (cost = find(from, &x))
X  {
X    put_to_stack(from, to, cost);
X    breadth(x, to);
X  }
X  else if (stk)
X  {
X    get_from_stack(&from, &to, &cost);
X    breadth(from, to);
X  }
X}
X
Xput_to_stack(from, to, cost)
X  int from, to, cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = (STKPTR)malloc(sizeof(struct _stack));
X  if (!stktmp)
X  {
X    printf("\nCannot allocate memory\n");
X    exit(1);
X  }
X
X  if (!stk)
X    stk = stktmp;
X  else
X  {
X    stklist = stk;
X    while (stklist->nextstk)
X      stklist = stklist->nextstk;
X	
X    stklist->nextstk = stktmp;
X  }
X  stktmp->nextstk = NULL;  
X  stktmp->to      = to;
X  stktmp->from    = from;
X  stktmp->cost    = cost;
X}
X
Xget_from_stack(from, to, cost)
X  int *from, *to, *cost;
X{
X  STKPTR stktmp, stklist;
X
X  stktmp = NULL;
X  stklist = stk;
X  while (stklist)
X  {
X    if (stklist->nextstk == NULL)
X    {
X      if (stktmp)
X        stktmp->nextstk = stklist->nextstk;
X      else
X        stk = stklist->nextstk;
X
X      *from = stklist->from;
X      *to   = stklist->to;
X      *cost = stklist->cost;
X  
X      free(stklist);
X
X      break;
X    }
X
X    stktmp = stklist;
X    stklist = stklist->nextstk;
X  }
X}
X  
Xfreestk()
X{
X  STKPTR stktmp, stklist;
X
X  stklist = stk;
X  while (stklist)
X  {
X    stktmp = stklist->nextstk;
X    free(stklist);
X    stklist = stktmp;
X  }
X
X  stk = NULL;
X}
________This_Is_The_END________
if test `wc -l < search4.c` -ne 358; then
  echo 'shar: search4.c was damaged during transit (should have been 358 lines)'
fi
fi
echo 'x - link.dat'
if test -f link.dat; then echo 'shar: not overwriting link.dat'; else
sed 's/^X//' > link.dat << '________This_Is_The_END________'
X1 2 1000
X2 8 1000
X1 3 800
X1 8 1900
X3 7 1500
X3 6 1800
X3 2 500
X8 4 1000
X8 5 1500
X5 6 1500
X8 6 1000
________This_Is_The_END________
if test `wc -l < link.dat` -ne 11; then
  echo 'shar: link.dat was damaged during transit (should have been 11 lines)'
fi
fi
echo 'x - test'
if test -f test; then echo 'shar: not overwriting test'; else
sed 's/^X//' > test << '________This_Is_The_END________'
Xecho search1 link.dat 1 1 6
Xsearch1 link.dat 1 1 6
Xecho ----------
Xecho search1 link.dat 2 1 6
Xsearch1 link.dat 2 1 6
Xecho ----------
Xecho search2 link.dat 1 1 6
Xsearch2 link.dat 1 1 6
Xecho ----------
Xecho search2 link.dat 2 1 6
Xsearch2 link.dat 2 1 6
Xecho ----------
Xecho search3 link.dat 1 1 6
Xsearch3 link.dat 1 1 6
Xecho ----------
Xecho search3 link.dat 2 1 6
Xsearch3 link.dat 2 1 6
Xecho ----------
Xecho search4 link.dat 1 1 6
Xsearch4 link.dat 1 1 6
Xecho ----------
Xecho search4 link.dat 2 1 6
Xsearch4 link.dat 2 1 6
Xecho ----------
________This_Is_The_END________
if test `wc -l < test` -ne 24; then
  echo 'shar: test was damaged during transit (should have been 24 lines)'
fi
fi
echo 'x - search.doc'
if test -f search.doc; then echo 'shar: not overwriting search.doc'; else
sed 's/^X//' > search.doc << '________This_Is_The_END________'
X                   Copyright (C) 1993 by ALBERTO SANTINI.
X                            All Rights reserved.
X
XAuthor: Alberto Santini
XDate: January 14, 1993
X
XPermission is hereby garanted to copy all 
Xor any part of this program for free distribution.  
XThe author's name and this copyright notice must be included in any copy.
XThis program is provided ``as is'' without any express or implied warranties.
X
XComments and suggestions may be mailed to 
X
X	Alberto Santini
X 	V. Compiano, 7
X	43040 - VNO. MELEGARI (PR)
X	ITALY
X
Xbut this implies no obligation on the part of the author.
X
XUsers are encouraged to modify and extend this program,
Xand such modifications should be commented with appropriate attribution.
XThis program should not be considered a final product, but rather it is hoped
Xthat it will serve as a stimulus for further experimentation and development.
X
X
X
XFile:
X
Xsearch.doc	It is this document.
X
Xtest		It is a script testing all ways of search.
X
Xlink.dat	It is a file including the data of graph.
X
Xsearch0.c	Search in a graph using depth first method;
X                data structure is the array.
X                From "Artificial Intelligence using C" by H. Schildt.
X
Xsearch1.c	Search in a graph using depth first, breadth first methods;
X                data structure is the list.
X
Xsearch2.c	Search in a graph using hill climber, less cost methods.
X
Xsearch3.c	Search in a graph using depth first, breadth first methods
X                with multiple solutions ( streets cut ).
X
Xsearch4.c	Search in a graph using depth first, breadth first methods
X                with multiple solutions ( nodes cut ).
________This_Is_The_END________
if test `wc -l < search.doc` -ne 49; then
  echo 'shar: search.doc was damaged during transit (should have been 49 lines)'
fi
fi
echo 'x - makefile'
if test -f makefile; then echo 'shar: not overwriting makefile'; else
sed 's/^X//' > makefile << '________This_Is_The_END________'
Xall: search0 search1 search2 search3 search4
X
Xsearch0: search0.c
X	cc -o $* $*.c
X
Xsearch1: search1.c
X	cc -o $* $*.c
X
Xsearch2: search2.c
X	cc -o $* $*.c
X
Xsearch3: search3.c
X	cc -o $* $*.c
X
Xsearch4: search4.c
X	cc -o $* $*.c
X
Xsearch.shar:
X	shar -o gsearch search?.c link.dat test search.doc makefile
________This_Is_The_END________
if test `wc -l < makefile` -ne 19; then
  echo 'shar: makefile was damaged during transit (should have been 19 lines)'
fi
fi
