Kruscal's union-find algorithm
6/12/2021 Homework 09. Roads https://foothillcollege.instructure.com/courses/16873/assignments/514051 1/6 Homework 09. Roads Due Monday by 11:59pm Points 100 Homework 09. Roads Homework 09. Roads A few weeks after "accepting the resignation letter from an" A.I. ethics researcher (https://en.wikipedia.org/wiki/Timnit_Gebru) , a large tech company's A.I. went rogue and decided to "disrupt the transportation industry" by making it's self-driving cars destroy all the roads around Mountain View. Luckily, no people or infrastructure was harmed thanks to the Mitchells (https://www.imdb.com/title/tt7979580/) who stopped the A.I. Your job is to write a program reads in data about what roads/edges used to exist (what roads we can rebuild) and then outputs which road segments (edges, not entire roads/paths) we should rebuild first. There are two requirements: If we could get from node A to node B before the A.I. destroyed the roads, we should be able to get from node A to node B after rebuilding the roads. We want to rebuild the least amount of road (the least total length) possible because roads are expensive... or something. You may discuss the homework as much as you like (in Canvas or Discord) as long as you don't share code for your solution. See https://www.youtube.com/watch?v=FBD-dFzEe7I (https://www.youtube.com/watch?v=FBD-dFzEe7I) (https://www.youtube.com/watch?v=FBD-dFzEe7I) for an example input and output. Data Format There are two files that contain the data: nodes.txt (for nodes) and roads.txt (for edges). https://en.wikipedia.org/wiki/Timnit_Gebru https://www.imdb.com/title/tt7979580/ https://www.youtube.com/watch?v=FBD-dFzEe7I https://www.youtube.com/watch?v=FBD-dFzEe7I 6/12/2021 Homework 09. Roads https://foothillcollege.instructure.com/courses/16873/assignments/514051 2/6 This data is a simplified version of some data from openstreetmap.org (https://www.openstreetmap.org/#map=13/37.3859/-122.0936) . We're going to treat the data as if it represents an undirected graph (even though some roads are actually 1-way roads). nodes.txt The first line of nodes.txt contains 4 double s: minimum x coordinate, min y coordinate, maximum x coordinate, and max y coordinate Every other line represents a 2D point (the nodes) which have 3 parts: a int_least64_t OSM ID that uniquely identifies that node, a double x coordinate, and a double y coordinate. All coordinates are in kilometers. Here's an example: -8.280193126928674 -5.628216599999846 8.268958471249428 5.628216599999846 26027650 -3.1377879410553775 2.563702419600297 26027651 -2.6985453920733153 3.5639327087998054 26027653 -3.2265598654362253 2.441053738800085 26027655 -3.3576316196990637 2.3328570797998402 ... roads.txt Every line in roads.txt has 3 main parts: A int_least64_t OSM ID that uniquely identifies that part of a road A list of Node IDs The number of nodes, N, that make up that part of the road (in order) N OSM IDs that for the nodes The name of the road Note that the same road may show up multiple times because it has multiple parts. The list of node IDs corresponds to multiple edges, for example the line 173846420 4 257878162 6093953294 6093463504 257877916 Foothill Expressway denotes a part of a road Foothill Expressway with the unique ID 173846420 and N = 4 nodes which represent the following N - 1 = 3 edges: (257878162, 6093953294), (6093953294, 6093463504), and (6093463504, 257877916). Note: The graph is undirected, so in essence, the edges edges: (6093953294, 257878162), (6093463504, 6093953294), and (257877916, 6093463504) are also added. ... 172246147 2 1831703524 1831703525 South Fair Oaks Avenue 172246148 2 65515006 1831703524 South Fair Oaks Avenue 173846420 4 257878162 6093953294 6093463504 257877916 Foothill Expressway 173846425 16 257878172 6439285157 2497999653 272297873 272297872 430586728 1247892271 272297870 2722 97869 272297868 272297867 272297866 272297865 272297864 272297862 65400152 Foothill Expressway 174890533 17 65653802 6518635038 65457620 6518635037 2323163806 6473961499 65608871 6473961498 23231 63808 7301457508 7301457504 7301457500 6473963471 65641377 6473963473 7824956488 65653798 Emerson St https://www.openstreetmap.org/#map=13/37.3859/-122.0936 6/12/2021 Homework 09. Roads https://foothillcollege.instructure.com/courses/16873/assignments/514051 3/6 reet ... Warning: This data is... messy and hard to interpret in real life: A single "road" may be represented twice (once for each direction) xor just one time. There may be multiple different roads with the same name that are actually unrelated. To keep this data small, many unnamed roads and paths are missing. Some roads may not actually be usable by cars. Some roads are public while others are privately owned. -- You don't have to worry about this for the purpose assignment but you should know in case you ever want to use this kind of data for a real project. Example Program Here's an example program that shows how you can read and interpret the data. You don't need to use any of this code; it's just here in case you find it helpful: road_length_demo.cpp #include
#include #include #include #include #include