Changeset 1993 in genesis for nodes/channelga.ml

Timestamp:

Apr 12, 2004, 9:37:29 PM (21 years ago)

Author:

lodewijk

Message:

• channelga.py is obsolete
• parsers voor de speciale gevallen erin gezet, lijkt te werken

File:

• nodes/channelga.ml (modified) (8 diffs)

nodes/channelga.ml

@@ -19 +19 @@
      - on node x, interfaces y and z are well separated and can live on the
        same channel
+     - the link between x on y and z on w is very important, make sure it is
+       well separated on both ends of the link
      - interface x on node y will bother interface z on node w and need to
        be on separate channels
@@ -45 +47 @@
 (** How long should the system iterate after an improvement? *)
 and max_stagnant_iterations = 2000
-(** What is the chance for an ESSID to channel assignment to mutate to a 
+(** What is the chance for an ESSID-to-channel assignment to mutate to a 
     random channel? *)
-and mutation_rate = 0.1;;
+and mutation_rate = 0.1
+(** The most basic score table *)
+and scoretable = [ ((<=) 2,  1);
+                   ((==) 2, -30);
+                   ((==) 1, -70);
+                   ((==) 0, -100) ]
 
 (* the type definitions. note that Caml has trouble with mutually recursive
@@ -79 +86 @@
 let groups = Hashtbl.create 4
 
+(* Now the hashes for the special cases *)
+(** Hash mapping from nodename to a list of winame's indicating the wi's that
+    don't interfere with eachother for the given node *)
 let nointerference = Hashtbl.create 4
+(** List of (nodename1, winame1, nodename2, winame2) tuples indicating a very
+    important link that should be well-separated on both ends *)
+let importantlinks = ref []
+(** Hash mapping from nodename to a list of unusable channels for that node *)
 let unusable = Hashtbl.create 4
-let interference = []
-
-let scoretable = [ ((<=) 2,  1);
-                   ((==) 2, -30);
-                   ((==) 1, -70);
-                   ((==) 0, -100) ]
+(** List of (nodename1, winame1, nodename2, winame2) tuples indicating two
+    interfering interfaces on different nodes *)
+let interference = ref []
+
+(** Run the given diff against the given scoretable and return the score *)
 let rec runtable t diff =
      match t with
@@ -114 +127 @@
 let copyarray src dest = Array.blit src 0 dest 0 (Array.length src)
 
-let in_list l i = try
-                        let _ = List.find ((==) i) l in
+(** Is the given element in the given list? uses compare, so it works on
+    strings as well *)
+let in_list l e = try
+                        let _ = List.find (fun x -> (compare e x) == 0) l in
                         true
                   with Not_found -> false
@@ -133 +148 @@
         let is_unusable = in_list unusable in
         if (is_unusable channel1) || (is_unusable channel2) then -10000
-        else if in_list nointerference (maketuple wi1 wi2) then 1
+        else if (in_list nointerference wi1.wi_name) &&
+                (in_list nointerference wi2.wi_name) then 1
         else runtable scoretable diff;;
 
@@ -148 +164 @@
         base_score * (List.length n.node_wis)
 
-let test_interference c (wi1, wi2) = 
+(** Score the given pair of interferent interfaces against the given
+    configuration *)
+let score_interference c (nodename1, winame1, nodename2, winame2) = 
+        let wi1 = List.find (fun wi -> (compare wi.wi_name winame1) == 0) (Hashtbl.find nodes nodename1).node_wis in
+        let wi2 = List.find (fun wi -> (compare wi.wi_name winame2) == 0) (Hashtbl.find nodes nodename2).node_wis in
         let channel1 = c wi1.wi_essid in
         let channel2 = c wi2.wi_essid in
         let diff = abs (channel1 - channel2) in
-        runtable scoretable diff
+        let res = runtable scoretable diff in
+        res
 
 (** Given a list of nodes and a configuration, return the score for the whole
-    configuration. This is the sum of the scores for all nodes. *)
+    configuration. This is the sum of the scores for all nodes, plus the sum
+    of the scores for all user-specified interferent pairs of interfaces. *)
 let score_configuration ns c =
         let mapper = Hashtbl.find c in
         let foldfunc acc n = acc + (node_score mapper n) in
         let nodescores = List.fold_left foldfunc 0 ns in
-        let interference_penalty = List.fold_left (fun a i -> a + test_interference mapper i) 0 interference in
-        nodescores + interference_penalty;;
-
-(** Given a filename, return a list of all the lines in the file with the given
-   filename. Don't count on the order of the lines in the result. *)
-let snarf_lines fname =
-        let infile = open_in fname in
-        let result = ref [] in
-        try
-                while true do
-                        result := (input_line infile)::!result
-                done;
-                !result (* never gets here *)
-        with End_of_file -> !result
-
-(** Given the name of the node currently being parsed, parse the given tuple
-    that consists of a wi name and an essid. *)
-let parse_pair nodename (wname, essid) = 
-        let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = essid} in
-        let foo = try
-                        let group = Hashtbl.find groups essid in
-                        group.group_wis <- new_wi::group.group_wis;
-                  with Not_found ->
-                        let group = { group_essid = essid; group_wis = [ new_wi ] } in
-                        Hashtbl.add groups essid group in
-        new_wi
-
-let parse_fields fields = 
-        let nodename = head fields in
-        let rec makepairs l = match l with
-                                []              -> []
-                              | x::[]           -> assert false
-                              | a::b::xs        -> (a, b)::(makepairs xs) in
-        let wis = List.map (parse_pair nodename) (makepairs (tail fields)) in
-        let sorted_wis = List.sort compare wis in
-        let node = { node_name = nodename; node_wis = sorted_wis } in
-        Hashtbl.add nodes nodename node
-
-let parse_file fname =
-        let spacere = Str.regexp " " in
-        List.iter (parse_fields $ (Str.split spacere)) (snarf_lines fname)
-        ;;
+        let interference_score = List.fold_left (fun a i -> a + score_interference mapper i) 0 !interference in
+        nodescores + interference_score;;
 
 (** Return a random configuration. For some reason, if this function accesses
@@ -216 +198 @@
         let sorted_nodes = List.sort (fun a b -> compare (a.node_name) (b.node_name)) (values nodes) in
         List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes
-
-let parse_nodeclusters fname = 
-        let spacere = Str.regexp " " in
-        (* handle a row of fields. the first field is the supernode name, the
-           rest are the subnode names. create a new node for the supernode,
-           stuff all the wi's of the subnodes under it, names prefixed with
-           their original node's names for clarity, and remove the subnodes
-           from the nodes hashtable *)
-        let do_fields f = let nodename = head f in
-                          let subnodenames = tail f in
-                          let subnodes = List.map (Hashtbl.find nodes) subnodenames in
-                          List.iter (Hashtbl.remove nodes) subnodenames;
-                          let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in
-                          let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in
-                          let node = { node_name = nodename; node_wis = wis } in
-                          Hashtbl.add nodes nodename node in
-        List.iter (do_fields $ (Str.split spacere)) (snarf_lines fname);;
 
 (** Generalized evolutionary algorithm driver. 
@@ -269 +234 @@
         population.(0);;
 
+(** BEGIN PARSING CODE *)
+
+(** Given a filename, return a list of all the lines in the file with the given
+   filename. Don't count on the order of the lines in the result. *)
+let snarf_lines fname =
+        let infile = open_in fname in
+        let result = ref [] in
+        try
+                while true do
+                        result := (input_line infile)::!result
+                done;
+                !result (* never gets here *)
+        with End_of_file -> !result
+
+(** Read the main input from the given filename *)
+let parse_file fname =
+        let spacere = Str.regexp " " in
+        (** Given the name of the node currently being parsed, parse the given tuple
+            that consists of a wi name and an essid. *)
+        let parse_pair nodename (wname, essid) = 
+                let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = essid} in
+                let foo = try
+                                let group = Hashtbl.find groups essid in
+                                group.group_wis <- new_wi::group.group_wis;
+                          with Not_found ->
+                                let group = { group_essid = essid; group_wis = [ new_wi ] } in
+                                Hashtbl.add groups essid group in
+                new_wi in
+        let parse_fields fields = 
+                let nodename = head fields in
+                let rec makepairs l = match l with
+                                        []              -> []
+                                      | x::[]           -> assert false
+                                      | a::b::xs        -> (a, b)::(makepairs xs) in
+                let wis = List.map (parse_pair nodename) (makepairs (tail fields)) in
+                let sorted_wis = List.sort compare wis in
+                let node = { node_name = nodename; node_wis = sorted_wis } in
+                Hashtbl.add nodes nodename node in
+        List.iter (parse_fields $ (Str.split spacere)) (snarf_lines fname)
+        ;;
+
+(* the parsers for the special case components *)
+
+(** The first field is the nodename, the rest are interface names *)
+let parse_nointerference fs = Hashtbl.add nointerference (head fs) (tail fs)
+(** Read four fields from the given list and add them as a tuple to the given
+    list reference *)
+let parse_quadruplet l fs = 
+        let f = List.nth fs in
+        l := (f 0, f 1, f 2, f 3)::!l
+(** The first field is the nodename, the rest are channels.*)
+let parse_unusable fs =
+        let channels = List.map int_of_string (tail fs) in
+        Hashtbl.add unusable (head fs) channels
+(** The first field is the supernode name, the rest are the names of the
+    subnodes. Construct a new node for the supernode and remove the subnodes
+    from the nodes hash *)
+let parse_supernode fs =
+        let nodename = head fs in
+        let subnodenames = tail fs in
+        let subnodes = List.map (Hashtbl.find nodes) subnodenames in
+        List.iter (Hashtbl.remove nodes) subnodenames;
+        let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in
+        let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in
+        let node = { node_name = nodename; node_wis = wis } in
+        Hashtbl.add nodes nodename node
+
+let parse_special_conf fname =
+        let spacere = Str.regexp " " in
+        let functable = [ ("nointerference", parse_nointerference);
+                          ("important", parse_quadruplet importantlinks);
+                          ("interference", parse_quadruplet interference);
+                          ("unusable", parse_unusable);
+                          ("supernode", parse_supernode) ] in
+        let do_line fs = (List.assoc (head fs) functable) (tail fs) in
+        try 
+                List.iter (do_line $ Str.split spacere) (snarf_lines fname)
+        with x -> ()
+
+(** END PARSING CODE *)
+
 let main = 
         parse_file Sys.argv.(1);
-        parse_nodeclusters "coupled.conf";
+        parse_special_conf "special.conf";
         Random.self_init();
         let all_nodes = values nodes in