[Lemon-user] Fwd: Re: max number of arcs in ListDigraph

[Kovács Péter]

-------- Original Message --------
Subject: Re: [Lemon-user] max number of arcs in ListDigraph
Date: Tue, 25 Sep 2012 17:05:31 -0400
From: Leandro Callegari Coelho <leandro.cc at gmail.com>
To: Kovács Péter <kpeter at inf.elte.hu>

Thanks a lot Peter, I appreciate your answer. (And BTW, I appreciate the
support of the LEMON mailing list.)

Leandro


Leandro C. Coelho
"Absence of evidence is not evidence of absence"
Dr. Carl Sagan (1934-96)


On 12-09-25 4:39 PM, Kovács Péter wrote:
> 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)
>>
>