35 typedef struct _HEAD_ADJ
68 assert(tcliquegraph !=
NULL);
70 return tcliquegraph->nnodes;
76 assert(tcliquegraph !=
NULL);
78 return tcliquegraph->weights;
88 assert(tcliquegraph !=
NULL);
89 assert(tcliquegraph->ncachededges == 0);
90 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
91 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
103 if( currentadjedge > lastadjedge || *lastadjedge < node2 )
108 while( currentadjedge <= lastadjedge )
110 if( *currentadjedge >= node2 )
112 if( *currentadjedge == node2 )
132 assert(tcliquegraph !=
NULL);
133 assert(tcliquegraph->ncachededges == 0);
134 assert(0 <= node && node < tcliquegraph->
nnodes);
135 assert(nnodes == 0 || nodes !=
NULL);
136 assert(adjnodes !=
NULL);
145 for( i = 0; i <
nnodes; i++ )
147 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
148 assert(i == 0 || nodes[i-1] < nodes[i]);
149 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
151 if( *currentadjedge >= nodes[i] )
154 if( *currentadjedge == nodes[i] )
156 adjnodes[nadjnodes] = nodes[i];
179 assert(tcliquegraph !=
NULL);
183 (*tcliquegraph)->nnodes = 0;
184 (*tcliquegraph)->nedges = 0;
185 (*tcliquegraph)->weights =
NULL;
186 (*tcliquegraph)->degrees =
NULL;
187 (*tcliquegraph)->adjnodes =
NULL;
188 (*tcliquegraph)->adjedges =
NULL;
189 (*tcliquegraph)->sizenodes = 0;
190 (*tcliquegraph)->sizeedges = 0;
191 (*tcliquegraph)->cacheddegrees =
NULL;
192 (*tcliquegraph)->cachedorigs =
NULL;
193 (*tcliquegraph)->cacheddests =
NULL;
194 (*tcliquegraph)->ncachededges = 0;
195 (*tcliquegraph)->sizecachededges = 0;
205 assert(tcliquegraph !=
NULL);
207 if( *tcliquegraph !=
NULL )
209 if ( (*tcliquegraph)->adjedges !=
NULL )
216 if ( (*tcliquegraph)->cacheddegrees )
233 assert(tcliquegraph !=
NULL);
235 if( num > tcliquegraph->sizeedges )
239 newsize = 2*tcliquegraph->sizeedges;
244 tcliquegraph->sizeedges = newsize;
247 assert(num <= tcliquegraph->sizeedges);
259 assert(tcliquegraph !=
NULL);
261 if( num > tcliquegraph->sizecachededges )
265 newsize = 2*tcliquegraph->sizecachededges;
271 tcliquegraph->sizecachededges = newsize;
274 assert(num <= tcliquegraph->sizecachededges);
286 assert(tcliquegraph !=
NULL);
290 assert(tcliquegraph->adjnodes !=
NULL);
292 if( num > tcliquegraph->sizenodes )
297 newsize = 2*tcliquegraph->sizenodes;
305 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
307 tcliquegraph->weights[i] = 0;
308 tcliquegraph->degrees[i] = 0;
309 tcliquegraph->adjedges[i].first = tcliquegraph->nedges;
310 tcliquegraph->adjedges[i].last = tcliquegraph->nedges;
313 if( tcliquegraph->ncachededges > 0 )
315 assert(tcliquegraph->cacheddegrees !=
NULL);
317 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
318 tcliquegraph->cacheddegrees[i] = 0;
321 tcliquegraph->sizenodes = newsize;
323 assert(num <= tcliquegraph->sizenodes);
341 tcliquegraph->weights[node] = weight;
343 assert(tcliquegraph->degrees[node] == 0);
344 assert(tcliquegraph->adjedges[node].first <= tcliquegraph->nedges);
345 assert(tcliquegraph->adjedges[node].last == tcliquegraph->adjedges[node].first);
346 tcliquegraph->nnodes =
MAX(tcliquegraph->nnodes, node+1);
358 assert(0 <= node && node < tcliqueGetNNodes(tcliquegraph));
361 tcliquegraph->weights[node] = weight;
376 assert(tcliquegraph !=
NULL);
377 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
378 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
379 assert(node1 != node2);
385 if( tcliquegraph->ncachededges == 0 && tcliquegraph->sizenodes > 0 )
387 assert(tcliquegraph->cacheddegrees ==
NULL);
391 assert(tcliquegraph->cacheddegrees !=
NULL);
394 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node1;
395 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node2;
396 tcliquegraph->ncachededges++;
397 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node2;
398 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node1;
399 tcliquegraph->ncachededges++;
400 tcliquegraph->cacheddegrees[node1]++;
401 tcliquegraph->cacheddegrees[node2]++;
411 assert(tcliquegraph !=
NULL);
414 if( tcliquegraph->ncachededges > 0 )
424 assert(tcliquegraph->adjnodes !=
NULL);
425 assert(tcliquegraph->adjedges !=
NULL);
429 pos = tcliquegraph->nedges + tcliquegraph->ncachededges - 1;
430 for( n = tcliquegraph->nnodes-1; ; --n )
435 assert(tcliquegraph->adjedges[n].last - tcliquegraph->adjedges[n].first == tcliquegraph->degrees[n]);
438 olddegree = tcliquegraph->degrees[n];
439 tcliquegraph->degrees[n] += tcliquegraph->cacheddegrees[n];
442 pos -= tcliquegraph->cacheddegrees[n];
443 ninsertedholes += tcliquegraph->cacheddegrees[n];
444 assert(ninsertedholes <= tcliquegraph->ncachededges);
445 if( ninsertedholes == tcliquegraph->ncachededges )
450 for( i = tcliquegraph->adjedges[n].last - 1; i >= tcliquegraph->adjedges[n].first; --i, --pos )
452 assert(0 <= i && i < pos && pos < tcliquegraph->nedges + tcliquegraph->ncachededges);
453 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[i];
457 tcliquegraph->adjedges[n].first = pos+1;
458 tcliquegraph->adjedges[n].last = pos+1 + olddegree;
460 assert(n == tcliquegraph->nnodes-1
461 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
463 assert(ninsertedholes == tcliquegraph->ncachededges);
464 assert(tcliquegraph->adjedges[n].last == pos+1);
466 for( --n; n >= 0; --n )
467 assert(tcliquegraph->cacheddegrees[n] == 0);
471 for( i = 0; i < tcliquegraph->ncachededges; ++i )
475 n = tcliquegraph->cachedorigs[i];
476 dest = tcliquegraph->cacheddests[i];
477 assert(0 <= n && n < tcliquegraph->
nnodes);
478 assert(0 <= dest && dest < tcliquegraph->nnodes);
479 assert(tcliquegraph->adjedges[n].last <= tcliquegraph->nedges + tcliquegraph->ncachededges);
480 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
481 assert(n == tcliquegraph->nnodes-1
482 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
485 for( pos = tcliquegraph->adjedges[n].last;
486 pos > tcliquegraph->adjedges[n].first && dest < tcliquegraph->adjnodes[pos-1]; --pos )
488 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
490 tcliquegraph->adjnodes[pos] = dest;
491 tcliquegraph->adjedges[n].last++;
493 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
497 tcliquegraph->nedges += tcliquegraph->ncachededges;
503 tcliquegraph->ncachededges = 0;
504 tcliquegraph->sizecachededges = 0;
508 assert(tcliquegraph->ncachededges == 0);
509 assert(tcliquegraph->sizecachededges == 0);
510 assert(tcliquegraph->cacheddegrees ==
NULL);
511 assert(tcliquegraph->cachedorigs ==
NULL);
512 assert(tcliquegraph->cacheddests ==
NULL);
521 for( n = 0; n < tcliquegraph->nnodes; ++n )
525 assert(tcliquegraph->adjedges[n].first == pos);
526 assert(tcliquegraph->adjedges[n].last == tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n]);
528 for( i = tcliquegraph->adjedges[n].first; i < tcliquegraph->adjedges[n].last-1; ++i )
530 assert(tcliquegraph->adjnodes[i] < tcliquegraph->adjnodes[i+1]);
532 pos = tcliquegraph->adjedges[n].last;
534 assert(pos == tcliquegraph->nedges);
544 const char* filename,
560 assert(tcliquegraph !=
NULL);
561 assert(scaleval > 0.0);
564 if( (file = fopen(filename,
"r")) ==
NULL )
566 if( (file = fopen(
"default.dat",
"r")) ==
NULL )
580 charresult = fgets(probname, sizeofprobname, file);
581 if( charresult ==
NULL )
583 infoMessage(
"Error while reading probname in file %s", filename);
592 infoMessage(
"[%s:%d] No memory in function call", __FILE__, __LINE__);
598 probname[sizeofprobname-1] =
'\0';
599 tmp[sizeofprobname] =
'\0';
602 while( (
int) strlen(tmp) == sizeofprobname && tmp[strlen(tmp)-1] !=
'\n' )
604 charresult = fgets(tmp, sizeofprobname, file);
606 if( charresult ==
NULL )
608 infoMessage(
"Error while reading probname in file %s", filename);
619 result = fscanf(file,
"%d", &(*tcliquegraph)->nnodes);
622 infoMessage(
"Error while reading number of nodes in file %s", filename);
628 result = fscanf(file,
"%d", &(*tcliquegraph)->nedges);
631 infoMessage(
"Error while reading number of edges in file %s", filename);
636 if( (*tcliquegraph)->nnodes < 0 || (*tcliquegraph)->nedges < 0 )
638 infoMessage(
"\nInvalid number of %s (%d) in file: %s", (*tcliquegraph)->nnodes < 0 ?
"nodes" :
"edges",
639 (*tcliquegraph)->nnodes < 0 ? (*tcliquegraph)->nnodes : (*tcliquegraph)->nedges, filename);
648 infoMessage(
"Run out of memory while reading file %s", filename);
655 infoMessage(
"Run out of memory while reading file %s", filename);
662 infoMessage(
"Run out of memory while reading file %s", filename);
669 infoMessage(
"Run out of memory while reading file %s", filename);
675 for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
677 result = fscanf(file,
"%lf", &weight);
680 infoMessage(
"Error while reading weights of nodes in file %s", filename);
685 (*tcliquegraph)->weights[i] = (
TCLIQUE_WEIGHT)(weight * scaleval);
686 assert((*tcliquegraph)->weights[i] >= 0);
691 for( i = 0; i < (*tcliquegraph)->nedges; i++ )
695 result = fscanf(file,
"%d%d", &node1, &node2);
698 infoMessage(
"Error while reading edges in file %s", filename);
703 if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
705 infoMessage(
"\nInvalid node index (%d) in file: %s", node1 < 0 ? node1 : node2, filename);
711 if( node1 != currentnode )
715 (*tcliquegraph)->degrees[currentnode] = 0;
716 (*tcliquegraph)->adjedges[currentnode].first = i;
717 (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
719 (*tcliquegraph)->degrees[currentnode]++;
720 (*tcliquegraph)->adjnodes[i] = node2;
721 (*tcliquegraph)->adjedges[currentnode].last++;
733 const char* filename,
742 assert(tcliquegraph !=
NULL);
743 assert(scaleval > 0.0);
746 if( (file = fopen(filename,
"w")) ==
NULL )
753 fprintf(file,
"%s\n", probname);
754 fprintf(file,
"%d\n", tcliquegraph->nnodes);
755 fprintf(file,
"%d\n", tcliquegraph->nedges);
758 for( i = 0; i < tcliquegraph->nnodes; i++ )
759 fprintf(file,
"%f\n", (
double)tcliquegraph->weights[i]/scaleval);
762 for( i = 0; i < tcliquegraph->nnodes; i++ )
764 for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
765 fprintf(file,
"%d %d\n", i, tcliquegraph->adjnodes[j]);
779 assert(tcliquegraph !=
NULL);
781 return tcliquegraph->nedges + tcliquegraph->ncachededges;
789 assert(tcliquegraph !=
NULL);
790 assert(tcliquegraph->ncachededges == 0);
792 return tcliquegraph->degrees;
800 assert(tcliquegraph !=
NULL);
801 assert(tcliquegraph->ncachededges == 0);
803 return tcliquegraph->adjnodes;
815 assert(tcliquegraph !=
NULL);
816 assert(tcliquegraph->ncachededges == 0);
817 assert(0 <= node && node < tcliquegraph->
nnodes);
819 adjedges = tcliquegraph->adjedges;
820 assert(adjedges !=
NULL);
821 assert(adjedges[node].first >= 0);
825 assert(adjnodes !=
NULL);
827 return &adjnodes[adjedges[node].first];
842 assert(tcliquegraph !=
NULL);
843 assert(tcliquegraph->ncachededges == 0);
844 assert(0 <= node && node < tcliquegraph->
nnodes);
846 adjedges = tcliquegraph->adjedges;
850 assert(adjedges !=
NULL);
851 assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
854 assert(adjedges[node].last - adjedges[node].first == degrees[node]);
857 assert(adjnodes !=
NULL);
859 return &adjnodes[adjedges[node].last-1];
871 assert(tcliquegraph !=
NULL);
872 assert(tcliquegraph->ncachededges == 0);
875 weights = tcliqueGetWeights(tcliquegraph);
878 for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
883 infoMessage(
"node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
887 assert(lastadjedge + 1 - currentadjedge == degrees[i]);
889 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