Class Tree
Description Channel Routing is a kind of routing problem where the routing area is
restricted to a rectangular channel. A channel consists of two horizontal rows
with terminals on them. The terminals are numbered 1, 2, and so on from left
to right. The routing area is divided into layers and each layer has one or
more tracks parallel to the two rows of terminals. A connection requirement,
called a net, specifies the terminals that must be interconnected through
a routing path, which consists of one horizontal segment placed on some track
in a layer and several vertical segments (dogleg-free). A channel routing
problem is to find routing paths for a given set of nets for a given channel
such that no paths overlap each other. The following figure depicts a solution
to a problem for a one-layer channel.



Input format

The input file contains the following atoms:

a. An atom that specifies the number of layers N in the channel:

layers(N).

b. An atom that specifies the number of tracks M in each layer:

tracks(M).

c. A set of connecting requirements, each of which has the format:

connect(Id,Row,Term)

where Id is the id of a net, Row is either top (meaning the top row) or
bot (meaning the bottom row), and Term is a terminal numer. For example:

connect(n1,top,1). connect(n1,top,2). connect(n2,top,3).
connect(n2,top,6). connect(n2,bot,7).

Output format

The output gives a layout for the given set of nets as a ternary predicate

pos(Id,L,T)

where Id the id of a net, L is the number of the layer, and T is the number
of the track assigned to the net. For example:

pos(n1,1,1). pos(n2,1,3).

The output should be "no_solution" if the constraints are not satisfiable.

Constraints

Let pos(A,La,Ta) and pos(B,Lb,Tb) be the layout for two nets A and B.
The two nets overlap if either of the following is true:

a. If the two nets are placed in the same layer (La=Lb) and there exist
connections connect(A,top,Term) and connect(B,bot,Term)
(i.e., A connects to the top terminal and B connects to the bottom
terminal with the same number) such that Ta>=Tb.

b. If the two nets are placed on the same track (La=Lb and Ta=Tb) and
there exist connections connect(A,_,TermAMin), connect(A,_,TermAMax)
and connect(B,_,TermB) such that TermAMin =< TermB =< TermAMax
('_' means that it is either top or bot).

Sample input

layers(1). tracks(7).
connect(n1,top,1). connect(n1,top,2).
connect(n2,bot,1). connect(n2,bot,3). connect(n2,top,4).
connect(n3,bot,2). connect(n3,top,5). connect(n3,top,7).
connect(n4,top,3). connect(n4,top,6). connect(n4,bot,7).
connect(n5,bot,5). connect(n5,top,9). connect(n5,top,11).
connect(n6,bot,6). connect(n6,top,8). connect(n6,bot,9).
connect(n7,bot,8). connect(n7,bot,12).
connect(n8,top,10). connect(n8,bot,11).
connect(n9,bot,10). connect(n9,top,12).

Sample output

pos(n1,1,1). pos(n2,1,5). pos(n3,1,2). pos(n4,1,4). pos(n5,1,3).
pos(n6,1,5). pos(n7,1,6). pos(n8,1,4). pos(n9,1,5).

Authors: Neng-Fa Zhou
Affiliation: CUNY Brooklyn College
Encodings
1 - 1 of 1