graph in SML of NJ

I need to write some function using ML, this function receives the list of the edges of the directed graph [(1,2),(1,3),(3,2)], it means directed edge from 1 to 2 and from 1 to 3..., and I receive also two vertices, I need to find all possible ways from开发者_如何学Python first vertex to second and list of the possible paths, for example for vertices 1, 2, I need to display the list [[1,2],[1,3,2]], how can I do it ML if can't store data about the vertices, thanks in advance for any idea.

---

If you want to store data about the vertices, you need a finite map from verticies to data. The map might offer a signature like this:

type 'a vmap (* vertex map *)
val empty : 'a vmap  (* empty map *)
val insert : vertex * 'a * 'a vmap -> 'a vmap  (* add info about a vertex *)
val lookup : vertex * 'a vmap -> 'a option  (* look for info about a vertex *)

To implement this signature, you could consider a simple list of vertex * 'a pairs, or something more ambitious like a balanced binary search tree.

---

You can store data about the vertices!

For example, Do you want to record which vertices you have visited?

Let's say you have a function which recursively explores all possible unexplored edges from the current vertex.

It can accept a vector of unexplored edges, plus the current vertex and the target vertex. It will return a vector of paths that successfully make it to the target vertex.

Internally, it will locate the set of edges that begin on this vertex, and recurse onto itself for each edge in this set, removing the chosen edge from the list of unexplored edges into each subfunction.

---

Sorry, I Couldn't Resist

I saw this same puzzle (er question) pop-up on Yahoo! Answers, and I answered it.

The implementation started out as a design based on creating a tree to traverse the graph; but it finally ended up matching the design expressed earlier by Alex Brown.

Originally the planning was done in Haskell, hence this helper function:

fun replicate len el = 
    if len = 0 then nil else el::replicate (len -1) el

The main implementation:

fun routes  dst (edges:(int * int) list) src  = 
    let val (very_possible,remotely_possible) =
            if null edges
            then (nil,nil)
            else List.partition ((fn s=> s = src) o #1) edges 
        val (raw_solutions,dsts_is_nx_srcs) = 
            List.partition  ((fn d => d = dst) o #2) very_possible
        val solutions = replicate  (length raw_solutions) [src,dst]
        val full_rest_routes =
            let val rest_rest_routes = 
                    map (routes dst remotely_possible)  
                            ( map #2 dsts_is_nx_srcs )
              in map (fn lst => src::lst) (List.concat rest_rest_routes)
     end
     in case (very_possible, solutions, remotely_possible)
        of (nil, _,  _)       => nil
         |  (_::_, (p::ps), _) =>  solutions @ full_rest_routes
         |  (_::_, nil, _::_)  =>  full_rest_routes
  |  (_   , nil, nil )  => nil
     end

The user interface:

fun getPaths edges src dst  =  routes dst edges src 

The code above is from routes4.sml; but the testing and IO is omitted. Even though this isn't too long, I am still hoping it coud be simplier.