The input and output formats used in our program are the same used by the PACE Challenge 2018 (Track 3, Heuristic). The description below was extracted from the link https://pacechallenge.org/2018/steiner-tree/
We use the format ".gr" to specify graphs.
The file starts with a line ‘SECTION Graph’. The next two lines are of the form ‘Nodes #nodes’ and ‘Edges #edges’, always in that order, where #nodes is the number of vertices and #edges is the number of edges of the graph. The #edges next lines are of the form ‘E u v w’ where u and v are integers between 1 and #nodes representing an edge between u and v of weight the positive integer w. The following line reads ‘END’ and finishes the list of edges.
There is then a section Terminals announced by two lines ‘SECTION Terminals’ and ‘Terminals #terminals’ where #terminals is the number of terminals. The next #terminals lines are of the form ‘T u’ where u is an integer from 1 to #nodes, which means that u is a terminal. Again, the section ends with the line ‘END’.
The file ends with a subsequent line ‘EOF’. Here is an example of a small graph.
SECTION Graph
Nodes 5
Edges 6
E 1 2 1
E 1 4 3
E 3 2 3
E 2 4 4
E 3 5 10
E 4 5 1
END
SECTION Terminals
Terminals 2
T 2
T 4
END
EOF
We use the format ".ost" to specify Steiner trees. The file starts with the line ‘VALUE x’ where x is the weight of the found Steiner tree. The next lines are of the form ‘u v’ where u and v are two vertices of the graph linked by an edge and lists all the edges of the found Steiner tree. Here is a small example.
VALUE 20
1 3
3 5
7 3
10 7
7 22