The files describing the RST construction domain (rst.lp), some RST routing problems shown in figures (fig2, fig4) or used in our experiments (A, B, C, D), with the grid-points not covered by the obstacles (points.lp), and the other files mentioned below are enclosed in rst-lparse-basic.tar.gz.
With these files, we can solve RST construction problems using cmodels (with zchaff). For instance, a solution to problem A, with n=58 and radius=8, can be computed by the command
For a more efficient computation, we can add to the domain description noadjacency constraints and some other constraints presented in the file heuristics.lp:
To restrict the lengths of paths in an RST construction problem, we need the file restrict_length.lp. For instance, a solution to problem A, with n=58 and radius=8, where every path connecting a sink point to the source point is at most l=16, can be computed by the command
To construct a tree, that may not be an RST, we need the file tree.lp. For instance, a tree connecting the sink points to the source point in problem C, with n=85 and radius=8, can be computed by the command
Note that adding the file tree.lp above makes the domain description nontight.
For larger problems, you can try problems E and F.
To solve wire routing problems where pairs of pins are connected, in addition to rst.lp and points.lp, we need the file routing.lp. For instance, a solution to problem fig9 shown in Figure 9, with n=50 and radius=5, can be computed by the command
Some other routing problems of this kind (p7, p15, p20, p25) and the file routing.lp are enclosed in rst-lparse-basic.tar.gz.
Other ASP formalizations of wire routing problems where pairs of pins are connected:
(for more information, see Chapter 7 of "Theory and Applications of Answer Set Programming," E. Erdem, Ph.D. Thesis, Technical Report CS-TR-02-69, Department of Computer Sciences, University of Texas at Austin, 2002.)
(for more information, see "Wire routing and satisfiability planning," E. Erdem, V. Lifschitz, and M. D. F. Wong, in Proceedings of the First International Conference on Computational Logic (CL'00), pages 822-836, 2000.)