笔记

67. Conversions

A graph is defined as a set of nodes and a set of edges, where each edge is a pair of different nodes.

There are several ways to represent graphs in OCaml.

• One method is to list all edges, an edge being a pair of nodes. In this form, the graph depicted opposite is represented as the following expression:

# [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')];;
- : (char * char) list =
[('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]

We call this edge-clause form. Obviously, isolated nodes cannot be represented.

• Another method is to represent the whole graph as one data object. According to the definition of the graph as a pair of two sets (nodes and edges), we may use the following OCaml type:

# type 'a graph_term = {nodes : 'a list;  edges : ('a * 'a) list};;
type 'a graph_term = { nodes : 'a list; edges : ('a * 'a) list; }

Then, the above example graph is represented by:

# let example_graph =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]};;
val example_graph : char graph_term =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]}

We call this graph-term form. Note, that the lists are kept sorted, they are really sets, without duplicated elements. Each edge appears only once in the edge list; i.e. an edge from a node x to another node y is represented as (x, y), the couple (y, x) is not present. The graph-term form is our default representation. You may want to define a similar type using sets instead of lists.

• A third representation method is to associate with each node the set of nodes that are adjacent to that node. We call this the adjacency-list form. In our example:

    (* example pending *)

• The representations we introduced so far well suited for automated processing, but their syntax is not very user-friendly. Typing the terms by hand is cumbersome and error-prone. We can define a more compact and “human-friendly” notation as follows: A graph (with char labelled nodes) is represented by a string of atoms and terms of the type X-Y. The atoms stand for isolated nodes, the X-Y terms describe edges. If an X appears as an endpoint of an edge, it is automatically defined as a node. Our example could be written as:

# "b-c f-c g-h d f-b k-f h-g";;
- : string = "b-c f-c g-h d f-b k-f h-g"

We call this the human-friendly form. As the example shows, the list does not have to be sorted and may even contain the same edge multiple times. Notice the isolated node d.

Write functions to convert between the different graph representations. With these functions, all representations are equivalent; i.e. for the following problems you can always pick freely the most convenient form. This problem is not particularly difficult, but it’s a lot of work to deal with all the special cases.

adjacency-list form定义都没给我怎么转化啊。

let human_to_graph s= let h_edges = String.split_on_char ' ' s in
	let add_node node ns = 
		if not (List.exists (fun e -> e = node) ns) 
				then node::ns else ns
	in
	let rec aux l ns es= match l with
		| [] -> {nodes = ns;edges = es}
		| p::t -> 
			let (ns,es) = if String.length p = 1 then(add_node p.[0] ns, es)
            else
			let ns = add_node p.[0] ns in
			let ns = add_node p.[2] ns in
			let es = if not (List.exists (fun e -> e=(p.[0], p.[2])) es) 
				then (p.[0], p.[2])::es else es in
			(ns, es) in
			aux t ns es
	in
	aux h_edges [] []

又没答案。

68. Path From One Node to Another One

Write a function paths g a b that returns all acyclic path p from node a to node b ≠ a in the graph g. The function should return the list of all paths via backtracking.

# let example_graph =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]};;
val example_graph : char graph_term =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]}
# paths example_graph 'f' 'b';;
- : char list list = [['f'; 'c'; 'b']; ['f'; 'b']]

感觉得写一些通用的图的方法。比如 list.contain 这种的，有无环判断真的很麻烦。

有预感又要死循环了，很痛苦。

很多地方可以用 Option 改良一下，能好看很多。癌，差不多得了。

let paths g start end_node = 
    	let nodes,edges = g.nodes, g.edges in
        let rec find_to s edges = match edges with
            | [] -> []
            | (from, next)::t -> if from = s then next::find_to s t
                else if next = s then from::find_to s t
                else find_to s t
        in
        let rec valid_next path ns = match ns with
            | [] -> []
            | h::t -> if (List.exists (fun e-> e=h) path) then (valid_next path t) else h::(valid_next path t)
        in
        let rec aux path now = 
            let next_nodes = valid_next path (find_to now edges) in
            let goals = List.map (fun e -> e::path) (List.filter (fun e -> e = end_node) next_nodes) in
            let others = List.filter (fun e -> e != end_node) next_nodes in
            List.fold_left (fun n t-> n @ (aux (t::path) t)) goals others
        in
        List.map (fun e-> List.rev e) (aux [start] start);;

这个 neighbors 写的就比我的 find_to 要好，还能把去环逻辑下压到这个函数里完成了，挺好的，有点像 Graph.filter 了。

List.mem 就是 List.contain 哦。

妙啊，它其实是从 b 走到 a 的，这样就不用 List.rev 了。这个递归也做的比我优雅多了，强啊，递归出来是个 list list，又被 concat_map 打平。

# (* The datastructures used here are far from the most efficient ones
     but allow for a straightforward implementation. *)
  (* Returns all neighbors satisfying the condition. *)
  let neighbors g a cond =
    let edge l (b, c) = if b = a && cond c then c :: l
                        else if c = a && cond b then b :: l
                        else l in
    List.fold_left edge [] g.edges
  let rec list_path g a to_b = match to_b with
    | [] -> assert false (* [to_b] contains the path to [b]. *)
    | a' :: _ ->
       if a' = a then [to_b]
       else
         let n = neighbors g a' (fun c -> not (List.mem c to_b)) in
           List.concat_map (fun c -> list_path g a (c :: to_b)) n

  let paths g a b =
    assert(a <> b);
    list_path g a [b];;
