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
