[GRASS-dev] Network Analysis

GRASS GIS GRASS GIS developer
1

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

2

Hi Daniel,

nice job you did with the new network analysis modules! Obviously you have understood dglib, this is very good news :slight_smile: 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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev

3

Hello Markus,

Thanks for the comments. I will definitely add your suggestion to the
code. I should have some time to do it this or next week.

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?

Daniel

On Mon, Sep 14, 2009 at 12:31 PM, Markus Metz
<markus.metz.giswork@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 :slight_smile: 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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev

4

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@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 :slight_smile: 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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev