Vraag:
Alternatief voor Graphviz met betere automatische plaatsing van knooppunten voor grote grafieken?
Victor Stafusa
2014-02-05 03:24:47 UTC
view on stackexchange narkive permalink

In het verleden heb ik Graphviz gebruikt om grafieken te tekenen. Het is een leuk hulpmiddel voor kleine grafieken.

Maar helaas, voor grote grafieken, is Graphviz echt waardeloos:

  • Het kruiste altijd randen die duidelijk zonder een kruis konden worden getekend.
  • Het plaatst verschillende teksten over elkaar heen, waardoor ze onleesbaar worden.
  • Het heeft geen herbruikbare stijl (zoals CSS), en je moet dezelfde personalisaties herhalen in knooppunten en randen over, over en opnieuw.
  • Als de gebruiker dat wil, zeg dan gewoon de positie van twee knooppunten omwisselen. Om dit te doen, is het vaak nodig om het bronbestand zwaar te hacken, waarbij waarschijnlijk niet-gerelateerde delen van de grafiek in het proces worden geschroefd.
  • Het is heel gemakkelijk om kleine wijzigingen aan te brengen op een geïsoleerde plaats van de grafiek, dwingt Graphviz zware grote veranderingen elders af, waardoor het werkuren om het ervan te overtuigen vaak ongeldig wordt gemaakt.
  • Het verspilt veel ruimte in de grafiek en tegelijkertijd overvol op sommige plaatsen zo krap .
  • Soms maken sommige randen zeer kronkelige paden om het bronknooppunt met het doelknooppunt te verbinden, met vreemde, nutteloze curven en veel over elkaar geplaatste lateraal lopende randen.
  • Het heeft lawine-effecten . Triviale wijzigingen ergens in de grafiek kunnen de Graphviz-heuristiek verstoren, wat resulteert in een compleet andere grafiek.
  • Veel bugs ...

Ik wil iets dat als, een gebruiker kan ik eenvoudig:

  • Definieer wat de knooppunten zijn, mogelijk met de toe te passen stijl.
  • Zeg wat de randen zijn, mogelijk met de toe te passen stijl.

En dan geeft het programma:

  • Een grafiek met het minimaal mogelijke aantal kruisingen.
  • Mooi uitgelijnde knooppunten zijn goed.

Ik wil NIET:

  • Veel hacks toevoegen aan invoer alleen omdat de tool te dom is om te zien dat het twee specifieke knooppunten zou kunnen verwisselen om een ​​kruising te verwijderen.
  • Handmatig randen en knooppunten positioneren.
  • Lawine-effecten krijgen.

Wat zou een goede vervanging van Graphviz kunnen zijn? Ik wil echt dat het een gratis is.

Opmerking: het maakt me niet zoveel uit in het formaat waarin de grafiek moet worden ingevoerd, zolang ik maar een bestand kan opslaan en bewerken met de grafische beschrijving (wat de taal van een dergelijke beschrijving ook is). Het is dus absoluut niet nodig om nog steeds bij de punttaal of iets dergelijks te zijn (in feite zou ik graag mijn puntbestanden helemaal weggooien, aangezien er veel meer hacks zijn dan de daadwerkelijke grafische beschrijving daar). / p>

