<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle19
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="NO-BOK" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Hi Johannes,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Sorry for the delayed response.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">You could try v.net and then use igraph.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">See:
<a href="https://github.com/NINAnor/gudbrand_hydro/blob/master/v.igraph.order.py">
https://github.com/NINAnor/gudbrand_hydro/blob/master/v.igraph.order.py</a><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">as an example for network analysis using a GRASS python script in combination with igraph.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">What you would need is to compute the paths between all possible combinations of sampling sites (using e.g. http://igraph.org/python/doc/igraph.GraphBase-class.html#get_shortest_paths).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Once you got a unique list of edges you can use v.extract I guess to get your subnetwork…<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Or if you continue with network analysis you could just use:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><a href="http://igraph.org/python/doc/igraph.GraphBase-class.html#subgraph_edges">http://igraph.org/python/doc/igraph.GraphBase-class.html#subgraph_edges</a><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Hope that is somehow useful…<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Cheers<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Stefan<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> grass-user [mailto:grass-user-bounces@lists.osgeo.org]
<b>On Behalf Of </b>Johannes Radinger<br>
<b>Sent:</b> torsdag 28. september 2017 13.04<br>
<b>To:</b> Markus Metz <markus.metz.giswork@gmail.com><br>
<b>Cc:</b> GRASS user list <grass-user@lists.osgeo.org><br>
<b>Subject:</b> Re: [GRASS-user] Extract subnet from grass vector network based on selected nodes<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-GB">Hi all,<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB">I just tried two different tools that both work to extract a subnetwork that connects a set of selected nodes:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB">1) v.net.allpairs works fine and a subnetwork is extracted. However, this definitely needs some clean up and layer/attribute operations to get the connected tables/cats from the original network<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB">2) v.net.steiner also works fine. However, it seems that this approach takes slightly longer than v.net.allpairs.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-GB">In general both approaches are rather slow if one wants to extract a subnetwork based on e.g. >1000 selected nodes from a very large network. For example, my initial (large) network consists
of >100000 lines which makes any further analysis rather slow. Thus, I wanted to minimize the network to one that still connects my target nodes but skips parts that are not needed.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-GB">Thank you for you suggestions, anyway.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB">/Johannes<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-GB">On Thu, Sep 28, 2017 at 10:06 AM, Markus Metz <</span><a href="mailto:markus.metz.giswork@gmail.com" target="_blank"><span lang="EN-GB">markus.metz.giswork@gmail.com</span></a><span lang="EN-GB">> wrote:<o:p></o:p></span></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-GB"><br>
<br>
On Thu, Sep 28, 2017 at 9:43 AM, Moritz Lennert <</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB">> wrote:<br>
><br>
> On 28/09/17 08:51, Markus Metz wrote:<br>
>><br>
>><br>
>><br>
>> On Wed, Sep 27, 2017 at 11:55 PM, Moritz Lennert <</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB"> <mailto:</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB">>>
wrote:<br>
>> ><br>
>> > On 27/09/17 21:03, Markus Metz wrote:<br>
>> >><br>
>> >><br>
>> >><br>
>> >> On Wed, Sep 27, 2017 at 4:07 PM, Moritz Lennert <</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB"> <mailto:</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB">>
<mailto:</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB"> <mailto:</span><a href="mailto:mlennert@club.worldonline.be" target="_blank"><span lang="EN-GB">mlennert@club.worldonline.be</span></a><span lang="EN-GB">>>>
wrote:<br>
>> >> ><br>
>> >> ><br>
>> >> ><br>
>> >> > Le 27 septembre 2017 13:11:54 GMT+02:00, Johannes Radinger <</span><a href="mailto:johannesradinger@gmail.com" target="_blank"><span lang="EN-GB">johannesradinger@gmail.com</span></a><span lang="EN-GB"> <mailto:</span><a href="mailto:johannesradinger@gmail.com" target="_blank"><span lang="EN-GB">johannesradinger@gmail.com</span></a><span lang="EN-GB">>
<mailto:</span><a href="mailto:johannesradinger@gmail.com" target="_blank"><span lang="EN-GB">johannesradinger@gmail.com</span></a><span lang="EN-GB"> <mailto:</span><a href="mailto:johannesradinger@gmail.com" target="_blank"><span lang="EN-GB">johannesradinger@gmail.com</span></a><span lang="EN-GB">>>>
a écrit :<br>
>> >> > >Hi,<br>
>> >> > ><br>
>> >> > >I have a GRASS vector network that represents a river network (with<br>
>> >> > >many<br>
>> >> > >first order tributaries) and that has additional connected nodes that<br>
>> >> > >represent sampling sites.<br>
>> >> > ><br>
>> >> > >I'd like to extract a minimum subnetwork of the full network that still<br>
>> >> > >connects a set of selected nodes (e.g. identified by their cat).<br>
>> >> > >However,<br>
>> >> > >network edges (i.e. river segments) that are not necessary to connect<br>
>> >> > >the<br>
>> >> > >sampling points should be excluded in the new subnetwork. Is there a<br>
>> >> > >function or process in GRASS GIS to extract such a subnetwork that<br>
>> >> > >fully<br>
>> >> > >connects a set of selected nodes?<br>
>> >> ><br>
>> >> > not sure but maybe v.net.spanningtree ?<br>
>> >><br>
>> >> v.net.spanningtree calculates a tree covering all nodes in the network, not only selected nodes, therefore v.net.spanningtree does not apply here.<br>
>> ><br>
>> ><br>
>> > If you connect only the selected nodes to the network, wouldn't that work ? Or does v.net.spanningtree consider all connections between lines as nodes ?<br>
>><br>
>> v.net.spanningtree considers all internal nodes of the network. See also<br>
>> </span><a href="https://en.wikipedia.org/wiki/Spanning_tree" target="_blank"><span lang="EN-GB">https://en.wikipedia.org/wiki/Spanning_tree</span></a><span lang="EN-GB"><br>
><br>
><br>
> Ok, thanks. So, one would need to "disconnect" lines at non-selected nodes for this to work.<o:p></o:p></span></p>
</div>
</div>
</div>
<p class="MsoNormal"><span lang="EN-GB">or use v.net.steiner (see my previous reply)<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-GB">><br>
> And maybe some clarification on what is meant by "nodes" in the sentence "A spanning tree is a minimum cost subnetwork connecting all nodes in an undirected network" in the man page might help future users.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB">Yes, that would help. I needed to look at the library fn NetA_spanning_tree() to be sure.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal">Markus M<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">><br>
> Moritz <o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</body>
</html>