What is a good data structure to represent an undi

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

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 2

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

Answer 3

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 4

We can represent a graph as a list of lists,we call this datastructure: an adjacency list .