What is a good data structure to represent an undirected graph?
data-structures, functor, graph, sml, structure
Solution
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.
Problem
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) ```