» ASP Competition


Channel Routing

Problem 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).


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).

Sampe 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).

Sampe 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