Large scale problem with array and linked list

[shmokarami]

Hello everybody
I have a question, can anyone help me?
I write a program to solve "Shortest Path Problem"
and use an array of linked list to store the parameters (the nodes and arcs of network),
my program works correctly when the number of nodes (the size of array) is less than 150,
But it is interrupted for large scale networks (for example 2000 nodes)
and report this error:
"Windows has triggered a breakpoint in Network1.exe.

This may be due to a corruption of the heap, which indicates a bug in Network1.exe or any of the DLLs it has loaded.

This may also be due to the user pressing F12 while Network1.exe has focus.

The output window may have more diagnostic information."
What should I do?

[LB]

Have you checked your program for possible mistakes? If possible, could you post your code and point out where you think the problem may be?

[S G H]

Well if you also output what's in the output window before this message it could be of more help.

[shmokarami]

Thanks for your attention;
I copied the output window here:
"'Network1.exe': Loaded 'C:\Windows\System32\msvcr100d.dll', Symbols loaded.
Critical error detected c0000374
Windows has triggered a breakpoint in Network1.exe.

This may be due to a corruption of the heap, which indicates a bug in Network1.exe or any of the DLLs it has loaded.

This may also be due to the user pressing F12 while Network1.exe has focus.

The output window may have more diagnostic information.
"

[shmokarami]

this program work correctly for n<=1200,
the program is:
"//#include "stdafx.h"
#include <iostream>
#include <time.h>
//#include <stdio.h>
//#include <stdlib.h>
#include <math.h>
#include <fstream>

using namespace std;
//using namespace System;

class arc
{
// const int M=1000000;
public:
arc(int Id=0, int co=1000000, int tr=1000000, int co_scaled=1000000, arc* ne=0) : ID(Id), cost(co), transit_time(tr), cost_scaled(co_scaled),next(ne) {}

int ID; // The tail(nodes) or head(B) of arc.
int cost;
int cost_scaled;
int transit_time;
arc* next;
};
class path{
public:
path(int ID=0, int d=1000000, int pr=0) : ID(ID), d(d), pr(pr) {}

int ID; // The ID of node.
int d; // The distance from source.
int pr; // the pred
};

class Network{
public:
int n; //number of nodes.
int s; //source
int t; // sink
int T; //time horizon
void nodes_initials();
void creat_Network();
void add_arc_nodes(int , arc );
void add_arc_B(int , arc );
void print_cost( );
void print_cost_B( );
int Shortest_Path_Dijkstra(int ,int );
int Find_Min_Temp(int [],int );
int CSP_FPTAS(double ,double ,double );
int CSP( );
void compute_cost_scaled(double );
int max_cost( );
arc **nodes;
arc **B; //B[i} shows the incoming arc of the node i;

private:

};

void Network::nodes_initials(){

cout<< "Please enter the nmber of nodes:"<<endl;
cin>> n;
cout<< "Please enter the ID of source:"<<endl;
cin>> s;
cout<< "Please enter the ID of sink:"<<endl;
cin>> t;
cout<< "Please enter the time horizon:"<<endl;
cin>> T;
nodes=new arc *[n+1];
B=new arc *[n+1];
for (int i=0; i<=n; i++)
{
nodes[i]=new arc;
B[i]=new arc;
}
}
void Network::add_arc_nodes(int i, arc a) // i is the head of arc a.
{
arc* q;
if (nodes[i]->ID==0)
{
nodes[i][0]=a;
}
else
{ int count=1;
q=&nodes[i][0];
while (q->next!=0)
{
q=q->next;
count++;
}
nodes[i][count]=a;
nodes[i][count-1].next=&nodes[i][count];

}

}

