Example C++ Code: Finding Redundancy In A Network

#include < sys/ddi.h >
#include < fstream.h >
#include < iostream.h >
#include < stdlib.h >
#include < stdio.h >

class Array
{
public:
  Array(int r, int c)
  {
     int i;

     if (c > 0)
     { rows=r; cols=c; array = new int[r*c]; }
     else
     { rows=1; cols=r; array = new int[r]; for (i=0 ; i < r ; i++) array[i]=c; }
  }
  Array(int c)
  {
     rows=1; cols=c; array = new int[c];
  }
  int  get(int i, int j)
  {
     if (i < 0 || i > rows) return 0;
     if (j < 0 || j > cols) return 0;
     return array[i*cols+j];
  }
  int get(int i)
  {
     if (i < 0 || i > cols) return 0;
     return array[i];
  }
  void put(int i, int j, int k)
  {
     if (i >= 0 && i < = rows && j >= 0 && j < = cols) array[i*cols+j] = k;
  }
  void put(int i, int k)
  {
     if (i >= 0 && i < = cols) array[i] = k;
  }
  ~Array() { delete array; }

private:
  int rows;
  int cols;
  int *array;
};

class IntStack
{
public:
   IntStack(int num) {  top = 0; maxelem = num; s = new int[maxelem]; }
   void  push(int t)
   {
      if (top == maxelem) return;
      s[top++] = t;
   }
   int pop()
   {
      if (top == 0) return -1;
      return s[--top];
   }
   void display()
   {
     if (top == 0) { cout << "(empty)\n";  return; }
     for (int t=0 ; t < top ; t++) cout << s[t] << " ";
     cout << "\n";
   }
   int   empty()  {  return top == 0;  }
private:
   int *s;
   int top;
   int maxelem;
};

#define MAX_CITIES 100

/***-------------------------------------------------***/
/*** Redundancy:                                     ***/
/***   Input: A network (n by n array of 0-1 values) ***/
/***          A number of cities (n above)           ***/
/***   Output: 1 if network is redundant             ***/
/***           0 otherwise                           ***/
/*** Checks network links for redundant connections  ***/
/***-------------------------------------------------***/
int redundancy(Array *links, int cities)
{
   IntStack *s = new IntStack(MAX_CITIES);
   Array *visited = new Array(MAX_CITIES);
   Array *parent  = new Array(MAX_CITIES,-1);
   int i, current=0;

   s->push(current);
   while (!s->empty())
   {
      current = s->pop();
      while (!s->empty() && visited->get(current)) current = s->pop();
      visited->put(current, 1);
      for (i=0 ; i < = cities ; i++)
      {
         if (!links->get(current,i) || current == i) continue;
         if (!visited->get(i))
         {
            s->push(i);
            parent->put(i,current);
	 }
         else
         if (i != parent->get(current)) return 1;
      }
   }
   return 0;
}

int main(int argc, char **argv)
{
   Array *links = new Array(MAX_CITIES, MAX_CITIES);
   char *buffer = new char[128];
   int city1, city2, cost, cities=0;

   if (argc != 2)
   {
      printf("Usage: redundacy filename");
      exit(0);
   }
   fstream fin(argv[1], ios::in);
   while (fin.getline(buffer, 128, '\n'))
   {
      sscanf(buffer, "%d%d", &city1, &city2);
      links->put(city1,city2,1);
      cities = max(max(cities, city1), city2);
   }
   fin.close();

   printf("((%d))\n",redundancy(links,cities));

   return 1;
}