Vector network analysis: Difference between revisions

From GRASS-Wiki
Jump to navigation Jump to search
No edit summary
(+v.net.visibility)
 
(22 intermediate revisions by 4 users not shown)
Line 1: Line 1:
= Vector network analysis =
GRASS GIS provides support for vector network analysis using the [http://trac.osgeo.org/grass/browser/grass/trunk/lib/vector/dglib/ DGlib] Directed Graph Library.
 
GRASS provides support for vector network analysis using the [http://trac.osgeo.org/grass/browser/grass/trunk/lib/vector/dglib/ DGlib] Directed Graph Library.


GRASS GIS 7 has [[WxGUI Vector Network Analysis Tool]] front-end, which supports some of the vector network analysis modules.
__TOC__
== Implemented algorithms ==
== Implemented algorithms ==


The following algorithms are implemented (GRASS 6.5+):
The following algorithms have been implemented:


* Vector maintenance: {{cmd|v.net|version=70}}
* Vector maintenance: {{cmd|v.net}}
* Shortest path: {{cmd|d.path|version=64}} and {{cmd|v.net.path|version=70}}
* Shortest path: {{cmd|v.net.path}}
* Shortest path between all pairs of nodes {{cmd|v.net.allpairs|version=70}}
* Shortest path between all pairs of nodes {{cmd|v.net.allpairs}}
* Allocation of sources (create subnetworks, e.g. police station zones): {{cmd|v.net.alloc|version=70}}
* Allocation of sources (create subnetworks, e.g. police station zones): {{cmd|v.net.alloc}}
* Iso-distances (from centers): {{cmd|v.net.iso|version=70}}
* Iso-distances (from centers): {{cmd|v.net.iso}}
* Computes bridges and articulation points: {{cmd|v.net.bridge|version=70}}
* Computes bridges and articulation points: {{cmd|v.net.bridge}}
* Computes degree, centrality, betweeness, closeness and eigenvector centrality measures: {{cmd|v.net.centrality|version=70}}
* Computes degree, centrality, betweeness, closeness and eigenvector centrality measures: {{cmd|v.net.centrality}}
* Computes strongly and weakly connected components: {{cmd|v.net.components|version=70}}
* Computes strongly and weakly connected components: {{cmd|v.net.components}}
* Computes vertex connectivity between two sets of nodes: {{cmd|v.net.connectivity|version=70}}
* Computes vertex connectivity between two sets of nodes: {{cmd|v.net.connectivity}}
* Computes shortest distance via the network between the given sets of features: {{cmd|v.net.distance|version=70}}
* Computes shortest distance via the network between the given sets of features: {{cmd|v.net.distance}}
* Computes the maximum flow between two sets of nodes: {{cmd|v.net.flow|version=70}}
* Computes the maximum flow between two sets of nodes: {{cmd|v.net.flow}}
* Computes minimum spanning tree: {{cmd|v.net.spanningtree|version=70}}
* Computes minimum spanning tree: {{cmd|v.net.spanningtree}}
* Minimum Steiner trees (star-like connections, e.g. broadband cable connections): {{cmd|v.net.steiner|version=70}}
* Minimum Steiner trees (star-like connections, e.g. broadband cable connections): {{cmd|v.net.steiner}}
* Finds shortest path using timetables: {{cmd|v.net.timetable|version=70}}
* Finds shortest path using timetables: {{cmd|v.net.timetable}}
* Traveling salesman (round trip): {{cmd|v.net.salesman|version=70}}
* Traveling salesman (round trip): {{cmd|v.net.salesman}}
* Performs visibility graph construction: {{cmd|v.net.visibility}}


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  {{cmd|d.vect}} (set display=dir).
Vector directions (directed graph) 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  {{cmd|d.vect}} (set display=dir).
Use [[Turntable]] to assign costs to turns on the network.


* see the {{cmd|vectorintro}} "vector map processing and network analysis" help page
* see the {{cmd|vectorintro|desc=vector map processing and network analysis}} help page


== Example: Shortest path routing ==
== Example: Shortest path routing ==
Line 31: Line 33:
* see the {{cmd|v.net.path}} and {{cmd|d.path}} help pages
* see the {{cmd|v.net.path}} and {{cmd|d.path}} help pages


== Turntable extension (to be added soon) ==
== Common parameters ==


The turntable module (v.net.turntable) is one of vector network analysis modules.
* '''input''' - This is the name of input vector map or data source for direct OGR access.
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.
* '''output''' - This is the name for output vector map.


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.
* '''type''' - This parameter defines arc type, which can be line or boundary.
 
* '''alayer''' - This parameter is a number and defines the arc layer. Vector features can have category values in different layers. This number determines which layer to use. When used with direct OGR access this is the layer name.
 
* '''nlayer''' - This parameter is a number and defines the node layer. Vector features can have category values in different layers. This number determines which layer to use. When used with direct OGR access this is the layer name.
 
* '''afcolumn''' - This is name of the cost column for moving in forward direction or forward and backward directions together.
 
* '''abcolumn''' - This is name of the cost column for moving in backward direction.
 
* '''ncolumn''' - This is name of the cost column for moving through nodes.
 
If you are not familiar with layers concept in GRASS see [[Vector Database Management]].


== New ideas ==
== New ideas ==
Line 45: Line 58:


== Screenshots ==
== Screenshots ==
* more screenshots [http://grass.osgeo.org/screenshots/vector.php from the GRASS website]


=== GRASS GIS 7 screenshots ===
[[Image:Grass7_vector_network_tool_salesman.png|center|600px|thumb|Travelling salesman ({{cmd|v.net.salesman}})]]


[[Image:V.net.iso.png|center|600px|thumb|{{cmd|v.net.iso}} - Split net to bands between cost isolines (direction from centre). Costs of centre node are used in calculation.]]
[[Image:Grass7_vector_network_tool_alloc.png|center|600px|thumb|Subsets for nearest centers ({{cmd|v.net.alloc}})]]


[[Image:wxgui-vnet-alloc.png|center|600px|thumb|Subsets for nearest centers ({{cmd|v.net.alloc}})]]


[[Image:V.net.alloc.png|center|600px|thumb|{{cmd|v.net.alloc}} - Allocates subnets for nearest centres (direction from centre). Costs of centre node are used in calculation.]]
See also
* [[WxGUI Vector Network Analysis Tool]]
* more screenshots [https://grass.osgeo.org/screenshots/vector/ from the GRASS website]


=== Old GRASS 5 screenshots ===


[[Image:D.path.jpg|center|600px|thumb|{{cmd|d.path}} - Find shortest path for selected starting and ending node.]]
<center>
{|
| [[Image:V.net.iso.png|center|400px|thumb|{{cmd|v.net.iso}} - Split net to bands between cost isolines (direction from centre). Costs of centre node are used in calculation.]]
|[[Image:V.net.alloc.png|center|400px|thumb|{{cmd|v.net.alloc}} - Allocates subnets for nearest centres (direction from centre). Costs of centre node are used in calculation.]]
|-
|[[Image:D.path.jpg|center|400px|thumb|{{cmd|d.path}} - Find shortest path for selected starting and ending node.]]
|&nbsp;
|}
</center>


== See also ==
== See also ==


* [[Turntable]]
* [[GSoC Network Analysis]]: many new modules!
* [[GSoC Network Analysis]]: many new modules!


Line 63: Line 91:


* [http://www.ing.unitn.it/~grass/docs/tutorial_64_en/htdocs/esercitazione/network_analysis/index.html Network analysis tutorial] by University of Trento, Italy
* [http://www.ing.unitn.it/~grass/docs/tutorial_64_en/htdocs/esercitazione/network_analysis/index.html Network analysis tutorial] by University of Trento, Italy


== External links ==
== External links ==
Line 70: Line 97:


[[Category:Documentation]]
[[Category:Documentation]]
[[Category:FAQ]]
[[Category:Vector]]
[[Category:Vector]]
[[Category:Network Analysis]]

Latest revision as of 12:21, 28 February 2019

GRASS GIS provides support for vector network analysis using the DGlib Directed Graph Library.

GRASS GIS 7 has WxGUI Vector Network Analysis Tool front-end, which supports some of the vector network analysis modules.

Implemented algorithms

The following algorithms have been implemented:

Vector directions (directed graph) 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). Use Turntable to assign costs to turns on the network.

Example: Shortest path routing

Common parameters

  • input - This is the name of input vector map or data source for direct OGR access.
  • output - This is the name for output vector map.
  • type - This parameter defines arc type, which can be line or boundary.
  • alayer - This parameter is a number and defines the arc layer. Vector features can have category values in different layers. This number determines which layer to use. When used with direct OGR access this is the layer name.
  • nlayer - This parameter is a number and defines the node layer. Vector features can have category values in different layers. This number determines which layer to use. When used with direct OGR access this is the layer name.
  • afcolumn - This is name of the cost column for moving in forward direction or forward and backward directions together.
  • abcolumn - This is name of the cost column for moving in backward direction.
  • ncolumn - This is name of the cost column for moving through nodes.

If you are not familiar with layers concept in GRASS see Vector Database Management.

New ideas

Screenshots

GRASS GIS 7 screenshots

Travelling salesman (v.net.salesman)
Subsets for nearest centers (v.net.alloc)
Subsets for nearest centers (v.net.alloc)

See also

Old GRASS 5 screenshots

v.net.iso - Split net to bands between cost isolines (direction from centre). Costs of centre node are used in calculation.
v.net.alloc - Allocates subnets for nearest centres (direction from centre). Costs of centre node are used in calculation.
d.path - Find shortest path for selected starting and ending node.
  

See also

Tutorials

External links

Retrieved from "https://grasswiki.osgeo.org/w/index.php?title=Vector_network_analysis&oldid=25524"