Q

圖形數據結構

2011-03-23 71 views 1 likes

1

比方說，我有MyClass{ private LargeMatrix mtrx; hashCode(){...}}圖形數據結構

JGraphT（也許所有的圖形數據結構）好像是用哈希表來頂點映射。那麼當我使用MyClass而不是String l1,l2,l3時會影響速度嗎？

這種情況下的優點和缺點是什麼？我應該重寫哈希碼（刪除矩陣哈希碼）？有沒有使用引用而不是哈希表的圖形？

所以我的代碼是：

package ann; 

import org.jgrapht.DirectedGraph; 
import org.jgrapht.graph.DefaultEdge; 
import org.jgrapht.graph.SimpleDirectedGraph; 

/** 
* @author marmoush 
* 
*/ 
public class Network 
{ 
    DirectedGraph<String, DefaultEdge> diGraph; 
    String l1="hello1"; 
    String l2="hello1"; 
    String l3="hello3"; 
    /** 
    * 
    */ 
    public Network() 
    { 

     diGraph = new SimpleDirectedGraph<String, DefaultEdge>(DefaultEdge.class); 
     diGraph.addVertex(l1); 
     diGraph.addVertex(l2); 
     diGraph.addVertex(l3); 

     diGraph.addEdge(l1, l2); 
     System.out.println(diGraph.containsEdge(l1,l2)); 
     // TODO Auto-generated constructor stub 
    } 

} 


Exception in thread "main" java.lang.IllegalArgumentException: loops not allowed 
    at org.jgrapht.graph.AbstractBaseGraph.addEdge(Unknown Source) 
    at ann.Network.<init>(Network.java:28) 
    at test.TestNetwork.main(TestNetwork.java:9)

因爲（我認爲）l1.hashCode()==l2.hashCode()

編輯： 矩陣可能是零，有時還是那些，它們隨時間變化，所以我會盡力拿出與區分這些對象的東西，這似乎是愚蠢的解決方案。爲什麼不能通過那裏的位置選擇頂點或什麼？

我應該重新發明輪子嗎？用一個使用Vectors而不是哈希表的圖表？或者有工作？

2011-03-23 Ismail Marmoush

A

回答

2

我將創建一個頂點類並實現equals()和hashcode()適當。速度影響不是那麼大，如果頂點的ID是數字，它甚至可以更快。

2011-03-23 14:04:26 Soronthar

0

好吧，它確實有意義，你的objectl1和l2是一樣的，即使它存儲在內存中的不同位置，對於圖是同一個頂點。

是否有一個原因，爲什麼你需要在圖中相同的頂點？也許有一種解決方法

2011-03-23 13:53:47 sharpner

+0

有時候這些矩陣可能是零，它們會隨着時間而改變。所以我不會允許它通過散列碼來選擇 – 2011-03-23 13:54:52

+0

l1和l2永遠不會存儲在內存中的不同位置。看到我上面的答案。 – rtperson 2011-03-23 13:58:46

0

字符串在Java中是不可變的，所以l1和l2保證指向完全相同的在內存中的位置。這是該語言的一個很好的功能，它可以加快字符串處理的速度，但它會在這樣的情況下讓你感到困擾。

這就是爲什麼你會得到循環異常。我懷疑你想要一個無向圖結構。

對於參考，請參見Java語言規格section 3.10.5：

同一類（§8）在同一封裝（§7）表示爲相同的參考
字符串內文字字符串對象（§4.3.1）。

同一包中不同類中的文字字符串表示對同一個字符串對象的引用。

不同包中不同類中的文字字符串同樣代表對同一個String對象的引用。

2011-03-23 13:57:59 rtperson

+0

就像澄清一樣，l1和l2保證指向內存中完全相同的位置，因爲它們都是用String文字初始化的。如果l2在初始化時像'String l2 = new String（「hello1」）'那麼'l1 == l2'將是false。 – Soronthar 2011-03-23 14:01:38

+0

仍然哈希表的結果是相同的，它會拋出一個異常 – 2011-03-23 14:05:35

+0

我的問題是與字符串，它與HashTable被用作索引器，我想要使用列表或向量 – 2011-03-23 14:06:35

0

問題是這種圖形不允許循環。您必須將圖表種類更改爲AbstractBaseGraph，您可以在其中將變量loopAllowed設置爲true，或者您可以嘗試在SimpleDirectedGraph中更改此變量。

問題：我無法更改SimpleDirectedGraph中的變量，但可以使用其他類型的圖表來允許您這樣做。

我希望我能幫助你。

2012-06-05 08:42:54

相關問題