題:
Graphviz的替代方案,可以為大型圖形提供更好的自動節點放置?
Victor Stafusa
2014-02-05 03:24:47 UTC
view on stackexchange narkive permalink

過去,我使用Graphviz創建圖形繪圖。

但是不幸的是,對於大圖,Graphviz確實很爛:

  • 它總是交叉的邊緣,顯然可以畫出沒有十字的邊緣。
  • 它會疊加不同的文本,使它們不可讀。
  • 它沒有可重複使用的樣式(如CSS),並且您需要在節點和邊緣上,上方,上方和上方重複相同的個性化設置再次。
  • 如果用戶願意,只需交換兩個節點的位置即可。為此,經常需要對源文件進行大量修改,可能會在此過程中擰緊圖形的不相關部分。
  • 很容易的是,為了在源文件的一個孤立位置進行較小的更改圖中,Graphviz強迫在其他地方進行重大的重大更改,經常使試圖說服它正確繪製的工作時間無效。
  • 它浪費了圖中的大量空間,同時又非常擁擠某些地方
  • 有時,某些邊緣會形成非常彎曲的路徑,將源節點與目標節點連接起來,具有奇怪的無用曲線和大量重疊的橫向延伸邊緣。
  • 它具有雪崩效應。在圖形中的某個地方進行瑣碎的修改可能會擾亂Graphviz的啟發式方法,從而導致圖形完全不同。
  • 許多錯誤...

我想要的是,一個用戶,我可以簡單地做到:

  • 定義節點是什麼,可能帶有要應用的樣式。
  • 說出什麼是邊,可能帶有要應用的樣式。

然後程序給出:

  • 具有盡可能少的交叉次數的圖。
  • 對齊的節點很好。

我不想:

  • 僅因為該工具太愚蠢而無法看到它可以交換兩個特定的節點,所以在輸入中添加了很多技巧。刪除交叉點。
  • 手動定位邊緣和節點。
  • 獲取雪崩效果。

那麼,什麼可以很好地替代Graphviz?我真的希望它是免費的。

注意:我不太在乎輸入圖形的格式,只要我可以使用該格式保存和編輯文件即可。圖形描述(無論這種描述的語言是什麼)。因此,絕對沒有必要使用點語或類似的東西(事實上,我很樂意完全丟棄我的點文件,因為那裡的黑客比實際的圖形描述要多得多)。 / p>

