Vector network analysis
Vector network analysis
GRASS provides support for vector network analysis using the DGlib Directed Graph Library.
Implemented algorithms
The following algorithms are implemented (GRASS 6.5+):
- Vector maintenance: v.net
- Shortest path: d.path and v.net.path
- Shortest path between all pairs of nodes v.net.allpairs
- Allocation of sources (create subnetworks, e.g. police station zones): v.net.alloc
- Iso-distances (from centers): v.net.iso
- Computes bridges and articulation points: v.net.bridge
- Computes degree, centrality, betweeness, closeness and eigenvector centrality measures: v.net.centrality
- Computes strongly and weakly connected components: v.net.components
- Computes vertex connectivity between two sets of nodes: v.net.connectivity
- Computes shortest distance via the network between the given sets of features: v.net.distance
- Computes the maximum flow between two sets of nodes: v.net.flow
- Computes minimum spanning tree: v.net.spanningtree
- Minimum Steiner trees (star-like connections, e.g. broadband cable connections): v.net.steiner
- Finds shortest path using timetables: v.net.timetable
- Traveling salesman (round trip): v.net.salesman
Vector directions are defined by the digitizing direction (a-->--b). You can navigate either omnidirectionally or differently in each directions as both directions are supported. Network modules provide parameters to assign attribute columns to the forward and backward direction. To see how a vector is directed, use the "display" parameter of d.vect (set display=dir).
- see the vectorintro "vector map processing and network analysis" help page
Example: Shortest path routing
- see the v.net.path and d.path help pages
Extensios
The turntable module (v.net.turntable) is one of vector network analysis modules. It creates a turntable with the costs for every possible turn on every possible node (intersection, crossroad) in given layer. U-turns are taken in account too.
For better handling, a linegraph is created. In this linegraph, every line is represented by two nodes. These nodes have positive and negative values respectively, with their absolute values identical. Every node corresponds to opposite line direction. The positive node matches the direction of line. The negative node matches the opposite direction. For better understanding, let's have a travelling subject standing on a line (road) before an intersection wanting to cross it. This line's direction is TOWARDS the intersection. Travelling from this line through the intersection means that the subject is currently standing on the POSITIVE node representation of the line. After crossing to this line from any permitted direction, the subject gets to the NEGATIVE point representation of the line.
These two nodes (corresponding to the same line) are connected with two U-turns (for both directions). Every U-turn direction belongs to another intersection. U-turn from the POSITIVE node to the NEGATIVE one belongs to the intersection we are going to cross. The other U-turn belongs to the intersection at the opposite end of this line.
New ideas
- Vector network analysis ideas (please help to realize)
Screenshots
- more screenshots from the GRASS website
See also
- GSoC Network Analysis: many new modules!
Tutorials
- Network analysis tutorial by University of Trento, Italy