什么是表示无向图的良好数据结构?
我需要构造一个无向图。我不需要它做任何太花哨的事情,但理想情况下它会像这样工作:
structure UDG = UndirectedGraph
val g = UDG.empty
val g = UDG.addEdges(g, n1, [n2, n4, n7]) (* n1 is connected to n2, n4, and n7 *)
val g = UDG.addEdge(g, n2, n3)
UDG.connected(g, n2) (* returns [n1, n3] *)
SML/NJ 中是否有一个好的数据结构来建模这些关系?我应该自己推出吗?
更新
我已经尝试滚动自己的更新,但是当我尝试测试它时,出现类型不匹配错误。我对 SML 结构和函子的经验非常基础,所以我认为我做的事情显然是错误的。我该如何让它发挥作用?另外,你能帮我把它做成一个'a graph
吗?从语义上来说,这似乎更有意义。
代码
signature ORD_NODE =
sig
type node
val compare : node * node -> order
val format : node -> string
end
signature GRAPH =
sig
structure Node : ORD_NODE
type graph
val empty : graph
(* val addEdge : graph * Node.node * Node.node -> graph
* addEdge (g, x, y) => g with an edge added from x to y. *)
val addEdge : graph * Node.node * Node.node -> graph
val format : graph -> string
end
functor UndirectedGraphFn (Node : ORD_NODE) :> GRAPH =
struct
structure Node = Node
structure Key = struct
type ord_key = Node.node
val compare = Node.compare
end
structure Map = BinaryMapFn(Key)
type graph = Node.node list Map.map (* Adjacency list *)
val empty = Map.empty
fun addEdge (g, x, y) = (* snip *)
fun format g = (* snip *)
end
structure UDG = UndirectedGraphFn(struct
type node = int
val compare = Int.compare
val format = Int.toString
end)
错误
当我这样做时
structure UDG = UndirectedGraphFn(struct type node = int val compare = Int.compare val format = Int.toString end) UDG.addEdge (UDG.empty,1,2)
,我得到类型不匹配:
Error: operator and operand don't agree [literal] operator domain: UDG.graph * ?.UDG.node * ?.UDG.node operand: UDG.graph * int * int in expression: UDG.addEdge (UDG.empty,1,2)
I need to construct an undirected graph. I don't need it to do anything too fancy, but ideally it would work like this:
structure UDG = UndirectedGraph
val g = UDG.empty
val g = UDG.addEdges(g, n1, [n2, n4, n7]) (* n1 is connected to n2, n4, and n7 *)
val g = UDG.addEdge(g, n2, n3)
UDG.connected(g, n2) (* returns [n1, n3] *)
Is there a good data structure in SML/NJ to model these relationships? Should I just roll my own?
Updates
I've gone ahead and tried rolling my own, but I get a type mismatch error when I try to test it. My experience with SML structures and functors is pretty basic, so I think I'm doing something obviously wrong. How do I get this to work? Also, can you help me make this an 'a graph
? That seems to make more sense, semantically.
Code
signature ORD_NODE =
sig
type node
val compare : node * node -> order
val format : node -> string
end
signature GRAPH =
sig
structure Node : ORD_NODE
type graph
val empty : graph
(* val addEdge : graph * Node.node * Node.node -> graph
* addEdge (g, x, y) => g with an edge added from x to y. *)
val addEdge : graph * Node.node * Node.node -> graph
val format : graph -> string
end
functor UndirectedGraphFn (Node : ORD_NODE) :> GRAPH =
struct
structure Node = Node
structure Key = struct
type ord_key = Node.node
val compare = Node.compare
end
structure Map = BinaryMapFn(Key)
type graph = Node.node list Map.map (* Adjacency list *)
val empty = Map.empty
fun addEdge (g, x, y) = (* snip *)
fun format g = (* snip *)
end
structure UDG = UndirectedGraphFn(struct
type node = int
val compare = Int.compare
val format = Int.toString
end)
Error
When I do
structure UDG = UndirectedGraphFn(struct type node = int val compare = Int.compare val format = Int.toString end) UDG.addEdge (UDG.empty,1,2)
I get a type mismatch:
Error: operator and operand don't agree [literal] operator domain: UDG.graph * ?.UDG.node * ?.UDG.node operand: UDG.graph * int * int in expression: UDG.addEdge (UDG.empty,1,2)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
好吧,我不熟悉这种语言(请原谅我的无知):
我只是使用以下结构:
所以基本上小数点之前的第一个数字代表顶点,每个边将代表小数点(有点像 IP 地址),
这样:
可以存储为:
1.2.5
2.1.5.3
3.2.4
4.3.5.6
5.1.2.4
6.4
那么在你的代码中,添加/删除边很简单,而且很容易解析(因为顶点总是第一个数字)
OK I'm not familiar with this language (please pardon my ignorance):
I'd simply use the following structure:
so basically the first digit before the decimal would represent the Vertice, and each Edge would be represented followed by a decimal point (kind of like an IP address)
such that:
could be stored as:
1.2.5
2.1.5.3
3.2.4
4.3.5.6
5.1.2.4
6.4
Then in your code, its simple to add/delete edges, and very easy to parse (because the vertice is always the first number)
有多种可能性,各有利弊,适合图表上的不同操作。
这个不错的介绍提供了背景和示例使用邻接列表和邻接矩阵。
以无方向的方式使用它们需要权衡(空间与速度)。 本课程材料详细介绍了邻接列表样式并提供了一些关于在无向使用中可能进行的更改的想法。
There are several possibilities with differing pros and cons suited to different operations on the graphs.
This nice intro gives background and examples of using Adjacency Lists and Adjacency Matrices.
Using them in an undirected fashion involves trade offs (space verses speed). this course material goes into more detail on the adjacency list style and provides some thoughts on the possible alterations for use in undirected usage.
一个非常简单的表是哈希表,其中键作为源节点,值作为连接节点的列表。然后编写一个 add 函数,执行两次哈希表插入,一次插入为 (src, tgt),另一次插入为 (tgt, src)。
在 ocaml 中:
这将是一个有向图,只是您需要在插入时添加两个方向。哈希表查找函数将充当您的
connected
函数。(实际上,在 Ocaml 中,哈希表为一个键提供多个值,因此您只需使用
Hashtbl.find_all
函数并保存列表。但这是最容易转换为 SML 的。)A really easy one would be a hashtable, with the key as the source node, and the value as a list of connecting nodes. Then write an add function that does two hashtable insertions, one as (src, tgt), the other as (tgt, src).
In ocaml:
This would be a directed graph, it's just you would add both directions on insert. The hashtable lookup function will act as your
connected
function.(Actually, in Ocaml hashtables offer multiple values for a key, so you could just use the
Hashtbl.find_all
function and save the list. But this is the easiest to translate into SML.)我们可以将图表示为列表的列表,我们称这种数据结构为:邻接表
。
We can represent a graph as a list of lists,we call this datastructure: an adjacency list
.