[Demexp-dev] Delegation and ocamlgraph: an example and a list of issues

[David MENTRE]

Hello,

Thanks to the help of ocamlgraph authors, I've built an example of
delegation graph using ocamlgraph. I'm going to list on this example the
list of issues we must solve to have a correct delegation mechanism in
demexp. 

The example delegation graph is as followed. Delegate(n) is a delegate
of id /n/. The same for Individual(n). Question(n, tag_list) is a
question of id /n/ and with associated list of tags /tag_list/.
Delegation(t) is a delegation over tag /t/.

 Individual(1)---------------------------------------+
      |                                              |
      |                                              |
  Delegation("t")                             Delegation("u")
      |                                              |
      |                                              |
      V                                              V
 Delegate(2)<--Delegation("t")--Individual(4)    Delegate(5)
      |                             .                .
      |                            .                ..
  Delegation("t")                 .                . .
      |                          .                .  .
      V                         .                .   .
 Delegate(3)                 Vote             Vote   .
      .                       .                .    Vote
      .                      .                .      .
     Vote                   .                .       .
      .                    .                .        .
      V                   .                .         V
 Question(1, ["t";"u"])<...................    Question(2, ["u"])


This graph can be represented using ocamlgraph with following code:

(* to compile:
   ocamlopt -I /usr/local/lib/ocaml/3.08.3/ocamlgraph/ graph.cmxa \
       delegation-graph.ml

   ocamlc -I /usr/local/lib/ocaml/3.08.3/ocamlgraph/ graph.cma \
       delegation-graph.ml

   PNG figure: ./a.out |dot -Tpng > example.png

   PS figure:  ./a.out |dot -Tps|gv -
*)

(*
We take following delegation graph as example:

 Individual(1)---------------------------------------+
      |                                              |
      |                                              |
  Delegation("t")                             Delegation("u")
      |                                              |
      |                                              |
      V                                              V
 Delegate(2)<--Delegation("t")--Individual(4)    Delegate(5)
      |                             .                .
      |                            .                ..
  Delegation("t")                 .                . .
      |                          .                .  .
      V                         .                .   .
 Delegate(3)                 Vote             Vote   .
      .                       .                .    Vote
      .                      .                .      .
     Vote                   .                .       .
      .                    .                .        .
      V                   .                .         V
 Question(1, ["t";"u"])<...................    Question(2, ["u"])


*)

open Graph

module Exemple2 = struct

  module V = struct
    type t =
        Individual of int (* id *)
      | Delegate of int (* id *)
      | Question of int * string list (* id * question_tags *)
  end

  module E = struct
    type t =
        Delegation of string (* delegated_tag *)
      | Vote
    let compare = compare
    let default = Vote
  end

  module G = Imperative.Digraph.AbstractLabeled(V)(E)

  let g = G.create ()
  let add = G.add_edge_e g
  let _  =
    let i1 = G.V.create (V.Individual(1)) in
    let d2 = G.V.create (V.Delegate(2)) in
    let d3 = G.V.create (V.Delegate(3)) in
    let i4 = G.V.create (V.Individual(4)) in
    let d5 = G.V.create (V.Delegate(5)) in
    let q1 = G.V.create (V.Question(1, ["t";"u"])) in
    let q2 = G.V.create (V.Question(2, ["u"])) in
    let i1_d2 = G.E.create i1 (E.Delegation("t")) d2 in
    let d2_d3 = G.E.create d2 (E.Delegation("t")) d3 in
    let d3_q1 = G.E.create d3 (E.Vote) q1 in
    let i4_d2 = G.E.create i4 (E.Delegation("t")) d2 in
    let i4_q1 = G.E.create i4 (E.Vote) q1 in
    let i1_d5 = G.E.create i1 (E.Delegation("u")) d5 in
    let d5_q1 = G.E.create d5 (E.Vote) q1 in
    let d5_q2 = G.E.create d5 (E.Vote) q2 in
    add i1_d2;
    add d2_d3;
    add d3_q1;
    add i4_d2;
    add i4_q1;
    add i1_d5;
    add d5_q1;
    add d5_q2
      (*  ... *)

  (* Naive count of number of votes *)

  let nb_vote g =
    G.fold_edges_e
      (fun e c -> match G.E.label e with E.Vote -> c+1 | _ -> c) g 0

  (* Example of teh use of predefined algorithms. For example, computation
     of Strongly Connected Components as lists *)

  module SCC = Components.Make(G)
  let sccl = SCC.scc_list g

  (* Use of Graphviz *)

  module Display = struct
    let vertex_name v = match G.V.label v with
      V.Individual(n) -> "indiv"^(string_of_int n)
    | V.Delegate(n) -> "deleg"^(string_of_int n)
    | V.Question(n,l) ->
        "Quest_n"^(string_of_int n)^"_tags_"^List.fold_right (^) l ""
    let graph_attributes _ = []
    let default_vertex_attributes _ = []
    let vertex_attributes _ = []
    let default_edge_attributes _ = []
    let edge_attributes e = match G.E.label e with
      E.Delegation t -> [`Style `Bold; `Label t]
    | E.Vote -> [`Style `Dotted; `Label "vote"]
    include G
  end
  module Dot = Graphviz.Dot(Display)


  let _ = Dot.output_graph stdout g



end

Using dot of graphviz, we can represent it in a picture:

ocamlgraph is not very well documented for beginners but once that basic
data structures are layed out, it should be pretty easy to apply its
algorithms. And having facilities to draw delegation graphs could be
useful.

Going back to demexp delegation system, issues to solve in above graph
are:

 - there is a conflict for Individual(4) as he delegates on tag "t" to
   Delegate(2) that makes a vote on Question(1) and as he votes directly
   on the same Question(1). This conflict is due to the fact that
   Question(1) has two tags "t" and "u". This conflict should be solve
   by asking Individual(4) to give a preference between "t" and "u", and
   taking into account only one of the two votes;

 - there is a conflict for Individual(1) as he delegates on tag "t" to
   Delegate(2) and also delegates on tag "u" to Delegate(5). Both
   delegations are leading to a vote on Question(1). In the same way, as
   previously, using a preference of Individual(1), one should take only
   one of the two votes into account.

If we assume that (i) Individual(1) prefers "t" over "u" and (ii)
Individual(4) prefers "u" over "t", we have following weights:

 - Delegate(3)->Question(1): weight 1 as only delegation from
   Individual(1) (through Delegates 2 and 3) is taken into account as
   Individual(1) prefers "t" over "u";

 - Individual(4)->Question(1): weight 1, as per choice of Individual(4);

 - Delegate(5)->Question(1): weight 0 as Individual(1) prefers "t" over
   "u";

 - Delegate(5)->Question(2): weight 1, as there is no conflict for
   Individual(1) for Question(2) (only tag "u").

I hope this example makes the delegation system more clear. See an old
email for an attempt to formalize all of this in a more rigorous way[1]:
  http://lists.gnu.org/archive/html/demexp-dev/2004-11/msg00005.html

I don't know yet how to use ocamlgraph to solve thoses issues, and even
if it is possible. I started to look at algorithms that remove edges in
case of conflicts but, as hopefully showed in above example, removing an
edge would make the vote counting invalid. The problem is open. ;)



As usual, feel free to ask questions (no pun intended).


Yours,
d.

Footnotes: 
[1]  There are small errors in the paper, but the overall descritpion
     should be valid.
-- 
pub  1024D/A3AD7A2A 2004-10-03 David MENTRE <address@hidden>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A