val neighbors : 'a graph_term -> 'a -> ('a -> bool) -> 'a list = <fun>
val list_path : 'a graph_term -> 'a -> 'a list -> 'a list list = <fun>
val paths : 'a graph_term -> 'a -> 'a -> 'a list list = <fun>

69. Cycle From a Given Node

Write a functions cycle g a that returns a closed path (cycle) p starting at a given node a in the graph g. The predicate should return the list of all cycles via backtracking.

# let example_graph =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]};;
val example_graph : char graph_term =
  {nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
   edges = [('h', 'g'); ('k', 'f'); ('f', 'b'); ('f', 'c'); ('c', 'b')]}
# cycles example_graph 'f';;
- : char list list =
[['f'; 'b'; 'c'; 'f']; ['f'; 'c'; 'f']; ['f'; 'c'; 'b'; 'f'];
 ['f'; 'b'; 'f']; ['f'; 'k'; 'f']]

偷一手上一道题的 neighbors 好吧。

let neighbors g a cond =
 let edge l (b, c) = if b = a && cond c then c :: l
                     else if c = a && cond b then b :: l
                     else l in
 List.fold_left edge [] g.edges;;

val neighbors : 'a graph_term -> 'a -> ('a -> bool) -> 'a list = <fun>

let cycles g start = 
	let rec list_path g to_b = match to_b with
		| [] -> assert false (* [to_b] contains the path to [b]. *)
		| a' :: t ->if a' = start && List.length to_b!=1 then [to_b]
    	else
    		let n = neighbors g a' (fun c -> c=start || (not (List.mem c to_b))) in
        	List.concat_map (fun c -> list_path g (c :: to_b)) n
	in
	list_path g [start];;

val cycles : 'a graph_term -> 'a -> 'a list list = <fun>

强啊，这个思路。

# let cycles g a =
    let n = neighbors g a (fun _ -> true) in
    let p = List.concat_map (fun c -> list_path g a [c]) n in
    List.map (fun p -> p @ [a]) p;;
val cycles : 'a graph_term -> 'a -> 'a list list = <fun>

70. Construct All Spanning Trees

Write a function s_tree g to construct (by backtracking) all spanning trees of a given graph g. With this predicate, find out how many spanning trees there are for the graph depicted to the left. The data of this example graph can be found in the test below. When you have a correct solution for the s_tree function, use it to define two other useful functions: is_tree graph and is_connected Graph. Both are five-minutes tasks!

# let g = {nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'];
         edges = [('a', 'b'); ('a', 'd'); ('b', 'c'); ('b', 'e');
                  ('c', 'e'); ('d', 'e'); ('d', 'f'); ('d', 'g');
                  ('e', 'h'); ('f', 'g'); ('g', 'h')]};;
val g : char graph_term =
  {nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'];
   edges =
    [('a', 'b'); ('a', 'd'); ('b', 'c'); ('b', 'e'); ('c', 'e'); ('d', 'e');
     ('d', 'f'); ('d', 'g'); ('e', 'h'); ('f', 'g'); ('g', 'h')]}

生成树吗，都是搞最小生成树的，结果你来个生成树，又得想个方法怎么好去重了。

哦，好像也不用去重，不需要多节点出发的，单节点就能获得所有结果了。

let s_tree g = 
	let rec aux used_nodes edges now = if List.length used_nodes = List.length g.nodes then [{nodes = used_nodes; edges = edges}] else
		let next_nodes = neighbors g now (fun e -> not (List.mem e used_nodes)) in
			let rec go_next remain = match remain with
				| [] -> []
				| h::t -> (aux (h::used_nodes) ((h,now)::edges) h) @ go_next t
			in
		go_next next_nodes
		in
	match g.nodes with
		| []-> raise Not_found
		| h::t -> aux [h] [] h

let is_tree g = if List.length (s_tree g) = 1 then true else false 

let is_connected g = if List.length (s_tree g) = 0 then false else false 

癌，我服了，又没答案。

稍微盯了一下，感觉应该是全的。

71. Construct the Minimal Spanning Tree

Write a function ms_tree graph to construct the minimal spanning tree of a given labelled graph. A labelled graph will be represented as follows:

# type ('a, 'b) labeled_graph = {nodes : 'a list;
                               labeled_edges : ('a * 'a * 'b) list};;
type ('a, 'b) labeled_graph = {
  nodes : 'a list;
  labeled_edges : ('a * 'a * 'b) list;
}

(Beware that from now on nodes and edges mask the previous fields of the same name.)

Hint: Use the algorithm of Prim. A small modification of the solution of P83 does the trick. The data of the example graph to the right can be found below.

# let g = {nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'];
         labeled_edges = [('a', 'b', 5); ('a', 'd', 3); ('b', 'c', 2);
                          ('b', 'e', 4); ('c', 'e', 6); ('d', 'e', 7);
                          ('d', 'f', 4); ('d', 'g', 3); ('e', 'h', 5);
                          ('f', 'g', 4); ('g', 'h', 1)]};;
val g : (char, int) labeled_graph =
  {nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'];
   labeled_edges =
    [('a', 'b', 5); ('a', 'd', 3); ('b', 'c', 2); ('b', 'e', 4);
     ('c', 'e', 6); ('d', 'e', 7); ('d', 'f', 4); ('d', 'g', 3);
     ('e', 'h', 5); ('f', 'g', 4); ('g', 'h', 1)]}

你来了，复习一遍 Prim 好吧。

总结