Graftegning - Graph drawing

Denne artikkelen handler om det generelle emnet graftegning. For det årlige forskningssymposiet, se International Symposium on Graph Drawing .
Grafisk fremstilling av en liten brøkdel av WWW , som viser hyperkoblinger .

Graftegning er et område innen matematikk og datavitenskap som kombinerer metoder fra geometrisk grafteori og informasjonsvisualisering for å utlede todimensjonale skildringer av grafer som stammer fra applikasjoner som sosiale nettverksanalyse , kartografi , lingvistikk og bioinformatikk .

En tegning av en graf eller et nettverksdiagram er en illustrasjon av hjørnene og kantene på en graf. Denne tegningen skal ikke forveksles med selve grafen: svært forskjellige oppsett kan tilsvare den samme grafen. I det abstrakte er det eneste som betyr noe hvilke par hjørner som er forbundet med kanter. I betongen påvirker imidlertid arrangementet av disse hjørnene og kantene i en tegning dets forståelighet, brukervennlighet, fabrikasjonskostnad og estetikk . Problemet blir verre hvis grafen endres over tid ved å legge til og slette kanter (dynamisk graftegning) og målet er å bevare brukerens mentale kart.

Grafiske konvensjoner

Rettet graf med pilspisser som viser kantretninger

Grafer tegnes ofte som node -link diagrammer der toppunktene er representert som disker, bokser eller tekstetiketter og kantene er representert som linjesegmenter , polyliner eller kurver i det euklidiske planet . Nodelinkdiagrammer kan spores tilbake til verkene fra Pseudo-Lull fra 1300- og 1500-tallet som ble utgitt under navnet Ramon Llull , en polymat fra 1200-tallet. Pseudo-Lull tegnet diagrammer av denne typen for komplette grafer for å analysere alle parvise kombinasjoner mellom sett med metafysiske begreper.

Når det gjelder dirigerte grafer , danner pilspisser en vanlig grafisk konvensjon for å vise orienteringen ; brukerstudier har imidlertid vist at andre konvensjoner som nedtrapping gir denne informasjonen mer effektivt. Oppad plantegning bruker konvensjonen om at hver kant er orientert fra et nedre toppunkt til et høyere toppunkt, noe som gjør pilspisser unødvendige.

Alternative konvensjoner til node -link -diagrammer inkluderer tilstøtelsesrepresentasjoner som sirkelpakninger , der hjørner representeres av uforenede områder i planet og kantene er representert ved tilstøtninger mellom regioner; skjæringsrepresentasjoner der hjørner er representert av ikke-usammenhengende geometriske objekter og kanter er representert ved deres kryss; synlighetsrepresentasjoner der hjørner er representert av områder i planet og kantene er representert av områder som har en uhindret siktlinje til hverandre; konfluente tegninger, der kantene er representert som glatte kurver innenfor matematiske togspor ; tekstiler, der noder er representert som horisontale linjer og kanter som vertikale linjer; og visualiseringer av adjasensmatrisen i grafen.

Kvalitetstiltak

Mange forskjellige kvalitetstiltak er definert for graftegninger, i et forsøk på å finne objektive midler for å evaluere deres estetikk og brukervennlighet. I tillegg til å veilede valget mellom forskjellige layoutmetoder for den samme grafen, prøver noen layoutmetoder å direkte optimalisere disse målene.

