/* /* to compile: gcc mkgraph.c -o mkgraph -lm /* /* MODULE: MKGRAPH - Make Graph /* /* PROGRAMMER'S NAME: Steve Goddard /* /* FUNCTIONAL DESCRIPTION: /* This module generates graphs for the connected components workshop. /* The graphs consist of pairs of 32-bit integers. Each pair of /* numbers makes up one edge in the graph. /* /* This program is a textbook case of what happens when a program /* is written with moving requirements. It has been cleaned up some, /* but is still pretty messy. The data structures still need /* work, but it runs... This program should be multiple source /* files, but is easier to distribute like this. /* /* The routines that make up the MKGRAPH module and their basic /* responsibilities are: /* /* edge_is_good(int dU,int dV) if the U-V edge is good, then the edge /* is inserted into the global_asEdge[] list and it returns TRUE. /* If U-V edge (or V-U edge) exists or is a self-loop, FALSE is /* returned. /* /* create_vertices(int iStartRange,int iEndRange,tBoolean fFill) mallocs /* space for global_nVertices = 1+(iStarRange-iEndRange). If fFill /* is TRUE, the global_ahVertices array is initialized with node /* IDs = iStartRange to iEndRange. /* /* get_vertex_index() returns a vertex index from 0 to global_nVertices-1. /* This index is used for the edge set and as an index into /* global_ahVertices to retrieve the node ID. /* /* fill_component(int iStartRange, int iEndRange,int nEdges,int dVertexDegree, /* fComponentsSelected,tBoolean fCreateVertices,FILE *hGraphFile) /* allocates space for the necessary data structures and then calls /* generate_constant_degree() or generate_varying_degree() to create /* the appropriate graph. If dVertexDegree != 0, then /* generate_constant_degree() is called. Allocated space is freed /* after the component is created. /* /* calculate_parameters( int nComponents, int nNodes, int dDensity, /* int dVertexDegree, int *nNodesPerComponent, /* int *nNewComponents, int *nEdgesPerComponent) /* calculates the number of new components, edges per component, and /* and the number of nodes per component. If nComponents is non-zero, /* then nNodesPerComponent will be equal to nNodes unless there wasn't /* enough heap space to malloc the necessary memory. Then the number /* of components is increased and number of nodes per component reduced /* to retain the overall number of nodes = nNodes*nComponents. /* /* generate_varying_degree(int nNodes,int nEdges, /* tBoolean fComponentsSelected,FILE *hGraphFile) /* creates nEdges and writes them into the graph file (hGraphFile) using /* vertices IDs from the specified range. If fComponentsSelected is /* TRUE, all nodes over the range will be part of the same component. /* The structure of the component is specified by global_eStructure: /* psuedorandom, chain, or star. The degree if each vertex varies. /* /* generate_constant_degree(int nNodes, int nEdges, /* tBoolean fComponentsSelected,FILE *hGraphFile) /* creates nEdges and writes them into the graph file (hGraphFile) using /* vertices IDs from the specified range. If fComponentsSelected is /* TRUE, all nodes over the range will be part of the same component. /* The structure of the component is specified by global_eStructure: /* psuedorandom, chain, or star. An attempt is made to create edges /* such that all nodes have the same degree. Exceptions to this are /* the center of the star, and extra nodes that have already mated to /* each other, but there doesn't exist any other nodes with vertex /* degree <= dVertexDegree to which they can mate. /* When fComponentsSelected is TRUE, create_single_component() is /* called to create initially link all nodes together in either /* a chain or star structure. /* /* create_single_component(int nNodes, int *nEdges, tBoolean fClosed, /* FILE *hGraphFile) /* is called by generate_*_degree() to create a single component. /* /* usage_error (char *progname) prints out usage information about the /* program. /* /* create_nComponents(int nComponents,int iStart,int iEnd,int dDensity, /* int dVertexDegree,FILE *hGraphFile) /* creates N connected graph components. The node IDs range from /* iStart to iEnd. All components are written into the file hGraphFile. /* /* make_one_graph(int nComponents, int dDensity, /* FILE *ahFiles[],FILE *hGraphFile) is called /* make_hard_graphs() to extract one node from each of N components, /* and make a psuedorandom graph from these nodes with density = dDensity. /* Then this graph and the N components are written to hGraphFile. /* /* make_hard_graphs(int dLevel,int nComponents, int iStart,int iEnd, /* int dDensity,int dVertexDegree,FILE *hGraphFile) is /* a recursive fuction that implements the function G(T,n,r) described /* by Guy Blelloch to Jan Prins. This funtion is my implementation of /* this functions as described by Jan Prins to me. The hard graphs /* have dLevel levels when first call. Each level has nComponents /* with nodes in the range of iStart to iEnd. The Density passed to /* make_one_graph is alternated at each level. Even levels are /* created with the density defined on the command line (or default). /* Odd levels have a density of 100-dDensity such that the graphs /* alternate from dense to sparse at each level. Level 0 is made up /* of N components with the density, structure, and number of nodes /* per component specified on the command line. /* */ #include #include #include #define FALSE 0 #define TRUE 1 #define iNULL 0 #define DEFAULT_nNodes 16384 #define DENSITY_THRESHOLD 60 #define MAX_RESEEDS 5 #define MAX_FILES 240 /* maxinum scratch files */ #define MAX_COMPONENTS MAX_FILES /* maxinum number of components */ #define RECOVERY_MIN_NODES 256 /* Used to check for allocation problems */ #define MIN_NODES 2 /* minimum number of nodes */ #define MIN_HARD_LEVEL 0 /* => not a hard graph */ #define MAX_HARD_LEVEL MAX_FILES-2 /* max level of recursion */ #define DEFAULT_dDensity 2 #define DEFAULT_dVertexDegree 0 #define DEFAULT_nComponents 0 #define DEFAULT_eStructure pseudorandom #define DEFAULT_zStructure "random" #define DEFAULT_dHard 0 #define fCLOSED TRUE #define fOPEN FALSE #ifndef SEEK_SET #define SEEK_SET 0 #endif /* This structure is used for global_asEdge as a linked list /* stored in an array that contains edge information. The /* array global_asEdge is initially indexed with global_aMatchingV[dU]. /* (The array entry global_aMatchingV[dU] contains the index into the /* global_asEdge which is a linked lists of the associated vertices /* that make up edges begining with dU. /* e.g. If dU = 4 and global_aMatching[dU] = 1, then /* global_asEdge[1].v = 2 is the second vertex of the edge 4-2. /* The field global_asEdge[1].inext = 2 is a pointer to the next /* matching V vertix s.t. 4 - global_asEdge[1].v is another edge /* in the graph that has been created. If the inext field is == 0, /* then this is the last (or only vertex) matched with dU. /* */ typedef struct sgEdgeList { /* edge list structure */ int v; /* second vertex */ int inext; /* next edge */ }tEdgeList; /* This structure is used for global_asNodeInfo and could /* probably be combined with global_ahVertices to further /* simplify the data structures used. dMarked isn't really /* need anymore -- we could use dDegree == 0 instead with /* one tricky check when we start of the while loop in /* create_single_component. /* */ typedef struct sgDegreeList { /* degree list structure */ int dDegree; /* degree -- used by */ /* generate_constant_degree() */ /* to tack nodes degrees */ char dMarked; /* marked flag -- used by */ /* create_single_component() */ /* to tack free/used nodes */ }tDegreeList; /* This structure is used to store intermediate component information /* while the graph is being built. All components are eventually /* combined into one file. /* */ typedef struct sgComponentInfo { /* degree list structure */ FILE *hFile; /* Scratch file */ int v; /* vertex in component - used by*/ /* make_one_graph() */ char dMarked; /* marked flag used to write */ /* Graph randomly into one file */ }tComponentInfo; /* This is a simple edge structure consisting of the /* U-V vertex pairs that create the edge. /* */ typedef struct sgEdge{ /* single Edge */ int dU; /* first vertex of edge */ int dV; /* second vertex of edge */ } tEdge; /* All graph components are one of three structures: /* star, chain, or psuedorandom /* */ typedef enum egStructure { star, /* Star structure */ chain, /* Chain structure */ pseudorandom /* Pseudorandom structure */ } tStructure; typedef int tBoolean; tEdgeList *global_asEdge; /* pointer to edge list used to */ /* store created edges */ int *global_aMatchingV; /* starting index into global_asEdge */ /* of matching vertex */ tDegreeList *global_asNodeInfo; /* structure storing vertex degree */ /* of nodes and a marked field */ tEdge global_sEdge; /* Edge structure - will hold */ /* the last edge created */ tBoolean global_fPrintInfo=FALSE;/*Don't print extra info */ tBoolean global_fTestingNewComponents = FALSE; /* not testing */ char *global_zProgName; /* Stores name of the program */ tStructure global_eStructure = DEFAULT_eStructure; /* pseudorandom */ int global_nEdgesCreated = 0; /* # of edges created so far */ int *global_ahVertices = NULL; /* pointer to array of nodes IDs*/ int global_nVertices = 0; /* size of global_nVertices array */ int global_dVertexDegree = DEFAULT_dVertexDegree; /* default vertex degree */ tBoolean edge_is_good(int dU,int dV); void create_vertices(int iStartRange,int iEndRange,tBoolean fFill); int get_vertex_index(); void fill_component(int iStartRange, int iEndRange,int nEdges,int dVertexDegree, tBoolean fComponentsSelected,tBoolean fCreateVertices,FILE *hGraphFile); void calculate_parameters( int nComponents, int nNodes, int dDensity, int dVertexDegree, int *nNodesPerComponent, int *nNewComponents, int *nEdgesPerComponent); void generate_varying_degree(int nNodes,int nEdges, tBoolean fComponentsSelected,FILE *hGraphFile); void generate_constant_degree(int nNodes, int nEdges, tBoolean fComponentsSelected,FILE *hGraphFile); void create_single_component(int nNodes, int *nEdges, tBoolean fClosed, FILE *hGraphFile); void usage_error (char *progname); void create_nComponents(int nComponents,int iStart,int iEnd,int dDensity, int dVertexDegree,FILE *hGraphFile); void make_one_graph(int nComponents, int dDensity, FILE *ahFiles[],FILE *hGraphFile); void make_hard_graphs(int dLevel,int nComponents, int iStart,int iEnd, int dDensity,int dVertexDegree,FILE *hGraphFile); /* Main entry point for this progam. Get and check the options and /* then create the requested graph. Most of the real work is done /* in the supporting routines. /* */ void main(int argc, char *argv[]) { extern char *optarg; extern int optind, opterr; int i,c; int mVertexDensity=FALSE; /* Vertex/Density options mutex */ int iStartRange,iNewComponents; int nComponents = DEFAULT_nComponents;/* Default: undefined # */ int nEdges; /* number of edges to create */ float flt_nNodes,flt_Density; char *zFileName; /* Name of final graph file */ int nNodesPerComponent,nNewComponents,nEdgesPerComponent; tEdge sNewEdge; tEdge *asEdge; FILE *hFinalGraphFile; int dHardLevel = DEFAULT_dHard; /* Default level of hard graphs */ int nNodes = DEFAULT_nNodes; /* Default number of nodes */ /* range: 1-nNodes */ int dDensity = DEFAULT_dDensity ; /* Default %Density */ int nEdgesPerEvenLevel,nEdgesPerOddLevel; global_zProgName = argv[0]; /* name of executable */ if (argc > 1) { /* Assume the last parameter is the output graph file name */ zFileName = argv[argc-1]; } else { zFileName = NULL; } /* process the command line options */ while ((c = getopt (argc, argv, "c:d:h:n:o:ps:tv:")) != EOF) switch(c) { case 'c': /* Number of Components */ nComponents = atoi(optarg); if (nComponents > MAX_COMPONENTS) { fprintf(stderr, "Invalid option: nComponents must be < %d.\n",MAX_COMPONENTS); usage_error (global_zProgName); exit(-1); } break; case 'd': /* %Density of graph */ /* SMG - Used to not allow both Vertex Degree and Density options /* SMG - to be specified at the same time since they both couldn't /* SMG - be used until hard graph procesing was added. When hard /* SMG - graphs are requested, then they both will be used. /* */ /* SMG if (mVertexDensity) { fprintf(stderr, "Invalid option: Density cannot be set when Vertex Degree is specified.\n"); usage_error (global_zProgName); exit(-1); } else { SMG */ dDensity = atoi(optarg); mVertexDensity = TRUE; /* set mutex */ /* SMG } SMG */ break; case 'h': /* Level of recursion defined for Hard Graphs /* Defaults to 0 => don't create hard graphs. /* The larger the level, the harder the graph. /* */ dHardLevel = atoi(optarg); if (dHardLevel < MIN_HARD_LEVEL || dHardLevel > MAX_HARD_LEVEL ) { fprintf(stderr, "Hard option specified is out of range: %d <= hard <= %d\n", MIN_HARD_LEVEL,MAX_HARD_LEVEL); usage_error (global_zProgName); exit(-1); } if (dHardLevel && nComponents == DEFAULT_nComponents) { /* dHardLevel > 1 AND nComponents not defined */ /* --depending on DEFAULT_nComponents being 0 */ /* set nComponents to the level of recursion chosen for hard graphs /* Each level of the hard graph will have nComponents /* */ nComponents = dHardLevel; } break; case 'n': /* Number of nodes in component (or graph if no nComponents defined)*/ nNodes = atoi(optarg); if (nNodes < MIN_NODES) { nNodes = MIN_NODES; fprintf(stderr, "\n\tInvalid option: nNodes must >= %d.\n",MIN_NODES); fprintf(stderr, "\n\t\tnNodes set to %d.\n",MIN_NODES); } break; case 'o': /* output graph file */ zFileName = optarg; break; case 'p': /* print extra debug info -- only partially used */ global_fPrintInfo = TRUE; break; case 's': /* define the structure of the components */ /* Planned on forcing strict names of the /* structures, but relaxed and now match /* the first character of star or chain /* -- BUT left old match in ... why?? /* */ if (!strcmp(optarg,"star") || (*optarg == 's')) { global_eStructure = star; } else if (!strcmp(optarg,"chain") || (*optarg == 'c')) { global_eStructure = chain; } else { global_eStructure = pseudorandom; } break; case 'v': /* Vertex Degree -- used to create graphs with constant degrees */ /* SMG - Used to not allow both Vertex Degree and Density options /* SMG - to be specified at the same time since they both couldn't /* SMG - be used until hard graph procesing was added. When hard /* SMG - graphs are requested, then they both will be used. /* */ /* SMG if (mVertexDensity) { fprintf(stderr, "Invalid option: Density cannot be set when Vertex Degree is specified.\n"); usage_error (global_zProgName); exit(-1); } else { SMG */ global_dVertexDegree = atoi(optarg); mVertexDensity = TRUE; /* set mutex */ /* SMG } SMG */ break; case 't': /* This option tests the malloc of the data structures /* for the given sizes. Used for testing only. /* */ global_fTestingNewComponents = TRUE; break; default: /* Print an error message for the bad argument */ fprintf(stderr, "\n\tUnrecognized or incomplete argument '%s'. Exiting\n", argv[optind-1]); usage_error (global_zProgName); exit(-1); } calculate_parameters(nComponents,nNodes,dDensity, global_dVertexDegree,&nNodesPerComponent, &nNewComponents,&nEdgesPerComponent); if (dHardLevel) { /* hard graph requested */ int nEvenLevels,nOddLevels,tmp,iLevel; float fltEvenDensity; float fltOddDensity; tmp = (MAX_FILES-dHardLevel)/2; if (nComponents > tmp) { fprintf(stderr, "The number of components is greater than the max # of open files allowed.\n"); fprintf(stderr, "\tMax number of components is (MAX_FILES-Selected_Hard_level)/2 = %d\n", tmp); usage_error (global_zProgName); exit(-1); } else if (nNewComponents > tmp) { fprintf(stderr, "\nThe size of each component was too large for available memory.\n"); fprintf(stderr, "Additional temporary components were to be created to compensate,\n"); fprintf(stderr, "but the new number of components would be greater than the\n"); fprintf(stderr, "maximum number of open files allowed.\n"); fprintf(stderr, "\tMax number of components is (MAX_FILES-Selected_Hard_level)/2 = %d\n", tmp); usage_error (global_zProgName); exit(-1); } /* update new number of nodes */ nNodes = (int) nNodesPerComponent*pow((double)nNewComponents,(double)(dHardLevel+1)); /* dMinNodes = (int) pow((double)(nNodesPerComponent*nNewComponents),(double)dHardLevel); if (nNodes < dMinNodes){ nNodes = dMinNodes; } */ /* set number of edges */ /* Calculate the density of even and odd levels of the hard graph. /* Each of these levels consists of edges made up of nodes/graphs /* of a lower level. The lowest level has nEdgesPerComponent. /* */ /* density at even levels */ fltEvenDensity =((float)dDensity)/100.0; /* density at odd levels */ fltOddDensity =((float)(100-dDensity))/100.0; /* nEdges in components */ if (global_eStructure == pseudorandom || (global_eStructure == chain && global_dVertexDegree > 0)) { /* /* if structure is random OR it is a chain and global_dVertex > 0 /* then the components are closed and we create one more edge /* than nEdgesPerComponent in each component /* */ nEdges = (int) (nEdgesPerComponent+1) * pow((double)nNewComponents,(double)(dHardLevel+1)); } else { /* /* component is open and nEdgesPerComponent stays the same /* */ nEdges = (int) nEdgesPerComponent * pow((double)nNewComponents,(double)(dHardLevel+1)); } /* number of edges in each even level */ nEdgesPerEvenLevel = (int)(((nNewComponents*(nNewComponents-1))/2)*fltEvenDensity); if (nEdgesPerEvenLevel < 1 ) { /* make sure each component has at least 1 edge */ nEdgesPerEvenLevel=1; } /* number of edges in each odd level */ nEdgesPerOddLevel = (int)(((nNewComponents*(nNewComponents-1))/2)*fltOddDensity); if (nEdgesPerOddLevel < 1 ) { /* make sure each component has at least 1 edge */ nEdgesPerOddLevel=1; } /* Calculate the number of even and hard levels */ nOddLevels = nEvenLevels = dHardLevel/2; if (dHardLevel % 2) { nOddLevels++; /* Hard levels is odd so add one more to nOddLevels */ } /* NOW set the total number of edges in the graph. /* This is actually only an estimate! When a constant /* vertex degree is requested in the components, we /* get fewer edges than desired. /* */ /* nEdges = nEdges + (nOddLevels*nEdgesPerOddLevel) + (nEvenLevels*nEdgesPerEvenLevel);*/ /* start at the top of the graph tree and sum subgraphs at /* each level and then add the sum to the cumalative number /* of edges. /* */ for (i=0,iLevel=dHardLevel; i < dHardLevel;i++,iLevel--) { if (iLevel % 2) { /* odd Level */ nEdges = nEdges + (int)(nEdgesPerOddLevel*pow(nComponents,i)); } else { /* even Level */ nEdges = nEdges + (int)(nEdgesPerEvenLevel*pow(nComponents,i)); } } } else { /* not a hard graph */ /* update new number of nodes */ nNodes = nNodesPerComponent*nNewComponents; /* set number of edges */ /* This is actually only an estimate! When a constant /* vertex degree is requested in the components, we /* get fewer edges than desired. /* */ nEdges = nEdgesPerComponent*nNewComponents; } /* Open output file */ if ((zFileName == NULL) || (zFileName[0] == '-')) { /* Bad file name - or didn't get a file name /* display usage /* */ fprintf(stderr,"Output file name is requrired! Exiting\n"); usage_error (global_zProgName); exit(-1); } else { char zError[300]; /* open output file */ if ( (hFinalGraphFile = fopen(zFileName, "wb")) == NULL) { sprintf(zError,"Error opening file %s",zFileName); perror(zError); usage_error (global_zProgName); exit(-1); } } if (dHardLevel) { fprintf(stdout,"\nA hard graph was chosen with %d recusive calls\n", dHardLevel); fprintf(stdout,"to the funtion G(T,n,r) as defined by Guy Blelloch.\n"); fprintf(stdout,"The lowest level of the recursively defined graph\n"); fprintf(stdout,"will consist of:\n"); } if (nNewComponents != 1 && nNewComponents != nComponents) { fprintf(stdout,"\tTemp Components: %d\n",nNewComponents); fprintf(stdout,"\tFinal Components: %d\n",nComponents); } else { fprintf(stdout,"\tComponents: %d\n",nComponents); } if (global_dVertexDegree) { /* Vertex Degree specified */ fprintf(stdout, "\tVertex Degree: %d\n",global_dVertexDegree); } else { fprintf(stdout, "\tDensity: %d\n",dDensity); } if (global_eStructure == star) { /* display graph structure */ fprintf(stdout,"\tStructure: %s\n", "Star"); } else if (global_eStructure == chain) { fprintf(stdout,"\tStructure: %s\n", "Chain"); } else if (global_eStructure == pseudorandom) { fprintf(stdout,"\tStructure: %s\n", "Random"); } fprintf(stdout, "\tNodesPerComponent: %d\n",nNodesPerComponent); fprintf(stdout,"\tEdgesPerComponent: %d\n",nEdgesPerComponent); if (dHardLevel) { fprintf(stdout,"Levels 1 to %d will consist of nodes from\n",dHardLevel); fprintf(stdout,"the lower levels with alternating density.\n"); fprintf(stdout,"\tEven level density: %s%d\n","%",dDensity); fprintf(stdout,"\tOdd level density: %s%d\n","%",100-dDensity); fprintf(stdout,"\tnEdgesPerEvenLevel: %d\n",nEdgesPerEvenLevel); fprintf(stdout,"\tnEdgesPerOddLevel: %d\n",nEdgesPerOddLevel); } fprintf(stdout, "\tTotal Nodes in the Graph: %d\n",nNodes); fprintf(stdout,"\tApproximate number of Edges: %d\n",nEdges); if (dHardLevel) { /* hard graph */ make_hard_graphs(dHardLevel,nNewComponents,0,nNodes-1, dDensity, global_dVertexDegree,hFinalGraphFile); } else { /* not a hard graph */ /* /* Only using one level of Graph Function G(T,n,r). /* */ /* Use nComponents rather than nNewComponents. create_nComponents() /* will call calculate_parameters() again and recreate nNewComponents. /* This is inefficient, but what you get with moving requirements. /* We may take out calculate_pararmeters above... /* */ /* nNodes = nComponents ? nNodes*nComponents : nNodes; */ create_nComponents(nComponents,0,nNodes-1,dDensity, global_dVertexDegree,hFinalGraphFile); } exit(0); } /**********************************************************************/ /* SYNOPSIS: */ void create_vertices(int iStartRange,int iEndRange,tBoolean fFill) { /* /* Create an global array that holds verices. If fFill is TRUE, /* then fill the array with verex numbers over the range iStartRange /* to iEndRange. get_vertex_index() randomly indexes into this range to /* return a vertex. /* /* This routine allows creating a sequential range of verticies from /* which to select nodes of the graph, but it also lets the caller /* fill in the array with different values. The latter feature /* is used to create Hard graphs of the form G(T,n,r). /* */ int i; if (global_ahVertices) { free(global_ahVertices); /* free the old array */ } global_nVertices = (iEndRange-iStartRange)+1; /* get the number of nodes */ global_ahVertices = malloc(global_nVertices*sizeof(int)); if (global_ahVertices == NULL) { fprintf(stderr, "create_vertices() - Allocation Failed.\n"); exit(-1); } if (fFill) { /* need to fill the array with vertex IDs */ for (i=0; i < global_nVertices; i++) { global_ahVertices[i] = iStartRange++; } } } /**********************************************************************/ /* SYNOPSIS: */ int get_vertex_index() { /* /* This routine calls rand to genereate an index between /* 0 and global_nVertices-1. This index is then used to select a /* vertex from the array of vertices. /* */ return (rand() % global_nVertices); } /**********************************************************************/ /* SYNOPSIS: */ tBoolean edge_is_good(int dU,int dV) { /* /* edge_is_good(int dU,int dV) if the U-V edge is good, then the edge /* is inserted into the global_asEdge[] list and it returns TRUE. /* If U-V edge (or V-U edge) exists or is a self-loop, FALSE is /* returned. /* */ int inext,iLastV; if ( dU == dV ) { /* check if this edge is a self loop */ return(FALSE); /* self loop => return false */ } /* These data Structures use index 0 to represent NULL. /* Therefore, all indices are offset by one when used in /* this routine. /* */ dU++; /* add one for correct offsets */ dV++; /* add one for correct offsets */ if ( global_aMatchingV[dU] ) { /* check if this vertex is part of an edge yet */ /* aVertex[dU] is an index into asEdge such that /* asEdge[aVertex[dU]].v is the second vertex of the edge. /* If asEdge[aVertex[dU]].v == dV, then the edge exists already. /* return False /* Else /* if asEdge[aVertex[dU]].inext != iNULL then /* check the next V (in the list) to which inext points. /* else -- inext == iNULL /* edge is not in list and can be inserted. /* */ inext = global_aMatchingV[dU]; /* matching v index for this u */ do { if (global_asEdge[inext].v == dV) /* next matching v for this u */ return(FALSE); /* matched => return false */ iLastV = inext; /* store the index of last V */ inext = global_asEdge[inext].inext; /* next v after this v in list */ } while ( inext != iNULL && inext <= global_nEdgesCreated ); } /* Edge u-v is not in the list */ if ( global_aMatchingV[dV] ) { /* need to check both directions */ inext = global_aMatchingV[dV]; /* matching u index for this v */ do { if (global_asEdge[inext].v == dU) /* next matching u for this v */ return(FALSE); /* matched => return false */ inext = global_asEdge[inext].inext; /* next u after this u in list */ } while ( inext != iNULL && inext <= global_nEdgesCreated ); } /* Edge was not found so insert the edge in the list */ if (global_aMatchingV[dU]) { /* check if this vertex is part of an edge yet */ /* This vertex is already part of one edge. Find the last edge /* in its matching V list and add this dV to the list. /* */ /* Set inext of last matching v to this dV entry */ global_asEdge[iLastV].inext = ++global_nEdgesCreated; } else { /* First u-v edge for this dU */ /* matching v index for this u */ global_aMatchingV[dU] = ++global_nEdgesCreated; } /* Now add dV entry to asEdge. The inext field is /* already iNULL and need not be updated. /* */ /* global_nEdgesCreated++; */ global_asEdge[global_nEdgesCreated].v = dV; /* next matching v for this u */ /* u-v edge (nor v-u edge) was not in the list, but has now been /* added correctly. Return true! /* */ return (TRUE); } /**********************************************************************/ /* SYNOPSIS: */ void fill_component(int iStartRange, int iEndRange,int nEdges,int dVertexDegree, tBoolean fComponentsSelected,tBoolean fCreateVertices,FILE *hGraphFile) { /* /* fill_component(int iStartRange, int iEndRange,int nEdges,int dVertexDegree, /* tBoolean fComponentsSelected,tBoolean fCreateVertices,FILE *hGraphFile) /* allocates space for the necessary data structures and then calls /* generate_constant_degree() or generate_varying_degree() to create /* the appropriate graph. If dVertexDegree != 0, then /* generate_constant_degree() is called. Allocated space is freed /* after the component is created. /* */ int nNodes; nNodes = 1+(iEndRange-iStartRange); global_aMatchingV = calloc(nNodes+1,sizeof(int)); global_asEdge = calloc((1+nEdges),sizeof(tEdgeList)); if (dVertexDegree||fComponentsSelected) { global_asNodeInfo = calloc(nNodes,sizeof(tDegreeList)); } else { /* Default: undertermined degree */ global_asNodeInfo = (tDegreeList *)&nNodes; /* dummy pointer value to simplify checks */ } if (fCreateVertices) { /* create verices */ create_vertices(iStartRange,iEndRange,fCreateVertices); } if (global_asEdge == NULL || global_aMatchingV == NULL || global_asNodeInfo == NULL) { fprintf(stderr, "fill_component() - Allocation Failed.\n"); exit(-1); } if (dVertexDegree) { /* Degree specified for all nodes */ generate_constant_degree(nNodes,nEdges,fComponentsSelected,hGraphFile); } else { /* Default: undertermined degree */ generate_varying_degree(nNodes,nEdges, fComponentsSelected,hGraphFile); } free((void *)global_aMatchingV); free((void *)global_asEdge); free((void *)global_ahVertices); if (dVertexDegree||fComponentsSelected) { free((void *)global_asNodeInfo); global_asNodeInfo = NULL; } global_aMatchingV = NULL; global_asEdge = NULL; global_ahVertices = NULL; } /**********************************************************************/ /* SYNOPSIS: */ void calculate_parameters( int nComponents, int nNodes, int dDensity, int dVertexDegree, int *nNodesPerComponent, int *nNewComponents, int *nEdgesPerComponent){ /* nNodes is really input nNodesPerComponent */ /* calculate_parameters( int nComponents, int nNodes, int dDensity, /* int dVertexDegree, int *nNodesPerComponent, /* int *nNewComponents, int *nEdgesPerComponent) /* calculates the number of new components, edges per component, and /* and the number of nodes per component. If nComponents is non-zero, /* then nNodesPerComponent will be equal to nNodes unless there wasn't /* enough heap space to malloc the necessary memory. Then the number /* of components is increased and number of nodes per component reduced /* to retain the overall number of nodes = nNodes*nComponents. /* */ tBoolean fComponentsSelected,fDone = FALSE; float fltDensity; tEdgeList *asEdge; int *aVertexU; tDegreeList *aNodes; if (nComponents) { fComponentsSelected = TRUE; } else { fComponentsSelected = FALSE; nComponents = 1; } *nNewComponents = nComponents; /* calculate required # components */ /* *nNodesPerComponent = nNodes/(*nNewComponents); */ *nNodesPerComponent = nNodes; /* use nNodes per component */ if (*nNodesPerComponent <= 1 ) { *nNodesPerComponent=2; /*make sure each component has at least 2 nodes*/ } fltDensity =((float)dDensity)/100.0; while (!fDone) { if (dVertexDegree) { *nEdgesPerComponent = (dVertexDegree*(*nNodesPerComponent))/2; aNodes = malloc((*nNodesPerComponent)*sizeof(tDegreeList)); } else { /* Default: undertermined degree */ *nEdgesPerComponent = (int)(((*nNodesPerComponent*(*nNodesPerComponent-1))/2)*fltDensity); if (*nEdgesPerComponent < 1 ) { /* make sure each component has at least 1 edge */ *nEdgesPerComponent=1; } if(fComponentsSelected) { aNodes = malloc((*nNodesPerComponent)*sizeof(tDegreeList)); if (*nEdgesPerComponent < *nNodesPerComponent) { /* need at least nNodesPerComponent edges in each component /* when complete components are requested. /* */ *nEdgesPerComponent = *nNodesPerComponent - 1; } } else { /* dummy pointer value to simplify checks */ aNodes = (tDegreeList *)nNodesPerComponent; } } asEdge = malloc((1+(*nEdgesPerComponent))*sizeof(tEdgeList)); aVertexU = malloc((1+(*nNodesPerComponent))*sizeof(int)); if (asEdge == NULL || aVertexU == NULL || aNodes == NULL || global_fTestingNewComponents) { if ((*nNodesPerComponent) % 2) { (*nNodesPerComponent)++; /* make it even */ } (*nNodesPerComponent) /= 2; (*nNewComponents)*=2; if (asEdge != NULL) free((void *)asEdge); if (aVertexU != NULL) free((void *)aVertexU); if (dVertexDegree && aNodes != NULL) /* free valid pointer */ free((void *)aNodes); } else { /* malloc worked */ fDone = TRUE; } if (*nNewComponents > MAX_COMPONENTS) { fprintf(stderr, "\nThe size of each component was too large for available memory.\n"); fprintf(stderr, "Additional temporary components were to be created to compensate,\n"); fprintf(stderr, "but the new number of components would be greater than the\n"); fprintf(stderr, "maximum number of open files allowed.\n"); fprintf(stderr, "nComponets.\n"); fprintf(stderr, "\tnumber of components is %d\n",MAX_COMPONENTS); usage_error (global_zProgName); exit(-1); } if (!fDone && (*nNodesPerComponent) <= RECOVERY_MIN_NODES) { if (global_fTestingNewComponents){ /* only pass through once with this flag */ global_fTestingNewComponents = FALSE; } else { /* major malloc problem */ fprintf(stderr, "Allocation Failed for %d Nodes Per Component.\n", RECOVERY_MIN_NODES); exit(-1); } } } free((void *)aVertexU); free((void *)asEdge); if (dVertexDegree || fComponentsSelected) { /* aNodes is valid by the time we get here */ free((void *)aNodes); } } /**********************************************************************/ /* SYNOPSIS: */ void generate_varying_degree(int nNodes, int nEdges, tBoolean fComponentsSelected,FILE *hGraphFile) { /* /* generate_varying_degree(int nNodes,int nEdges, /* tBoolean fComponentsSelected,FILE *hGraphFile) /* creates nEdges and writes them into the graph file (hGraphFile) using /* vertices IDs from the specified range. If fComponentsSelected is /* TRUE, all nodes over the range will be part of the same component. /* The structure of the component is specified by global_eStructure: /* psuedorandom, chain, or star. The degree if each vertex varies. /* */ int i,iEdgeChecks=0,nNewSeeds=0,nEdgesLeft=nEdges; global_nEdgesCreated = 0; if(fComponentsSelected) { if (global_eStructure == pseudorandom) { create_single_component(nNodes,&nEdgesLeft,fCLOSED,hGraphFile); } else { create_single_component(nNodes,&nEdgesLeft,fOPEN,hGraphFile); } } /* generate nEdges by calling rand() to assign u and v */ for (i=1+(nEdges-nEdgesLeft); i <= nEdges; i++,iEdgeChecks=0) { global_sEdge.dU = get_vertex_index(); /* first vertex of edge */ global_sEdge.dV = get_vertex_index(); /* sedond vertex of edge */ while (!edge_is_good(global_sEdge.dU,global_sEdge.dV)){ global_sEdge.dU = get_vertex_index(); /* first vertex of edge */ global_sEdge.dV = get_vertex_index(); /* second vertex of edge */ if (++iEdgeChecks > nEdges*3) { int dTmp; /* generate a new seed -- having trouble getting a good edge */ if (++nNewSeeds < MAX_RESEEDS) { srand(dTmp=rand()); iEdgeChecks = 0; if (global_fPrintInfo) { fprintf(stdout, "generate_varying_degree - Called srand(%d)\n",dTmp); } } else { int j,k; /* Density is so high (usually > 90% when we get here) /* that we can't find the last few edges with the psuedo /* random number generator. So we brute force fill the /* graph by searching for a good edge, one edge at a time. /* The edge_is_good() routine will prevent duplicate and /* selve edges from being selected. /* */ if (global_fPrintInfo) { fprintf(stdout, "\tgenerate_varying_degree - Must force fill component!\n"); } for (j=0; j < nNodes && i <= nEdges; j++){ for (k=0; k < nNodes && i <= nEdges; k++){ if (edge_is_good(j,k)){ i++; global_sEdge.dU = global_ahVertices[j]; /* first vertex of edge */ global_sEdge.dV = global_ahVertices[k]; /* second vertex of edge */ if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",global_sEdge.dU,global_sEdge.dV); } fwrite((void *)&global_sEdge, sizeof(tEdge),1,hGraphFile); } } } i = nEdges+1; /* make sure we exit for loop -- Kludge! */ break; } } } if (nNewSeeds < MAX_RESEEDS) { /* edge generated at random */ global_sEdge.dU = global_ahVertices[global_sEdge.dU]; /* first vertex of edge */ global_sEdge.dV = global_ahVertices[global_sEdge.dV]; /* second vertex of edge */ if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",global_sEdge.dU,global_sEdge.dV); } fwrite((void *)&global_sEdge, sizeof(tEdge),1,hGraphFile); } /* else edge created by force and already written out */ } } /**********************************************************************/ /* SYNOPSIS: */ void generate_constant_degree(int nNodes, int nEdges,tBoolean fComponentsSelected,FILE *hGraphFile) { /* /* generate_constant_degree(int nNodes, int nEdges, /* tBoolean fComponentsSelected,FILE *hGraphFile) /* creates nEdges and writes them into the graph file (hGraphFile) using /* vertices IDs from the specified range. If fComponentsSelected is /* TRUE, all nodes over the range will be part of the same component. /* The structure of the component is specified by global_eStructure: /* psuedorandom, chain, or star. An attempt is made to create edges /* such that all nodes have the same degree. Exceptions to this are /* the center of the star, and extra nodes that have already mated to /* each other, but there doesn't exist any other nodes with vertex /* degree <= dVertexDegree to which they can mate. /* When fComponentsSelected is TRUE, create_single_component() is /* called to create initially link all nodes together in either /* a chain or star structure. /* */ int i,iEdgeChecks=0,nNewSeeds=0; int iNewNodeTries=0,nEdgesLeft=nEdges; global_nEdgesCreated = 0; /* for (i=0; i <= nNodes; i++) { global_asNodeInfo[i].dMarked = FALSE; global_asNodeInfo[i].dDegree = 0; } */ nNewSeeds = 0; if(fComponentsSelected) { if (global_eStructure == pseudorandom || (global_eStructure == chain && global_dVertexDegree > 0)) { create_single_component(nNodes,&nEdgesLeft,fCLOSED,hGraphFile); } else { create_single_component(nNodes,&nEdgesLeft,fOPEN,hGraphFile); } } for (i=1+(nEdges-nEdgesLeft); i <= nEdges; i++,iEdgeChecks=0) { int iU,iV; iU = get_vertex_index(); /* first vertex of edge */ iV = get_vertex_index(); /* sedond vertex of edge */ while ((global_asNodeInfo[iU].dDegree >= global_dVertexDegree) || (global_asNodeInfo[iV].dDegree >= global_dVertexDegree) || !edge_is_good(iU,iV)){ iU = get_vertex_index(); /* first vertex of edge */ iV = get_vertex_index(); /* second vertex of edge */ if (++iEdgeChecks > nEdges*3) { int dTmp; /* generate a new seed -- having trouble getting a good edge */ if (++nNewSeeds < MAX_RESEEDS) { srand(dTmp=rand()); iEdgeChecks = 0; if (global_fPrintInfo) { fprintf(stdout, "generate_constant_degree - Called srand(%d)\n",dTmp); } } else { int j,k; /* Density is so high (usually > 90% when we get here) /* that we can't find the last few edges with the psuedo /* random number generator. So we brute force fill the /* graph by searching for a good edge, one edge at a time. /* The edge_is_good() routine will prevent duplicate and /* selve edges from being selected. /* */ if (global_fPrintInfo) { fprintf(stdout, "\tgenerate_constant_degree - Must force fill component!\n"); } for (j=0; j < nNodes && i <= nEdges; j++){ for (k=0; k < nNodes && i <= nEdges; k++){ if ((global_asNodeInfo[j].dDegree < global_dVertexDegree) && (global_asNodeInfo[k].dDegree < global_dVertexDegree) && edge_is_good(j,k)){ i++; global_asNodeInfo[j].dDegree++; global_asNodeInfo[k].dDegree++; /* first vertex of edge */ global_sEdge.dU = global_ahVertices[j]; /* second vertex of edge */ global_sEdge.dV = global_ahVertices[k]; if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n", global_sEdge.dU,global_sEdge.dV); fprintf(stdout,"\tiU.dDegree = %d, iV.dDegree= %d\n", global_asNodeInfo[j].dDegree, global_asNodeInfo[k].dDegree); } fwrite((void *)&global_sEdge, sizeof(tEdge),1,hGraphFile); } } } i = nEdges+1; /* make sure we exit for loop -- Kludge! */ break; } } } if (nNewSeeds < MAX_RESEEDS) { /* edge generated at random */ global_sEdge.dU = global_ahVertices[iU]; /* first vertex of edge */ global_sEdge.dV = global_ahVertices[iV]; /* second vertex of edge */ global_asNodeInfo[iU].dDegree++; global_asNodeInfo[iV].dDegree++; if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",global_sEdge.dU,global_sEdge.dV); fprintf(stdout,"\tiU.dDegree = %d, iV.dDegree= %d\n", global_asNodeInfo[iU].dDegree, global_asNodeInfo[iV].dDegree); } fwrite((void *)&global_sEdge, sizeof(tEdge),1,hGraphFile); } /* else edge created by force and already written out */ } } /**********************************************************************/ /* SYNOPSIS: */ void usage_error (char *progname) { /* /* usage_error (char *progname) prints out usage information about the /* program. /* */ float fltDensity; int nEdges,nComponents,nNodesPerComponent,nEdgesPerComponent; int nNodes; nComponents = DEFAULT_nComponents; nNodesPerComponent = DEFAULT_nNodes; fltDensity =((float)DEFAULT_dDensity)/100.0; nEdgesPerComponent = (int)(((nNodesPerComponent*(nNodesPerComponent-1))/2)*fltDensity); if (nComponents) { nEdges = nEdgesPerComponent * nComponents; nNodes = nNodesPerComponent * nComponents; } else { nEdges = nEdgesPerComponent; nNodes = nNodesPerComponent; } fprintf(stderr, "usage: %s [-n nNodes] [-d Density] [-c nComponents] \\ \n", progname); fprintf(stderr, "\t\t[-h DifficultyLevel] [-v VertexDegree] [-s Structure] -o File\n"); fprintf(stderr, "\t-n\tNumber of Nodes in each Component\n"); fprintf(stderr, "\t-d\tGraph Density (%s Complete)\n","%"); fprintf(stderr, "\t-c\tNumber of Components\n"); fprintf(stderr, "\t-h\tDifficultyLevel (Hard): %d <= hard <= %d\n", MIN_HARD_LEVEL,MAX_HARD_LEVEL); fprintf(stderr, "\t-s\tStructure of Graph == star | chain | random)\n"); fprintf(stderr, "\t-v\tVertex Degree (for all nodes)\n"); fprintf(stderr, "\t-o\tOutput File\n"); fprintf(stderr, "\tDefaults:\n\t\tnNodes:\t\t%d\n",nNodes); fprintf(stderr, "\t\tDensity:\t%d%s\n",DEFAULT_dDensity,"%"); fprintf(stderr, "\t\tnComponents:\t%d\n",nComponents); fprintf(stderr, "\t\tHard:\t\t%d\n",DEFAULT_dHard); fprintf(stderr, "\t\tVertex Degree:\t%d\n",DEFAULT_dVertexDegree); fprintf(stderr, "\t\tStructure:\t%s\n",DEFAULT_zStructure); fprintf(stderr, "These default values will yield %d Edges.\n",nEdges); fprintf(stderr, "nComponents == 0 means the number of Components is undefined,\n"); fprintf(stderr, "but then nNodes is the number of nodes in the graph.\n"); fprintf(stderr, "Difficutly Level == 0 means the function G(T,n,r) is applied once.\n"); fprintf(stderr, "Difficutly Level > 0 represents the number of levels of recursive \n"); fprintf(stderr, "calls to the G(T,n,r) with each level making nComponents calls to\n"); fprintf(stderr, "the function G(T,n,r) as defined by Guy Blelloch.\n\n"); fprintf(stderr,"Example: %s -n%d -d%d -c%d -h%d -s%s -ograph_file\n", global_zProgName, nNodes,DEFAULT_dDensity,nComponents, DEFAULT_dHard,DEFAULT_zStructure); fprintf(stderr, "\tCreates the default graph in the file graph_file\n"); printf("%c",'\07'); } /**********************************************************************/ /* SYNOPSIS: */ void create_single_component(int nNodes, int *nEdgesLeft, tBoolean fClosed,FILE *hGraphFile) { /* create_single_component(int nNodes, int *nEdges, tBoolean fClosed, /* FILE *hGraphFile) /* is called by generate_*_degree() to create a single component. /* */ tEdge sEdge; /* Edge structure - will hold the edge to be written */ int iEdgeChecks=0,nNewSeeds=0; int nEdges,iFirst,iLast,iU,iV,i; nEdges = nNodes-1; /* ASSUMPTION: no edges are created yet! */ /* create a single component with degree == 2 */ global_nEdgesCreated = 0; iFirst = get_vertex_index(); /* first vertex of edge */ global_asNodeInfo[iFirst].dMarked = TRUE; /* mark node used */ /* initial V is same as U */ iV = iFirst; /* second vertex of edge */ for (i=1; i <= nEdges; i++,iEdgeChecks=0) { if (global_eStructure == star) { /* create a star */ iU = iFirst; iV = iLast = get_vertex_index(); if (global_fPrintInfo) { fprintf(stdout, "\tStar structure - U = %d, V = %d\n",iU,iV); } } else { iU = iV; /* create a chain */ iV = iLast = get_vertex_index(); if (global_fPrintInfo) { fprintf(stdout, "\tChain structure - U = %d, V = %d\n",iU,iV); } } while (global_asNodeInfo[iV].dMarked == TRUE || !edge_is_good(iU,iV)) { /* get new sedond vertex of edge */ iV = iLast = get_vertex_index(); if (++iEdgeChecks > nEdges*3) { int dTmp; /* generate a new seed -- having trouble getting a good edge */ if (++nNewSeeds < MAX_RESEEDS) { srand(dTmp=rand()); iEdgeChecks = 0; if (global_fPrintInfo) { fprintf(stdout, "create_single_component - Called srand(%d)\n",dTmp); } } else { int j,k; /* Density is so high (usually > 90% when we get here) /* that we can't find the last few edges with the psuedo /* random number generator. So we brute force fill the /* graph by searching for a good edge, one edge at a time. /* The edge_is_good() routine will prevent duplicate and /* selve edges from being selected. /* */ if (global_fPrintInfo) { fprintf(stdout, "\tcreate_single_component - Must force fill component!\n"); } if (global_eStructure == star) { global_sEdge.dU = global_ahVertices[iU]; /* first vertex of edge */ for (k=0; k < nNodes && i <= nEdges; k++){ if (!global_asNodeInfo[k].dMarked && edge_is_good(iU+1,k+1)){ i++; global_asNodeInfo[k].dMarked = TRUE; global_asNodeInfo[k].dDegree++; global_asNodeInfo[iU].dDegree++; iV = iLast = k; global_sEdge.dV = global_ahVertices[k]; /* second vertex of edge */ /* /* swap U,V edge direction at random upon writing edge /* in an attempt to not write out a direct chain /* */ if (rand()%2) { /* Swap U and V */ sEdge.dU = global_sEdge.dV; sEdge.dV = global_sEdge.dU; } else { /* DON'T Swap U and V */ sEdge.dU = global_sEdge.dU; sEdge.dV = global_sEdge.dV; } if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",sEdge.dU,sEdge.dV); } fwrite((void *)&sEdge, sizeof(tEdge),1,hGraphFile); break; } } } else { for (j=0; j < nNodes && i <= nEdges; j++){ for (k=0; k < nNodes && i <= nEdges; k++){ if (!global_asNodeInfo[k].dMarked && edge_is_good(iU,k)){ i++; global_asNodeInfo[k].dMarked = TRUE; global_asNodeInfo[k].dDegree++; global_asNodeInfo[iU].dDegree++; global_sEdge.dU = global_ahVertices[iU]; /* first vertex of edge */ iV = iLast = k; global_sEdge.dV = global_ahVertices[k]; /* second vertex of edge */ /* /* swap U,V edge direction at random upon writing edge /* in an attempt to not write out a direct chain /* */ if (rand()%2) { /* Swap U and V */ sEdge.dU = global_sEdge.dV; sEdge.dV = global_sEdge.dU; } else { /* DON'T Swap U and V */ sEdge.dU = global_sEdge.dU; sEdge.dV = global_sEdge.dV; } if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",sEdge.dU,sEdge.dV); } fwrite((void *)&sEdge, sizeof(tEdge),1,hGraphFile); break; } } iU = iV; /* create a chain */ } } i = nEdges+1; /* make sure we exit for loop -- Kludge! */ break; } } } if (nNewSeeds < MAX_RESEEDS) { /* edge generated at random */ global_asNodeInfo[iV].dMarked = TRUE; /* mark node used */ global_asNodeInfo[iV].dDegree++; global_asNodeInfo[iU].dDegree++; global_sEdge.dU = global_ahVertices[iU]; /* first vertex of edge */ global_sEdge.dV = global_ahVertices[iV]; /* second vertex of edge */ if (global_fPrintInfo) { fprintf(stdout, "\tstructure - 1st global_dU = %d, global_V = %d\n", global_sEdge.dU, global_sEdge.dV); } /* /* swap U,V edge direction at random upon writing edge /* in an attempt to not write out a direct chain /* */ if (rand()%2) { /* Swap U and V */ sEdge.dU = global_sEdge.dV; sEdge.dV = global_sEdge.dU; } else { /* DON'T Swap U and V */ sEdge.dU = global_sEdge.dU; sEdge.dV = global_sEdge.dV; } if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",sEdge.dU,sEdge.dV); } fwrite((void *)&sEdge, sizeof(tEdge),1,hGraphFile); } /* else edge created by force and already written out */ } if (fClosed && edge_is_good(iFirst,iLast)){ /* connect the first vertex with the last /* to close the component /* */ sEdge.dU = global_sEdge.dU = global_ahVertices[iLast]; sEdge.dV = global_sEdge.dV = global_ahVertices[iFirst]; nEdges++; global_asNodeInfo[iLast].dDegree++; global_asNodeInfo[iFirst].dDegree++; /* sEdge.dV and global_sEdge.dV already set */ if (global_fPrintInfo) { fprintf(stdout,"u = %d, v = %d\n",sEdge.dU,sEdge.dV); } fwrite((void *)&sEdge, sizeof(tEdge),1,hGraphFile); } if (global_eStructure == star && global_dVertexDegree != 0 ) { /* star structure - only count two of the edges created. /* Let the center of the star possibly have a greater /* vertex degree the than the other nodes. /* */ nEdges = nEdges > 1 ? 2 : nEdges; /* make sure we created 2+ edges */ } if (nEdges <= *nEdgesLeft) { *nEdgesLeft -= nEdges; } else { *nEdgesLeft = 0; } if (global_fPrintInfo) { fprintf(stdout, "\tLeaving create_single_component() \n"); } } /**********************************************************************/ /* SYNOPSIS: */ void create_nComponents(int nComponents,int iStart,int iEnd,int dDensity, int dVertexDegree,FILE *hGraphFile) { /* /* create_nComponents(int nComponents,int iStart,int iEnd,int dDensity, /* int dVertexDegree,FILE *hGraphFile) /* creates N connected graph components. The node IDs range from /* iStart to iEnd. All components are written into the file hGraphFile. /* */ int nComponentsAdded,iNewComponents,nEmptyFiles=0; int nNodesPerComponent,nNewComponents,nEdgesPerComponent; tComponentInfo *asComponentInfo; /* Component info */ tEdge sNewEdge; int nNodes,i; /* Only using one level of Graph Function G(T,n,r). /* connect any extra components created to provide /* the proper number of components /* */ nNodes = 1+(iEnd-iStart); /* Set nNodes to the number of nodes per component desired. /* If nComponents == 0, then leave nNodes unchanged. /* */ nNodes = nComponents ? nNodes/nComponents : nNodes; /* if nComponents is 0, then the number of components created is undefined */ calculate_parameters(nComponents,nNodes,dDensity,dVertexDegree, &nNodesPerComponent, &nNewComponents,&nEdgesPerComponent); if (nComponents == 0 && nNewComponents == 1) { /* /* nComponents is undefined and and only one file /* is needed to create the graph. Also, tell /* fill_component() to create the vertices over the /* range specified (TRUE parameter). /* */ fill_component(iStart,iEnd, nEdgesPerComponent,dVertexDegree, FALSE,TRUE,hGraphFile); } else { static dTotalComponents = 1; /* /* Create more than one component. Pass nComponents as a boolean value /* to indicate whether or not one component is requested. It may be /* that nNewComponents is > 1 but nComponents is 0 due to memory constraints /* and nNodes requested. If nComponents is > 1, then fComponentsSelected /* will be TRUE in fill_component () /* */ asComponentInfo= (tComponentInfo *)malloc(nNewComponents*sizeof(tComponentInfo)); if (asComponentInfo == NULL) { /* malloc error */ fprintf(stderr, "create_nComponents() - Allocation Failed.\n"); exit(-1); } fprintf(stdout, "Creating Components #%d to #%d\n",dTotalComponents, dTotalComponents + nNewComponents - 1); dTotalComponents+=nNewComponents; for (iNewComponents=0; iNewComponents < nNewComponents; iStart+=nNodesPerComponent,iNewComponents++) { int dTmp; char zError[80]; if ( (asComponentInfo[iNewComponents].hFile = tmpfile()) == NULL) { sprintf(zError,"Error opening scratch file #%d",iNewComponents+1); perror(zError); exit(-1); } /* Tell fill_component() to create the vertices over the /* range specified (TRUE parameter). /* */ fill_component(iStart,iStart+nNodesPerComponent-1, nEdgesPerComponent, dVertexDegree,(tBoolean) nComponents, TRUE, asComponentInfo[iNewComponents].hFile); /* keep track of old dU,dV and connect components */ asComponentInfo[iNewComponents].v = (rand() %2) ? global_sEdge.dV : global_sEdge.dU; asComponentInfo[iNewComponents].dMarked = FALSE; /* generate a new seed for the next component */ srand(dTmp=rand()); } nComponentsAdded = nNewComponents - nComponents; for (i=0,iNewComponents--; i < nComponentsAdded; i++,iNewComponents--) { /* connect components by starting with a U vertex from the last /* component created and linking it to a V vertex from the second /* to last working backward /* */ fprintf(stdout, "Linking Component #%d with Component #%d\n", iNewComponents+1,i+1); sNewEdge.dU = asComponentInfo[iNewComponents].v; sNewEdge.dV = asComponentInfo[i].v; /* write the joining edge */ fwrite((void *)&sNewEdge, sizeof(tEdge),1,hGraphFile); } /* Now rewind scratch files containing components */ for (i=0;i < nNewComponents; i++) { fseek(asComponentInfo[i].hFile,0L, SEEK_SET); } /* Now write components to graph file */ while (nEmptyFiles < nNewComponents) { tEdge sEdge; int iComponent; size_t tmp; for (i=0,iComponent = rand() % nNewComponents ;i < nNewComponents; i++,iComponent=((++iComponent)%nNewComponents)) { if (fread((void *)&sEdge, sizeof(tEdge),1, asComponentInfo[iComponent].hFile) != 1 ) { if (!feof(asComponentInfo[iComponent].hFile)) { /* not empty */ fprintf(stderr, "Error reading scratch files.\n"); exit(-1); } else if (!asComponentInfo[iComponent].dMarked) { asComponentInfo[iComponent].dMarked = TRUE; nEmptyFiles++; } } else { if (tmp=fwrite((void *)&sEdge, sizeof(tEdge),1, hGraphFile) != 1) { fprintf(stderr, "Error writing graph file.\n"); exit(-1); } } } } /* Now close scratch files containing components. /* The scratch file will automatically be deleted /* upon closure. /* */ for (i=0;i < nNewComponents; i++) { fclose(asComponentInfo[i].hFile); } free(asComponentInfo); } } /**********************************************************************/ /* SYNOPSIS: */ void make_hard_graphs(int dLevel,int nComponents, int iStart,int iEnd, int dDensity,int dVertexDegree,FILE *hGraphFile) { /* /* make_hard_graphs(int dLevel,int nComponents, int iStart,int iEnd, /* int dDensity,int dVertexDegree,FILE *hGraphFile) is /* a recursive fuction that implements the function G(T,n,r) described /* by Guy Blelloch to Jan Prins. This funtion is my implementation of /* this functions as described by Jan Prins to me. The hard graphs /* have dLevel levels when first call. Each level has nComponents /* with nodes in the range of iStart to iEnd. The Density passed to /* make_one_graph is alternated at each level. Even levels are /* created with the density defined on the command line (or default). /* Odd levels have a density of 100-dDensity such that the graphs /* alternate from dense to sparse at each level. Level 0 is made up /* of N components with the density, structure, and number of nodes /* per component specified on the command line. /* */ FILE *ahFiles[nComponents]; int i,nNodes,nNodesPerComponent; /* A little more description for this routine: /* (Hopefully it agrees with the above text... :) /* /* The following is text extacted from mail Jan Prins sent me w.r.t. /* hard graphs as Guy Blelloch defined it to Jan. /* /* "Let G(T,n,r) be graphs with n nodes and sparsity r (however you want /* to define that), where the nodes are drawn from T. Now T is a set /* that can contain vertices and graphs. To connect a two nodes V,W that /* are themselves graphs, you pick a random edge between a node of V and /* a node of W. /* /* Now the hard graphs are ones in which G is applied recursively, so /* that we get say a sparse graph whose nodes are fairly dense graphs /* whose nodes are sparse graphs, ... etc." /* /* This implementation is of course, my interpretation of this function. /* The lowest level (level 0) consists of pow(nComponents,dLevels+1) /* components. These components have unique edges and node ranges. /* The next level up consists ncomponents of subgraphs s.t. each subgraph /* has nComponents nodes. The nComponents nodes come from nComponent unique /* nodes (one node per component. The subgraph is then created with a /* pseudorandom structure. The density of each subgraph is dependent on /* the level of recursion and the dDensity defined. Even Level subgraphs /* have density = dDensity. Odd level subgraphs have 100 - dDensity. Of /* course each level from 1 to dHardLevel is a subgraph of nComponents /* of Subgraphs from lower levels. Hense, the recursive definition. /* */ nNodes = 1+(iEnd-iStart); nNodesPerComponent = nNodes/nComponents; if (nNodesPerComponent==0) { dLevel = 0; /* abort depth traversal - ran out of nodes */ nNodesPerComponent=2; /*make sure each component has at least 2 nodes*/ } /* May get some extra nodes that are not part of a component */ nNodes = nComponents*nNodesPerComponent; if (dLevel==0) { /* Lowest Level - create the n Components in the graph file */ create_nComponents(nComponents,iStart,iEnd,dDensity, dVertexDegree,hGraphFile); } else { char zError[80]; int iStartRange,iEndRange; /* Create the nComponents that are each hard graphs */ for (i=0; i < nComponents; i++) { /* create N Components and combine to one file */ iStartRange=iStart + (i*nNodesPerComponent); iEndRange=iStart + ((i+1)*nNodesPerComponent) - 1; if ( (ahFiles[i] = tmpfile()) == NULL) { sprintf(zError,"Error opening scratch file at Level %d",dLevel); perror(zError); exit(-1); } /* recursively calls itself to make each level */ make_hard_graphs(dLevel-1,nComponents, iStartRange,iEndRange, dDensity, dVertexDegree,ahFiles[i]); } /* Now make this a hard graph */ /* Density alternates at each level */ if ((dLevel % 2) == 1) { /* odd Level */ dDensity = 100-dDensity; /* inverse density for odd levels */ } /* output is put in hGraphFile */ make_one_graph(nComponents,dDensity,ahFiles,hGraphFile); for (i=0; i < nComponents; i++) { fclose(ahFiles[i]); /* close scratch files */ } } } /**********************************************************************/ /* SYNOPSIS: */ void make_one_graph(int nComponents, int dDensity, FILE *ahFiles[],FILE *hGraphFile) { /* /* make_one_graph(int nComponents, int dDensity, /* FILE *ahFiles[],FILE *hGraphFile) is called /* make_hard_graphs() to extract one node from each of N components, /* and make a psuedorandom graph from these nodes with density = dDensity. /* Then this graph and the N components are written to hGraphFile. /* */ int nEdges,i,nEmptyFiles=0; float fltDensity; char afEmpty[nComponents]; /* create a new array of vertices, but don't initialize them */ create_vertices(1,nComponents,FALSE); /* Now load the vertices table by getting one vertex from each component */ for (i=0; i < nComponents; i++) { fseek(ahFiles[i],0L, SEEK_SET); if (fread((void *)&global_ahVertices[i], sizeof(int),1, ahFiles[i]) != 1) { fprintf(stderr, "Error reading scratch files.\n"); exit(-1); } } /* Create one graph with these edges - putting it in hGraphFile. /* Pass 0 for dVertexDegree => varying degree graph at this level. /* Let the number of components produced at this level develop /* randomly (i.e, don't specify one component - 1st FALSE parameter). /* Tell fill_component() NOT to create the vertices over the /* range specified (2nd FALSE parameter). /* */ fltDensity =((float)dDensity)/100.0; nEdges = (int)(((nComponents*(nComponents-1))/2)*fltDensity); if (nEdges == 0) { /* need at least one edge */ nEdges = 1; } fill_component(1,nComponents, nEdges,0,FALSE,FALSE,hGraphFile); /* Now Create one graph by moving the edges from ahFiles[] /* to hGraphFile. /* First rewind scratch files containing components /* */ for (i=0;i < nComponents; i++) { fseek(ahFiles[i],0L, SEEK_SET); afEmpty[i] = FALSE; } /* Now write components to graph file */ while (nEmptyFiles < nComponents) { tEdge sEdge; int iComponent; size_t tmp; for (i=0,iComponent = rand() % nComponents ;i < nComponents; i++,iComponent=((++iComponent)%nComponents)) { if (fread((void *)&sEdge, sizeof(tEdge),1, ahFiles[iComponent]) != 1 ) { if (!feof(ahFiles[iComponent])) { /* not empty */ fprintf(stderr, "Error reading scratch files.\n"); exit(-1); } else if (!afEmpty[iComponent]) { afEmpty[iComponent] = TRUE; nEmptyFiles++; } } else { if (tmp=fwrite((void *)&sEdge, sizeof(tEdge),1, hGraphFile) != 1) { fprintf(stderr, "Error writing graph file.\n"); exit(-1); } } } } }