本项目针对集成电路线网布线问题，完成了以下工作：
- 完成了一套用于电路构成元素和约束条件表示的数据结构。可以覆盖本次比赛测试样例中所使用的METAL、VIA、CELL等电路构成元素
- 完成了一套针对LEF和DEF文件的parse库。可以覆盖本次比赛测试样例中使用的LEF、DEF语法子集，将代码文本所描述的电路结构、元件和约束条件信息转换到上一条所说的数据结构表示
- 完成了用于电路布线的功能模块。针对DEF描述的元件放置与连接关系，根据LEF中描述的元件属性与约束条件进行布线（放置导线和via）
由于我们希望减少算法执行过程中冗余的信息，因此需要自行设计数据结构进行电路表示（这样可以在布线时更快地查找相关信息）。不过这样就无法使用cadence的开源parser。因此我们给出了一个相较cadence parser更简洁的parser实现，它使用简单的状态机堆叠构成，高效地对DEF和LEF代码进行分析，并将分析结果转换成我们需要的数据结构。
下面将分别介绍我们的电路表示结构与Parser设计
我们的数据结构分为对DEF表示结构和对LEF表示结构两部分。DEF表示结构通过DEF parser对DEF代码进行分析而实例化，LEF表示结构则是通过分析LEF代码而实例化。DEF表示了一个实际电路的元件的摆放与连接关系，LEF则表示了METAL、VIA、CELL等电路元件与布线所需部件的属性。
描述被放置于版图中的元件（对应DEF文件的COMPONENTS代码块）
QString instNamecomponent对象的名字。这是component对象在DEF文件中的标识名字
QString cellName这个（种）元件的名字。在LEF表示结构中查询这个名字，可以得到关于这个（种）元件的具体描述
举个例子，元件CELL1可以在版图中被放置多个，它们可以被命名为inst1和inst2。那么CELL1就是cellName，inst1就是instName
float x
float y
component对象在版图中被放置的位置
QString dire
component对象在版图中被放置的方向
描述某个component对象上的一个接口，一般用于表示导线的终端。这个类仅记录component对象名字和接口名字，关于这个接口的具体信息需要到LEF表示中查询
QString instNamecomponent对象的名字
QString pinName接口的名字
通过component对象名查询到component对象，再通过component对象的cellName属性查询LEF表示结构中的cell对象，即可在cell对象中通过pinName查询到对应cell中这个接口的相关信息
描述一组接口间的连接（对应DEF文件的NETS代码块）
QString name这组连接的名字
vector<pin> allPin连接的所有接口（将这些接口连接在一起）
描述版图某一金属层的属性
int m金属层对象的ID
float width本金属层中导线的宽度
float spacing本金属层中导线的最小间距（中心线距离）
float area=-1单条导线的最小面积约束（-1表示无约束）
bool vertical本层导线是水平走线还是竖直走线，true为竖直走线
QString getName()如m=1，那么这个函数将返回METAL1。METAL+金属层ID是LEF文件中对金属层的标识名字。有时需要使用这个名字进行一些查询
描述穿透连接两层金属的孔
int m1起始金属层ID
int m2目标金属层ID（一般是相邻的）
float spacing孔所占的面积
描述一个元件
QString cellName（这种）元件的名字
QString instName元件对象在DEF中的标识名字。每个LEF::cell对象都对应了一个DEF::component对象，可以用这个名字实现二者间的查询。可以参照上一节中的component类小节
float sizeA1
float sizeA2元件对象的长与宽
vector<pin> allPin元件对象中的所有接口（这个pin是下小节所说的LEF::pin，不是前面的DEF::pin）
obs o元件中所有不可走线的障碍区域（不同层的障碍区域在obs对象中分别存储）
void setToLayout(float setX, float setY, QString dire)已知元件对象被放置到版图的坐标和方向时，将该对象的所有接口和障碍区域rect按dire所描述的方向进行旋转，并转换到版图坐标系
描述一个接口（接口对象会组合到cell对象当中）。与DEF表示中的pin类不同的是，这个类中存储接口的具体属性
QString name接口的名字
QString layer接口所在层的名字（为metal::getName()的返回值格式）
vector<rect> allRect构成接口的所有rect。如果导线想要与这个接口连接，与其中任意一个rect连接即可
void setToLayout(float setX, float setY, QString dire)已知接口对象所在的cell被放置到版图的坐标和方向时，将该接口中所有rect的坐标按dire所描述的方向进行旋转，并转换到版图坐标系
我们实现了两个不同的parser分别解析DEF代码和LEF代码。它们都使用简洁的状态机堆叠构成。
defParser(QString code)构造parser对象时传入DEF代码文本内容。构造函数中会直接进行parse，将分析结果直接存入本对象的allComponent、allPin（本题暂不考虑）和allNet数据成员中
Parser分为扫描COMPONENTS和扫描NETS两个子状态，分别对应COMPONENTS和NETS代码块。COMPONENTS代码块中有多个component的描述；NETS代码块中有多个net的描述，每个net由多个DEF::pin组成。在进入状态后，parser会逐行提取这些component、net（包含其中的pin）的信息，并构造对象，将其存储到数据成员中
lefParser(QString code)构造parser对象时传入LEF代码文本内容。构造函数中仅会对代码进行简单拆分，不进行parse。通过下面介绍的get系列函数获取LEF中某个cell、metal、via的信息
LEF::via getVia(int m1,int m2)获取某个via的信息。如传入参数m1=1,m2=2，则会在LEF代码中查找VIA12的信息，构造LEF::via对象并返回
LEF::metal getMetal(int _m)获取某个metal的信息。如传入参数_m=1，则会在LEF代码中查找METAL1的信息，构造LEF::metal对象并返回
LEF::cell getCell(QString cellName)获取某个cell的信息。如传入参数cellName=”CELL1”，则会在LEF代码中查找CELL1的信息，构造LEF::cell对象并返回。
对cell的解析过程有扫描OBS和扫描PIN两个子状态（由私有成员函数getOBS和getPin实现），分别对应cell代码块中的PIN子代码块（有多个）和OBS子代码块（有一个）。两个子状态函数可以提取cell中pin和OBS的信息，并添加到cell对象的allPin和o成员中
布局模块接受DEF parser和LEF parser作为输入。DEF parser中包含对DEF代码分析后得到的电路结构。LEF parser指定了布线所使用的LEF文本，但先不对它进行分析，在布线过程中再对需要知道的信息进行实时查询。
下面将以布线模块的成员函数为单元，对布线过程进行分步说明（按函数调用顺序）
构造函数用于初始化资源，即向LEF parser查询DEF中所有的component对应的cell。并将cell对象和cell中所有的rect根据DEF指定的版图坐标和放置方向转换到版图坐标系。
connectAllNet函数尝试分别连接DEF中各个net下的所有接口（如net1下的所有接口要被连接在一起，net2下的所有接口要被连接在一起……）。这也是我们的核心任务。
我们采用基于贪心思想的策略：一个接口总是先与离它最近的接口连接。为了达到这一目的，我们首先应当对接口进行排序，如allPin是存储一个net下所有接口的数组，那么排序的逻辑为：
- 数组第0个元素不变
- 第1个元素替换为距离第0个元素最近的那个pin
- 第2个元素替换为距离第1个元素最近的那个pin
- ……以此类推
这样排序后，将第i接口与第i+1个接口进行连接即可。这个功能由connect函数完成。
connect函数尝试放置导线和via连接两个接口。
首先我们要选择走线的起点和终点。由于接口由多个rect构成，将导线连接到任意一个rect都视为对这个接口的连接。那么为了使得导线长度最短，我们选择连接两个接口最近的rect。如接口1在接口2左上，那么连接接口1右下和接口2左上的两个rect。
选择了起点和终点后，先生成最短曼哈顿路线的导线，即：
显然，这样的路径有两条（从r1出来先水平走，或者从r1出来先竖直走）。这里的选择涉及到r1对应的金属m1是允许水平走线还是允许竖直走线。我们选择金属m1允许的方向，这样可以保证第一条导线合法。按照这种策略，第一条导线金属层与r1所在的金属层相同，为m1。那么第二条导线将选择介于m1和m2之间、且走线方向与m1相反的金属层。这样可以使得需要的via尽量少。不过目前放置的这两条导线没有考虑与其它导线和obs区域冲突的问题，首先需要解决冲突。
对于目前的水平、竖直两条导线，分别调用checkLine函数检查与其碰撞的冲突矩形。
这里说的冲突矩形包含了obs区域、其它接口的rect和其它同层导线。需要注意的是，因为LEF约束了导线间的最短距离，在计算该导线与其它导线是否碰撞时，两条导线的宽都将膨胀(spacing-width)/2。如下图所示：
checkLine将会返回与其碰撞的“最左下”冲突矩形。如如下图所示的情况：
checkLine仅会返回矩形1。这是因为解决冲突需要有一个顺序：先解决导线“碰撞”到的第一个矩形。这样会保证所做的工作是有效的。
举个例子：
如果先绕过第二个冲突矩形，那么它左边的导线依然与第一个冲突矩形冲突，此时再解决第一个冲突，不能保证绕过第一个冲突的导线末端可以与绕过第二个冲突矩形的导线首端顺利连接。
而先绕过第一个冲突矩形后，我们可以重新生成最短路径导线：
然后对新的最短路径导线（导线2与导线3）检查冲突即可。此时导线1一定是可用的。
需要注意的是，这个顺序只需要在解决所有冲突时一致即可，实际可以将“最左下”的作为“第一个冲突矩形”，也可以将“最右上”的作为第一个冲突矩形。
按照此逻辑，可以解决冲突，基于原先最短路径的导线生成符合LEF约束要求的导线。