Plan graf tegnet uten overlappende kanter
  • Den kryssing antall av en tegning er antall par med kanter som krysser hverandre. Hvis grafen er plan , er det ofte praktisk å tegne den uten kantkryss; det vil si, i dette tilfellet, representerer en graftegning en grafinnbygging . Imidlertid oppstår ikke -plane grafer ofte i applikasjoner, så graftegningalgoritmer må generelt tillate kantoverganger.
  • Det område av en tegning er så stor som den minste omgivende boks , i forhold til den nærmeste avstanden mellom hvilke som helst to toppunkter. Tegninger med mindre område er generelt å foretrekke fremfor de med større areal, fordi de gjør at tegningene kan vises i større størrelse og derfor mer leselig. Den sideforhold av avgrensningsboksen, kan også være viktig.
  • Symmetri -visning er problemet med å finne symmetri -grupper innenfor en gitt graf, og finne en tegning som viser så mye av symmetrien som mulig. Noen layoutmetoder fører automatisk til symmetriske tegninger; Alternativt starter noen tegnemetoder med å finne symmetrier i inndatagrafen og bruke dem til å konstruere en tegning.
  • Det er viktig at kantene har så enkle former som mulig, for å gjøre det lettere for øyet å følge dem. På polylinjetegninger kan kompleksiteten til en kant måles med antall bøyninger , og mange metoder tar sikte på å gi tegninger få få bøyninger eller få bøyninger per kant. På samme måte for spline -kurver kan kompleksiteten til en kant måles med antall kontrollpunkter på kanten.
  • Flere vanlige kvalitetstiltak angår kantlengder: det er generelt ønskelig å minimere den totale lengden på kantene så vel som maksimal lengde på en kant. I tillegg kan det være å foretrekke at kantlengdene er jevne fremfor svært varierte.
  • Vinkeloppløsning er et mål på de skarpeste vinklene i en graftegning. Hvis en graf har hjørner med høy grad, vil den nødvendigvis ha liten vinkeloppløsning, men vinkeloppløsningen kan begrenses nedenfor av en funksjon av graden.
  • Den skråning antall av en kurve som er det minste antall av distinkte skråningshelninger som trengs i en tegning med rett linjesegment kanter (slik at kryssinger). Kubikkgrafer har skråningstall på maksimalt fire, men grafer i grad fem kan ha ubegrenset stigningstall; det er åpent om stigningstallet for grad-4-grafer er begrenset.

Oppsettsmetoder

En kraftbasert nettverksvisualisering.

Det er mange forskjellige grafoppsettstrategier:

  • I kraft-baserte layout systemer, grafen tegning programvare modifiserer en første toppunktet plassering ved kontinuerlig å bevege knutepunktene i henhold til et system av krefter som er basert på fysikalske metaforer relatert til systemer av fjærer eller molekylmekanikk . Vanligvis kombinerer disse systemene attraktive krefter mellom tilstøtende hjørner med frastøtende krefter mellom alle par av hjørner, for å søke et oppsett der kantlengder er små mens hjørner er godt atskilt. Disse systemene kan utføre gradient nedstigningsbasert minimering av en energifunksjon , eller de kan oversette kreftene direkte til hastigheter eller akselerasjoner for de bevegelige hjørnene.
  • Spektrale layoutmetoder bruker som koordinater egenvektorene til en matrise, for eksempel Laplacian, avledet fra adjasensmatrisen i grafen.
  • Ortogonale layoutmetoder, som gjør at kantene på grafen kan løpe horisontalt eller vertikalt, parallelt med koordinataksene i oppsettet. Disse metodene ble opprinnelig designet for VLSI og PCB layout problemer, men de har også blitt tilpasset for graftegning. De involverer vanligvis en flerfasetilnærming der en inngangsgraf planiseres ved å erstatte krysningspunkter med hjørner, en topologisk innebygging av den planiserte grafen blir funnet, kantretninger velges for å minimere bøyninger, hjørner plasseres konsekvent med disse orienteringene, og til slutt et layout komprimeringstrinn reduserer området på tegningen.
  • Treoppsettalgoritmer disse viser en rotfestet trelignende formasjon, egnet for trær . Ofte, i en teknikk som kalles "ballongoppsett", tegnes barna til hver node i treet på en sirkel rundt noden, med radiene til disse sirklene avtagende på lavere nivåer i treet, slik at disse sirklene ikke overlapper hverandre.
  • Lagdelte graftegningsmetoder (ofte kalt Sugiyama-stiltegning) er best egnet for rettet asykliske grafer eller grafer som er nesten asykliske, for eksempel grafer over avhengigheter mellom moduler eller funksjoner i et programvaresystem. I disse metodene er grafens noder ordnet i horisontale lag ved bruk av metoder som Coffman - Graham -algoritmen , på en slik måte at de fleste kantene går nedover fra ett lag til det neste; etter dette trinnet er nodene i hvert lag ordnet for å minimere kryssinger.
