What is a good data structure to represent an undirected graph?

Question

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)

Answer 1

I don't think you'll have any luck with a built-in. Just roll your own, as you put it.

Answer 2

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.

Answer 3

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:

let add n1 n2 =
  let aux n1 n2 =
    match Hashtbl.find_option tbl n1 with
    | None -> Hashtbl.add tbl n1 [n2]
    | Some nodes -> Hashtbl.replace tbl n1 (n2::nodes)
  in
  let _ = aux n1 n2 in
  aux n2 n1

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.)