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,
561 assert(tcliquegraph !=
NULL);
562 assert(scaleval > 0.0);
565 if( (file = fopen(filename,
"r")) ==
NULL )
567 if( (file = fopen(
"default.dat",
"r")) ==
NULL )
581 charresult = fgets(probname, sizeofprobname, file);
582 if( charresult ==
NULL )
584 infoMessage(
"Error while reading probname in file %s", filename);
593 infoMessage(
"[%s:%d] No memory in function call", __FILE__, __LINE__);
599 probname[sizeofprobname-1] =
'\0';
600 tmp[sizeofprobname] =
'\0';
603 while( (
int) strlen(tmp) == sizeofprobname && tmp[strlen(tmp)-1] !=
'\n' )
605 charresult = fgets(tmp, sizeofprobname, file);
607 if( charresult ==
NULL )
609 infoMessage(
"Error while reading probname in file %s", filename);
620 result = fscanf(file,
"%d", &(*tcliquegraph)->nnodes);
623 infoMessage(
"Error while reading number of nodes in file %s", filename);
629 result = fscanf(file,
"%d", &(*tcliquegraph)->nedges);
632 infoMessage(
"Error while reading number of edges in file %s", filename);
637 if( (*tcliquegraph)->nnodes < 0 || (*tcliquegraph)->nedges < 0 )
639 infoMessage(
"\nInvalid number of %s (%d) in file: %s", (*tcliquegraph)->nnodes < 0 ?
"nodes" :
"edges",
640 (*tcliquegraph)->nnodes < 0 ? (*tcliquegraph)->nnodes : (*tcliquegraph)->nedges, filename);
649 infoMessage(
"Run out of memory while reading file %s", filename);
656 infoMessage(
"Run out of memory while reading file %s", filename);
663 infoMessage(
"Run out of memory while reading file %s", filename);
670 infoMessage(
"Run out of memory while reading file %s", filename);
676 for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
678 result = fscanf(file,
"%lf", &weight);
681 infoMessage(
"Error while reading weights of nodes in file %s", filename);
686 (*tcliquegraph)->weights[i] = (
TCLIQUE_WEIGHT)(weight * scaleval);
687 assert((*tcliquegraph)->weights[i] >= 0);
692 for( i = 0; i < (*tcliquegraph)->nedges; i++ )
696 result = fscanf(file,
"%d%d", &node1, &node2);
699 infoMessage(
"Error while reading edges in file %s", filename);
704 if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
706 infoMessage(
"\nInvalid node index (%d) in file: %s", node1 < 0 ? node1 : node2, filename);
712 if( node1 != currentnode )
716 (*tcliquegraph)->degrees[currentnode] = 0;
717 (*tcliquegraph)->adjedges[currentnode].first = i;
718 (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
720 (*tcliquegraph)->degrees[currentnode]++;
721 (*tcliquegraph)->adjnodes[i] = node2;
722 (*tcliquegraph)->adjedges[currentnode].last++;
734 const char* filename,
743 assert(tcliquegraph !=
NULL);
744 assert(scaleval > 0.0);
747 if( (file = fopen(filename,
"w")) ==
NULL )
754 fprintf(file,
"%s\n", probname);
755 fprintf(file,
"%d\n", tcliquegraph->nnodes);
756 fprintf(file,
"%d\n", tcliquegraph->nedges);
759 for( i = 0; i < tcliquegraph->nnodes; i++ )
760 fprintf(file,
"%f\n", (
double)tcliquegraph->weights[i]/scaleval);
763 for( i = 0; i < tcliquegraph->nnodes; i++ )
765 for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
766 fprintf(file,
"%d %d\n", i, tcliquegraph->adjnodes[j]);
780 assert(tcliquegraph !=
NULL);
782 return tcliquegraph->nedges + tcliquegraph->ncachededges;
790 assert(tcliquegraph !=
NULL);
791 assert(tcliquegraph->ncachededges == 0);
793 return tcliquegraph->degrees;
801 assert(tcliquegraph !=
NULL);
802 assert(tcliquegraph->ncachededges == 0);
804 return tcliquegraph->adjnodes;
816 assert(tcliquegraph !=
NULL);
817 assert(tcliquegraph->ncachededges == 0);
818 assert(0 <= node && node < tcliquegraph->
nnodes);
820 adjedges = tcliquegraph->adjedges;
821 assert(adjedges !=
NULL);
822 assert(adjedges[node].first >= 0);
826 assert(adjnodes !=
NULL);
828 return &adjnodes[adjedges[node].first];
843 assert(tcliquegraph !=
NULL);
844 assert(tcliquegraph->ncachededges == 0);
845 assert(0 <= node && node < tcliquegraph->
nnodes);
847 adjedges = tcliquegraph->adjedges;
851 assert(adjedges !=
NULL);
852 assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
855 assert(adjedges[node].last - adjedges[node].first == degrees[node]);
858 assert(adjnodes !=
NULL);
860 return &adjnodes[adjedges[node].last-1];
872 assert(tcliquegraph !=
NULL);
873 assert(tcliquegraph->ncachededges == 0);
876 weights = tcliqueGetWeights(tcliquegraph);
879 for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
884 infoMessage(
"node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
888 assert(lastadjedge + 1 - currentadjedge == degrees[i]);
890 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)
#define BMScopyMemoryArray(ptr, source, num)
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