Deepening I, How to make a network

learning objective: How to set up a network with the GeoDMS

In this section, we will do a deep dive into how to create a connected network and all the consequential items we need to create before using the impedance functions (based on Dijkstra’s algorithm).

This module is a continuation/deepening of Module 6a, Working with networks over a road network.

template instantiation to create the network

In the configuration file, you’ll find the container NetworkSpec; here, the actual network is created, amended and thus prepared for the analysis.

container NetworkSpec :=
  templates/MakeNetwork(  
      org 
    , dest
    , network
    , org/geometry
    , dest/geometry
    , network/geometry
    , 'car'
);

This is called a template instantiation. A container is configured, which calls the template MakeNetwork, and passes along a set of case parameters. This particular template needs 7 case parameters; what case parameters are needed is configured in the template itself:

template MakeNetwork  
{
   // begin case parameters
   unit<uint32> orgDomain;  
   unit<uint32> destDomain;  
   unit<uint32> roadDomain;  
  
   attribute<rdc> orgLocations  (orgDomain);  
   attribute<rdc> destLocations (destDomain);  
   attribute<rdc> roads         (arc, roadDomain);  
  
   parameter<string> network_type;  
   // end case parameters
  
   ...  
}

So, this template interprets the first seven arguments as these units/attributes/parameters. Within this template, you can refer to these case parameters as you would refer to any other item.

select a fully connected network

The next container in the template is called MakeConnectedRoads. This piece of the script makes sure that only roads that are actually connected to the main network are considered, since we cannot travel to and from a road that has no connection to the main network. First, we make two attributes which contain the start and endpoints of each arc in the road network, using the first_point and last_point functions.

attribute<rdc> first_point (roadDomain) := first_point(roads);  
attribute<rdc> last_point  (roadDomain) := last_point(roads);

Using the function union_unit, the domain unit roadDomain is duplicated and appended. In combination with the attribute function union_data, the point set first_point and last_point from the roadDomain are combined into a single point set. To assign the SequenceNr, or relation to the original arcs, to each point, you will take the id number (id) modulo the number of rows (nrofrows) from the roadDomain. To tell GeoDMS that this is an index number to another domain, set the value type to that domain (roadDomain) and cast the expression to that value type using the value function. By right-clicking on the item in the GeoDMS GUI or pressing CTRL + D while selecting this item, you can view the data in a table form.

attribute<roadDomain> SequenceNr := value(id(.) % nrofrows(roadDomain), roadDomain);

The next important step is to find unique nodes in the network. A node, in this case, is each beginning or endpoint of a link. We find the unique nodes by using the unique function of the point geometries. This results in a new domain, which consequently has a smaller or equal number of records than the original domain (in this case, the Pointset).

Then, you’ll find the F1 and F2, which are the relation attributes to the from points (start node) and to points (end node) of the links. We find this relation by looking up the first_point geometry in the NodeSet (which was the set of unique points), using the rlookup function. Remember, since this is again a relation attribute, we must set the value type to the target domain.

attribute<NodeSet> F1 (roadDomain) := rlookup(first_point, NodeSet/Values);  
attribute<NodeSet> F2 (roadDomain) := rlookup(last_point,  NodeSet/Values);

We then use those in combination with the connected_parts function to see to which connected network a link is connected. That function results in a new domain unit, here called Networks, with one entry per connected sub-network. It contains a generated subitem called PartNr: an attribute of the NodeSet that relates each node to the network (or part) to which it is connected. You could assume that the network with the most nodes in it is the main network, so in order to determine this, we count the number of nodes in each part. This can be accomplished by giving each record the value 1 (const) and then summing (sum) each record over the PartNr. Then, by determining the maximum value (max), we can look up which part (or sub-network) has the most nodes and, therefore, should be considered the main network:

unit<uint32> Networks := connected_parts(F1, F2)
{
   attribute<uint32> NrOfNodes    := sum(const(1, NodeSet), PartNr);
   parameter<uint32> MaxNrOfNodes := max(NrOfNodes);
   parameter<.>      Main         := rlookup(MaxNrOfNodes, NrOfNodes);
}

We then create a subset of the nodes which are not connected to that main network. Since PartNr is an attribute of the NodeSet, the condition Networks/PartNr <> Networks/Main is a boolean attribute of the NodeSet. When creating a subset based on a certain condition, we can look up and add attributes using that selection with the org_rel. That is the index number of the records that are in the selection.

unit<uint32> NodesNotConnected := select_with_org_rel(Networks/PartNr <> Networks/Main)  
{  
   attribute<rdc> Point := NodeSet/Values[org_rel];  
}

Now, we need to make an attribute in the roadDomain that identifies which arcs are part of the connected network so that we can create a subset based on that. This is a compound expression; first, we do a rlookup that gives the index number of each point in the Pointset domain from the NodesNotConnected domain. Since these are nodes that are not connected, we create a boolean of those points that are not in the NodesNotConnected domain. And finally, we want the arc, not the points. So, we use the inverted relation of the SequenceNr to find those arcs.

attribute<bool> IsConnected (roadDomain) := isNull(rlookup(Pointset/point, NodesNotConnected/point))[invert(Pointset/SequenceNr)];

As mentioned earlier, we now only need to take a subset to get all the connected roads. Again, we use select_with_org_rel and look up the attributes we need via the org_rel:

unit<uint32> Result := select_with_org_rel(IsConnected)
{
   attribute<rdc>           line (arc) := roads[org_rel];
   attribute<OSM/roadtype>  roadtype   := roadDomain/roadtype[org_rel];
   attribute<km_hr>         max_speed  := roadDomain/max_speed[org_rel];
}

connect origin and destinations to network

