Hi Everyone, Good day to you all.
I am solving a problem : to Generate a Random Network. I hv divided the problem into two parts. First generate a Graph, then from the graph from a network.
Here the code generates a random graph.
User Gives n ->no. of nodes , and the prog. generates the graph with n nodes.
Constraints:
1. No Self Loop
2. Each node must have atleast 3 edges
3. Each node can have at max 7 edges.
-------------------------------------------------
Here is what the problem is. I have used int in all, as a result the program runs fine for an input ( n ) < 32768 . But I would like the program to run for input of an even larger number. For that i used the Replace all function of my IDE ( code::blocks) and replaced all int with long . Except the MAIN of course.
No Luck. Still the program goes into infinte loop for n>32768.
I Know why that happens, int resets to n when input is 32768+n .
So changing it to Long should have solved the problem. I thought so. :( :( :( :(
---------------------------------------------------
Now what the program does :
Struct adj -> The Adjacency List. Adj shall store the node number, and the number of edges node n has, and the address of next nodes.
struct nodes ->Stores the node number and the edge length (from n) and the address of next nodes.
edc : Global , tracks how many nodes has atleast 3 edges.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Function :
randomed : Generates Random no. based on lower bound a, upper bound b ( for the edge length );
checknd : checks whether a node exists in the list, if not adds it, else discards it.
disp : outputs the adjacency list to a file.
-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-

#include<iostream>
#include<ctime>
#include<fstream>
using namespace std;
struct nodes;
struct adj
{
    int ndnm;
    int nmed;
    nodes *next;
};
struct nodes
{
    int ndnm;
    int edln;
    nodes *next;
};
int edc=0; // counts no of nodes hving atleast 3 edges
int randomed(int a,int b);
void checknd(nodes *t,adj *list,int u, int v, int edlength);
void disp(adj *list,int n);
int main()
{
   
    t=time(0);
    srand((unsigned int) t);
    cout<<"\nEnter the number of nodes ... :";
    int n;
    cin>>n;
    adj *list=new adj[n+1];
    int i=0;
    for(i=0;i<=n;i++)
    {
        list[i].ndnm=i;
        list[i].nmed=0;
        list[i].next=NULL;
    }
    cout<<"Adjacency List Initialization Formation finished.\n";
 /*
    for(i=0;i<=n;i++)
    {
        cout<<"Node Num :"<<list[i].ndnm<<"\n";
        cout<<"Number of edges :"<<list[i].nmed<<"\n";
        cout<<"Address Stored in *next :"<<list[i].next<<"\n";
    }
*/
    int n1,n2;
    cout<<"\nEnter Edge Length Limit :\n";
    cout<<"\nEnter lower bound :";
    cin>>n1;
    cout<<"\nEnter upper bound :";
    cin>>n2;

    int count=0,edlength;        // Counts the no. of nodes having atleast 3 edges.
    int u=0,v=0;                //Stores the Node number .... Randomy generated
    nodes *temp,*temp2;
    while(edc!=n)
    {
        u=rand()%n+1;
        v=rand()%n+1;
        if(u!=v)
        {
            if(list[u].nmed<7 && list[v].nmed<7)
            {
                edlength=randomed(n1,n2);
                if(list[u].nmed==0)
                {
                    list[u].next=new nodes;
                    temp=list[u].next;
                    temp->ndnm=v;
                    temp->edln=edlength;
                    temp->next=NULL;
                    list[u].nmed++;
                }
                else
                {
                    checknd(list[u].next,list,u,v,edlength);
                }
                if(list[v].nmed==0)
                {
                    list[v].next=new nodes;
                    temp2=list[v].next;
                    temp2->ndnm=u;
                    temp2->edln=edlength;
                    temp2->next=NULL;
                    list[v].nmed++;
                }
                else
                {
                    checknd(list[v].next,list,v,u,edlength);
                }

            }
        }
    }
    disp(list,n);
    cin.ignore();

    return 0;
}

//Now the code of the function which shall generate the length of the edges. randomly
int randomed(int a, int b)
{
    return (a+rand()%(b-a)+1);
}

//Function which checks the adjacency list of each node and finds whether
//an edge exist to the node , if not then adds the edge. :)
void checknd(nodes *t,adj *list,int u,int v,int edlength)
{
    int flag=0;
    nodes *t2; // Stores the Node which Has next as NULL;
    do
    {
        if(t->ndnm==v)
        {
            flag=1;
        }
        if(t->next==NULL)
            t2=t;
        t=t->next;
    }
    while(t!=NULL);
    t=t2;
    if(flag==0)
    {
        t->next=new nodes;
        t=t->next;
        t->next=NULL;
        t->ndnm=v;
        list[u].nmed++;
        if(list[u].nmed==3)
        {
            edc++;            // Here the no. of nodes having 3 edges atleast are incremented. Global edc.
        }
        t->edln=edlength;
    }
}

void disp(adj *list, int n)    // Function which displays the output to a File.
{
    ofstream file;
    file.open("d:\\illusionist\\node.txt");
    int i=0;
    nodes *temp;
    for(i=1;i<=n;i++)
    {
        temp=list[i].next;
        file<<"\n"<<list[i].ndnm<<"\t---->";
        do
        {
            file<<" "<<temp->ndnm<<"-";
            temp=temp->next;
        }
        while(temp);
    }
}

I would really like to know how can i make this program accept and run with bigger input. :)
Your time reading my post is most appreciated. Thanks a lot for your time.
Regards
MiniGWeek

Recommended Answers

All 3 Replies

you are using a 16 bit compiler. which one?

I am using Code::Blocks editor, and the minigw compiler that comes along with it. ALso Just tested it with Visual CPP Express Edition 2005 , same problem.

lol
My dilemma is solved. here is why the above was not working for an input greater than 32768 .. because rand() is a pseudorandom number generator between the seed [ set by srand() or the default if u do nt use srand() ] and RAND_MAX . RAND_MAX is an integer constant defined in cstdib.
Its value is 32767. As a result all the nodes randomly generated , lied between 32678. it seems i need to define my own function usinf rand() such that for an input greater than 32768 , it caters to that.
Thank u all for dropping by :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.