[Lemon-user] max number of arcs in ListDigraph

[Kovács Péter]

Hi,

This issue has nothing to do with the ListDigraph implementation, since 
the arcs are not added to the graph structure.

As far as I see, there are two problems here:
   1. In the for loop, you must use < instead of <=!
   2. You allocate large arrays on the stack, which may be the reason of 
the problem. I tried this code and got segmentation fault (even if I 
fixed the above issue). However, using std::vector or a dynamically 
allocated array (ListDigraph::Arc* arc; arc = new 
ListDigraph::Arc[nArcs]; ... delete [] arc;), everything works fine. 
Note that these solutions use the heap space for allocating the arrays 
instead of the stack.

I strongly suggest you to use std::vector instead of arrays in virtually 
all cases.

Anyway, there is no limit for the size of ListDigraph and other graph 
structures in their implementation. I often work with huge graphs 
containing e.g. 30-40 millions of arcs and I haven't encountered any 
issues yet.

Best regards,
Peter


On 2012.09.25. 19:56, Leandro Callegari Coelho wrote:
> Hello list,
>
> What is the max number of arcs that a ListDigraph can take?
>
> Take a look at the following example:
>
>
> -----------------------------------------
> #include <lemon/list_graph.h>
> #include <lemon/network_simplex.h>
> #include <unistd.h>
> #include <cstdlib>
> #include <iostream>
> #include <fstream>
> #include <limits.h>
>
> using namespace lemon;
> using namespace std;
>
> typedef ListDigraph::Node Node;
> typedef ListDigraph::Arc Arc;
> typedef ListDigraph::NodeIt NodeIt;
> typedef ListDigraph::ArcIt ArcIt;
> ListDigraph g;
>
> int main(int argc, char *argv[])
> {
>
>     int nNodes = 5000;
>     ListDigraph::Node node[nNodes];
>     for (int i=0; i<=nNodes; ++i)
>        node[i] = g.addNode();
>
>
>     cout << "\n\t Max value of integer is " << INT_MAX << endl;
>     int nArcs = 2000000;
>     cout << "nArcs is equal to " << nArcs << endl;
>     ListDigraph::Arc  arc[nArcs];
>     cout << " All arcs are defined. "<< endl;
>
>     ListDigraph::ArcMap<double>  costMap(g);
>     ListDigraph::ArcMap<int>    lowerMap(g);
>     ListDigraph::ArcMap<int>    upperMap(g);
>
>     cout << "\n\n All is done!" << endl;
>     return (0);
> }
> ------------------------------------------
>
> if I set nArcs = 2100000, then the program crashes in ListDigraph::Arc
> arc[nArcs];
>
> In the worst case I know I would need something like 5 million arcs. It
> certainly is not a limit of the int type, nor a memory issue (at this time).
>
> Regards,
> Leandro
>
> --
>
> LCC
>
> "Absence of evidence is not evidence of absence"
> Carl Sagan (1934 - 96)
>