In the previous section, we have selected a fully connected network. Now, we will connect our origin and destination points to that network. Points could seemingly lie on a road, but might not exactly do so, or points could be far away from a road. In either case, we need to connect them (for an illustration, see Impedance general). Therefore, we first combine all points into a single unit using union_unit and union_data, as you have seen before. Since there could be duplicates, we identify and omit those using the unique function:

unit<uint32> locations := union_unit(orgDomain, destDomain)  
{  
   attribute<rdc> Values := union_data(., orgLocations, destLocations);   
}
unit<uint32> UniqueLocation := unique(locations/values);

And finally, we use the connect function to connect the points to the road network. The connect function results in a new domain unit with two generated subitems: geometry, the combined arc set of the original roads and the new connections, and arc_rel, the relation towards the original arcs (null for the new connecting links).

Obviously, these new connections do not have an assigned road type or maximum speed. We, therefore, manually assign a road type called ‘connectlink’ to those; the index number of that road type is 69 in the OSM roadtype classification. In the same way, we assign a default maximum speed of 25 km/h to the new connecting links.

unit<uint32> RoadsWithLocations := connect(MakeConnectedRoads/result/line, OrgToDest/UniqueLocation/values)  
{  
    attribute<OSM/roadtype> roadtype  := MakeDefined(MakeConnectedRoads/result/roadtype[arc_rel], value(69, OSM/roadtype));  
    attribute<km_hr>        max_speed := IsDefined(MakeConnectedRoads/result/max_speed[arc_rel]) 
                                         ? MakeConnectedRoads/result/max_speed[arc_rel] 
                                         : 25[km_hr];
}

create a link set and calculate impedances

Now, we have a fully connected network, to which our origin and destination points are connected, but we do not have a complete set of impedances. Impedance is the resistance of a segment of the road. It is displayed as the time needed to travel over that segment. It, therefore, depends on the type of transport used. In this example, we are using the car. The maximum speed per road is part of the source data and was passed along in the previous sections, with a default speed for the new connecting links. But first, we will need to split the arc set into segments using arc2segm; we then have individual straight segments. This function results in a new domain unit with three generated subitems: point and nextpoint, the first and last point of each segment, and sequence_rel, the relation to the original arcs. We then calculate the impedance per segment by first measuring the length of that segment using arc_length and dividing that by the looked-up maximum speed.

unit<uint32> LinkSet := arc2segm(RoadsWithLocations/geometry)  
,   DialogData = "segments"  
,   DialogType = "Map"  
{  
   attribute<rdc>          segments (arc) := points2sequence(PointSet/Point, PointSet/SequenceNr, PointSet/Ordinal);  
   attribute<km_hr>        max_speed      := RoadsWithLocations/max_speed[sequence_rel];  
   attribute<OSM/roadtype> roadtype       := RoadsWithLocations/roadtype[sequence_rel];  
   attribute<s>            impedance_link := arc_length(segments, m) / value(max_speed, m_s);  
   
   unit<uint32> PointSet := union_unit(LinkSet, LinkSet)  
   {  
      attribute<rdc>     Point      := Union_Data(., LinkSet/point, LinkSet/nextpoint);  
      attribute<LinkSet> SequenceNr := value(id(.) % nrofrows(LinkSet), LinkSet);  
      attribute<uint32>  Ordinal    := id(.) / nrofrows(LinkSet);  
   }  
}

The impedance matrix algorithm we will use to do the actual network analysis needs several attributes to run. First, it needs a unit that contains all the nodes in the network, the NodeSet. In order to create this, we will, as we have done before, create a point set with all points using union_unit and union_data. The second and third arguments are F1 and F2, which are the starting and end points of each link (segment). The fourth item we need is the previously created impedance; here, we only link to that item. The fifth and sixth items are the index numbers of origin and destination nodes in the NodeSet.

unit<uint32> NodeSet  := unique(LinkSet/PointSet/Point);  
  
attribute<NodeSet> F1 (LinkSet) := rlookup(LinkSet/Point,     NodeSet/Values);  
attribute<NodeSet> F2 (LinkSet) := rlookup(LinkSet/nextpoint, NodeSet/Values);  
  
attribute<s>       impedance   (LinkSet)    := abs(LinkSet/impedance_link);   
attribute<NodeSet> nr_orgNode  (orgDomain)  := rlookup(orgLocations,  NodeSet/Values);  
attribute<NodeSet> nr_destNode (destDomain) := rlookup(destLocations, NodeSet/Values);

And that is all the template does: it turns a raw set of arcs and two point sets into a connected network with an impedance, the F1/F2 node relations, and the relations of the origin and destination points towards the NodeSet.

With these items in place, we can do the actual analysis. Back in the analysis container, where NetworkSpec is the instantiated template, we feed them to the impedance algorithm. This is exactly the call that is explained argument by argument in Module 6a, Working with networks over a road network: the impedance and the F1/F2 node relations are the three obligatory arguments, the nr_orgNode and nr_destNode relations serve as the startPoint and endPoint node relations, and the parameter MaxTravelTime (1800 seconds) is the cut argument.

unit<uint64> Impedance_cut := 
impedance_matrix_od64('bidirectional(link_flag);startPoint(Node_rel);endPoint(Node_rel);cut(OrgZone_max_imp);od:OrgZone_rel,DstZone_rel'
  , NetworkSpec/impedance
  , NetworkSpec/F1
  , NetworkSpec/F2  
//////
  ,    NetworkSpec/LinkSet/roadtype!= OSM/roadtype/motorway 
    && NetworkSpec/LinkSet/roadtype!= OSM/roadtype/motorway_link
  , NetworkSpec/OrgToDest/nr_orgNode  
  , NetworkSpec/OrgToDest/nr_destNode 
  , MaxTravelTime
);

---

Go back to Module 6a, Working with networks over a road network