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

OK I'm not familiar with this language (please pardon my ignorance):

I'd simply use the following structure:

V.E1.E2.En+1
V2.E1.E2.En+1
Vn+1.E1.E2.En+1

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)

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.