Module 5: Working with networks

From ObjectVision

Jump to: navigation, search

Contents

Preparing a network

In this module we will use the OpenStreetMap network to calculate travel times between origin and destination point sets. However, first, we must prepare the network since the downloaded OSM is just a set of lines with a typology. We must make sure that the network is connected and, therefore, we connect the origin and destination point sets to the network. For this purpose we use a script that is quite extensive but necessary. In this section you will be guided through this script, in that way you will be able to understand the different steps, and begin to understand the GeoDMS logic behind it.

Before we begin, let's download the network configuration here: configuration/data


For this example we will calculate the traveltime to the nearest intercity train station from each municipality. In the container SourceData we have the trainstation points and the address-weighted-municipality centroid points. These point sets are configured like you have seen in Module 2: Working with different data sources. Next, in the container Analysis/NetworkDist we see org and dest. Those are simply redirections to the origin and destination domain:

unit<uint32> org    := SourceData/Municipality;
unit<uint32> dest   := SourceData/Train_stations;

In this way you can access sub items from SourceData/Municipality by simply referring to, for example, org/geometry. This is not necessary, but makes the code shorter and more importantly it makes the code more versatile and easier to change. When, for example, you change the origin point set to something else. Only the unit org has to change instead of all the references to items in org.

Then there is the container NetwerkSpec, in here the actual network is created, amended and thus prepared for the analysis.

container NetworkSpec :=
	Templates/MakeNetwork(
		  org
		, dest
		, SourceData/Car_network
		, org/WeightedAddressCentroid
		, dest/geometry
		, SourceData/Car_network/line
		, '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 7 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 script makes sure that only roads that are actually connected to the main netwerk 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 operators

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

Using the operator union_unit, the domain unit roadDomain is duplicated and appended. In combination with the attribute operator union_data the pointset first_point and last_point from the roadDomain are combined into a single pointset. 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 operator. 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 begin or endpoint of a link. We find the unique nodes by using the unique operator 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 operator. 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 operator to see to which connected network a link is connected. That operator creates an attribute called PartNr that relates to the network (or part) to which a link 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:

attribute<uint32>   NrOfNodes    := sum(const(1, NodeSet), PartNr);

Then by determining the maximum value (max) we can lookup which PartNr (or sub-network) has the most nodes and therefore should be considered the main network.

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. When creating a subset based on a certain condition, we can lookup and add attributes using that selection with the nr_OrgEntity. That is the index number of the records that are in the selection.

unit<uint32> NodesNotConnected := Subset(networks/partnr <> networks/main)
{
	attribute<rdc> Point := NodeSet/Values[Nr_OrgEntity];
}

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 subset based on that. This is a compound expression, first we do a rlookup that gives the index number of each point in 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:

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

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. 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 operator:

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 operator to connect the points to the road network. Obviously, these new connection do not have an assigned roadtype. We therefore manually assign a roadtype called 'connecting link' to those, the index number of that road type is 69.

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

Create a linkset 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 road. It is displayed as the time needed to travel over that segment. It, therefore, depends on type of transport used. In this example, we are using the car. In the OSM classifications the maximum speed per road type is pre-configured. Since we know the road type for each segment we can look this up. But first, we will need to split the arc set to segments using arc2segm, we then have individual straight segments. We calculate then the impedance per segment by first measuring the length of that segment using arc_length and dividing that by the looked up speed from the classifications.

unit <uint32> LinkSet := arc2segm(RoadsWithLocations/UnionData)
,	DialogData = "segments"
,	DialogType = "Map"
{
	attribute<rdc>                    segments (arc)               := points2sequence(PointSet/Point, PointSet/SequenceNr, PointSet/Ordinal);
	attribute<OSM/roadtype>  roadtype                         := RoadsWithLocations/roadtype[SequenceNr];
	attribute<s>                       impedance_link               := arc_length(segments, m) / OSM/roadtype/CarSpeedOutside_ms[roadtype];
	
	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 Dijkstra 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. like we have done before, create a point set with all points using union_unit and union_data. The second and third item are the F1 and F2, which are the starting and end point 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)          := LinkSet/impedance_link; 
attribute<NodeSet> nr_orgNode  (orgDomain)    := rlookup(orgLocations, NodeSet/Values);
attribute<NodeSet> nr_destNode (destDomain)  := rlookup(destLocations, NodeSet/Values);

Dijkstra

The actual analysis is done in the attribute OD, here the Dijkstra algorithm (dijkstra_m64, this is actually one of many different dijkstra variable which we will not go into at this point) is specified with a couple of options. In this case a string with several settings separated by a semi-colon, additional settings for an option are specified using a colon. This string is followed by 8 arguments separated by a comma:

dijkstra_m64('bidirectional(link_flag);startPoint(Node_rel):max_imp;endPoint(Node_rel);limit(OrgZone_max_mass,DstZone_mass)'
  1. The first argument is bidirectional(link_flag), this tells the algorithm that all roads are bidirectional except those specified using the link flag. The term between brackets shows that we need to give it some value. So we give an argument which tells it which segments are not bidirectional. Those are the links that are motorways or motorway link.
  2. The second argument startPoint(Node_rel):max_imp tells the algorithm the index number of the origin points, the nr_orgNode. The additional term max_imp says that we want the maximum impedance from each origin point to each destination point.
  3. The nr_destNode.
  4. limit(OrgZone_max_mass,DstZone_mass) this limits the search from each origin to destinations. Since we want only the travel time to the closest destination, we set OrgZone_max_mass to 1, so that the algorithm stops when he has reached 1 mass unit of destination. And DstZone_mass specificies that mass of a destination, in this case this is 1 for each destination.

After the string with options, the arguments are listed. The first three are always required, no matter which settings you use: impedance, F1 and F2. That is the impedance (travel time in seconds) over a link (a connection between two points), and the F1 and F2 are the beginning and endpoint of said link. Then are the 5 arguments that are specified in the options string: link_flag, nr_orgNode, nr_destNode, 1f (for the OrgZone_max_mass), and const(1f, dest) for the mass of each destination.


unit<uint64> OD := 
	dijkstra_m64('bidirectional(link_flag);startPoint(Node_rel):max_imp;endPoint(Node_rel);limit(OrgZone_max_mass,DstZone_mass)'
		, NetworkSpec/OrgToDest/impedance
		, NetworkSpec/OrgToDest/F1
		, NetworkSpec/OrgToDest/F2
		//////
		, NetworkSpec/OrgToDest/LinkSet/roadtype != classifications/OSM/roadtype/V/motorway  
                       && NetworkSpec/OrgToDest/LinkSet/roadtype != classifications/OSM/roadtype/V/motorway_link 
		, NetworkSpec/OrgToDest/nr_orgNode
		, NetworkSpec/OrgToDest/nr_destNode
		, 1f, const(1f, dest)
	);

This operator creates only one attribute: OrgZone_MaxImp, since this was specified by a colon in the options string after startPoint(Node_rel). In the GeoDMS GUI double click on this item, it will probably be done calculating after a few seconds, and show for each municipality the time in seconds needed to reach the closest train station. If you are knowlegdeable with Dutch topography/infrastructure you can assess whether the outcome seems plausible.


Go to previous module: Module 4: Doing basic analyses with grid data

Go to next module: Module 6: Doing land-use allocation

Personal tools