[GRASS-dev] Network Analysis

[Markus Metz]

Daniel Bundala wrote:
> Regarding the bug: It is definitely a bug and I will have a look at
> it. But I think that it would be better if dglib supported multiple
> edges between nodes. Not only it is probably intended behaviour if
> there are multiple lines between nodes, but in some cases (e.g.,
> v.net.flow module), you do not want the minimum but maximum cost edge.
> In fact, you want all edges. There should not be any substantial
> problem with multiple edges, but I am not sure whether dglib supports
> them. What do you think?
>   
I guess that dglib supports multiple edges, because each edge (at least 
in Vect_net_build_graph()) is added with a unique ID, consequently there 
could be several edges connecting the same two nodes. If not that would 
mean that a new edge would replace an old edge connecting the same two 
nodes? With the help of your example, I see now that it would make sense 
to have multiple edges. I haven't come around yet to create a test 
vector for BUG2 and see whether dglShortestPath() really returns the 
shortest path or uses the edges inserted last even if they are more 
costly. Same for dglShortestDistance. I guess that determines where and 
how to fix BUG2, on module level or on library level.

Markus M

> Daniel
>
> On Mon, Sep 14, 2009 at 12:31 PM, Markus Metz
> <markus.metz.giswork at googlemail.com> wrote:
>   
>> Hi Daniel,
>>
>> nice job you did with the new network analysis modules! Obviously you have
>> understood dglib, this is very good news :-) Maybe you could have a look at
>> BUG2 [1] for network analysis? I have an idea but am not sure if it is
>> correct. There is also a wish to have costs as type double instead of int,
>> but it seems that this means a lot of modification of dglib. What do you
>> think?
>>
>> Regarding the new modules, I have a suggestion: all modules use
>>
>>   nlines = Vect_get_num_lines(&In);
>>   for (i = 1; i <= nlines; i++) {
>>       int type = Vect_read_line(&In, Points, Cats, i);
>>       ...
>>   }
>>
>> or similiar. Vect_read_line exits with a fatal error for dead lines, adding
>>
>>   if (!Vect_line_alive(&In, i))
>>       continue;
>>
>> before Vect_read_line() would avoid that. See e.g. Vect_copy_map_lines() in
>> Vlib/map.c.
>>
>> Best,
>>
>> Markus M
>>
>> [1] https://trac.osgeo.org/grass/ticket/584
>>
>>
>> Daniel Bundala wrote:
>>     
>>> Hello everyone,
>>>
>>> during the past few months I worked on a Google Summer of Code project
>>> to extend GRASS network functionality. I sent a final summary report
>>> to OSGeo GSoC mailing list. Since there are people not subscribed to
>>> that mailing list who might be interested in the project, I was asked
>>> to sent the report to this list and stress the paragraph on inclusion
>>> into the main GRASS....
>>>
>>>
>>>
>>>
>>> The goal of my project, which I have successfully accomplished, was to
>>> implement modules for network analysis. This includes basic methods
>>> such as: strongly and weakly connected components, minimum spanning
>>> trees, bridges and articulation points as well as more complicated and
>>> advanced tools for calculating maximum flow, minimum cut or
>>> k-connectivity in a network. There is also a bunch of modules finding
>>> shortest paths in a network. One module computes all-pairs shortest
>>> paths, another finds the shortest paths between nodes and a given set
>>> of features and, finally, there is a module that finds fastest paths
>>> using timetables.
>>> All module follow standard GRASS conventions. This holds both for the
>>> code and user interface. I also tried to make the modules as flexible
>>> as possible -- each of them accepts a wide range of parameters, which
>>> can alter the behaviour. Moreover, the algorithms are separated from
>>> the modules and stored in a library. An effect of this is that the
>>> modules are mostly straightforward (only exception is v.net.timetable)
>>> and consist only of reading the input, calling a few library functions
>>> and writing an appropriate output. Another advantage of this approach
>>> is that the “core functionality” can be reused in other modules. Much
>>> more about the modules (a lot of pictures and link to code) can be
>>> found at mi wiki: http://grass.osgeo.org/wiki/GSoC_Network_Analysis.
>>>
>>> I have learnt a lot about GRASS and its vector architecture however
>>> this was my second summer working on vector modules. This was the
>>> first time I really had to work with attributes data and so I have
>>> learnt a lot about the data management. At the beginning, I found the
>>> system with many layers and multiple categories a bit complicated but
>>> in the process of developing the modules I have discovered its
>>> expressiveness and enormous power.
>>>
>>> At the moment, my code is stored in add-ons repository. I already know
>>> about several people using the modules for their work and I hope that
>>> the modules will eventually be integrated into the main distribution
>>> and bring eternal joy to all GRASS users.
>>>
>>> Finally, I want to thank my mentor (Wolf Bergenheim), OSGEO project
>>> coordinator (Wolf Bergenheim) and the whole GRASS, OSGeo and Google
>>> Summer of Code community for support, T-shirts and for doing a
>>> wonderful job! Thanks!
>>> Daniel
>>> _______________________________________________
>>> grass-dev mailing list
>>> grass-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/grass-dev
>>>
>>>
>>>       
>
>