Kijk mensen, dit is hoe je hier een vraag stelt (en ik ga de 'graphviz echt waardeloos' blurb over het hoofd zien, omdat je goed kunt uitleggen waarom het 'waardeloos' is).
Een collega zegt dat d3.js (het grootste deel van) de positionering goed doet. Het heeft duidelijk andere niet-zo-leuke bijwerkingen, zoals browsergebaseerd en dynamisch (d.w.z. niet iedereen krijgt dezelfde output), dus het is misschien niet wat je wilt.
Voordat ik Graphvis gebruikte, genereerde ik grafieken in Perl met Graph :: Easy (en met Graph). http://search.cpan.org/~tels/Graph-Easy/lib/Graph/Easy.pm Ik zou Graph of Graph :: Easy niet aanbevelen. Ik migreerde * weg * van hen om mijn perl-programma een dotfile als een string uit te laten spugen en er graphvis op uit te voeren.
Volgens meer informatie van een cow-orker is graphviz redelijk goed (ja, we weten hoe slecht de output kan zijn, maar het probleem is totaal niet triviaal) voor het algemene geval. Als je bepaalde aannames kunt doen (zoals geen cycli), zijn er betere algoritmen, maar graphviz lijkt ze ook te bundelen (speel een beetje met zijn opties). Je hebt clustering nodig, en dit wordt alleen gemakkelijker benaderbaar als je aannames kunt gebruiken over de invoergegevens.
@mirabilos Geloof me, ik heb al veel opties geprobeerd (sinds 2011). Als de grafiek geen cyclus had, zou hij degenereren tot een soort boom en gemakkelijk te tekenen zijn. Mijn grafiek heeft echter veel cycli en heeft ongeveer 200 knooppunten. Om dat met graphviz af te handelen, moest ik de grafiek opsplitsen in 12 onafhankelijke subgraphs, waarbij ik de knooppunten herhaalde die in meer dan één grafiek voorkomen. Verder moest ik veel onzichtbare knooppunten, randen en clusters toevoegen. In mijn grafieken hebben de clusters weinig of geen semantische betekenis, het zijn slechts hacks om te proberen Graphviz te dwingen zijn werk goed te doen.
@Oxinabox, ja dat is triest. Maar gezien het enorme aantal hacks in de heuristiek, tags en structuur van graphviz, denk ik dat een herstart vanaf nul veel beter zou zijn dan een vork.
Computational Science SE heeft hier dezelfde vraag: http://scicomp.stackexchange.com/questions/3315/visualizing-very-large-link-graphs.Naast GraphViz zijn er verschillende opties beschikbaar: Gratis * [JavaScript InfoVis Toolkit] ( http://philogb.github.com/jit/index.html)* [igraph] (http://igraph.sourceforge.net/) pakket voor het [R statistisch systeem] (http: //cran.r-project .org /) * [zGrViewer] (http://zvtm.sourceforge.net/zgrviewer.html) * [Grote Graph Library] (http://lgl.sourceforge.net/) Niet-vrij * [GraphInsight] (http : //www.graphinsight.com/)
Deze voldoen niet aan de behoeften van het OP omdat het te handmatig is, maar voor sommige gebruikers is [Cupid] (http://nedbatchelder.com/blog/201401/svg_figures_with_cupid.html) een geldige manier om verder te gaan.
Kun je een voorbeeldgrafiek posten (of een link geven naar) van een voorbeeldgrafiek die je zou willen opmaken?
@Sebastian Nou, ik heb het bedrijf al verlaten waar we dit probleem hadden. Maar misschien heb ik de gegevens ergens in een back-upbestand.
Als u dat doet, plaats het dan hier niet, om te voorkomen dat u in juridische problemen komt. U mag geen gegevens hebben die toebehoren aan een bedrijf dat u heeft verlaten.
Vijf antwoorden:
#1
+73
north at graphviz
2014-03-14 03:24:51 UTC
view on stackexchange narkive permalink

Sorry voor de teleurstelling. Graphviz zou op veel manieren beter kunnen zijn, maar op dit moment zijn de vooruitzichten daarvoor niet geweldig, omdat AT&T het werk niet zo veel ondersteunt als in het verleden en sommige auteurs (zoals ik) zijn vertrokken om andere werk. We zijn op zoek naar mensen die het willen overnemen, dus laat het ons weten.

We zijn ook onder de indruk van yFiles.

Probeer ook Tom Sawyer-software; ze hebben veel technisch talent en hebben veel gewerkt aan geavanceerde lay-outmethoden en interactieve tools. (Mogelijk moet u $$$ uitgeven omdat de gratis proefperiode lijkt te zijn beëindigd.)

De vraag zei niet welke specifieke lay-outtool of opties werden geprobeerd of hoe groot een "groot" netwerk is, dus het is niet duidelijk wat te suggereren.

Als "groot" misschien honderden knooppunten betekent, probeer dan neato -Goverlap = false (om overlapping van knooppunttekstlabels te voorkomen) en mogelijk -Gmodel = subset om te proberen voor betere clustering. (Deze opties zijn niet de standaard, omdat bij data-analyse, bijvoorbeeld in bio-informatica, een rechte MDS-inbedding een nauwkeurigere weergave van afstanden in het onderliggende netwerk geeft.)

Als "groot" duizenden knooppunten betekent, misschien vele duizenden, gebruik sfdp in plaats van neato opnieuw met -Goverlap = false. (Het subset-afstandsmodel is niet beschikbaar in sfdp, omdat het niet duidelijk is hoe om te gaan met variabele randlengtes bij het samenvoegen van randen in een hiërarchische oplosser.) U kunt een goed voorbeeld van een 1054-knooppuntgrafiek zien hier

Voor "verspilde ruimte problemen" in het geval van losgekoppelde componenten, zie ook de pack en packmode attributen. De oplossingen voor dergelijke problemen liggen niet voor de hand (in feite probeert u onregelmatige vormen optimaal in te pakken, met aanvullende beperkingen, en soms op de schaal van wat mensen als 'groot' beschouwen, dus zijn subkwadratische algoritmen nodig.) Voor verbonden grafieken, experimenteer met -Overlap-opties.

Dat zijn de suggesties. Wat betreft excuses en uitleg ...

Wat iemand het "lawine-effect" noemt, wordt ook wel lay-outinstabiliteit genoemd met betrekking tot (kleine) veranderingen in de invoergrafiek. Dit is een eigenschap van bijna alle batch-grafiekopmaakprogramma's en constraint solvers. Dus je zou moeten zoeken naar interactieve tools zoals de D3 spring embedder layout, en Tim Dwyer heeft hier veel goed aan gedaan toen hij bij Microsoft was, dus misschien zal hun Graph Layout Toolkit (AGL) ooit zijn interactieve beperkingsmethoden overnemen. Gewoon een observatie, de meeste onderzoekers en programmeurs hebben niet geprobeerd om schaal, interactiviteit en esthetiek allemaal tegelijkertijd aan te vallen (kies een van de twee hierboven ...)

Het stijlprobleem is ook een goed probleem , we hadden gewoon geen tijd / energie om het aan te pakken, aangezien de meeste grafieken automatisch worden gegenereerd, dus je kunt stijlen toepassen in een of ander voorbewerkingsprogramma of script. Er moet ook rekening mee worden gehouden dat de grafiek niet alleen een statische ontleedboom is, maar dat nadat een grafiek is gelezen, het stijlblad of de attributen van objecten waarop de stijlen zijn toegepast, kunnen worden gewijzigd, en dat de grafiek vervolgens moet worden uitgeschreven. correct op een manier die de oorspronkelijke structuur zoveel mogelijk behoudt. Niet onoverkomelijk, maar dit zijn details die zorgvuldig moeten worden overwogen.

Bugs kunnen worden gerapporteerd op www.graphviz.org onder Bug and Issue Tracking.

Globale edge-routing met vloeiende curven - moeilijk probleem. Merk op dat veel coole lay-outs van sommige andere tools gebogen randen gebruiken, maar ze tekenen gewoon over al het andere dat in de weg zit. Ik denk dat we deze functie ook aan Graphviz hebben toegevoegd. Ik denk ook dat er een CHI- of INFOVIS-papier was dat laat zien dat zulke gebogen randen eigenlijk iets moeilijker te lezen zijn dan rechte lijnen.

Oversteken - enige lokale optimalisatie is wellicht mogelijk. Weet niet zeker welke tool wordt gebruikt. Het is gemakkelijk om specifieke voorbeelden aan te wijzen waar lay-outs beter zouden kunnen zijn, maar moeilijker om een ​​effectieve oplossing te bedenken waarbij een "minimum aantal kruisingen" de zaken in het algemeen niet erger zou maken.

Merk op dat ik rechtstreeks aangesloten bij Graphviz.

Ik stemde op. Stephen North is een [welbekende expert] (http://scholar.google.co.uk/citations?user=_QJP9-0AAAAJ&hl=nl) in grafische visualisatie, en gezien de bashing van Graphviz door het OP is het kostbaar om zijn inzicht te hebben als antwoord. (Ik begrijp de frustratie van het OP echter wel, maar grafieken zijn een moeilijk probleem)
#2
+30
Sebastian
2014-03-10 17:51:38 UTC
view on stackexchange narkive permalink

Mijn softwareaanbeveling is " yEd" - een gratis grafische tekenapplicatie voor algemene doeleinden, zoals in bier, die heel hard probeert om de problemen op te lossen waar je tegenaan bent gelopen. Voor zover ik weet, gebruikt deze software de beste vrij beschikbare implementaties van de layout-algoritmen.

Nu naar het meer gedetailleerde antwoord dat geschikter zou zijn voor StackOverflow dan voor "Software-aanbeveling":

Het probleem dat u probeert op te lossen, is een heel moeilijk probleem (vooral in de zin van rekenkundig moeilijk ), dus het is onwaarschijnlijk dat u een hulpmiddel zult vinden dat al uw problemen in gelijke mate kan oplossen goed. Er zijn een aantal gratis oplossingen (GraphViz is waarschijnlijk een van de beste) en een behoorlijk aantal commerciële concurrenten. Voor de commerciële yFiles grafische tekenbibliotheek is er een gratis (zoals in bier) platformonafhankelijke applicatie beschikbaar die u kunt uitproberen. Het kan gegevens uit verschillende indelingen importeren, stijltoewijzingen op uw gegevens toepassen en biedt een enorme verzameling verschillende lay-outalgoritmen. Het heet yEd en kan zonder enige installatie worden uitgevoerd in een webversie vanaf hier. De desktopversie kan worden gestart als een java "webstart" -toepassing rechtstreeks vanuit de browser of na het installeren van een van de zelfstandige programma's voor Windows, Linux en Mac.

Sommige lay-outalgoritmen mogen waarschijnlijk niet worden gebruikt met zeer grote grafieken (tienduizenden elementen), omdat ze heel lang zullen worden uitgevoerd of te veel geheugen nodig hebben, maar meestal is er minstens één opmaakstijl die goed bij uw gegevens zou moeten passen. Als u tegen de API moet programmeren, moet u een licentie verkrijgen voor de onderliggende bibliotheek (beschikbaar voor Java, .net, Javascript), wat in strijd is met uw "gratis" vereiste, maar dit zou u nog meer controle geven over de lay-out.

Disclaimer : ik werk voor het bedrijf dat dit (gratis) product maakt, maar op Stack Exchange vertegenwoordig ik mijn werkgever niet. Ik heb het grootste deel van mijn academische en professionele tijd besteed aan software voor het tekenen van grafieken sinds het einde van de jaren negentig en ik geloof dat ik een zeer grondige kennis heb van de markt en de beschikbare software (zowel gratis als commercieel). Er kunnen andere tools beschikbaar zijn en ik hoop dat deze site geweldige alternatieven kan bieden - ik zal ze zeker niet ontkennen.

+1. Het OP-verzoek is onmogelijk (het programma geeft een grafiek met het minimaal mogelijke aantal kruisingen, voor een grote grafiek -> NP-hard dus veel geluk). Dit antwoord is deskundige kwaliteit.
Ik stemde ook op. Als er ooit een plek was waar je experts wilt laten binnenkomen, dan gaat het om moeilijke problemen, en dit is vooral leuk om te horen van experts als het gaat om het verkrijgen van software.
Gebruik [dottoxml] (https://bitbucket.org/dirkbaechle/dottoxml) om van GraphViz (`.dot`) naar een formaat te converteren dat yEd kan lezen.
Als onafhankelijke gebruiker van yEd (niet gelieerd aan het bedrijf) bevestig ik dat yEd de beste gratis software is die er is (en ik heb er veel geprobeerd)
#3
+16
Franck Dernoncourt
2014-03-14 05:43:03 UTC
view on stackexchange narkive permalink

Om heel specifiek te antwoorden op het verzoek van de vraag, aangezien de andere twee antwoorden uitstekend werk leverden om uit te breiden:

Wat je vraagt ​​is niet mogelijk. U wilt een programma dat een "grafiek met het minimaal mogelijke aantal kruisingen" geeft, en u hebt specifiek gevraagd dat het programma werkt voor grote grafieken.

Het bepalen van het kruisingsnummer van een grafiek is echter een moeilijk NP-probleem (Garey en Johnson toonden dat het NP-compleet is in 1983).

Daarom kan een dergelijk programma niet garanderen dat de grafiek met het minimaal mogelijke aantal kruisingen binnen een redelijke tijd wordt gevonden, waardoor het programma onbruikbaar wordt.

Er kan een "redelijk klein" aantal overtochten zijn, niet strikt globaal minimum.
#4
+5
BrianV
2019-11-15 04:01:36 UTC
view on stackexchange narkive permalink

Dit zou zeker worden beschouwd als een "GraphViz-gebaseerde oplossing", maar als je met GraphViz werkt, wil je misschien eens kijken naar Gephi. Het is veel beter in staat om grote grafieken te verwerken.

#5
+1
user11879
2018-11-17 00:04:44 UTC
view on stackexchange narkive permalink

PlantUML is een open-source tool waarmee gebruikers UML-diagrammen kunnen maken vanuit een gewone teksttaal. De taal van PlantUML is een voorbeeld van een toepassingsspecifieke taal. Het gebruikt Graphviz-software om zijn diagrammen op te maken. Het is gebruikt om blinde studenten met UML te laten werken. PlantUML helpt ook blinde software-ingenieurs bij het ontwerpen en lezen van UML-diagrammen.

enter image description here

Sorry, maar dit helpt helemaal niet. De auteur vraagt ​​expliciet om software die de problemen beter oplost dan GraphViz doet. Dit sluit dus uiteraard GraphViz-gebaseerde oplossingen uit. En UML-diagrammen zijn ook zeker niet de typische toepassingen voor "grote grafieken". Wilde je een andere vraag beantwoorden?


Deze Q&A is automatisch vertaald vanuit de Engelse taal.De originele inhoud is beschikbaar op stackexchange, waarvoor we bedanken voor de cc by-sa 3.0-licentie waaronder het wordt gedistribueerd.
Loading...