parser_r.c

17个最短路径源代码。代码效率高

		k = sscanf ( in_line,"%*c %ld %ld", &source, &source2 );
 
		if ( k < 1 )
                  /* source number is not red */
                  { err_no = EN11; goto error; }

		if ( k == 2 )
                  /* more than one source in node (source) line */
                  { err_no = EN9; goto error; }

		if ( source < 0 || source > n )
                  /* wrong value of source */
                  { err_no = EN12; goto error; }

                node_max = 0;
                node_min = n;
		break;

      case 'd':                    /* sink description */
                /* another parser may support sink description */
		err_no = EN13; goto error;

      case 'a':                    /* arc description */
		if ( no_nlines == 0 ) 
                  /* there was not source description above */
                  { err_no = EN14; goto error; }

		if ( no_alines >= m )
                  /*too many arcs on input*/
                  { err_no = EN16; goto error; }
		
		if (
                    /* reading an arc description */
                    sscanf ( in_line,"%*c %ld %ld %ld",
                                      &tail, &head, &length )
                    != 3 
                   ) 
                    /* arc description is not correct */
                    { err_no = EN15; goto error; }

		if ( tail < 0  ||  tail > n  ||
                     head < 0  ||  head > n  
		   )
                    /* wrong value of nodes */
		    { err_no = EN17; goto error; }

		arc_first[tail + 1] ++; /* no of arcs outgoing from tail
                                           is stored in arc_first[tail+1] */

                /* storing information about the arc */
		arc_current -> tail = nodes + tail;
		arc_current -> head = nodes + head;
		arc_current -> len  = length;

		/* searching minimumu and maximum node */
                if ( head < node_min ) node_min = head;
                if ( tail < node_min ) node_min = tail;
                if ( head > node_max ) node_max = head;
                if ( tail > node_max ) node_max = tail;

		no_alines ++;
		arc_current ++;
		break;

	default:
		/* unknown type of line */
		err_no = EN18; goto error;
		break;

    } /* end of switch */
}     /* end of input loop */

/* ----- all is red  or  error while reading ----- */ 

if ( feof (stdin) == 0 ) /* reading error */
  { err_no=EN21; goto error; } 

if ( no_lines == 0 ) /* empty input */
  { err_no = EN22; goto error; } 

if ( no_alines < m ) /* not enough arcs */
  { err_no = EN19; goto error; } 

if ( no_tlines == 0 ) /* input doesn't contain problem name */
  strcpy ( problem_name, DEFAULT_NAME );

  
/********** ordering arcs - linear time algorithm ***********/

/* first arc from the first node */
( nodes + node_min ) -> first = arcs;

/* before this loop arc_first[i+1] is the number of arcs outgoing from i;
   after this loop arc_first[i] is the position of the first 
   outgoing from node i arcs after they would be ordered;
   it is transformed to pointer and written to node.first[i]
   */
 
for ( i = node_min + 1; i <= node_max + 1; i ++ ) 
  {
    arc_first[i]          += arc_first[i-1];
    ( nodes + i ) -> first = arcs + arc_first[i];
  }


for ( i = node_min; i < node_max; i ++ ) /* scanning all the nodes  
                                            exept the last*/
  {
    node_i = nodes + i;           /* converting number to pointer */
    last = ( node_i + 1 ) -> first;
                                   /* arcs outgoing from i must be cited    
                                   from position arc_first[i] to the position
                                 equal to initial value of arc_first[i+1]-1  */

    for ( arc_current = arcs + arc_first[i]; 
          arc_current < last; 
          arc_current ++ )

      { tail_p = arc_current -> tail;

	while ( tail_p != node_i )
          /* the arc arc_current  is not in place because arc cited here
             must go out from node_i;
             we'll put it to its place and continue this process
             until an arc in this position would go out from node_i */

	  { arc_new      = arcs + arc_first [ tail_p - nodes ];
	  	  	    
	    /* arc_current must be cited in the position arc_new    
	       swapping these arcs:                                 */

	    head_p               = arc_new -> head;
	    arc_new -> head      = arc_current -> head;
	    arc_current -> head = head_p;

	    arc_current -> tail  = arc_new -> tail;
	    arc_new -> tail      = tail_p;

	    length              = arc_new -> len;
	    arc_new -> len      = arc_current -> len;
	    arc_current -> len = length;

	    arc_first [ tail_p - nodes ] ++ ;

            tail_p = arc_current -> tail;
	  }
      }
    /* all arcs outgoing from  i  are in place */
  }       

/* -----------------------  arcs are ordered  ------------------------- */

/* -------------- constructing lists of incoming arcs ----------------- */

for ( i = node_min; i <= node_max; i++ )
{    node_i             = nodes + i;
     node_i -> first_in = (arc*)NULL;
}

arc_last = arcs + m - 1;

for ( arc_current = arc_last; arc_current >= arcs; arc_current -- )
   {
     node_i                = arc_current -> head;
     arc_current -> next_t = node_i -> first_in;
     node_i -> first_in    = arc_current;
   }

/* ----- assigning output values ----- */
*m_ad = m;
*n_ad = node_max - node_min + 1;
*source_ad = nodes + source;
*node_min_ad = node_min;
*nodes_ad = nodes + node_min;
*arcs_ad = arcs;

if ( source < node_min || source > node_max )
  /* bad value of the source */
  { err_no = EN20; goto error; }
  
if ( (*source_ad) -> first == ((*source_ad) + 1) -> first ) 
  /* no arc goes out of the source */
  { err_no = EN20; goto error; }


/* free internal memory */
free ( arc_first );

/* Uff! all is done */
return (0);

/* ---------------------------------- */
 error:  /* error found reading input */

fprintf ( stderr, "\nPrs%d: line %d of input - %s\n", 
         err_no, no_lines, err_message[err_no] );

exit (1);

}
/* --------------------   end of parser  -------------------*/

/*

main()
{

arc *arp, *t;
node *ndp, *source, *k;
long n, m, nmin, i; 
char *name[21];
int l;

l=parse( &n, &m, &ndp, &arp, &source, &nmin, name );

printf ( "code: %d\n", l );
printf ( "%s\nn= %ld, m= %ld, nmin= %ld, source = %ld\n",
        name,
        n,m,nmin, (source-ndp)+nmin );

printf ("\nordered arcs:\n");
for ( k = ndp; k< ndp + n; k++ )
  { i = (k-ndp)+nmin;
    for ( t=k -> first; t != (k+1)-> first; t++ )
      printf ( " %2ld %2ld %4ld\n",
               ((t->tail)-ndp)+nmin, ((t->head)-ndp)+nmin, t->len
             );

  }

printf ("\nreversed order:\n");
for ( k = ndp; k< ndp + n; k++ )
for ( t = k -> first_in; t != NULL; t = t -> next_t )
      printf ( " %2ld %2ld %4ld\n",
               ((t->tail)-ndp)+nmin, ((t->head)-ndp)+nmin, t->len
             );

 }
*/