45 typedef struct _HEAD_ADJ
78 assert(tcliquegraph !=
NULL);
80 return tcliquegraph->nnodes;
86 assert(tcliquegraph !=
NULL);
88 return tcliquegraph->weights;
98 assert(tcliquegraph !=
NULL);
99 assert(tcliquegraph->ncachededges == 0);
100 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
101 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
113 if( currentadjedge > lastadjedge || *lastadjedge < node2 )
118 while( currentadjedge <= lastadjedge )
120 if( *currentadjedge >= node2 )
122 if( *currentadjedge == node2 )
142 assert(tcliquegraph !=
NULL);
143 assert(tcliquegraph->ncachededges == 0);
144 assert(0 <= node && node < tcliquegraph->
nnodes);
145 assert(nnodes == 0 || nodes !=
NULL);
146 assert(adjnodes !=
NULL);
155 for( i = 0; i <
nnodes; i++ )
157 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
158 assert(i == 0 || nodes[i-1] < nodes[i]);
159 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
161 if( *currentadjedge >= nodes[i] )
164 if( *currentadjedge == nodes[i] )
166 adjnodes[nadjnodes] = nodes[i];
189 assert(tcliquegraph !=
NULL);
193 (*tcliquegraph)->nnodes = 0;
194 (*tcliquegraph)->nedges = 0;
195 (*tcliquegraph)->weights =
NULL;
196 (*tcliquegraph)->degrees =
NULL;
197 (*tcliquegraph)->adjnodes =
NULL;
198 (*tcliquegraph)->adjedges =
NULL;
199 (*tcliquegraph)->sizenodes = 0;
200 (*tcliquegraph)->sizeedges = 0;
201 (*tcliquegraph)->cacheddegrees =
NULL;
202 (*tcliquegraph)->cachedorigs =
NULL;
203 (*tcliquegraph)->cacheddests =
NULL;
204 (*tcliquegraph)->ncachededges = 0;
205 (*tcliquegraph)->sizecachededges = 0;
215 assert(tcliquegraph !=
NULL);
217 if( *tcliquegraph !=
NULL )
219 if ( (*tcliquegraph)->adjedges !=
NULL )
226 if ( (*tcliquegraph)->cacheddegrees )
243 assert(tcliquegraph !=
NULL);
245 if( num > tcliquegraph->sizeedges )
249 newsize = 2*tcliquegraph->sizeedges;
254 tcliquegraph->sizeedges = newsize;
257 assert(num <= tcliquegraph->sizeedges);
269 assert(tcliquegraph !=
NULL);
271 if( num > tcliquegraph->sizecachededges )
275 newsize = 2*tcliquegraph->sizecachededges;
281 tcliquegraph->sizecachededges = newsize;
284 assert(num <= tcliquegraph->sizecachededges);
296 assert(tcliquegraph !=
NULL);
300 assert(tcliquegraph->adjnodes !=
NULL);
302 if( num > tcliquegraph->sizenodes )
307 newsize = 2*tcliquegraph->sizenodes;
315 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
317 tcliquegraph->weights[i] = 0;
318 tcliquegraph->degrees[i] = 0;
319 tcliquegraph->adjedges[i].first = tcliquegraph->nedges;
320 tcliquegraph->adjedges[i].last = tcliquegraph->nedges;
323 if( tcliquegraph->ncachededges > 0 )
325 assert(tcliquegraph->cacheddegrees !=
NULL);
327 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
328 tcliquegraph->cacheddegrees[i] = 0;
331 tcliquegraph->sizenodes = newsize;
333 assert(num <= tcliquegraph->sizenodes);
351 tcliquegraph->weights[node] = weight;
353 assert(tcliquegraph->degrees[node] == 0);
354 assert(tcliquegraph->adjedges[node].first <= tcliquegraph->nedges);
355 assert(tcliquegraph->adjedges[node].last == tcliquegraph->adjedges[node].first);
356 tcliquegraph->nnodes =
MAX(tcliquegraph->nnodes, node+1);
368 assert(0 <= node && node < tcliqueGetNNodes(tcliquegraph));
371 tcliquegraph->weights[node] = weight;
386 assert(tcliquegraph !=
NULL);
387 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
388 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
389 assert(node1 != node2);
395 if( tcliquegraph->ncachededges == 0 && tcliquegraph->sizenodes > 0 )
397 assert(tcliquegraph->cacheddegrees ==
NULL);
401 assert(tcliquegraph->cacheddegrees !=
NULL);
404 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node1;
405 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node2;
406 tcliquegraph->ncachededges++;
407 tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node2;
408 tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node1;
409 tcliquegraph->ncachededges++;
410 tcliquegraph->cacheddegrees[node1]++;
411 tcliquegraph->cacheddegrees[node2]++;
421 assert(tcliquegraph !=
NULL);
424 if( tcliquegraph->ncachededges > 0 )
434 assert(tcliquegraph->adjnodes !=
NULL);
435 assert(tcliquegraph->adjedges !=
NULL);
439 pos = tcliquegraph->nedges + tcliquegraph->ncachededges - 1;
440 for( n = tcliquegraph->nnodes-1; ; --n )
445 assert(tcliquegraph->adjedges[n].last - tcliquegraph->adjedges[n].first == tcliquegraph->degrees[n]);
448 olddegree = tcliquegraph->degrees[n];
449 tcliquegraph->degrees[n] += tcliquegraph->cacheddegrees[n];
452 pos -= tcliquegraph->cacheddegrees[n];
453 ninsertedholes += tcliquegraph->cacheddegrees[n];
454 assert(ninsertedholes <= tcliquegraph->ncachededges);
455 if( ninsertedholes == tcliquegraph->ncachededges )
460 for( i = tcliquegraph->adjedges[n].last - 1; i >= tcliquegraph->adjedges[n].first; --i, --pos )
462 assert(0 <= i && i < pos && pos < tcliquegraph->nedges + tcliquegraph->ncachededges);
463 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[i];
467 tcliquegraph->adjedges[n].first = pos+1;
468 tcliquegraph->adjedges[n].last = pos+1 + olddegree;
470 assert(n == tcliquegraph->nnodes-1
471 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
473 assert(ninsertedholes == tcliquegraph->ncachededges);
474 assert(tcliquegraph->adjedges[n].last == pos+1);
476 for( --n; n >= 0; --n )
477 assert(tcliquegraph->cacheddegrees[n] == 0);
481 for( i = 0; i < tcliquegraph->ncachededges; ++i )
485 n = tcliquegraph->cachedorigs[i];
486 dest = tcliquegraph->cacheddests[i];
487 assert(0 <= n && n < tcliquegraph->
nnodes);
488 assert(0 <= dest && dest < tcliquegraph->nnodes);
489 assert(tcliquegraph->adjedges[n].last <= tcliquegraph->nedges + tcliquegraph->ncachededges);
490 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
491 assert(n == tcliquegraph->nnodes-1
492 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
495 for( pos = tcliquegraph->adjedges[n].last;
496 pos > tcliquegraph->adjedges[n].first && dest < tcliquegraph->adjnodes[pos-1]; --pos )
498 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
500 tcliquegraph->adjnodes[pos] = dest;
501 tcliquegraph->adjedges[n].last++;
503 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
507 tcliquegraph->nedges += tcliquegraph->ncachededges;
513 tcliquegraph->ncachededges = 0;
514 tcliquegraph->sizecachededges = 0;
518 assert(tcliquegraph->ncachededges == 0);
519 assert(tcliquegraph->sizecachededges == 0);
520 assert(tcliquegraph->cacheddegrees ==
NULL);
521 assert(tcliquegraph->cachedorigs ==
NULL);
522 assert(tcliquegraph->cacheddests ==
NULL);
531 for( n = 0; n < tcliquegraph->nnodes; ++n )
535 assert(tcliquegraph->adjedges[n].first == pos);
536 assert(tcliquegraph->adjedges[n].last == tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n]);
538 for( i = tcliquegraph->adjedges[n].first; i < tcliquegraph->adjedges[n].last-1; ++i )
540 assert(tcliquegraph->adjnodes[i] < tcliquegraph->adjnodes[i+1]);
542 pos = tcliquegraph->adjedges[n].last;
544 assert(pos == tcliquegraph->nedges);
554 const char* filename,
569 assert(tcliquegraph !=
NULL);
570 assert(scaleval > 0.0);
571 assert(sizeofprobname >= 2);
574 if( (file = fopen(filename,
"r")) ==
NULL )
576 if( (file = fopen(
"default.dat",
"r")) ==
NULL )
592 probname[sizeofprobname-2] =
'\0';
593 charresult = fgets(probname, sizeofprobname, file);
594 if( charresult ==
NULL )
596 infoMessage(
"Error while reading probname in file %s.\n", filename);
601 while( probname[sizeofprobname-2] !=
'\0' );
605 result = fscanf(file,
"%d", &(*tcliquegraph)->nnodes);
608 infoMessage(
"Error while reading number of nodes in file %s.\n", filename);
613 if( (*tcliquegraph)->nnodes < 0 )
615 infoMessage(
"Invalid number of nodes (%d) in file: %s.\n", (*tcliquegraph)->nnodes, filename);
621 result = fscanf(file,
"%d", &(*tcliquegraph)->nedges);
624 infoMessage(
"Error while reading number of edges in file %s.\n", filename);
629 if( (*tcliquegraph)->nedges < 0 )
631 infoMessage(
"Invalid number of edges (%d) in file: %s.\n", (*tcliquegraph)->nedges, filename);
640 infoMessage(
"Run out of memory while reading file %s.\n", filename);
648 infoMessage(
"Run out of memory while reading file %s.\n", filename);
656 infoMessage(
"Run out of memory while reading file %s.\n", filename);
664 infoMessage(
"Run out of memory while reading file %s.\n", filename);
671 for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
673 result = fscanf(file,
"%lf", &weight);
676 infoMessage(
"Error while reading weights of nodes in file %s.\n", filename);
681 (*tcliquegraph)->weights[i] = (
TCLIQUE_WEIGHT)(weight * scaleval);
682 assert((*tcliquegraph)->weights[i] >= 0);
688 for( i = 0; i < (*tcliquegraph)->nedges; i++ )
692 result = fscanf(file,
"%d%d", &node1, &node2);
695 infoMessage(
"Error while reading edges in file %s.\n", filename);
700 if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
702 infoMessage(
"Invalid node index (%d) in file: %s.\n", node1 < 0 ? node1 : node2, filename);
708 if( node1 != currentnode )
712 (*tcliquegraph)->degrees[currentnode] = 0;
713 (*tcliquegraph)->adjedges[currentnode].first = i;
714 (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
716 (*tcliquegraph)->degrees[currentnode]++;
717 (*tcliquegraph)->adjnodes[i] = node2;
718 (*tcliquegraph)->adjedges[currentnode].last++;
730 const char* filename,
739 assert(tcliquegraph !=
NULL);
740 assert(scaleval > 0.0);
743 if( (file = fopen(filename,
"w")) ==
NULL )
750 fprintf(file,
"%s\n", probname);
751 fprintf(file,
"%d\n", tcliquegraph->nnodes);
752 fprintf(file,
"%d\n", tcliquegraph->nedges);
755 for( i = 0; i < tcliquegraph->nnodes; i++ )
756 fprintf(file,
"%f\n", (
double)tcliquegraph->weights[i]/scaleval);
759 for( i = 0; i < tcliquegraph->nnodes; i++ )
761 for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
762 fprintf(file,
"%d %d\n", i, tcliquegraph->adjnodes[j]);
776 assert(tcliquegraph !=
NULL);
778 return tcliquegraph->nedges + tcliquegraph->ncachededges;
786 assert(tcliquegraph !=
NULL);
787 assert(tcliquegraph->ncachededges == 0);
789 return tcliquegraph->degrees;
797 assert(tcliquegraph !=
NULL);
798 assert(tcliquegraph->ncachededges == 0);
800 return tcliquegraph->adjnodes;
812 assert(tcliquegraph !=
NULL);
813 assert(tcliquegraph->ncachededges == 0);
814 assert(0 <= node && node < tcliquegraph->
nnodes);
816 adjedges = tcliquegraph->adjedges;
817 assert(adjedges !=
NULL);
818 assert(adjedges[node].first >= 0);
822 assert(adjnodes !=
NULL);
824 return &adjnodes[adjedges[node].first];
839 assert(tcliquegraph !=
NULL);
840 assert(tcliquegraph->ncachededges == 0);
841 assert(0 <= node && node < tcliquegraph->
nnodes);
843 adjedges = tcliquegraph->adjedges;
847 assert(adjedges !=
NULL);
848 assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
851 assert(adjedges[node].last - adjedges[node].first == degrees[node]);
854 assert(adjnodes !=
NULL);
856 return &adjnodes[adjedges[node].last-1];
868 assert(tcliquegraph !=
NULL);
869 assert(tcliquegraph->ncachededges == 0);
872 weights = tcliqueGetWeights(tcliquegraph);
875 for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
880 infoMessage(
"node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
884 assert(lastadjedge + 1 - currentadjedge == degrees[i]);
886 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