void Network::add_arc_B(int j, arc a) // i is the head of arc a.
{
arc* q;
if (B[j]->ID==0)
{
B[j][0]=a;
}
else
{ int count=1;
q=&B[j][0];
while (q->next!=0)
{
q=q->next;
count++;
}
B[j][count]=a;
B[j][count-1].next=&B[j][count];

}

}
void Network::creat_Network() // read the network's parameter from data file.
{
int i;//head of arc.
int j;//tail of arc.
int co;// cost of arc.
int tr; //transit time of arc.

ifstream file;
file.open("Data.txt", ios::in);
while(file >> i >> j >> co >> tr)
{
arc a(j, co, tr);
add_arc_nodes(i,a);
arc b(i, co, tr);
add_arc_B(j,b);
}
file.close();
}



int Network::Shortest_Path_Dijkstra(int s,int t)
{
int* permanent;
int* temp;
int* select;
int* pred;
const int M=1000000;
permanent=new int[n]; //the permanent distance labels
temp=new int[n]; //the temp distance labels
select=new int[n]; //determines the permanent nodes.
pred=new int[n]; //the predecessors
for(int i=1; i<=n; i++) //initial assignment
{
permanent[i]=temp[i]=M;
pred[i]=select[i]=0;
}
permanent[s]=0;
select[s]=1;//initial assignment
pred[s]=s;


int j=s;
arc* q;
while (select[t]==0)
{
q=nodes[j];
while (q!=0 && q->ID!=0)
{ int k=q->ID;
if ( select[k]==0) // k is not permanet yet.
{
int d=q->cost;
if (temp[k]>=permanent[j]+d)
{
temp[k]=permanent[j]+d;
pred[k]=j;
}
}
q=q->next;
}
j=Find_Min_Temp(temp,n);
select[j]=1;
permanent[j]=temp[j];
temp[j]=M+1;
}
return permanent[t];
}


int Network::Find_Min_Temp(int temp[],int n)
{const int M=1000000;
int k;
int min=M;
for(int i=1; i<=n; i++)
if (temp[i]<min)
{
min=temp[i];
k=i;
}
return k;
}




int Network::CSP( )
{
int const M=1000000;
int upper=n*max_cost();
int** D; //D[i][c] shows the quickest path from s to i with cost of at most c;
int* pred;
D=new int *[n+1];
pred=new int [n+1];
for (int i=0; i<=n; i++){ D[i]=new int; pred[i]=0; }
arc* q=new arc;
for(int j=1; j<=n; j++) D[j][0]=M;
D[s][0]=0;
for(int c=1;c<=upper;c++)
{
for(int i=1;i<=n;i++)
{
D[i][c]=D[i][c-1];
q=&B[i][0];
if (q->ID!=0)
{
while(q!=0)
{
if(q->cost<=c)
if(q->transit_time+D[q->ID][c-q->cost]<D[i][c])
{
D[i][c]=q->transit_time+D[q->ID][c-q->cost];
pred[i]=q->ID;
}
q=q->next;
}

}
}
if(D[t][c]<=T) return(c);}
return(0);
}


void Network::compute_cost_scaled(double S)
{
arc* q;
for (int j=1; j<=n; j++)
if (B[j]->ID!=0)
{
q=&B[j][0];
while (q!=0)
{
q->cost_scaled=int(floor(q->cost/S))+1;
q=q->next;
}
}
}


int Network::max_cost( )
{
int const M=1000000;
int c=0;
arc* q;
for (int j=1; j<=n; j++)
{
if (B[j]->ID!=0)
{
q=&B[j][0];
while (q!=0)
{
if (q->cost>c) c=q->cost;
q=q->next;
}

}
}
return(c);
}

int main()
{ Network x;
int i;
x.nodes_initials();
x.creat_Network();
i=x.CSP();
cout<<i<<endl;

cin>>i;
return 0;
}
"


I know the problem occurs at "creat_Network()" function.
Thank you so much!

[S G H]

All I needed was the "Critical Error Detected" but I expected MSVC to be more verbose. Got to test this code to see the results. Also, next time it happens you will post some code, can you post it within the code tags? While you have your code selected, press the "<>" button on the right. This allows for good tabbing.
Example:

int a = 0; // Without Code Tags

