[Qgis-developer] a graph plugin for QGIS

[Giuliano Curti]

On 8/29/16, Giuliano Curti <giulianc51 at gmail.com> wrote:
> On 8/29/16, Anita Graser <anitagraser at gmx.at> wrote:
>> Dear Giuliano,

Hi Anita, Hi Paolo, Hi all

I had a look at the available material on the subject of graphs /
networks; I saw (very quickly) three products:
1) Library Network Analysis
2) the plugin Road Graph
3) the sDNAV plugin;

apart from the third product that seems to be the most complex tool
and I have not seen well, the other two seems contain essentially the
search for shortest paths by Dijkstra method;
confirmed the great importance of the Dijkstra method for the graph
theory, we need remember the many faces on the subject; in my (very
experimental) plugin I approach:
- the vertex and edge inquiry
- some (limited) editing (weight of edges)
- storage I/O
- trees (BFS, DFS)
- cycles
- minimum spanning tree (Jarnik-Prim and Boruvka-Kruskal)
- connectivity (cutpoints, bridges, vertex- and edge- connectivity)
- paths (shortest & not shortest, single & all)
- visualization with QGIS desktop
- (limited) import/export from/to SHP format;

I know, that's probably an approach more theoretic than practical
oriented, but I think that these topics represents fundamental tools
for graph analyzing; I will try to apply them in some actual case (the
road graph on my town? :-) and describe it in the last part of the
presentation article I uploaded at Slideshare;

in the topic of SHP import/export, it's very interesting the ability
to build graphs starting from SHP files available in the Library
Network Analysis, even though there does not convince me at all, for
example, the plethora of generated vertices (suffices imho the end
points) and the automatic intersection of linestring with a shared
vertex (I think might prevent the processing of not planar graphs);

so here's a first report (I took some commitment); I'll look better
the classes of the  Network Analysis Library and I will try also to
take a look at sDNAV plugin although I fear that now it is beyond of
my potential;
I repeat: I am not a graphs expert but a simple "mathematics" amateur,
but if I can do some help to this part of the QGIS would gladly give a
contribution;

sfmbe, thanks, bye,
giuliano