:	This is a shell archive.
:	Remove everything above this line and
:	run the following text with /bin/sh to create:
:	double.a
:	edge_to_wm
:	random.c
:	run.me
:	strip.a
:	t1.in
:	t2.in
: This archive created: Thu Jul 11 14:43:20 1991
cat << 'SHAR_EOF' > double.a
# double edges and put problem line in front 
# the -1, 555 and 999 are sorting indices 

$1 == "p"  {print "-1", $3, 2*$4}
$1 == "e"  {src = $2; dst = $3; cost = $4;
            degree[src]++;
            degree[dst]++;

            print src, 999, dst, cost;  
            print dst, 999, src, cost;
	}
END { for (i in degree) { print i, 555, degree[i], 0, 0 } 
}

SHAR_EOF
cat << 'SHAR_EOF' > edge_to_wm

#This shell file converts matching problems in the DIMACS input 
#format (.edge) to problems for Rothberg's weighted matching code wmatch.

case $# in 
0|1)  echo "Usage: edge_to_wmatch  input.edge  input.wmat"; exit 1
esac

awk -f double.a <$1 | sort +0 -1 | awk -f strip.a >$2
SHAR_EOF
cat << 'SHAR_EOF' > random.c
#include<stdio.h>
#include<math.h>

/*-----------------------------------------------------------------*/
/*  Generates random undirected graphs with $m$ edges, in          */ 
/*  Challenge format.  Instances have random uniform edge          */
/*  costs.                                                         */
/*  C. McGeoch at DIMACS, July 1991  */

/*  This uses a PORTABLE random number generator.    */
/*  It will give IDENTICAL sequences of random numbers for any      */
/*  architecture with at least 30-bit integers, regardless of the   */
/*  integer representation, MAXINT value, or roundoff/truncation    */
/*  method, etc.                                                    */

/*  Example input:         */
/*  nodes 1000             */
/*  edges  2500            */
/*  maxcost 1000           */ 
/*  seed  818182717        */

/*  Seed command is optional.                           */
/*  nodes  N  : specifies N nodes                       */ 
/*  edges  A  : specifies A edges                       */
/*  maxcost X : specifies maximum edge weight           */ 
/*  seed   S  : RNG seed; default system timer          */ 
/*------------------------------------------------------*/  

#define Assert( cond , msg ) if ( ! (cond) ) {printf("msg\n"); exit(); } ; 
#define MAXNODES 1000
#define MAXCOST 100000
#define PRANDMAX 1000000000       /* RNG Max Value */ 

#define TRUE 1
#define FALSE 0

typedef char string[50];


/* BST for Set searches */ 
typedef struct node_type {
  int val;
  struct node_type *left;
  struct node_type *right;
} treenode; 

int arc_size; 
treenode *root; 

/* ------RNG Global Variables---- */ 
int a; 
int b; 
long arr[55];  

/* Global Parameters */
long seed;
int nodes,edges; 
int rand_seed;        /*a boolean flag*/ 
int maxcost; 
int maxarcs, maxedges; 

string cmdtable[10];
int cmdtable_size; 

/*----RNG Initializer------------*/
/* Call once before using lprand */ 

void sprand (seed)
long seed; 
{
  int i, ii;
  long last, next;
  arr[0] = last = seed; 
  next = 1;
  for (i=1; i < 55; i++) {
    ii = ( 21 * i ) % 55;
    arr[ii] = next;
    next = last - next; 
    if (next < 0)
      next += PRANDMAX;
    last = arr[ii];
  }

  a = 0;
  b = 24; 
  for (i = 0; i < 165; i++) 
    last = lprand();
} /* sprand */

/*---------RNG---------------------*/
/* Returns long integers from the  */
/* range 0...PRANDMAX-1            */ 

long lprand()
{    long t;
     if (a-- == 0) a = 54;
     if (b-- == 0) b = 54;

     t = arr[a] - arr[b];

     if (t < 0) t+= PRANDMAX;
     
     arr[a] = t;

     return t;

   }/*lprand*/

/* Double precision RNG  */
double dprand()
{
  double x;
  x = (double) lprand() / PRANDMAX;
  return (x) ;
}

