圖形疑惑

Question

我有這樣的代碼在這裏：

type ('state,'letter) automaton = { 
    initial : 'state ; 
    final  : 'state -> bool ; 
    transition : 'letter -> 'state -> 'state ; 
} 

let example_graph = 
{ 
nodes = ['a'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k']; 
edges = ['h', 'g'; 'k', 'f'; 'f', 'b'; 'f', 'c'; 'c', 'b'] 

} 

它是OCaml的網站約graths給出的默認實例。

那麼我的問題在這裏，我如何使用圖表在OCaml？我的意思是Lists我們有一個大的功能頁面，可以幫助我們處理它，但是我還沒有找到任何有關圖形的預定義功能。

我有一個複雜的工作，做圖，更精確地說，我需要建立一個automaton與OCaml，但首先我想知道我該怎麼做簡單的認爲如獲取nodes從圖中，如何我可以打開我的節點和邊緣輸入值，或者我可以如何使用像這樣的圖形進行測試，例如我可以如何在節點之間移動......（以及每一個簡單的移動，你可以記住或任何地方我可以得到更多的信息將有所幫助）

基本上我想知道是否有任何地方在網絡上，我可以得到有關OCaml或功能的圖形更好的信息，如果你們可以給我一隻手！

感謝

PS：我已經做了我的搜索，沒有發現任何真正有用（只多複雜的代碼，像我這樣的初學者）

Answer 1

嗯，我想ocamlgraph是一個新的複雜一點OCaml程序員（但後來使用它將是一個好主意）。

從我的理解，你想要以一種可以理解的方式處理節點和邊緣。

首先，我會給你測試Map module的意見（與它的tutorial），因爲它是那麼這是一種快速簡單的方式（我實現了Glushkov's construction這個模塊，它的作品真的很好）。

爲了給你一個小的見解：

type ('state,'letter) automaton = { 
    initial : 'state ; 
    final  : 'state -> bool ; 
    transition : 'letter -> 'state -> 'state ; 
} 

這就是你看到的自動機到現在。

type ('state,'letter) automaton = { 
    initial : 'state ; 
    final  : 'state -> bool ; 
    transition : ('letter, 'state) list Map.Make('state); 
} 

這是我看到它（這不是一個正確的實現，因爲'state顯然也不是有序的類型，但這個想法是在這裏）。您可以將任何狀態映射到列表（也可能瞭解如何創建一個新的映射，您將使用Set而不是列表）狀態。

試着自己實施它，它可以是非常有用的，你可以學到很多東西。

Answer 2

OCaml對圖​​有很好的支持，這要歸功於OCamlgraph庫。它有據可查，功能非常強大，但它依賴於仿函數，並且通常會混淆OCaml新手。所以你也可以考慮嘗試我們爲了程序分析而開始的另一個graph library。它沒有公佈官方OPAM庫，但是你總是可以從我們自己的倉庫獲得最新的alpha版本：

opam repository add git://github.com/BinaryAnalysisPlatform/opam-repository.git 
opam install graphlib 

附： Graphlib不是OCamlgraph的替代品，它可以很好地發揮它的作用。它只是有一點不同的重點。當graphlib 更專注於圖數據結構時，OCamlGraph更專注於可用於任何圖表表示的泛型算法。所以它更容易使用，但難以延伸。