GSoC Network Analysis

Abstract: [1]

1st week report

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

2nd week report

Hello everyone,

While working on the module for computing articulation points, I found a bug in the code calculating bridges. So the first real thing I did this week was some bug fixing. Also, I have updated the module for connected components so that it outputs the computed values in a more useful way (Read: now it can be used for more than just producing nice pictures to the first weak report....). Anyway, everything is kept in a nice little database table. As the first sentence suggests, I have done a module for computing articulation points in the networks. Moreover, I have implemented a module that finds a minimum spanning tree in the graph. This pictures shows both new modules in work: red crosses are articulation points, green edges form a minimum spanning tree (all edges have equal weight) http://people.ksp.sk/~dano/grass/mstap.png. In the following picture, the green edges also form a minimum spanning tree, but this time, the speed limit is used as the weight of an edge. Note that the highway in the centre is not included in the spanning tree: http://people.ksp.sk/~dano/grass/mst.png. The latest version of the code will appear shortly in the add-ons repository.

Currently, I cannot persuade the compiler to compile the library correctly. So far, it does make cause any problems as no code is used by two modules. I will look into this later next week and I will probably start working on the family of modules using max-flows algorithm as well.

Daniel