/*----------------- Initialize tables and data  */ 
void init()
{ 
  
  cmdtable_size = 4; 
  strcpy(cmdtable[0], "sentinel.spot");
  strcpy(cmdtable[1], "nodes" );   /* required */ 
  strcpy(cmdtable[2], "edges"  );
  strcpy(cmdtable[3], "seed");
  strcpy(cmdtable[4], "maxcost");
  
  nodes = 100; 
  edges = 100; 
  maxcost = MAXCOST; 
  rand_seed = TRUE;

  root = NULL; 
  arc_size = 0; 

}   

/* ---------------- Random number utilities */

/* Initialize rng: replace with your own if you like */  
void init_rand(seed) 
long seed; 
{
  sprand(seed); 
}

/* Return an integer from [1..max] */  
int rand_int(max) 
int max;
{
  double x; 
  int i; 
  
  x = dprand();    /* replace with a system call if you like */ 
  i = (double) x * max + 1.0;
  return(i);
}

double rand_d()
{
   return(dprand());   /* replace with a system call if you like */ 
 }


/*-------------------------bst for selection wo replacement */ 

int inset(arc)
int arc;
{
  treenode *current;

  current = root; 
  while(current != NULL) {
    if (current->val > arc) { 
      current = current->left;
    }
    else if (current->val < arc) {
      current = current->right;
    }
    else 
      return(TRUE);
  }/*while*/

  return(FALSE);

}/*inset*/

/* insert arc into tree--assumes its not already in */ 

void insert(arc)
int arc;
{
  treenode *current;
  treenode *parent;

  if ( arc_size ==  0) {  /* first insertion */
    root = (treenode *) malloc(1*sizeof(treenode));
    root->val = arc;
    root->left = NULL;
    root->right= NULL; 
  }else{
    current = root;

    while (current != NULL) {
      parent = current; 
      /* search for the empty spot, saving parent */
      if (arc < parent->val) { 
	current = parent->left;
	}
      else if (arc > parent->val) {
	current = parent->right;
      }

    }/* while */ 
  
    current = (treenode *) malloc(1*sizeof(treenode));
    current->val = arc;
    current->left = NULL;
    current->right = NULL; 

    if (arc < (parent->val)) parent->left = current;
    else parent->right = current;
  }/*else not new  */

    arc_size++; 
} /* insert */

/*  generate edges in fairly sparse graphs */ 
void gen_edges1() 
{
   int i; 
   int src,dst; 
   int a; 
   int cost; 

  for (i=0; i< edges; i++) { 

    /* loop until an unused edge is found */ 
    /* and dont allow the upper diagonal */ 
    do {   
       a = rand_int(maxarcs);
       src = ((a-1) / (nodes-1)) + 1;        /* row number in 1..n */
       dst = (a % (nodes-2)) + 1;          /* col number in 1..n-1 */
       if (src == dst) {                /* move arc [i,i] to [i,n] */ 
	dst = nodes; 
      }

    } while ((src > dst) || (inset(a) == TRUE ));
 
    /* found one */ 
    insert(a); 
    cost  = rand_int(maxcost); 
    printf("e \t %d \t %d \t %d\n", src, dst, cost); 
  
  }/* for i */ 

 }/*gen_edges1 */ 


/*   generate edges in fairly dense graphs  */ 
/*  See Knuth V2, 3.4.5, Algorithm s        */

void gen_edges2() 
{
    double have; 
    double seen; 
    double need; 
    double total; 
    double x; 
    int src, dst; 
    int cost; 
  
    need = (double) edges;
    total = (double) maxedges;
    have = 0.0;
    seen = 0.0; 
 
    /* consider each edge in turn and decide whether to use it */ 

    for (src = 1; src <= nodes; src++) {
      for (dst = 1; dst < src; dst++) {

           if (have >= need) break; 
 
           x = rand_d();
   
           /* choose current edge with prob =  */
           /* (number left to choose)/(number left in set) */ 

           if ((total - seen) *x < (need - have) ) {

	     cost = rand_int(maxcost);
	     printf("e  %d  %d  %d \n", src, dst, cost);
	   }/* if */
	 }/*for dst*/
    }/*for src*/
  }/*gen_edges2*/

