[SoC] GRASS - Network Analysis, 1st week report

[Daniel Bundala]

Hello list,

I have agreed with my mentor, Wolf, to start working on my GSoC
project bit earlier so that I can concentrate more on the exams later.
Well, earlier means last Saturday and so this is my first week report.
Just a short introduction: I am Daniel, 3rd year at Oxford doing
Mathematics and Computer Science and some of you may remember me as
the student working on GRASS v.generalize module two years ago. My
project this year is about extending GRASS network/vector
functionality by writing a couple of modules. I have created a wiki
page: http://grass.osgeo.org/wiki/GSoC_Network_Analysis, which
contains some useful information such as this email and a link to the
abstract.

Anyway, after doing boring, but essential, tasks such as downloading
and compiling GRASS (I use 6.4 developer branch) I have done more
interesting stuff. I wrote a module for computing weakly and strongly
connected components. Using this module, I found errors in the
standard North Caroline datset. At least, I think that these are
errors. For example, if you zoom to [north: 232051.61663403  south:
230521.9965903  east: 640369.10332306  west: 638669.65919416] and let
GRASS draw roadsmajor map for you, you get something like this:
http://people.ksp.sk/~dano/grass/wcc1.jpg. (colours correspond to
different components, which I obtained using my module). Or, the same
map, but different location [north: 239329.55684214  south:
238882.80682937  east: 630466.77182694  west: 629997.32746966], and
you have another disconnected lines:
http://people.ksp.sk/~dano/grass/wcc2.jpg

Then, I have also written a module for computing bridges(edges whose
removal disconnects the graph) in the network and found another,
probably error. This time, it is in map "railroads". The location is
[north: 195851.98992388  south: 187604.09950596  east: 669691.16599023
 west: 663129.724274] and the picture is:
http://people.ksp.sk/~dano/grass/railroads.jpg. Note that the lines
are not connected at the point the red arrow points at. Also, it
seems, but I am not completely sure, that there is something wrong
with the red segment the green arrow points at. I think, that the
segment is not topologically connected to the network at both ends,
although, visually, it seems that it is.

Finally, here is a random picture from a module for computing bridges:
http://people.ksp.sk/~dano/grass/bridges.jpg. (The data is from
streets_wake map). The red edges are bridges. Strictly speaking, the
blue edges are bridges as well, but they are not the type of bridge
you usually look for/consider important. So I wrote another module
that can identify such chains hanging on the network and remove them.

The code should appear shortly in GRASS addons repository.

That is for the last week. I am not currently stuck at anything and I
plan to develop another modules over the next week. For exampe, module
for computing articulation points as the algorithm is almost the same
as for bridges.

Cheers,
Daniel