Dear Martin,
Sorry for delayed response, past two weeks were filled with
conferences and presentations. Let me share my experiences with large
scale routing on JUNG networks with you.
The biggest network we routed was 33000 nodes, 70000 edges
transportation graph. 16GB machine was able to handle JUNG's Dijkstra
and service repeated calls for paths with reasonable speed. As most of
paths were "local", I would expect that in general cache necessary to
handle such a graph would be larger.
One thing we experimented with was to switch to truncated
breadth-first search and caching of only requested paths. I attach a
sample modification of JUNG's code we played around. This approach
sacrifices sophistication for better control over speed / memory
trade-off.
We assume that your SimState can provide horizon for the
TruncatedDistanceLabeller. The code for TruncatedShortestPath
implements truncated breadth-first search, but as far as I see it does
not implement the limited caching. Let me know if such a solution
would be of interest to you.
Best regards
Maciej
On Mon, Nov 8, 2010 at 12:30 PM, Martin Pokropp
<[log in to unmask]> wrote:
> Dear Sean, Dear Mr. Balan, Mr. Panait and Mr. Latek,
>
> increasing the stack size does the job for the task of finding the
> components of the network with
>
> sim.field.network.stats.ConnectivityStatistics.getConnectedComponents(network)
>
> But the biggest component (size about 29000 nodes) now seems to be too big
> for the shortest path algorithms in
>
> sim.field.network.stats.NetworkStatistics.getMeanShortestPath(giantComponent,
> metric)
>
> I tried out very high heap sizes (2000M). The task goes on for minutes,
> then a "java.lang.OutOfMemoryError: java heap space" is thrown.
>
> Do you think that the Jung package would do the job here, or is the task
> generally too complex (I'm using an ordinary desktop pc)?
>
> Regards,
>
> Martin
>
>
>
>
>
>
> 2010/11/8 Sean Luke <[log in to unmask]>
>>
>> Martin, the right person to look into this is Gabriel Balan, and to a
>> lesser extend Liviu Panait (whom I am cc:ing). They were the two who put
>> this package together way back when. Gabriel is moving to New Hampshire so
>> may be in radio silence right now however.
>>
>> In the meantime we need to nail down whether or not it's a recursion bug
>> or a um, misfeature. Try increasing the stack size in Java. This is done
>> with the -Xss parameter. The default value is probably 512K. Try
>> increasing it considerably, like
>>
>> java -Xss16392k ...
>>
>> You should also increase the heap I guess. I'd do something like:
>>
>> java -Xss16392k -Xmx500M -Xms500M ...
>>
>> If you can't find a stack size which will complete the task, then it's
>> possibly the case that we're seeing a recursion bug here rather than a
>> maximal graph limit.
>>
>> Your other option is to go with Jung. Now beware: I believe that Jung
>> isn't serializable, so you may be stuck unable to checkpoint out. I am
>> cc:ing Maciej Latek, who knows a lot about jerry-rigging MASON to Jung.
>>
>> Sean
>>
>>
>> On Nov 8, 2010, at 10:52 AM, Martin Pokropp wrote:
>>
>>> Dear Sean, Dear Mason Users,
>>>
>>>
>>> For my simulated undirected network I intend to use the additional
>>> socialnets package provided with Mason. My network has 30000 nodes and is
>>> sparse with about 6 edges per node.
>>>
>>> As there are isolated nodes, I cannot get the mean Shortest Path of the
>>> whole network. Instead, I'm trying to analyse the biggest connected
>>> component by using
>>>
>>>
>>> sim.field.network.stats.ConnectivityStatistics.getConnectedComponents(network)
>>>
>>> Unfortunately the VM throws multiple stack overflow errors:
>>>
>>>
>>> Exception in thread "main" java.lang.StackOverflowError
>>> at sim.field.network.Network.getNodeIndex(Network.java:618)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:220)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222)
>>> at
>>> sim.field.network.stats.ConnectivityStatistics$ConnectedComponentFactory.exploreU(ConnectivityStatistics.java:222
>>> ...
>>>
>>> I guess that there are too many recursions and the getConnectedComponents
>>> method is not appropriate for networks such as mine?
>>>
>>> Best Regards,
>>>
>>> Martin
>>>
>>>
>>>
>>>
>>>
>
>
|