/*------------------Command input routines  */ 
int lookup(cmd)
char *cmd; 
{
 int i;
 int stop;

 strcpy( cmdtable[0], cmd);  /* sentinel */ 
 stop = 1;
 for (i = cmdtable_size; stop != 0; i--) stop = strcmp(cmdtable[i], cmd);

 return ( i + 1 ); 
}/*lookup*/

/*---------------------- Read command lines */ 
void get_input()
{
char cmd[50], buf[50];
int index;

  while (scanf("%s", cmd ) != EOF) {
    fgets(buf, sizeof(buf), stdin);
    index = lookup(cmd);
    switch(index) {

    case 0:  { fprintf(stderr, "%s: Unknown command. Ignored.\n", cmd);
	       break;
	     }
    case 1:  {sscanf( buf , "%d", &nodes); 
	      Assert( 0<=nodes && nodes<=MAXNODES , Nodes out of range. );
	      maxarcs =  ((nodes*nodes) - nodes); 
              maxedges = maxarcs/2; 
	      break;
	    }
    case  2: {sscanf (buf , "%d", &edges);
	      break;
	    }
    case 3: { sscanf( buf, "%d", &seed);
	       rand_seed  = FALSE;
	       break;
	    }
    case 4: { sscanf( buf, "%d", &maxcost);
              Assert( maxcost <= MAXCOST , Maxcost too high--recompile. ); 
              break;
            }
    }/*switch*/
  }/*while*/

  /* Do sanity checks */ 
  Assert( 0 <= edges && edges <= maxedges , Bad number of edges value. ); 

}/*input*/
/* ---------------------------Report parameters  */

void report_params()
{
  printf("c nodes %d\n", nodes);
  printf("c edges %d \n", edges);
  printf("c maxcost %d \n", maxcost); 
  if (rand_seed == TRUE) printf("c random seed\n");
  else printf("c seed %d\n", seed);
}

/*--------------------------- Generate and print out network  */ 
void generate_graph()
{
  if (rand_seed == TRUE) init_rand((int) time(0));
  else init_rand(seed); 

  /* Print first line and some comments  */

  printf("p edge  \t %d \t %d \n", nodes, edges);
  printf("c Matching problem with %d nodes and %d edges\n", 
          nodes, edges);
  printf("c Randomly generated---very little structure \n");
  printf("c Max edge weight %d\n", maxcost);

  report_params();

  /*  use different generation routines depending on density */

  if (edges < maxarcs / 8) gen_edges1(); 
  else gen_edges2();  

}/*generate_graph*/

main()
{

    init(); 
    get_input();
    generate_graph(); 
  } 
SHAR_EOF
cat << 'SHAR_EOF' > run.me

#do everything if no command line argument 

case $# in
0)echo "Compiling wmatch..." 
  make wmatch 

  echo "Generating inputs..."
  chmod +x edge_to_wm  
  cc random.c -o random
  random <t1.in >t1.edge
  random <t2.in >t2.edge
# convert input formats 
  edge_to_wm t1.edge t1.wm
  edge_to_wm t2.edge t2.wm

  echo "Running test 1" 
   echo "wmatch test 1" >>time.log
   time wmatch t1.wm >t1.out 2>>time.log
   echo " " >>time.log 

  echo "Running test 2" 
   echo "wmatch test 2" >>time.log 
   time wmatch t2.wm >t2.out 2>>time.log
   echo " " >>time.log  ;;

# if there is an argument, just run the tests

1) echo "Running test 1" 
    echo $1 >> time.log
    time wmatch t1.wm  >t1.out 2>>time.log
    echo " " >>time.log 

   echo "Running test 2" 
    echo $1 >> time.log
    time wmatch t2.wm  >t2.out 2>>time.log
    echo " " >>time.log  ;; 

esac


SHAR_EOF
cat << 'SHAR_EOF' > strip.a
$1 == -1  { print $2, $3, "U"}

$2 == 555 { print  $3,  $1,  $4, $5}

$2 == 999 { print $3, $4}

SHAR_EOF
cat << 'SHAR_EOF' > t1.in
nodes 128
edges 4096
maxcost 100
seed 9806737
SHAR_EOF
cat << 'SHAR_EOF' > t2.in
nodes 256
edges 16384
maxcost 100
seed 9073561
SHAR_EOF
:	End of shell archive
exit 0