Zkouska 29.1.2025

Zkouška Directed Graph Distances

Create a program that computes distances in a directed graph, controlled by three command-line arguments:

• argv[1] The name of the input file containing the graph

• argv[2] The name of the input file containing distance queries

• argv[3] The name of the output file

All the three files are in the comma-separated-value format with a header row.

The first file describes the graph using three columns (in this order): node_1, node_2, distance. node_1 and node_2 may be arbitrary printable strings, not containing commas , and line delimiters. distance is a non-negative integer number in decimal form.

Example: edges01.txt 14 nodes 15 edges

node_1,node_2,distance
Albertov,Botanicka zahrada,1
Andel,Arbesovo namesti,1
Andel,Bertramka,2
Botanicka zahrada,Karlovo namesti,1
Andel,Na Knizeci,1
Albertov,Ostrcilovo namesti,1
Zvonarka,Bruselska,0
Albertov,Vyton,1
Andel,Zborovska,1
Botanicka zahrada,Albertov,1
Zborovska,Palackeho namesti,1
Palackeho namesti,Karlovo namesti,2
Karlovo namesti,Moran,1
Moran,Botanicka zahrada,1
Moran,Palackeho namesti,1

The second file contains the queries, i.e. pairs of nodes (in this order): node_1, node_2. Example: queries01.txt 10 queries

node_1,node_2
Albertov,Albertov
Albertov,Andel
Andel,Albertov
Albertov,Botanicka zahrada
Albertov,Karlovo namesti
Karlovo namesti,Albertov
Karlovo namesti,Botanicka zahrada
Botanicka zahrada,Albertov
Botanicka zahrada,Andel
Botanicka zahrada,Arbesovo namesti

The output file shall contain these three columns (in this order): node_1, node_2, distance. The rows of the output file must correspond to the rows of the second file, in the same order. The distance column shall contain the length of the shortest directed path from node_1 to node_2. If there is no path from node_1 to node_2, the distance column shall be empty.

Example: results01.txt Test 01 with edges01.txt queries01.txt

node_1,node_2,distance
Albertov,Albertov,0
Albertov,Andel,
Andel,Albertov,7
Albertov,Botanicka zahrada,1
Albertov,Karlovo namesti,2
Karlovo namesti,Albertov,3
Karlovo namesti,Botanicka zahrada,2
Botanicka zahrada,Albertov,1
Botanicka zahrada,Andel,
Botanicka zahrada,Arbesovo namesti,