Homework Networking

IS 100 ShanghaiTech University


You have to implement a program that generates a Minimum Spanning Tree for a given undirected graph.


The input comes on stdin with three items per line, separated by white space. The first two items are strings identifying the two nodes of an edge and the last part is an integer number bigger than 0, representing the weight of the edge.
The input may contain blank lines.
Lines starting with the hash sign (#) are comments and are to be ignored.
You can rely on the fact that all input graphs will have at most one edge between two nodes and no edges that start and end at the same node.
All input provided will have a unique solution for the minimum spanning tree.


The output should be on stdout. It is the minimum spanning tree of the input graph in the same format as the input (two node names and the eight of the edge, separated by spaces, each edge in a new line). The output will have to be sorted using the string comparison on the node names: Each edge should be printed with the smaller node printed first. The tree should be printed with the smallest node-names first. If there two edges "start" from the same node they have to be sorted after the goal node.
The graph may not be connected. So you may have to calculate multiple minimum spanning trees (so a forest).


# This is a comment
nodeA nodeB 12
nodeC nodeB 10

nodeC nodeA 8
f nodeB 5556
# another tree...
x1 x2 2
x3 x1 10
x3 x2 8

f nodeB 5556
nodeA nodeC 8
nodeB nodeC 10
x1 x2 2
x2 x3 8

Invalid input

In case invalid input is encountered the program should terminate with exit code 11 (you should also print some text about the error).

Implementation requirements

You have to implement and USE a class called Graph and another class called Edge (will be checked by hand).