36 typedef struct _HEAD_ADJ
69 assert(tcliquegraph !=
NULL);
71 return tcliquegraph->nnodes;
77 assert(tcliquegraph !=
NULL);
79 return tcliquegraph->weights;
89 assert(tcliquegraph !=
NULL);
90 assert(tcliquegraph->ncachededges == 0);
91 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
92 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
104 if( currentadjedge > lastadjedge || *lastadjedge < node2 )
109 while( currentadjedge <= lastadjedge )
111 if( *currentadjedge >= node2 )
113 if( *currentadjedge == node2 )
133 assert(tcliquegraph !=
NULL);
134 assert(tcliquegraph->ncachededges == 0);
135 assert(0 <= node && node < tcliquegraph->
nnodes);
136 assert(nnodes == 0 || nodes !=
NULL);
137 assert(adjnodes !=
NULL);
146 for( i = 0; i <
nnodes; i++ )
148 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
149 assert(i == 0 || nodes[i-1] < nodes[i]);
150 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
152 if( *currentadjedge >= nodes[i] )
155 if( *currentadjedge == nodes[i] )
157 adjnodes[nadjnodes] = nodes[i];
180 assert(tcliquegraph !=
NULL);
184 (*tcliquegraph)->nnodes = 0;
185 (*tcliquegraph)->nedges = 0;
186 (*tcliquegraph)->weights =
NULL;
187 (*tcliquegraph)->degrees =
NULL;
188 (*tcliquegraph)->adjnodes =
NULL;
189 (*tcliquegraph)->adjedges =
NULL;
190 (*tcliquegraph)->sizenodes = 0;
191 (*tcliquegraph)->sizeedges = 0;
192 (*tcliquegraph)->cacheddegrees =
NULL;
193 (*tcliquegraph)->cachedorigs =
NULL;
194 (*tcliquegraph)->cacheddests =
NULL;
195 (*tcliquegraph)->ncachededges = 0;
196 (*tcliquegraph)->sizecachededges = 0;
206 assert(tcliquegraph !=
NULL);
208 if( *tcliquegraph !=
NULL )
210 if ( (*tcliquegraph)->adjedges !=
NULL )
217 if ( (*tcliquegraph)->cacheddegrees )
234 assert(tcliquegraph !=
NULL);
236 if( num > tcliquegraph->sizeedges )
240 newsize = 2*tcliquegraph->sizeedges;
245 tcliquegraph->sizeedges = newsize;
248 assert(num <= tcliquegraph->sizeedges);
260 assert(tcliquegraph !=
NULL);
262 if( num > tcliquegraph->sizecachededges )
266 newsize = 2*tcliquegraph->sizecachededges;
272 tcliquegraph->sizecachededges = newsize;
275 assert(num <= tcliquegraph->sizecachededges);
287 assert(tcliquegraph !=
NULL);
291 assert(tcliquegraph->adjnodes !=
NULL);
293 if( num > tcliquegraph->sizenodes )
298 newsize = 2*tcliquegraph->sizenodes;
306 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
308 tcliquegraph->weights[i] = 0;
309 tcliquegraph->degrees[i] = 0;
310 tcliquegraph->adjedges[i].first = tcliquegraph->nedges;
311 tcliquegraph->adjedges[i].last = tcliquegraph->nedges;
314 if( tcliquegraph->ncachededges > 0 )
316 assert(tcliquegraph->cacheddegrees !=
NULL);
318 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
319 tcliquegraph->cacheddegrees[i] = 0;
322 tcliquegraph->sizenodes = newsize;
324 assert(num <= tcliquegraph->sizenodes);
342 tcliquegraph->weights[node] = weight;
344 assert(tcliquegraph->degrees[node] == 0);
345 assert(tcliquegraph->adjedges[node].first <= tcliquegraph->nedges);
346 assert(tcliquegraph->adjedges[node].last == tcliquegraph->adjedges[node].first);
347 tcliquegraph->nnodes =
MAX(tcliquegraph->nnodes, node+1);
359 assert(0 <= node && node < tcliqueGetNNodes(tcliquegraph));
362 tcliquegraph->weights[node] = weight;
377 assert(tcliquegraph !=
NULL);
378 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
379 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
380 assert(node1 != node2);
386 if( tcliquegraph->ncachededges == 0 && tcliquegraph->sizenodes > 0 )
388 assert(tcliquegraph->cacheddegrees ==
NULL);
392 assert(tcliquegraph->cacheddegrees !=
NULL);
395 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node1;
396 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node2;
397 tcliquegraph->ncachededges++;
398 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node2;
399 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node1;
400 tcliquegraph->ncachededges++;
401 tcliquegraph->cacheddegrees[node1]++;
402 tcliquegraph->cacheddegrees[node2]++;
412 assert(tcliquegraph !=
NULL);
415 if( tcliquegraph->ncachededges > 0 )
425 assert(tcliquegraph->adjnodes !=
NULL);
426 assert(tcliquegraph->adjedges !=
NULL);
430 pos = tcliquegraph->nedges + tcliquegraph->ncachededges - 1;
431 for( n = tcliquegraph->nnodes-1; ; --n )
436 assert(tcliquegraph->adjedges[n].last - tcliquegraph->adjedges[n].first == tcliquegraph->degrees[n]);
439 olddegree = tcliquegraph->degrees[n];
440 tcliquegraph->degrees[n] += tcliquegraph->cacheddegrees[n];
443 pos -= tcliquegraph->cacheddegrees[n];
444 ninsertedholes += tcliquegraph->cacheddegrees[n];
445 assert(ninsertedholes <= tcliquegraph->ncachededges);
446 if( ninsertedholes == tcliquegraph->ncachededges )
451 for( i = tcliquegraph->adjedges[n].last - 1; i >= tcliquegraph->adjedges[n].first; --i, --pos )
453 assert(0 <= i && i < pos && pos < tcliquegraph->nedges + tcliquegraph->ncachededges);
454 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[i];
458 tcliquegraph->adjedges[n].first = pos+1;
459 tcliquegraph->adjedges[n].last = pos+1 + olddegree;
461 assert(n == tcliquegraph->nnodes-1
462 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
464 assert(ninsertedholes == tcliquegraph->ncachededges);
465 assert(tcliquegraph->adjedges[n].last == pos+1);
467 for( --n; n >= 0; --n )
468 assert(tcliquegraph->cacheddegrees[n] == 0);
472 for( i = 0; i < tcliquegraph->ncachededges; ++i )
476 n = tcliquegraph->cachedorigs[i];
477 dest = tcliquegraph->cacheddests[i];
478 assert(0 <= n && n < tcliquegraph->
nnodes);
479 assert(0 <= dest && dest < tcliquegraph->nnodes);
480 assert(tcliquegraph->adjedges[n].last <= tcliquegraph->nedges + tcliquegraph->ncachededges);
481 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
482 assert(n == tcliquegraph->nnodes-1
483 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
486 for( pos = tcliquegraph->adjedges[n].last;
487 pos > tcliquegraph->adjedges[n].first && dest < tcliquegraph->adjnodes[pos-1]; --pos )
489 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
491 tcliquegraph->adjnodes[pos] = dest;
492 tcliquegraph->adjedges[n].last++;
494 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
498 tcliquegraph->nedges += tcliquegraph->ncachededges;
504 tcliquegraph->ncachededges = 0;
505 tcliquegraph->sizecachededges = 0;
509 assert(tcliquegraph->ncachededges == 0);
510 assert(tcliquegraph->sizecachededges == 0);
511 assert(tcliquegraph->cacheddegrees ==
NULL);
512 assert(tcliquegraph->cachedorigs ==
NULL);
513 assert(tcliquegraph->cacheddests ==
NULL);
522 for( n = 0; n < tcliquegraph->nnodes; ++n )
526 assert(tcliquegraph->adjedges[n].first == pos);
527 assert(tcliquegraph->adjedges[n].last == tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n]);
529 for( i = tcliquegraph->adjedges[n].first; i < tcliquegraph->adjedges[n].last-1; ++i )
531 assert(tcliquegraph->adjnodes[i] < tcliquegraph->adjnodes[i+1]);
533 pos = tcliquegraph->adjedges[n].last;
535 assert(pos == tcliquegraph->nedges);
545 const char* filename,
560 assert(tcliquegraph !=
NULL);
561 assert(scaleval > 0.0);
562 assert(sizeofprobname >= 2);
565 if( (file = fopen(filename,
"r")) ==
NULL )
567 if( (file = fopen(
"default.dat",
"r")) ==
NULL )
583 probname[sizeofprobname-2] =
'\0';
584 charresult = fgets(probname, sizeofprobname, file);
585 if( charresult ==
NULL )
587 infoMessage(
"Error while reading probname in file %s.\n", filename);
592 while( probname[sizeofprobname-2] !=
'\0' );
596 result = fscanf(file,
"%d", &(*tcliquegraph)->nnodes);
599 infoMessage(
"Error while reading number of nodes in file %s.\n", filename);
604 if( (*tcliquegraph)->nnodes < 0 )
606 infoMessage(
"Invalid number of nodes (%d) in file: %s.\n", (*tcliquegraph)->nnodes, filename);
612 result = fscanf(file,
"%d", &(*tcliquegraph)->nedges);
615 infoMessage(
"Error while reading number of edges in file %s.\n", filename);
620 if( (*tcliquegraph)->nedges < 0 )
622 infoMessage(
"Invalid number of edges (%d) in file: %s.\n", (*tcliquegraph)->nedges, filename);
631 infoMessage(
"Run out of memory while reading file %s.\n", filename);
638 infoMessage(
"Run out of memory while reading file %s.\n", filename);
645 infoMessage(
"Run out of memory while reading file %s.\n", filename);
652 infoMessage(
"Run out of memory while reading file %s.\n", filename);
659 for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
661 result = fscanf(file,
"%lf", &weight);
664 infoMessage(
"Error while reading weights of nodes in file %s.\n", filename);
669 (*tcliquegraph)->weights[i] = (
TCLIQUE_WEIGHT)(weight * scaleval);
670 assert((*tcliquegraph)->weights[i] >= 0);
676 for( i = 0; i < (*tcliquegraph)->nedges; i++ )
680 result = fscanf(file,
"%d%d", &node1, &node2);
683 infoMessage(
"Error while reading edges in file %s.\n", filename);
688 if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
690 infoMessage(
"Invalid node index (%d) in file: %s.\n", node1 < 0 ? node1 : node2, filename);
696 if( node1 != currentnode )
700 (*tcliquegraph)->degrees[currentnode] = 0;
701 (*tcliquegraph)->adjedges[currentnode].first = i;
702 (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
704 (*tcliquegraph)->degrees[currentnode]++;
705 (*tcliquegraph)->adjnodes[i] = node2;
706 (*tcliquegraph)->adjedges[currentnode].last++;
718 const char* filename,
727 assert(tcliquegraph !=
NULL);
728 assert(scaleval > 0.0);
731 if( (file = fopen(filename,
"w")) ==
NULL )
738 fprintf(file,
"%s\n", probname);
739 fprintf(file,
"%d\n", tcliquegraph->nnodes);
740 fprintf(file,
"%d\n", tcliquegraph->nedges);
743 for( i = 0; i < tcliquegraph->nnodes; i++ )
744 fprintf(file,
"%f\n", (
double)tcliquegraph->weights[i]/scaleval);
747 for( i = 0; i < tcliquegraph->nnodes; i++ )
749 for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
750 fprintf(file,
"%d %d\n", i, tcliquegraph->adjnodes[j]);
764 assert(tcliquegraph !=
NULL);
766 return tcliquegraph->nedges + tcliquegraph->ncachededges;
774 assert(tcliquegraph !=
NULL);
775 assert(tcliquegraph->ncachededges == 0);
777 return tcliquegraph->degrees;
785 assert(tcliquegraph !=
NULL);
786 assert(tcliquegraph->ncachededges == 0);
788 return tcliquegraph->adjnodes;
800 assert(tcliquegraph !=
NULL);
801 assert(tcliquegraph->ncachededges == 0);
802 assert(0 <= node && node < tcliquegraph->
nnodes);
804 adjedges = tcliquegraph->adjedges;
805 assert(adjedges !=
NULL);
806 assert(adjedges[node].first >= 0);
810 assert(adjnodes !=
NULL);
812 return &adjnodes[adjedges[node].first];
827 assert(tcliquegraph !=
NULL);
828 assert(tcliquegraph->ncachededges == 0);
829 assert(0 <= node && node < tcliquegraph->
nnodes);
831 adjedges = tcliquegraph->adjedges;
835 assert(adjedges !=
NULL);
836 assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
839 assert(adjedges[node].last - adjedges[node].first == degrees[node]);
842 assert(adjnodes !=
NULL);
844 return &adjnodes[adjedges[node].last-1];
856 assert(tcliquegraph !=
NULL);
857 assert(tcliquegraph->ncachededges == 0);
860 weights = tcliqueGetWeights(tcliquegraph);
863 for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
868 infoMessage(
"node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
872 assert(lastadjedge + 1 - currentadjedge == degrees[i]);
874 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemoryArrayNull(ptr)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
static TCLIQUE_Bool tcliqueEnsureSizeNodes(TCLIQUE_GRAPH *tcliquegraph, int num)
struct TCLIQUE_Graph TCLIQUE_GRAPH
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_GETWEIGHTS(tcliqueGetWeights)
#define BMSallocMemoryArray(ptr, num)
static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemory(ptr)
struct _HEAD_ADJ HEAD_ADJ
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemoryArray(ptr)
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)
void tcliquePrintGraph(TCLIQUE_GRAPH *tcliquegraph)
TCLIQUE_Bool tcliqueLoadFile(TCLIQUE_GRAPH **tcliquegraph, const char *filename, double scaleval, char *probname, int sizeofprobname)
TCLIQUE_GETNNODES(tcliqueGetNNodes)
TCLIQUE_Bool tcliqueSaveFile(TCLIQUE_GRAPH *tcliquegraph, const char *filename, double scaleval, const char *probname)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
TCLIQUE_ISEDGE(tcliqueIsEdge)
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
#define BMSallocMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
int * tcliqueGetAdjnodes(TCLIQUE_GRAPH *tcliquegraph)
static TCLIQUE_Bool tcliqueEnsureSizeEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
#define BMSclearMemoryArray(ptr, num)
memory allocation routines