int a = 0; // With Code Tags 

Oh, and, What should I input? Lol.
Also that may be going to be useless, I don't have that Data.txt... Going to take a look at the code anyways.

First thing I notice:

// nodes_initials()
nodes=new arc *[n+1]; // is this "n+1" on purpose? If you really meant "n" and not "n+1" see the next comment
B=new arc *[n+1];
for (int i=0; i<=n; i++) // If you meant "n", this should become "i<n" instead of "i<=n".
{
/* ... */
}

[cire]

Here, you treat nodes[i] as if it were an array.

void Network::add_arc_nodes(int i, arc a) // i is the head of arc a.
{
    arc* q;
    if (nodes[i]->ID==0)
    {
        nodes[i][0]=a;
    }
    else
    { 
        int count=1;
        q=&nodes[i][0];
        while (q->next!=0)
        {
            q=q->next;
            count++;
        }
        nodes[i][count]=a;
        nodes[i][count-1].next=&nodes[i][count];

    }

}

Here, you allocate memory for a single node at nodes[i].

void Network::nodes_initials(){

    cout<< "Please enter the nmber of nodes:"<<endl;
    cin>> n;
    cout<< "Please enter the ID of source:"<<endl;
    cin>> s;
    cout<< "Please enter the ID of sink:"<<endl;
    cin>> t;
    cout<< "Please enter the time horizon:"<<endl;
    cin>> T;
    nodes=new arc *[n+1];
    B=new arc *[n+1];
    for (int i=0; i<=n; i++)
    {
        nodes[i]=new arc;
        B[i]=new arc;
    }
}

[shmokarami]

Thank you, I apologize, It is my first time that I participant in a forum,
I try to be better next time!!! :-)
I use "n+1"instead "n" to set coordination index of array with data in Data file.

the small example of Data.tex is as follows:
1 2 5 6
1 3 10 1
2 3 1 4
2 4 3 2
3 4 1 3

[shmokarami]

here n=4,
source is 1
sink is 4
time horizon is 9

[shmokarami]

nodes is an array of linked list,
it is dynamic array.

[cire]

nodes is an array of linked list,
it is dynamic array.

If nodes is a dynamic array of linked lists, why are you trying to use it as an array of arrays? Where is the memory allocation for new nodes in the lists?

[shmokarami]

I don't understand what you mean exactly,
I think memory allocation for node is in

nodes=new arc *[n+1];
    B=new arc *[n+1];
    for (int i=0; i<=n; i++)
    {
        nodes[i]=new arc;
        B[i]=new arc;
    }

Could you please let me know which commands should be changed?

[cire]

I think memory allocation for node is in

Yes, yes. I was asking about allocation for new nodes.

We see there that you allocate memory for one arc. (Why do I feel like I'm repeating myself?) But you say that nodes[i] is a linked list. (And you treat nodes[i] in places as if it were an array.) Well, lists are generally capable of holding more than on element. My question is: When a new element is added to a list, where is the allocation for that element? The answer: Nowhere. You write to memory you shouldn't be writing to every time that happens.

By way of example, I would expect add_arc_nodes to look something like:

void Network::add_arc_nodes(int i, arc a) // i is the head of arc a.
{
    if ( nodes[i]->ID == 0 )   // list is unoccupied
        *nodes[i] = a ;
    else
    {
        arc* tail = nodes[i] ;

        //navigate to the end of the list
        while ( tail->next )
            tail = tail->next ;

        // behold:  memory allocation for new elements.
        tail->next = new arc(a) ;
    }
}

Note that B suffers from problems similar to nodes.

You also seem to think you need an array of pointers every time you use dynamic memory. That's simply not the case. There is not one delete (or smart pointer) in all of your code, although you're fairly liberal with dynamic allocation. So your program is one gigantic memory leak. CSP and shortest_path are leaking memory like a sieve.

You would do very well to use standard library containers rather than managing memory on your own.

[shmokarami]

I thank you for your consideration