/* See {MakeAdjacencyMatrix.h} */
#include <MakeAdjacencyMatrix.h>

/* This program implements the ShortestPath Algorithm from R. Floyd on
   Communications of the ACM, Volume 5, Number 6, June, 1962, pag 345

   Algorithm 97
   SHORTEST PATH
   Robert W. Floyd

   Procedure 
   ---------
             shortest path(m,n); value n; integer n; array m;
   Comments 
   --------

   Initially m[i,j] is the length of a direct link from point i of a network
   to point j. If no direct link exists, m[i,j] is initially 10^{10}. At
   completion, m[i,j] is the length of the shortest path from i to j. If nome
   exists, m[i,j] is  10^{10}.

   begin
   integer i,j,k; real inf,s; inf = 10^{10};
   for i= 1 step 1 until n do
   for j= 1 step 1 until n do
   if m[j,i] < inf then
   for k= 1 step 1 until n do
   if m[i,k] < inf then
   begin s= m[j,i] + m[i,k];
   if s < m[j,k] then m[j,k] = s
   end
   end shortest path

*/

#define MakeAdjacencyMatrix_C_author \
  "Created by L. P. Lozada, ca. 1999.\n" \
  "Modified by L.A.P.Lozada on 99-11-02."

#include <math.h>
#include <argparser.h>
#define _GNU_SOURCE
#include <stdio.h>
#include <Triangulation.h>
  
TYPE
typedef struct Options_t {
      char *inFile;             /* Initial guess file name (minus ".tp") */
  }

double AdjacencyMatrix = ARRAY OF double_vec_t;

double inf = Math.pow(10.0,10.0);
VAR 
Options_t *GetOptions(int argc, char **argv);

int main(int argc, char **argv)
  
  double *max;
      m : REF AdjacencyMatrix;
  { Options_t *o = GetOptions(argc, argv);
    char *topo_cmt = jsprintf("Created by %s on %s", PROG_NAME, Today());
    /* Random_t coins = MakeRandomSource(4615); */
    ??? tc = Triangulation.ReadToMa(o->inFile);
    ??? top = tc.top;
    {
       m = MakeAdjacencyMatrix(top);
       fprintf(stderr, "\nInput of the ShortestPath Algorithm: " \
                  o->inFile & ".tp\n");
       PrintHalfMatrix(m,top->node.nel);
       ShortestPath(m,top->node.nel);
       fprintf(stderr, "\nOutput of the ShortestPath Algorithm\n" & "\n");
       PrintHalfMatrix(m,top->node.nel);
       max = FindMaxDistance(m,top->node.nel);
       fprintf(stderr, "\nMax Distance: " & Fmt.LongReal(max) & "\n");
    
    return 0;
  }

AdjacencyMatrix *MakeAdjacencyMatrix(ElemTableRec_t *top, 
 )==
  REF ARRAY OF double_vec_t m ;
    v: REF ARRAY OF INTEGER;
  { m = NEW(REF ARRAY OF double_vec_t, top->node.nel, top->node.nel);
    for (i = 0; i < top->node.nel; i++)
    {
      for (j = 0; j < top->node.nel; j++)
      {
        m[i,j] = inf;
      }
    }

    for (i = 0; i < top->node.nel; i++)
    {
      ??? a = top->node[i];
        ??? star = Triangulation.Neighbors(a;
      with (top), 
      double nv = Triangulation->numberNeighborNode(star)
    ){
        m[i,i] = 0.0;
        v = NEW(REF ARRAY OF INTEGER, nv);
        for (k = 0; k < nv; k++)
        {
          v[k] = star[k]->num;
          m[i,v[k]] = 1.0;
          m[v[k],i] = 1.0;
        }
      }
    }
    return m;
  } /* END MakeAdjacencyMatrix */

/* UNUSED */
PROCEDURE PrintAdjacencyMatrix(*m : REF AdjacencyMatrix; n: INTEGER)
  
  { for (i = 0; i < n; i++){
      for (j = 0; j < n; j++)
      {
        if (m[i,j] == inf)
        {
          fprintf(stderr, "# ");
        }
        else
        {
          fprintf(stderr, Fmt.LongReal(m[i,j]) & " ");
        }
      }
      fprintf(stderr, "\n");
    }
  } /* END PrintAdjacencyMatrix */

PROCEDURE PrintHalfMatrix(*m : REF AdjacencyMatrix; n: INTEGER)
  
  { for (i = 0; i < n; i++){
      for (j = 0; j <= (i); j++)
      {
        if (m[i,j] == inf)
        {
          fprintf(stderr, "# ");
        }
        else
        {
          fprintf(stderr, Fmt.LongReal(m[i,j]) & " ");
        }
      }
      fprintf(stderr, "\n");
    }
  } /* END PrintHalfMatrix */
  
double FindMaxDistance(
   *m : REF AdjacencyMatrix;
   INTEGER n;
  )
      max = 0.0; 
  { for (i = 0; i < n; i++){
      for (j = 0; j <= (i); j++)
      {
        if (m[i,j] > max)
        {
          max = m[i,j];
        }
      }
    }
    return max;
  } /* END FindMaxDistance */
  
PROCEDURE ShortestPath(VAR m : REF AdjacencyMatrix; n : INTEGER)
  double *s;
  { for (i = 0; i < n; i++){
      for (j = 0; j < n; j++)
      {
        if (m[i,j] < inf)
        {
          for (k = 0; k < n; k++)
          {
            if (m[i,k] < inf)
            {
              s = m[j,i] + m[i,k];
              if (s < m[j,k]){ m[j,k] = s; }
            }
          }
        }
      }
     }
   } ShortestPath;

Options_t GetOptions ()
  { Options_t *o = (Options_t *)malloc(sizeof(Options_t));
    argparser_t *pp = argparser_new(stderr, argc, argv);
    argparser_set_help(pp, PROG_NAME " version " PROG_VERS ", usage:\n" PROG_HELP);
    argparser_set_info(pp, PROG_INFO);
    argparser_process_help_info_options(pp);
    
    argparser_get_keyword(pp, "-inFile");                               
        o->inFile = argparser_get_next(pp);
        argparser_finish(pp);                                       
      
  -----------------------------------
#define _HELP \
  fprintf(stderr, "Usage: MakeAdjacencyMatrix" \
   " -inFile <name>\n");
          
END¦                                              
      }
    }
    return o;
  } /* END GetOptions */

{
  DoIt()
} MakeAdjacencyMatrix.



  /* Copyright © 1999     Universidade Estadual de Campinas (UNICAMP)     */