[SoC] GRASS - Network Analysis - report

[Daniel Bundala]

Dear all,

After a break I took because of my exams, I have started working on my
GSoC project. I worked mostly on the (v.net.) flow module and related
issues. I have extended the module so that it is possible to specify
more than one point as the source and sink. Also, the module finds a
minimum cut (edges with minimum capacities separating source(s) from
sink(s)) in the network. Here is a picture of this:
http://people.ksp.sk/~dano/grass/mfmult.png. Red crosses are sources
and green ones are sinks (maybe, it is the other way round...) Blue
edges correspond to small flow, green to medium flow and red to high
flow. And the yellow edges are a minimum cut.

If the capacities of all edges are the same, minimum cut corresponds
to the smallest number of edges separating two sets of vertices. By
constructing an appropriate graph, it is also possible to find the
smallest set of vertices separating sources and sinks. I have written
code that does exactly this. In the next picture, orange points
separate red points from green points:
http://people.ksp.sk/~dano/grass/large.png. The next two pictures show
details of the previous one:
http://people.ksp.sk/~dano/grass/detail1.png,
http://people.ksp.sk/~dano/grass/detail2.png. For the next week, I
plan to turn this code into a module as the current version is more
useful for debugging than using. Also, I will extend it to handle
"node capacities". And I hope I will have time to start working on
another new module.

Daniel

This report appears also on my wiki page:
http://grass.osgeo.org/wiki/GSoC_Network_Analysis