Bue diagram
  • Bue diagrammer , en layout stil som går tilbake til 1960 -tallet, plasserer hjørner på en linje; kantene kan tegnes som halvsirkler over eller under linjen, eller som glatte kurver knyttet sammen fra flere halvsirkler.
  • Sirkulære layoutmetoder plasserer hjørnene i grafen på en sirkel, og velger nøye rekkefølgen på hjørnene rundt sirkelen for å redusere kryss og plassere tilstøtende hjørner nær hverandre. Kanter kan tegnes enten som akkorder i sirkelen eller som buer i eller utenfor sirkelen. I noen tilfeller kan flere sirkler brukes.
  • Dominanstegning plasserer hjørner på en slik måte at det ene toppunktet er oppover, høyre, eller begge deler av et annet hvis og bare hvis det kan nås fra det andre toppunktet. På denne måten gjør layoutstilen synlighetsforholdet til grafen visuelt tydelig.

Applikasjonsspesifikke graftegninger

Grafer og graftegninger som oppstår på andre anvendelsesområder inkluderer

I tillegg ligner plasseringen og rutingstrinnene for elektronisk designautomatisering (EDA) på mange måter graftegning, det samme er problemet med grådig innebygging i distribuert databehandling , og graftegningslitteraturen inneholder flere resultater lånt fra EDA -litteraturen. Imidlertid er disse problemene også forskjellige på flere viktige måter: for eksempel i EDA er områdeminimering og signallengde viktigere enn estetikk, og ruteproblemet i EDA kan ha mer enn to terminaler per nett mens det analoge problemet i graftegning generelt involverer bare par hjørner for hver kant.

Programvare

En graf tegning grensesnitt ( Gephi 0.9.1)

Programvare, systemer og leverandører av systemer for tegning av grafer inkluderer:

  • BioFabric programvare med åpen kildekode for visualisering av store nettverk ved å tegne noder som horisontale linjer.
  • Cytoscape , åpen kildekode-programvare for visualisering av molekylære interaksjonsnettverk
  • Gephi , programvare for analyse og visualisering av åpen kildekode
  • graph-tool , et gratis/gratis Python- bibliotek for analyse av grafer.
  • Graphviz , et grafisk tegningssystem med åpen kildekode fra AT&T Corporation
  • Linkurious , en kommersiell programvare for analyse og visualisering av nettverk for grafdatabaser
  • Mathematica , et generelt beregningsverktøy som inkluderer 2D- og 3D -grafvisualisering og grafanalyseverktøy.
  • Microsoft Automatic Graph Layout , open-source .NET-bibliotek (tidligere kalt GLEE) for å legge ut grafer
  • NetworkX er et Python -bibliotek for å studere grafer og nettverk.
  • Tom Sawyer Software Tom Sawyer Perspectives er grafikkbasert programvare for å bygge graf- og datavisualiserings- og analyseapplikasjoner i bedriftsklasse. Det er et Software Development Kit (SDK) med et grafikkbasert design og forhåndsvisningsmiljø.
  • Tulip (programvare) , et åpen kildekode datavisualiseringsverktøy
  • yEd , en grafredigerer med grafisk layoutfunksjonalitet
  • PGF/TikZ 3.0 med graphdrawingpakken (krever LuaTeX ).
  • LaNet-vi , en åpen kildekode programvare for visualisering av store nettverk
  • Edraw Max 2D programvare for teknisk teknisk diagram

Referanser

Fotnoter
Generelle referanser
Spesialiserte delemner

Eksterne linker