函數式語言怎樣表示圖呢？

01-27

函數式語言里，圖怎樣表示？圖上的各種演算法怎樣實現？
不限語言，不限圖種類（無環/有環，有無復邊，etc），不限應用場景（單機/分散式，etc），歡迎討論

平常直接用到較少，知道的有兩個：

1. Scala 有個Graph Library ：

GitHub - scala-graph/scala-graph: Graph for Scala is intended to provide basic graph functionality seamlessly fitting into the Scala Collection Library. Like the well known members of scala.collection, Graph for Scala is an in-memory graph library aiming at editing and traversing graphs, finding cycles etc. in a user-friendly way.

仿照scala集合庫的形式提供圖操作，其Graph的type為：

trait Graph[N, E[X] &<: EdgeLikeIn[X]]

N為node的類型，E[X]為edge的類型（X用於type check），構造edge用了一套DSL（各種花式箭頭而已），如1 ~ 2 表示UnDiEdge(1, 2) (無向邊) ；1 ~&> 2 % 2 為weight為2的節點1到節點2的有向邊

所以如下一圖：

http://www.scala-graph.org/img/guides/core/MixedGraph.jpg （網路出了問題，上傳不了圖了）

可以寫為：

val g = Graph(1~2 % 4, 2~3 % 2, 1~&>3 % 5, 1~5 % 3, 3~5 % 2, 3~4 % 1, 4~&>4 % 1, 4~&>5 % 0)

結構方面：

type N 和 E[X]只記錄構造傳人蔘數的節點和邊類型，如Int, UnDiEdge[Int]，內部則轉換為（wrapped ）InnerNode和InnerEdge類型，並構建兩個集合：Set[InnerNode]和 Set[InnerEdge]，並且type Graph也實現了Set[GraphParam] （GraphParam 類型是為了處理節點類型N和InnerNode類型，以及E[X]和InnerEdge類型的轉換而引入）或者應該說實現了Traversable，所以可以在Graph, NodeSet, EdgeSet使用filter，find等操作

加邊，加節點等操作都通過升為GraphParam類型後轉換為對內部NodeSet和EdgeSet的操作

其次，type Graph還實現了type AdjacencyListGraph，所以其內部含有一個（immutable的）鄰接表，那麼關於一些algorithm就好實現了，基於這個immutable的鄰接表就行了

註：以上所說都是針對該庫，immutable的Graph，它還提供了mutable的Graph

注2：代碼中with/extends trait應該說是面向對象的方式，但是轉為functional方式也是能做到的

-------------------------------------------

2. 還有一個分散式節點監控的庫：GitHub - Verizon/quiver: A reasonable library for modeling multi-graphs in Scala，其內部用到了圖的庫：Functional Graph Library/Haskell，是從Haskell那邊來的，上面介紹的圖類型有點粉切黑的感覺，這個就真的是很清真了。。。

這裡有文章講圖基本抽象和怎樣用command做圖分解的：A Comonad of Graph Decompositions

謝邀, 當年無聊收集了些資料一直沒看 (

Data.Graph -&> Structuring Depth-First Search Algorithms in Haskell

fgl: Martin Erwigs Functional Graph Library(Functional Graph Library/Haskell , Quiver)

https://github.com/athanclark/dag

nott.ac.uk 的頁面 Functional Programming with
Structured Graphs

http://macau.uni-kiel.de/servlets/MCRFileNodeServlet/dissertation_derivate_00006562/dissDanilenko.pdf Designing Functional Implementations
of Graph Algorithms

沒時間總結。。以OCaml為例推薦幾個參考的：

99 problems, 跳到Graph部分

Dexter Kozen（真.大神）的CS 3110 講義

某些知名庫如OCamlGraph（其文檔Designing a Generic Graph Library
using ML Functors也值得一看）

另外很多OCaml項目都喜歡自己造輪子，各種graph應該有不少。。。（

鄰接表不就是個 Map&&> 嗎？

瀉藥，這個問題在純函數式語言里確實不好解決，因為圖的很多運算包括構建過程都會遇到這樣一個問題：因為純函數式數據結構是不可變的，一個節點空間上指向的可能是另一個時間上還未被創建的節點，haskell里一個顯而易見的解法是使用ST或者IO，比如用IORef [Node]來保存節點指向的其他節點。這樣其他過程式語言的演算法在IO Monad里實現就可以了。

另一個做法是tying the knot，一個典型的應對cyclic的數據創建的做法，簡單的說我們讓先創建的數據節點包含一個thunk，推遲thunk求值來實現空間上的互相引用，但是這個做法可以應付創建，應付不了局部修改。所有的修改操作全量創建整個圖，當然查詢類演算法效率還是不錯的。

學渣跑題強答系列

可以去看cayley，開源圖資料庫。思路就是根據不同內容和方向類型(源或邊或終點儲存一堆 (源，邊，終點) 的集合。能搞函數式集合的話，自然就能搞函數式圖了。

更多內容見https://www.youtube.com/watch?v=-9kWbPmSyCI

struct edge {

int to, next, weight;

};

int pe;

vector& head;

vector& graph;

void addedge(int from, int to, int weight)

{

edge e;

e.to=to;

e.weight=weight;

e.next=head[from];

graph.push_back(e);

head[from]=pe++;

}

可以表示多重邊，實質是鄰接表