Skiktad grafritning

En skiktad ritning av en riktad acyklisk graf producerad av Graphviz

Skiktad grafritning eller hierarkisk grafritning är en typ av grafritning där hörnen på en riktad graf ritas i horisontella rader eller lager med kanterna generellt riktade nedåt. Det är också känt som grafritning i Sugiyama-stil efter Kozo Sugiyama , som först utvecklade denna ritstil.

Den idealiska formen för en skiktad ritning skulle vara en uppåtgående plan ritning , där alla kanter är orienterade i en konsekvent riktning och inga par av kanter korsar. Emellertid innehåller grafer ofta cykler, att minimera antalet inkonsekvent orienterade kanter är NP-hårt och att minimera antalet korsningar är också NP-hårt, så skiktade grafritningssystem tillämpar vanligtvis en sekvens av heuristik som minskar dessa typer av brister i ritningen utan att garantera att hitta en ritning med det minsta antalet brister.

Layoutalgoritm

Konstruktionen av en skiktad grafritning fortsätter i en sekvens av steg:

Om ingångsgrafen inte redan är en riktad acyklisk graf identifieras en uppsättning kanter vars omkastning kommer att göra den acyklisk. Att hitta den minsta möjliga uppsättningen av kanter är NP-komplett återkopplingsbågeuppsättning , så ofta används giriga heuristik här istället för exakta optimeringsalgoritmer. Den exakta lösningen på detta problem kan formuleras med hjälp av heltalsprogrammering . Alternativt, om antalet omvända kanter är mycket litet, kan dessa kanter hittas med en algoritm som kan hanteras med fasta parametrar .
Topparna av den riktade acykliska grafen som resulterar från det första steget tilldelas lager, så att varje kant går från ett högre lager till ett lägre lager. Målen för detta steg är att samtidigt producera ett litet antal lager, få kanter som spänner över ett stort antal lager och en balanserad tilldelning av hörn till lager. Till exempel, enligt Mirskys teorem , ger tilldelning av hörn efter skikt enligt längden på den längsta vägen med början från varje vertex en tilldelning med minsta möjliga antal skikt. Coffman -Graham-algoritmen kan användas för att hitta en skiktning med en förutbestämd gräns för antalet hörn per skikt och ungefär minimera antalet skikt som omfattas av denna begränsning. Att minimera bredden på det bredaste lagret är NP-hårt men kan lösas genom att förgrena sig och klippa eller approximeras heuristiskt. Alternativt kan problemet med att minimera det totala antalet lager som sträcks av kanterna (utan några begränsningar på antalet hörn per lager) lösas med linjär programmering . Heltalsprogrammeringsprocedurer , även om de är mer tidskrävande, kan användas för att kombinera kantlängdsminimering med gränser för antalet hörn per nivå.
Kanter som sträcker sig över flera lager ersätts av banor av dummy-vertices så att, efter detta steg, varje kant i den utökade grafen förbinder två hörn på intilliggande lager av ritningen.
Som ett valfritt steg kan ett skikt av kantkoncentrators toppar (eller konfluenta korsningar) läggas mellan två befintliga vertexskikt, vilket minskar kanttätheten genom att ersätta kompletta tvådelade subgrafer med stjärnor genom dessa kantkoncentratorer.
Topparna inom varje lager permuteras i ett försök att minska antalet korsningar mellan kanterna som förbinder det med föregående lager. Att hitta det minsta antalet korsningar eller hitta en maximal korsningsfri uppsättning kanter är NP-komplett, även när man beställer ett enstaka lager åt gången på detta sätt, så återigen är det typiskt att tillgripa heuristik, som att placera varje vertex vid en position som bestäms genom att hitta medelvärdet eller medianen av positionerna för dess grannar på den föregående nivån och sedan byta intilliggande par så länge som det förbättrar antalet korsningar. Alternativt kan ordningen av hörnen i ett skikt i taget väljas med hjälp av en algoritm som är följsam med fasta parametrar i antalet korsningar mellan det och det föregående skiktet.
Varje vertex tilldelas en koordinat inom sitt lager, i överensstämmelse med den permutation som beräknades i föregående steg. Överväganden i detta steg inkluderar att placera dummynoder på en linje mellan sina två grannar för att förhindra onödiga böjningar , och att placera varje vertex i en centrerad position med avseende på dess grannar. Sugiyamas ursprungliga arbete föreslog en kvadratisk programmeringsformulering av detta steg; en senare metod av Brandes och Köpf tar linjär tid och garanterar högst två böjar per kant.
Kanterna som vänds om i det första steget av algoritmen återställs till sina ursprungliga riktningar, dummy-vertices tas bort från grafen och hörn och kanter ritas. För att undvika skärningar mellan hörn och kanter, kan kanter som sträcker sig över flera lager av ritningen ritas som polygonala kedjor eller splinekurvor som passerar genom var och en av positionerna som är tilldelade attrappens hörn längs kanten.

Genomföranden

I sin enklaste form kan algoritmer för skiktritning av grafer kräva O( mn ) tid i grafer med n hörn och m kanter, på grund av det stora antalet dummy hörn som kan skapas. För vissa varianter av algoritmen är det dock möjligt att simulera effekten av dummy-vertices utan att faktiskt konstruera dem explicit, vilket leder till en nästan linjär tidsimplementering .

"Prick"-verktyget i Graphviz producerar skiktade ritningar. En grafritningsalgoritm i lager ingår också i Microsoft Automatic Graph Layout och i Tulip .

Variationer

Även om de vanligtvis ritas med hörn i rader och kanter som går uppifrån och ned, kan algoritmer för skiktritning istället ritas med hörn i kolumner och kanter från vänster till höger. Samma algoritmiska ramverk har också tillämpats på radiella layouter där graferna är arrangerade i koncentriska cirklar runt någon startnod och på tredimensionella skiktritningar av grafer.

I skiktade grafritningar med många långa kanter kan kantklatter reduceras genom att gruppera uppsättningar av kanter i buntar och dirigera dem tillsammans genom samma uppsättning dummy-hörn. På liknande sätt, för ritningar med många kanter som korsar mellan par av på varandra följande lager, kan kanterna i maximala tvådelade subgrafer grupperas i sammanflytande buntar.

Ritningar där hörnen är ordnade i lager kan konstrueras av algoritmer som inte följer Sugiyamas ramverk. Det är till exempel möjligt att avgöra om en oriktad graf har en ritning med högst k korsningar, med hjälp av h- lager, i en tidsperiod som är polynom för alla fasta val av k och h , genom att använda det faktum att de grafer som har ritningar av denna typ har begränsad vägbredd .

För skiktade ritningar av konceptgitter kan en hybridmetod som kombinerar Sugiyamas ramverk med additiva metoder (där varje vertex representerar en uppsättning och positionen för vertexen är en summa av vektorer som representerar element i uppsättningen) användas. I detta hybridtillvägagångssätt ersätts vertexpermutations- och koordinattilldelningsfaserna för algoritmen med en enda fas där den horisontella positionen för varje vertex väljs som en summa av skalärer som representerar elementen för den vertexen. Metoder för ritning av diagram i lager har också använts för att tillhandahålla en initial placering för kraftriktade grafritningsalgoritmer .