TODO:
transform the OSM map into a graph in the following way:
– Each street should be represented as a graph node
– Two graph nodes are connected by an edge if and only if the corresponding streets meet in some junction point
– Location (lat,lon) of a given node v (used during visualization) should be calculated as an average of a street end nodes, i.e.: (lat = (lat1+lat2)/2, lon = (lon1+lon2)/2)

(source data: galaxy.agh.edu.pl/sedziwy/krakow_ways_tiny.osm)

– Augment the above graph by additional vertices, representing bus stops
(In the OSM file they look like this:

<node id="276629967" version="3" timestamp="2022-10-26T06:43:12Z" lat="49.9890076" lon="19.956176">
<tag k="bus" v="yes"/>
<tag k="direction" v="forward"/>
<tag k="name" v="Fort Swoszowice 01"/>
<tag k="public_transport" v="stop_position"/>
</node>

)

A “bus stop” graph vertex is connected to the closest (in terms of Euclidean distance between [lat, lon] calculated for a “street node” and  a stop’s [lat, lon] pair) vertex representing a street.

 

TODO (Dec 4,  2024)

 

Step 1

Implement SplitGraph(G,U) procedure, for a given graph and some subset .

Description: SplitGraph returns two graphs, and such that
where ;  and are created as follows:

For each an edge , such that we replicate a node belonging to the vertex set with the least index (i.e., to for or otherwise) and
we add its replica to the vertex set with the higher index (i.e., for or otherwise).

Assign a list (say RL) to each replicated node, containing references to the graphs hosting other node’s replica(s).
Alternatively, the one centralized map (or any other structure) can be used to maintain those data.

For all pairs (including the newly added replicated nodes) :   if then .

Step 2

Split the graph representing OSM data for the city of Cracow, using recursively the above scheme. Please, keep in mind that after each split call, the references of replicas (in the RL list) should be refreshed (for the future purposes)