To reference or cite the objects present in the Software Heritage archive, permalinks based on SoftWare Heritage persistent IDentifiers (SWHIDs) must be used.
Select below a type of object currently browsed in order to display its associated SWHID and permalink.
# Description of the Input and Output formats for graphs and Steiner Trees 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/](https://pacechallenge.org/2018/steiner-tree/) ## Graph format (.gr) 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 ``` # Steiner Trees (.ost) 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 ```