看到人們,這是您在這裡問的問題(我將忽略“ graphviz確實很爛”,因為您出色地解釋了為什麼它“爛”了)。
一位同事說d3.js正確完成了大部分定位。顯然,它還有其他一些不太好的副作用,例如基於瀏覽器和動態的(即並非每個人都得到相同的輸出),所以它可能不是您想要的。
在使用Graphvis之前,我正在使用Graph :: Easy(以及Graph)在Perl中生成圖形。 http://search.cpan.org/~tels/Graph-Easy/lib/Graph/Easy.pm我不會推薦Graph或Graph :: Easy。我從他們那裡遷移了*,使我的perl程序將一個點文件作為字符串吐出並在其上執行graphvis。
根據母牛人的更多信息,對於一般情況,graphviz相當不錯(是的,我們知道輸出可能有多糟糕,但問題完全不平凡)。如果您可以做某些假設(例如,沒有周期),則有更好的算法,但graphviz似乎也將它們捆綁在一起(有點玩具的選項)。您需要聚類,而當您可以使用有關輸入數據的假設時,這只會變得更容易實現。
@mirabilos相信我,我已經嘗試了很多選擇(自2011年起)。如果圖形沒有循環,它將退化為某種樹,並且易於繪製。但是,我的圖實際上有很多周期,大約有200個節點。為了用graphviz處理這個問題,我不得不將圖分成12個獨立的子圖,並重複出現在多個圖中的節點。此外,我需要添加許多不可見的節點,邊緣和群集。在我的圖中,集群幾乎沒有語義含義,它們只是試圖強迫graphviz正確完成工作的黑客。
@Oxinabox,是的,這很可悲。但是,鑑於graphviz的啟發式,標記和結構中的大量駭客,我認為從零重啟比分叉要好得多。
計算科學SE在這裡有相同的問題:http://scicomp.stackexchange.com/questions/3315/visualizing-very-large-link-graphs。除了GraphViz,還有多個可用選項:免費* [JavaScript InfoVis Toolkit]( http://philogb.github.com/jit/index.html)* [R統計系統]的[igraph](http://igraph.sourceforge.net/)包(http://cran.r-project .org /)* [zGrViewer](http://zvtm.sourceforge.net/zgrviewer.html)* [大型圖形庫](http://lgl.sourceforge.net/)免費* [GraphInsight](http ://www.graphinsight.com/)
這些都不滿足OP的需求,因為它太手工了,但是對於某些用戶來說[Cupid](http://nedbatchelder.com/blog/201401/svg_figures_with_cupid.html)是一種有效的處理方式。
您可以發布(或提供指向)您想要佈局的示例圖嗎?
@Sebastian好,我已經離開了出現問題的公司。但是我可能將數據保存在某個備份文件中的某個位置。
如果這樣做,請不要在此處發布,以免陷入法律麻煩。您不應擁有屬於您所留下的公司的任何數據。
五 答案:
#1
+73
north at graphviz
2014-03-14 03:24:51 UTC
view on stackexchange narkive permalink

很抱歉讓您失望。 Graphviz在許多方面可能會更好,但是在這一點上前景並不理想,因為AT&T並不像過去那樣支持這項工作,而且有些作者(如我)已經離開尋找其他人了。工作。我們正在尋找想要接手的人,所以讓我們知道。

yFiles也給我們留下了深刻的印象。

也請嘗試 Tom Sawyer軟件;他們擁有大量的工程人才,並且在高級佈局方法和交互式工具方面做了很多工作。 (您可能需要花費$$費用,因為免費試用似乎已停止。)

該問題並未說明嘗試了哪種特定的佈局工具或選項,或者“大型”網絡的規模如何,所以尚不清楚建議什麼。

如果“大”表示可能有數百個節點,請嘗試 neato -Goverlap = false (以避免節點文本標籤重疊),並可能 -Gmodel = subset 嘗試更好的集群。 (這些選項不是默認選項,因為在數據分析(例如生物信息學)中,直接的MDS嵌入可以更準確地呈現底層網絡中的距離。)

如果“大”表示數千個節點,也許成千上萬,使用-Goverlap = false再次使用 sfdp 而不是 neato 。 (子集距離模型在sfdp中不可用,因為尚不清楚在分層求解器中合併邊時如何處理可變邊長。)您可以在這裡看到一個1054節點圖的好示例

對於在組件斷開連接時出現的“浪費空間問題”,另請參見pack和packmode屬性。解決此類問題的方法並不明顯(基本上,您試圖以最佳方式打包不規則形狀,並附加其他限制,有時甚至以人們認為“大”的大小進行縮放,因此需要二次方程式算法。)對於連通圖,請嘗試-重疊選項。

這些是建議。至於藉口和解釋...

某人所謂的“雪崩效應”也被稱為相對於輸入圖形中(較小)變化的佈局不穩定性。這是幾乎所有批處理圖佈局程序和約束求解器的屬性。因此,您應該尋找諸如D3彈簧嵌入器佈局之類的交互式工具,而Tim Dwyer在Microsoft時就做了很多出色的工作,因此也許有一天他們的Graph Layout工具箱(AGL)將採用他的交互式約束方法。只是觀察,大多數研究人員和程序員都沒有嘗試同時攻擊規模,交互性和美觀性(選擇以上任意兩項...)

樣式問題也是一個好問題,我們只是沒有時間/精力來解決它,因為大多數圖形都是自動生成的,因此您可以在某些預處理工具或腳本中應用樣式。還必須考慮的是,圖不僅是靜態的解析樹,而且在讀取圖之後,可以更改其樣式表或已應用樣式的對象的屬性,然後必須將圖寫出正確地以盡可能保留原始結構的方式。不是不可克服的,但是這些是必須仔細考慮的細節。

錯誤可以在www.graphviz.org的“錯誤和問題跟踪”下進行報告。

具有平滑曲線的全局邊緣佈線-難題。請注意,其他一些工具的許多外觀很酷的佈局都使用彎曲的邊緣,但它們只會覆蓋所有其他方式。我認為我們也將此功能添加到了graphviz中。另外,我認為有CHI或INFOVIS論文顯示出這種彎曲的邊緣實際上比直線更難正確讀取。

交叉-可能會進行一些局部優化。不確定正在使用什麼工具。容易指出一些具體的示例,其中佈局可能會更好,但很難發明出一種有效的解決方案,即“最小交叉點數”通常不會使總體情況惡化。

請注意,我在直接與Graphviz關聯。

我投票了。 Stephen North是圖形可視化領域的[公認專家](http://scholar.google.co.uk/citations?user=_QJP9-0AAAAJ&hl=zh-CN),並且鑑於OP對Graphviz的抨擊,非常有價值的見解作為答案。 (儘管我確實了解OP的挫敗感,但是繪製圖形是一個困難的問題)
#2
+30
Sebastian
2014-03-10 17:51:38 UTC
view on stackexchange narkive permalink

我的軟件推薦為“ yEd”-啤酒通用圖形繪製應用程序中的免費軟件,它非常努力地解決您遇到的問題。據我所知,該軟件使用了佈局算法的最佳可免費使用的軟件。

現在給出了更詳細的答案,該答案比“軟件推薦”更適合StackOverflow:

您要解決的問題是一個非常棘手的問題(尤其是在計算上困難的的意義上),因此您不太可能找到可以平等解決所有問題的工具好。有許多免費解決方案(GraphViz可能是最好的解決方案之一),並且有許多商業競爭對手。對於商業 yFiles圖形繪圖庫,有一個免費(如啤酒)跨平台應用程序可供您嘗試。它可以從幾種不同的格式導入數據,將樣式映射應用於您的數據,並提供了大量的不同佈局算法。它稱為 yEd,可以從此處在Web版本中運行而無需任何安裝。桌面版本可以直接從瀏覽器中啟動,也可以作為Java“ Webstart”應用程序啟動,也可以在安裝適用於Windows,Linux和Mac的獨立程序之一之後啟動。

某些佈局算法可能不應使用使用非常大的圖形(成千上萬個元素),因為它們將執行很長時間或需要太多的內存,但是在大多數情況下,至少有一種佈局樣式很適合您的數據。如果需要根據API進行編程,則需要許可基礎庫(可用於Java,.net,Javascript),這符合您的“免費”要求,但這將使您對佈局有更多的控制權。 / p>

免責聲明:我為創建此(免費)產品的公司工作,但是在Stack Exchange上,我不代表我的雇主。自1990年代後期以來,我將大部分學術和專業時間都花在了繪圖軟件上,我相信我對市場和可用軟件(免費和商用)都非常了解。可能還有其他工具可供使用,我希望這個網站能提出很多不錯的選擇-我當然不會拒絕。

+1。 OP請求是不可能的(程序給出的圖具有盡可能少的穿越次數,對於大圖-> NP很難,祝你好運)。這個答案是專家素質。
我也贊成。如果曾經有您希望專家介入的地方,那就是棘手的問題,在獲取軟件時,很高興聽到專家的意見。
要將GraphViz(.dot)轉換為yEd可以讀取的格式,請使用[dottoxml](https://bitbucket.org/dirkbaechle/dottoxml)。
作為yEd(不隸屬於該公司)的獨立用戶,我確認yEd是現有的最佳免費軟件(並且我已經嘗試了許多)
#3
+16
Franck Dernoncourt
2014-03-14 05:43:03 UTC
view on stackexchange narkive permalink

要非常具體地回答問題的要求,因為其他兩個答案在擴展範圍方面做得很好:

您所提出的問題是不可能的。您想要一個給出“具有最小可能交叉點數的圖形”的程序,並且特別要求該程序適用於大型圖形。

但是,確定圖的交叉數是一個 NP難題(Garey and Johnson 顯示它是NP完全問題,在1983年)。

因此,這樣的程序將無法保證在合理的時間內找到具有盡可能少的交叉次數的圖形,從而使該程序無用。

可能會有“相當少”的穿越次數,而不是嚴格的全球最低人數。
#4
+5
BrianV
2019-11-15 04:01:36 UTC
view on stackexchange narkive permalink

這肯定會被視為“基於GraphViz的解決方案”,但是如果您正在使用GraphViz,則可能要簽出 Gephi。處理大型圖形時,它的功能要強大得多。

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

PlantUML是一個開放源代碼工具,允許用戶從純文本語言創建UML圖。 PlantUML的語言是專用語言的示例。它使用Graphviz軟件佈置其圖表。它已用於允許盲人學生使用UML。PlantUML還可以幫助盲人軟件工程師設計和閱讀UML圖表。

enter image description here

抱歉,但這根本沒有幫助。作者明確要求提供一種比GraphViz更好地解決問題的軟件。因此,這顯然排除了基於GraphViz的解決方案。而且,UML圖當然也不是“大圖”的典型應用。您是要回答其他問題嗎?


該問答將自動從英語翻譯而來。原始內容可在stackexchange上找到,我們感謝它分發的cc by-sa 3.0許可。
Loading...