#include #include #include #include #include /* Code to generate the essential subgraph H of a random uniform graph G */ /* By C. McGeoch, modified 5/10 for AlgLab */ /* Version 3: memoization with a distance matrix, plus filter */ /* Cleaned up version2, but no time changes. */ /* Version 3 also includes BFS with loop abort and filter */ /* Inputs (one per line): */ /* nodes n */ /* trials t */ /* seed s (optional)*/ /* Output: (all on one line) */ /* Trial number, G.nodes, G.edges, */ /* Edges in H */ /* Cost of last edge in H */ /* Rank (in G) of last edge in H */ /* Rank (in G) of largest MST edge */ /* MST Diameter */ #define Assert( cond , msg ) if ( ! (cond) ) {printf("msg \n"); exit(1);} ; #define MAXNODES 2001 #define MAXEDGES 2001000 #define TRUE 1 #define FALSE 0 #define INFTY 999999999.0 typedef char string[50]; double dmatrix[MAXNODES][MAXNODES]; /*-------------------------------------------------------------------------*/ /* Definitions for G and E graphs */ /*-------------------------------------------------------------------------*/ typedef struct edgestr { /* Edges of essential subgraph (adj list) */ int dest; double cst; struct edgestr *next; } edgetype ; typedef struct nodestr { /* Nodes of essential subgraph */ edgetype *first; edgetype *last; } nodetype; typedef struct { /* Edges in random generated graph */ int vv; int ww; double cost; } gedgetype; int edgecount; /* Number edges generated */ int edgeindex; /* index in edge array of G*/ double curmax; double mydrand(); double drand48(); gedgetype edgeset[MAXEDGES]; /* Edges of G */ nodetype nodelist[MAXNODES]; /* Nodes of E*/ /*-----------------------------------------------------*/ /* Global parameters and param table */ /*-----------------------------------------------------*/ int nodes, trials, seed; int totedges; int rand_seed; /*boolean for random or supplied seed*/ string cmdtable[10]; int cmdtable_size; /*-------------------------------------------------------*/ /* Input Handlers and Misc. */ /*-------------------------------------------------------*/ /*--------------tabinit-------------------------*/ void tabinit() { cmdtable_size = 3; strcpy(cmdtable[0], "sentinel.spot"); strcpy(cmdtable[1], "nodes"); strcpy(cmdtable[2], "trials"); strcpy(cmdtable[3], "seed"); nodes=MAXNODES; trials=1; rand_seed = TRUE; } /*------------lookup command in table------------ */ int lookup (cmd) string cmd; { /* lookup commands in command table */ int i; int stop; strcpy(cmdtable[0], cmd); stop = 1; for (i=cmdtable_size; stop != 0 ; i--) stop = strcmp(cmdtable[i], cmd); return ( i+1 ); }/*lookup*/ /*------------translate input command---------------*/ void transinput() { char cmd[50], buf[50]; int index; while (scanf("%s", cmd) != EOF ) { fgets(buf, sizeof(buf), stdin); index = lookup (cmd); switch (index ) { case 0 : { printf("%s: Unknown command\n", cmd); break; } case 1 : { sscanf( buf, "%d", &nodes); Assert(1<=nodes && nodes<=MAXNODES , Nodes out of range. ); break; } case 2: { sscanf( buf, "%d", &trials); break; } case 3: { sscanf( buf, "%d", &seed); rand_seed = FALSE; break; } }/*switch*/ }/*while scanf */ if (rand_seed == TRUE) srand48((int) time(0)); else srand48(seed); }/*transinput*/ /*--------------------------------------------------------------------------*/ /* The Heap used for Dijkstra searches */ /* -------------------------------------------------------------------------*/ typedef struct { /* Heap elements */ int hid; /* node name */ double hval; /* distance from src */ } heaptype; int heapsize; /* heap is in locations 1..heapsize */ heaptype heap[MAXNODES]; int hloc[MAXNODES]; /* location backpointers in heap */ /* --heapinit -------initialize empty with one node, dist = 0 */ void heapinit(int src) { heap[1].hid = src; heap[1].hval = 0.0; hloc[heap[1].hid] = 1; heapsize = 1; } /*-------heapextract -----------------------------------------*/ heaptype heapextract() { heaptype heaptop = heap[1]; heap[1] = heap[heapsize--]; hloc[ heap[1].hid ] = 1; heaptype tmp; int hix = 1; int lchild, rchild, which; double min ; #ifdef HEAP int i; printf("removed %d %lf\n", heaptop.hid, heaptop.hval); printf("heap before siftdown :\n"); for (i = 1; i <= heapsize; i++) { printf("\t %d %d %d %lf\n",i, hloc[heap[i].hid], heap[i].hid, heap[i].hval); } #endif /* siftdown */ while ( hix < heapsize) { min = heap[hix].hval; which = hix; lchild = hix*2; if (lchild <= heapsize && heap[lchild].hval < min ) { min = heap[lchild].hval; which = lchild; } rchild = hix*2 + 1; if (rchild <= heapsize && heap[rchild].hval < min) { min = heap[rchild].hval; which = rchild; } if (which == hix) break; else { /* swap */ tmp = heap[hix]; heap[hix] = heap[ which ]; hloc[ heap[hix].hid] = hix; heap[ which ] = tmp; hloc[ heap[which].hid ] = which; hix = which; } }/* while */ #ifdef HEAP printf("\n heap after siftdown (size %d) to %d \n" , heapsize, hix); for (i= 1; i <= heapsize; i++) printf("%d %d %d %lf \n", i , hloc[heap[i].hid], heap[i].hid, heap[i].hval); printf("*\n"); fflush(stdout); #endif return heaptop; } /* extractmin */ /*---siftup from position hix ------------------------------------*/ void siftup (int hix) { heaptype tmp ; #ifdef HEAP int i; printf("before siftup from location %d \n", hix); for (i = 1; i <= heapsize; i++) printf("\t %d %d %d %lf \n", i, hloc[heap[i].hid], heap[i].hid, heap[i].hval); #endif while (hix > 1) { int parent = hix/2; if ( heap[hix].hval < heap[ parent ].hval ) { tmp = heap[hix]; heap[hix] = heap[parent]; heap[parent] = tmp; hloc[ heap[hix].hid ] = hix; hloc[ heap[parent].hid] = parent; hix = parent; } else break; }/*while*/ #ifdef HEAP printf("after siftup to location %d \n", hix); for (i = 1; i <= heapsize; i++) printf("\t %d %d %d %lf \n", i, hloc[heap[i].hid], heap[i].hid, heap[i].hval); #endif } /*---heapinsert------------------------------------------------*/ void heapinsert( int nodename, double dist ) { heapsize++; heap[heapsize].hid = nodename; heap[heapsize].hval = dist; hloc[ nodename ] = heapsize; siftup( heapsize); #ifdef DEBUG_H printf("\n hinsert %d %lf hsize %d \n", nodename, dist, heapsize); #endif } /* insert new into heap */ /* -heapgetinx--------------------return index for query, update */ int heapgetinx (int node) { return hloc[node]; } /*-heapgetdist----------------return distance for comparison */ double heapgetdist( int inx) { return heap[ inx ].hval; } /*heapdecreasekey-----------------------------------------------*/ void heapdecreasekey( int inx, double newval) { heap[ inx ].hval = newval; siftup (inx); } int queue[MAXNODES]; // bfs queue double qdist[MAXNODES]; //bfs queue int qstat[MAXNODES]; // status in queue or not double ubdiam; /*-----bfs-------------------------------------------------------*/ /*---------------------------------------------------------------*/ double bfs (int s, int d, double ecost, int rule) { // search from s to d in the graph, using BFS. // 1. up to limit ecost, or INFTY, filling in dmatrix for s. // 2. up to finding d, filling in dmatrix for s. // 3. up to component size, filling in dmatrix for row s. Return distance to d if found. if < nodes, diam ub is infty; or ub is twice max distance. int inqueue = 1; int outqueue = 0 ; int i; for (i = 1; i <= nodes; i++) qstat[i] = outqueue; queue[0] = s; qdist[0] = 0.0; qstat[s] = inqueue; int qfront = 0; // inv: location of first item in q int qback = 1; // inv: next item goes here int curnode; double curdist; double maxdist = 0.0; double sddist = INFTY; // default incase not found // ubdiam = INFTY; // default incase not connected int nodecount = 0; #ifdef DEBUGBFS printf("bfs %d %d %lf %lf \n" , s, d, ecost, ubdiam); #endif while ( qfront < qback ) { /* while not empty */ // inv: heap is in q[qfront .. qback-1] curnode = queue[qfront]; // dequeue curdist = qdist[qfront]; qfront++; nodecount++; #ifdef DEBUGBFS printf("\t dm %d %d %lf %lf \n", s, curnode, dmatrix[s][curnode], curdist); #endif // update dmatrix if ((dmatrix[s][curnode] == INFTY) || (dmatrix[s][curnode] > curdist)) { //every distance found is an ub on true distance-- make it better dmatrix[s][curnode] = curdist; dmatrix[curnode][s] = curdist; } if (curnode == d) { // found it sddist = curdist; if (rule == 2) return sddist; } if (curdist > ecost) { if (rule == 1) return curdist; // dist will be bigger than ecost (non-essential). Return curdist. } edgetype *nptr; int ename; double edist; /* for each neighbor e of curnode: add distance and put in queue*/ nptr = nodelist[curnode].first; while (nptr != NULL) { ename = nptr->dest; edist = curdist + nptr->cst; if (edist > maxdist) maxdist = edist; // longest distance s to any x. if ( qstat[ename] == outqueue ) { // ename not in queu already queue[qback] = ename; qdist[qback]=edist; qback++; qstat[ename] = inqueue; } nptr = nptr -> next; }/* for each neighbor */ }// while qnot eempty // queue is empty, and we haven't returned yet. Either not connected to d, or rule 3 applies. // either way sdist is correct finite (if found) or infinite if not found if (nodecount >= nodes-1) { if (2*maxdist < ubdiam) ubdiam = 2*maxdist; } #ifdef DEBUGBFS printf("\t diam %lf \n", ubdiam); #endif return sddist; }// bfs /*--------------------------------------------------------------------------*/ /* Essential Subgraph distance calculation, insert, init */ /*--------------------------------------------------------------------------*/ int diamcheck[MAXNODES]; int bfsworks = 0; /*-----distance: search from s to d in E, return distance or infty */ /* */ double distance(int s,int d, double ecost, int ssize ) { edgetype *nptr; int ename; double edist; double curdist; int unseen = 0; int inheap = 1; int seen = 2; int status[MAXNODES]; /* For shortest-path search */ /*V1: memoization*/ if ((dmatrix[s][d] != INFTY) && (dmatrix[s][d] < ecost)) return dmatrix[s][d]; double sddist = INFTY; if (ssize >= nodes-1) { // if connected, bfs to find a ub on diameter, and a guess for sdist if (diamcheck[s] == 0) { // havent yet checked diameter for s diamcheck[s] = 1; sddist = bfs ( s, d, ecost, 3); // return ub on d, also go to component and figure out ubdist if ((sddist == INFTY) || (sddist <= ecost)) bfsworks ++; if (sddist == INFTY ) return INFTY; // its essential if (sddist <= ecost) return sddist; // its non-essential }// } // if // if the sddist is INFINTY the edge is essential. No Dijkstra search. // else ssdist is finite. // if the ub sddist is less than or equal to ecost, the edge is non-essential. // No dijkstra search. // (rule 3) continue on to check the diameter. // all distances found are ubs on final distance s to d: // all distances found x via s to y are ubs on final distance: // If diameter ub is non-infinity, and less than ecost, the program is done. // // Dijkstra search, using ecost to filter. /* begin dijkstra search */ int i; for (i = 1; i <= nodes; i++) { status[i] = unseen; } status[s] = inheap; /* initalize heap to source vertex */ heapinit (s); heaptype x; while ( heapsize != 0 ) { x = heapextract(); /* V1: distance matrix */ dmatrix[s][x.hid] = x.hval; dmatrix[x.hid][s] = x.hval; if (x.hid == d) return x.hval; /* found it */ /* V2: abort the loop if this lb on distance to w is too big */ /* V2 is faster if this tuneup is not used */ // if (x.hval > ecost) return x.hval; status[x.hid] = seen; curdist = x.hval; /* for each neighbor e of x*/ nptr = nodelist[x.hid].first; while (nptr != NULL) { ename = nptr->dest; edist = curdist + nptr->cst; /* V2: filter the data structure */ if ( edist > ecost ); /* skip it */ else if (status[ename] == unseen) { heapinsert( ename, edist) ; status[ename] = inheap; } else if (status[ename]==inheap) { int heapx = heapgetinx(ename); if (edist < heapgetdist( heapx ) ) { heapdecreasekey (heapx, edist) ; } }/* else status = seen */ nptr = nptr -> next; }/* for each neaighbor */ }/* while heapsize */ return INFTY; /* didn't find d reachible from s */ }/*distance */ /*-------------insert---------------------------------------*/ void insert(int v, int w, double cost) { edgetype *newedge; edgetype *lptr; #ifdef DEBUGINS printf("\t\t subgrinsert %d %d %lf\n", v, w, cost); fflush(stdout); #endif /* insert edge in v list */ newedge = (edgetype *) malloc( sizeof( edgetype ) ); newedge->dest = w; newedge->cst = cost; newedge->next = NULL; if (nodelist[v].first == NULL) { nodelist[v].first = newedge; } else{ lptr = nodelist[v].last; lptr->next = newedge; } nodelist[v].last = newedge; /* insert in w list */ newedge = (edgetype *) malloc( sizeof( edgetype ) ); newedge->dest = v; newedge->cst = cost; newedge->next = NULL; if (nodelist[w].first == NULL) { nodelist[w].first = newedge; } else{ lptr = nodelist[w].last; lptr->next = newedge; } nodelist[w].last = newedge; }/*insert*/ /*-------------------------------------------------------------*/ /* Generation of random edges and costs */ /*-------------------------------------------------------------*/ /*------------------mydrand-------------------------------------*/ double mydrand() { return(drand48()); /* Reals on (0.0, 1.0]*/ } /*--------------- nextedge------------------------------------*/ /* Return the next edge, v, w, cost */ void nextedge( int* v, int* w, double* cost) { gedgetype tmp = edgeset[edgeindex++]; *v = tmp.vv; *w = tmp.ww; *cost = tmp.cost; } /*--dcompare-----------------------------------*/ /* for qsort */ int dcompare( const void *a, const void *b) { gedgetype *aa = (gedgetype* ) a; gedgetype *bb = (gedgetype* ) b; if ( aa->cost < bb->cost ) return -1; else if (aa-> cost > bb->cost ) return +1; else return 0; } /*-----------------graphinit-------------------------------------------------------*/ /* S: initialize nodes (nodelist with edgeset empty */ /* S is an adjacency list, with edges doubled */ /* G: is a list of random edges, in random vertex order */ /* The graph is undirected, nodes numbered 1..nodes, in array [1..nodes] */ /* There is one copy of each edge, oriented to indices (vv=lo, ww = hi) */ /* Sorted by edge cost */ void graphinit() { int i, j, k; /* initialize node pointers for the subgraph E */ totedges = nodes * (nodes-1) / 2; for (i=1; i<= nodes; i++) { nodelist[i].first = NULL; nodelist[i].last = NULL; } /* initialize edges in the random input graph */ k=0; for (i=1; i<= nodes-1 ; i++) { for (j=i+1; j<= nodes; j++) { edgeset[k].vv= i; edgeset[k].ww = j; edgeset[k].cost = mydrand(); /* random uniform 0..1 */ k++; } } /* sort the edges by cost */ qsort (edgeset, totedges, sizeof(gedgetype), dcompare); edgeindex = 0; /* first edge returned*/ #ifdef DEBUGSRT for (i = 0; i < totedges; i++) printf("%d \t %d \t %d \t %lf \n", i,edgeset[i].vv, edgeset[i].ww, edgeset[i].cost); fflush(stdout); #endif }/*graphinit*/ /*---printsg for output */ void printsg() { edgetype *nptr; int ename; double ecost; int i; int ctr; /* The subgraph */ for (i = 1; i <= nodes; i++) { printf("Node %d: \n ", i ); ctr = 0; nptr = nodelist[i].first; while (nptr != NULL ) { ename = nptr->dest; ecost = nptr->cst; printf("(%d %lf) \t", ename, ecost); nptr = nptr->next; if (ctr % 10 == 0) printf("\n"); } printf("\n"); } } /*---freesg for new trial */ void freesg() { edgetype *nptr; int i; edgetype *nextedge; /* The free subgraph */ for (i = 1; i <= nodes; i++) { nptr = nodelist[i].first; while (nptr != NULL ) { nextedge = nptr->next; free (nptr); nptr = nextedge; } nodelist[i].first = NULL; nodelist[i].last = NULL; } } /* V1: initialize the distance matrix */ void dminit() { int i, j; for (i = 1; i <= nodes; i++) diamcheck[i] = 0; for (i = 1; i <= nodes; i++) for (j= 1; j <= nodes; j++) dmatrix[i][j] = INFTY; } /*----------------------------------------------*/ /*---------------------main---------------------*/ int main(int argc, char** argv) { int DONE; double ecost; int v,w; int tr; double limit = 1.1; double lastcost = 1.1; int lastrank = totedges; int insertcount = 0; double mindist; tabinit(); transinput(); /* get input commands */ #ifdef DEBUG printf("input %d %d %d\n", nodes, trials, seed); fflush(stdout); #endif for( tr= 0 ; tr< trials; tr++) { graphinit(); /* generate random graph, initialize subgraph */ /* V1: initialize the distance matrix*/ dminit(); ubdiam = INFTY; limit = 1.1; /* larger than any edge size */ edgecount=0; /* num generated: incremented in nextedge */ insertcount = 0; /* num in subgraph */ lastcost = 0; /* last edge in graph */ lastrank = 0; /* rank of last edge in graph */ curmax = 1.0; /* modified in nextcost */ DONE = FALSE; while (!DONE) { /* generate the subgraph */ nextedge(&v, &w, &ecost); edgecount++; mindist = distance(v,w, ecost, insertcount); #ifdef DEBUG printf("edge %d : (%d %d %lf) dist %lf ", edgecount, v,w,ecost, mindist); if (mindist == INFTY) printf("ins \n"); else if (mindist > ecost) printf("ins \n"); else printf("out \n"); fflush(stdout); #endif if ( (mindist == INFTY)|| (mindist > ecost)) { insert(v,w,ecost); insertcount++; lastcost = ecost; lastrank = edgecount; } if (ubdiam != INFTY) limit = ubdiam; if (ecost > limit) DONE = TRUE; if (edgecount >= totedges) DONE = TRUE; }/*while still checking edges*/ #ifdef SEEOUTPUT printsg(); fflush(stdout); #endif // printf("bfs works %d ubdiam %lf\n", bfsworks, ubdiam); bfsworks =0; ubdiam= INFTY; printf("%d %d %d %d %lf %d %lf\n", tr, nodes, totedges, insertcount, lastcost, lastrank, limit); freesg(); }/*for each trial */ return 0; }/* main */