---
# System prepended metadata

title: minCost flow planning step

---

# Notice：
所示為GH，GV：L->B、R->T、W->H
若只需gh, gv圖,其實自graph開始便足夠

# 前置：
macro存在於一個vector(macros)中
已知每個block的x, y, w, h(worldbound)
Connection(Net)存在於一個vector(connections)中
已知Connection中的兩個名字

# L, R, B, T
give `connections` = chip.connections (vector\<Connection>)
foreach ( `connect` in `connections` ) 
&emsp;give `bound` = `Macro.worldBound`
&emsp;give `(L, B)` = `(bound.x, bound.y)`
&emsp;give `(R, T)` = `(bound.xMax, bound.yMax)`
&emsp;比較x, Li, Bi = 最小者；若有一樣大的x, 選y較小的
&emsp;比較x, Ri, Ti = 最大者；若有一樣大的x, 選y較大的

# sequence pair
(...bi ...bj ...,...bi ...bj ...) ⇒ xi + wi ≤ xj (7)
(...bj ...bi ...,...bi ...bj ...) ⇒ yi + hi ≤ yj (8)
foreach (`connect` in `connections`)
&emsp;add to (7)||(8) iif once

# Adjecency list：
1.	用一個for loop 做每一個connection
2.	addVertex：s, t, L1, R1…Ln,Rn
n為connections.size
3.	加s->Ｒ, L->t
addEdge(s, R1, 0, number_of_2_pin_net)... addEdge(s, Ri, 0, ?)
addEdge(L1 , t, 0, ?)...addEdge(Li, t, 0, ?)
4.	如果不存在,加此輪connection內的兩個macro的vertex,命名為nameX
if not :addVertex:connections[i]->macro1.name+”X”
if not :addVertex:connections[i]->macro2.name+”X”
(vertex的總個數應為n*2-重複用到的macro))
5.	加上兩個macro的connection, cost為當前macro的w/2
(用macro的名字在macros裡面找到w)
addEdge(Ri, connections[i]->macro1.name, macros[index].worldbound.w/2)
addEdge(Ri, connections[i]->macro2.name, macros[index].worldbound.w/2)
addEdge(connections[i]->macro1.name, Li, macros[index].worldbound.w/2)
addEdge(connections[i]->macro1.name, Li, macros[index].worldbound.w/2)

# UNSOLVED problems:
1.	capacity:論文中存在數值形式的capacity的只有當edge為s-r, l-t時，其餘皆是Unlimited。且不清楚題目是否給予capacity。
2.	於gh, gv圖(論文例子)，還存在一x1x2關係，我導不出來所以沒寫進去 
3.	用vector, list, linled-list?

