1、Dot算法描述（这里详细说明前3步）：DotAlgorithmDescription符号说明：Symbol:(v)：therankofnodev.结点v的rank。l(e)：thelengthofedgee,ife=(w,v)，thenl(e)=(v)(w)边e的长度，若e=(w,v)则，l(e)=(v)(w)。(v,w)：边(v,w)的weight。Theweightofe(v,w).(e)：边e的最小长度。是对边e的一个约束。Theminimallengthofedgee.Thisisaconstr
2、aintsofedge.slack(e)：l(e)(e)。nodesep(G)：同层结点中2个相邻结点之间允许的最少距离。Theminimaldistanceallowedbetweentwoadjacentnodesinthesamelevel.ranksep(G)：图的相邻2层之间允许的最少距离。Theminimaldistanceallowedbetweentwoadjacentlevelsinthegraph.xsize(v),ysize(v)：结点v的x方向大小和y方向大小。Thesizeofnodevinxcoo
3、rdinateandycoordinate,respectively.(e)：当e的2个端点都是真实结点时，为1；当一个是真实结点，一个是虚拟结点时，为2；当2个都是虚拟结点时，为8。Whenbothofedgeesnodesarerealnodes,thisvalueshouldbe1;Whenoneofthenodesofedgeeisrealone,andtheotherisavirtualnode,thevalueis2;andifbothofthenodesarevirtualnodes,
4、thevalueis8.第一步：分层step1:首先消除回路：removingcycles一种消除回路的方法是：深度优先遍历整个图，发现一个回路，就把回路内所有边的count加1，遍历完整张图之后，把count最大的那条边反向。重复上述过程直到没有回路。OnewaytoremovethecyclesingraphistotraversethewholegraphusingDFT,then,whenfindingacycle,add1tothecountvalueofalltheedgesinthecycle.Wh
5、enDFTcompletes,reversetheedgewiththelargestcountvalue.Repeattheaboveprocedureuntilthereisnocycleinthegraph.消除回路之后，这一步要解决的问题就是：让所有边的总“长度”最小这里所说的长度是指：边的终点的rank边的起点的rank然后乘以边的weight。此外，任意一条边e，它终点的rank起点的rank不能小于(e)。所谓(e)是一个人为规定的值，可以是0，1或者其他任意的值。对于分层这一步可以把(e)设为1。Whenallthecycl
6、esareremoved,nextstepistominimizethetotal“length”ofedges.Thevalue“length”heremeans:therankofedgesstartnodeminusthatoftheendnode,thenmultiplytheweightofthisedge.Additionally,theresultbysubtractingtherankofnodesofoneedgemustbelargerthan(e).(e)isa
7、man-setvalue,whichcouldbeanyvalue,e.g.0or1.weset(e)equalto1inlayering.这个问题的形式化描述是：Theformalspecificationofthisquestionis:minSw(v,w)(l(w)-l(v))subjectto:l(w)-l(v)>=d(v,w)"(v,w)memberE这类问题都可以用networksimplex算法解决。下面的几步也具有相似的形式化描述，也都是用networksimplex算法解决
8、的。Thiskindofquestioncanbecopedwithnetworksimplexalgorithm.Thefollowingstepshavesimilarformalspecificationandarehandledbynetworksimplexalgorithm.该算法的实现如下：Thisalgorithmisimplementedasbelow:首先建立一个feasiblespanningtree。First,createafeasiblespanningtree.feasibletree是这样
9、一个图：对于图中的任意一条边e，都有l(e)>=(e)。feasibletreeisagraphthatthel(e)isnolessthanthe(e)foreveryedgesinthegraph.spanningtree是这样一个图：对于图中的任意一条边e，都有l(e)=(e)。spanningtreeisagraphthatthel(e)isequaltothe(e)foreveryedgesinthegraph.feasiblespanningtree是给定图的一个子集。他拥有图的所
10、有结点和部分边。feasiblespanningtree中的所有边都满足：l(e)=(e)。不在feasiblespanningtree中出现，但在给定图中出现的边叫做non-treeedge。feasiblespanningtreeisasubsetofgivengraphwhichincludesallofthenodesandpartoftheedgeoforiginalgraph.Alltheedgesinfeasiblespanningtreesatisfythatthatthel(e)iseq
11、ualtothe(e).wecalltheedgesthatareinthegraphbutnotinthefeasiblespanningtreenon-treeedge.至于如何对一个给定图建立feasiblespanningtree这里不再赘述。Thequestionthathowtocreateafeasiblespanningtreeforgivengraphisoutofthescopeofthispaper.其次，在feasiblespanningtree的基础上计算各条边的cutvalu
12、e。secondly,calculatethecutvalueofeachedgesonthebasisoffeasiblespanningtree什么是cutvalue？在feasiblespanningtree中，去掉一条边e，可以把这个tree分成2部分。边e进入的那部分叫做头端部分，边e出来的那部分叫做尾端部分。cutvalue就是在所有边中，从尾端部分进入头端部分的那些边的weight的总和减去从头端部分进入尾端部分的那些边的weight的总和。例如下图：其中，虚线表示non-treeedge，结点和实线组成了feasiblespanning
13、tree，边上面所标的就是cutvalue(这个图中，所有边的weight都是1)。Thedefinitionofthecutvalue.Thefeasiblespanningtreewillbeseparatedintotwopartswhenremovingaparticularedgee.Wecallthepartwhichecomesintoasheadpart,andtheotherpartthatecomesoutastailpart.Thecutvalueiscalculated
14、bysubtractingthesumoftheweightoftheedgesthatenterintothetailpartfromtheheadpartoutofthesumoftheweightoftheedgesthatenterintotheheadpartfromthetailpart.Forexample,inthefollowinggraph,thedotedlinesshowthenon-treeedges.Allthenodesandsolidlinesc
15、omposethefeasiblespanningtree.Thecutvalueareshownnexttotheedge,assumingalltheweightofedgeis1.然后，找出feasiblespanningtree中，cutvalue小于0的边，用non-treeedge进行替换，并进行调整，直到feasiblespanningtree中所有边的cutvalue都大于等于0。Next,findtheedgewhosecutvalueislessthan0inthetree,exchange
16、itwithanon-treeedgeandrecalculatethecutvalue.Repeatthisprocedureuntilallthecutvalueofedgesarelargerthan0.对于上面的图，调整后效果如下：Forexample,weadjusttheabovegraphasfollows:这一步中，比较复杂的地方有：1）产生feasiblespanningtree2）计算cutvalue。Themostcomplicatecalculationinthissteparecr
17、eatingfeasiblespanningtreeandcomputingcutvalue。第二步：同层内结点排序step2:ordernodeinthesamerank这一步的目的是尽量减少交叉。算法实现如下：Thisstepaimstominimizethecrossings.Algorithmisimplementedasfollows:首先，确立各层结点的初始顺序。Firstofall,establishaninitialorderfornodesofeachrank.这一步比较简单，深度或者广度优先遍历第一步中
18、的feasibletree。按照遍历的顺序对各层的结点进行排序。Thisstepisrelativelysimple,depthorbreadth-firsttraversalofthefeasibletreecreatedinthefirststep.Sortthenodesineachrankinaccordancewiththeorderoftraversal.其次，进行若干次迭代，调整结点的排列顺序。这里把迭代的次数设定为25次（0-24）。Secondly,carryoutanumberofiterations
19、toadjusttheorderofthenode.Herethenumberofiterationissetto25(0-24).每一次迭代，要做两件事情：Eachiteration,todotwothings:第一件事是根据前一层（注意前一层不是上一层，前一层是指在处理本层之前处理的那一层。当从上层往下层进行处理的时候，前一层就是上一层；而当从下层往上层进行处理的时候，前一层就是下一层）结点的排列顺序，对本层结点进行排序。具体如下：Thefirstthingistoordernodesofthecurrentlevelbas
20、edontheorderofthenodesofthepre-level(Pre-levelhereisnottheupperlevel,itmeansthelevelhandledbeforethislevel.Inatop-to-bottomprocessing,pre-levelmeanstheupperlevel;butinabottom-to-topprocessing,pre-levelmeansthedownwardlevel).Asfollows:假设前一层的结点顺序为：a,b,c,
21、d,e,f,g。则他们的order分别为：0，1，2，3，4，5，6。Assumethenodesorderofthepre-levelis:a,b,c,d,e,f,g.Theorderofthem:0,1,2,3,4,5,6.本层有一个结点m，与前一层的结点a,c,d,f,g相连，则结点m的优先值为a,c,d,f,g的中值，也就是d的order，3。如此，将本层所有结点的优先值都计算出来然后升幂排序。Thecurrentlevelhasanodem,connectingwithnodea,c,d
22、,f,gofthepre-level,thepriorityvalueofnodemisthemedianofa,c,d,f,g,thatisnodedsorder,3.Nevertheless,allthenodespriorityvaluesarecomputed.Thenorderthenodesonpower-upsequencing.需要注意的是，当迭代次数为偶数的时候，自上而下进行处理；当迭代次数为奇数的时候，自下而上进行处理。Itshouldbenotedthat,evenasthe
23、numberofiterations,top-downprocessing;whenanoddnumberofiterations,bottom-upprocessing.第二件事是微调，也就是对于每一层的每两个相邻结点，对调它们的位置，如果对调后交叉次数减少了，就保留这次对调。否则恢复原来排列顺序。Thesecondthingisafine-tuning,thatis,foreverytwoadjacentnodesofeachlevel,reversedtheirposition.Ifthenumberofcrossi
24、ngsdecreasedaftertheswap,savetheneworder.Otherwise,restoretheoriginalorder.做完上面的两件事情之后，将新的结点排序与上次迭代的结点排序对比，如果有提高（交叉减少）就保存新的结点排序，否则放弃新的结点排序。继续下一次迭代。Aftertheabovetwothings,comparethenewnodesorderwiththepreviousone.Savethenewnodesorderifthereisanyimprovement(toredu
26、bonthesamerankandr(a,b)=(xsize(a)+xsize(b)/2+nodesep(G)这个问题与第一步中的问题有相似的形式化描述，因此也用networksimplex算法解决。（不过，这个与之前有所不同，之前是：l(w)-l(v)，而现在是：xw-xv）具体实现如下：Toachieveconcreteareasfollows:首先，确立初始坐标。Firstofall,toestablishtheinitialcoordinates.按照第二步中给出的结点顺序，从左到右设定结点坐标。第一个节点x坐标设为0，
27、第二个结点为nodesep(G)，第三个为2*nodesep(G)，依次类推，这样每个结点的坐标都是尽可能的靠近左侧。Accordingtothenodesordersubjecttostep2,fromlefttorightsetthecoordinatesofthenodes.Thexcoordinateofthefirstnodeisset0,thesecondisnodesep(G),thethirdis2*nodesep(G),followedbyanalogy,sothateverynod
28、eofthecoordinatesareasmuchaspossibleclosetotheleftsideineachlevel.其次，进行若干次迭代，调整结点的x坐标。这里把迭代的次数设定为9次（0-8）。Secondly,tocarryoutanumberofiterations,toadjustthexcoordinatesofthenodes.Herethenumberofiterationissetto9(0-8).每一次迭代，都要做如下几件事情：Everyiteration,dothefol
29、lowingthings:第一，取中值。这与第二步中的取中值是类似的。所不同的是，这里取的中值并不一定是结点将要安放的坐标，而只是结点想要安放的坐标。因为不同的结点可能会取到相同的中值，所以要给每个结点设置一个优先级，在发生冲突的时候首先满足优先级高的结点。这里的优先级定义为：结点与前一层相连的所有边的weight的总和。First,calculatemedian.Thisissimilartothemediancomputinginstep2.Thedifferenceisthatthemedianhereisnotnecessarilythe
30、coordinatewherethenodewillbeplaced,butthecoordinatewherethenodewantstoplace.Duetoanumberofnodesmaygetasamemedianvalue,sogiveeachnodeapriorityvalue.Whenconflicthappens,meetthehigherprioritynodefirst.Thepriorityhereisdefinedas:sumoftheweightofedg
31、eswhichconnectthisnodewiththepre-level.第二，边长度最小化。做这件事情的方法与上一件事情类似。所不同的是，这里不考虑虚拟结点。这是因为虚拟结点毕竟不是真实的结点，最终是要被删除的，所以应该弱化虚拟结点对接点坐标排布的影响。Second,minimizethelength.Thisissimilarwiththepreviousthing.Thedifferenceisthatthisdoesnottakeintovirtualnodes.Thisisbecausethevirtualnod
32、esarenotrealnodes,theywillberemovedintheend,soshouldweakentheeffectofvirtualnodesonthecoordinatesplacement.第三，结点微调。这一步开始时先把所有结点装入一个队列。当一个结点被移出队列的时候，该结点的x坐标被设定为在不违反r(a,b)的情况下，尽可能的靠近所有与它相邻的结点（包括上一层的和下一层的结点）的中值。如果这个新的位置与之前的位置不同，就把所有与它相邻并且不在队列中的结点重新放入队列。重复这个过程直到队列为空。（这个地方不大理解，这样的
33、话会不会死循环？）Third,thenodefine-tuning.Initiallyallnodesarequeued.Whenanodeisremovedfromthequeue,itisplacedascloseaspossibletothemedianofallitsneighbors(bothupanddown)subjecttotheseparationfunctionr(a,b).Ifthenodesplacementischanged,itsneighborsarere-que
34、uedifnotalreadyinthequeue.Repeatthisprocessuntilthequeueisempty.(Donotquiteunderstandthisplace,sowillthecycleofdeath)第四，路径优化。就是把由虚拟结点构成的路径变成直线。如下图：Fourth,optimizethepath.Itisthatstraightenthepathconstitutebyvirtualnodes.Plansareasfollows:为虚拟结点为真实结点第五，用networksimplex算法优化结点排布。由于这一步的问题的形式化描述与第一步中的不同，这一步是在x方向上的networksimplex算法，而第一步时y方向上的networksimplex算法。所以要对原来的