message_graph-0.1.4 - proof of concept (very rough)

[boud]

hi samizdat-devel,

i'm putting up my present version of using graphviz to show the 
networking among messages. i think it's still a loooooooong way
from being anywhere near usable and i think dmitry asked some questions
which i haven't answered yet.  But i just wanted to get this out
on the mailing list so that it doesn't get forgotten and also 
as something like "proof of concept" to inspire people. :)

So at the moment if you find this messy (not properly documented,
etc. etc.), don't worry - just ignore it. :)

It' incredibly slow (due to file creation? job spawning? both?).

On the comamnd line, neato takes only 0.02 s, 
but calling from apache/mod-ruby -> ruby-graphviz -> 
graphviz makes neato take 10 seconds, i.e. 500 times slower.

i guess maybe mod_graphviz would be needed???


WHAT IT IS: graphical interface - clickable display of network of
foci/messages. 
* Focuses and featured messages have configurable colours.  Non-featured
messages are black.
* The font size is linearly dependent on the number of messages linked
to the focus.


EXTERNAL LIBRARIES:
(1.0) aptitude install graphviz graphviz-dev
    + wget http://gregoire.lejeune.free.fr/ruby-graphviz_0.6.0.tar.gz
    + ruby extconf.rb config / make / install

MINOR - patches:
(1.1) graphviz.rb:  message_graph_graphviz.rb
(1.2) graphviz/constants.rb:  message_graph_constants.rb

SMALL - patch:
(1.4) index_rb_message_graph_0.1.4:  message_graph_index.rb 
(includes reference RDF feed patch which can be commented out)

MAIN WORK:
(1.3) hacks/message_graph.rb_0.1.4.1

CONFIG EXAMPLE:
(1.5) samizdat.yaml  -> hacks/message_graph_samizdat.yaml


i'm including these below - i don't know if it's better on the mailing
list or as a "branch" in cvs. i'm happy either way.

cheers
boud


----------------------------------------------------------------------

::::::::::::::
message_graph_constants.rb
::::::::::::::
--- /usr/local/lib/site_ruby/1.8/graphviz/constants.rb~ 2005-01-05 
22:11:40.000000000 +0100
+++ constants.rb_0.1.4  2006-10-22 05:16:43.000000000 +0200
@@ -14,6 +14,8 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA

+# 21.10.2006 boud indymedia: added cmapx
+
 module Constants
   ## Const: Output formats
   FORMATS = [
@@ -26,6 +28,7 @@
     "imap",
     "ismap",
     "cmap", 
+    "cmapx",   # cmap is deprecated; cmapx produces better XML
     "jpeg",
     "png",
     "xpm", 
@@ -70,11 +73,13 @@
     "layer",
     "margin",
     "mclimit",
+    "mode", # added for neato
     "nodesep",
     "nslimit",
     "nslimit1",
     "ordering",
     "orientation",
+    "overlap", # added for neato
     "page",
     "pagedir",
     "quantum",
@@ -86,6 +91,7 @@
     "rotate",
     "samplepoints",
     "searchsize",
+    "sep", # added for neato
     "size",
     "style",
     "URL"



::::::::::::::
message_graph_graphviz.rb
::::::::::::::
--- /usr/local/lib/site_ruby/1.8/graphviz.rb~   2006-10-20 03:59:17.000000000 
+0200
+++ graphviz.rb_0.1.4   2006-10-22 05:00:45.000000000 +0200
@@ -207,7 +207,7 @@

       #cmd = find_executable( @prog )
       # cmd = find_executable0( @prog ) # boud HACK
-      cmd = "/usr/bin/dot"  # boud HACK
+      cmd = "/usr/bin/neato"  # boud HACK
       if cmd == nil
         raise StandardError, "GraphViz not installed"
       end


::::::::::::::
message_graph_index.rb
::::::::::::::
--- /usr/share/samizdat/cgi-bin/index.rb~       2006-11-29 18:46:48.000000000 
+0100
+++ /usr/share/samizdat/cgi-bin/index.rb        2006-12-06 04:30:50.695656216 
+0100
@@ -12,6 +12,9 @@

 require 'samizdat/engine'

+require 'import_feeds.rb'  # TODO - should this be load or require?
+require 'message_graph'  # TODO: file hierarchy probably wrong
+
 # messages that are related to any focus (and are not comments or old
 # versions), ordered chronologically by date of relation to a focus (so that
 # when message is edited, it doesn't flow up)
@@ -161,6 +164,12 @@
     features = features.join + %{<div class="foot">} + t.nav_rss(rss_features) 
+
       t.nav(features.size < config['limit']['features'],
       skip_feature + 1, 'index.rb?', 'skip_feature') + "</div>\n"
+
+     # This is to include a graph using  message_graph.rb
+     # TODO: It should be made a configurable option, etc.
+     node_pairs = collect_features_graph(0, false, limit_page)
+     features += message_graph_method(node_pairs)
+
   end

   if render_updates
@@ -172,6 +181,15 @@
       t.nav_rss(rss_updates) + t.nav(updates.size, skip + 1))
   end

+  imported_feeds = ""   # default is zero-length string
+  if( config['import_feeds'] )
+    imported_feeds = %{<tr><td class="links-head">}+ _('RDF Feeds')+ 
+    '</td></tr>
+    <tr><td class="links">' + import_feeds_method + '</td></tr>'
+  end 
+
+
+
   page =
     if full_front_page
 %{<table>
@@ -182,8 +200,8 @@
     <td class="focuses">#{focuses}</td>
     <td class="features" rowspan="3">#{features}</td>
     <td class="updates" rowspan="3">#{updates}</td>
-  </tr>
-  <tr><td class="links-head">}+_('Links')+'</td></tr>
+  </tr>} +  imported_feeds + 
+  %{<tr><td class="links-head">}+_('Links')+'</td></tr>
   <tr><td class="links">
     <div class="focus"><a href="query.rb?run&amp;query='+CGI.escape('SELECT ?resource WHERE 
(dc::date ?resource ?date) (s::inReplyTo ?resource ?parent) LITERAL ?parent IS NOT NULL ORDER BY ?date 
DESC')+'">'+_('All Replies')+'</a></div>
     <div class="focus"><a href="foci.rb">'+_('All Focuses 
(verbose)')+'</a></div>


::::::::::::::
message_graph.rb_0.1.4.1
::::::::::::::
#!/usr/bin/env ruby
#
# Samizdat message graph
#
#   Copyright (c) 2002-2006  Dmitry Borodaenko <address@hidden>,
#   Boud (Indymedia) <address@hidden>
#
#   This program is free software.
#   You can distribute/modify this program under the terms of
#   the GNU General Public License version 2 or later.
#
# vim: et sw=2 sts=2 ts=8 tw=0

require 'samizdat/engine'
require "graphviz"

# 06.12.2006 - works (but slow) with:
#     graphviz       2.2.1-1sarge1
#

# similar to collect_features in index.rb, but aims to put together
# information useful for creating a graph
# (http://en.wikipedia.org/wiki/graph_theory) 
def collect_features_graph(skip, showhidden=false, limit=config['limit']['features'])
  hidden = " AND ?hidden = 'false'" unless showhidden
  list = cache.fetch_or_add(%{features_graph/#{skip}/#{showhidden}/#{limit}}) do
    rdf.select_all( %{
SELECT ?msg, ?rating, ?focus
WHERE (rdf::predicate ?stmt dc::relation)
      (rdf::subject ?stmt ?msg)
      (rdf::object ?stmt ?focus)
      (dc::date ?stmt ?date)
      (s::inReplyTo ?msg ?parent)
      (dct::isVersionOf ?msg ?current)
      (s::rating ?stmt ?rating)
      (s::hidden ?msg ?hidden)
LITERAL ?rating >= :threshold AND
        ?parent IS NULL AND ?current IS NULL #{hidden}
GROUP BY ?msg, ?focus, ?rating
ORDER BY max(?date) DESC}, limit, limit * skip,
      { :threshold => config['graph']['threshold'] }
    )
#.collect {|m,p| m }   # unwrap DBI::Row
  end
#  list.collect {|msg| yield msg }
end



# create a GraphViz object for the set of pairs of messages in  node_pairs
# node_pairs is an array (in principle, a hash should work just as well)
def output_one_graph(graph_id, node_pairs_weighted,
                     output_parameter, file_parameter)

  # initialise GraphViz object
  g = GraphViz::new( graph_id,
                     "output" => output_parameter,
                     "file" => file_parameter )

  # standard graph attributes: http://www.graphviz.org/doc/info/attrs.html
  g.node["shape"] = "plaintext"
  g.node["color"] = "black"

  g.edge["color"] = "black"
  g.edge["weight"] = "1"
  #  g.edge["style"] = "bold"
  g.edge["label"] = ""

  g["size"] = "6,10"
  g["sep"] = "0.2" # minimum separation in inches; see attrs.html as above
  g["overlap"] = "false"
  g["mode"]= "ipsep"

  title_length_max = config['limit']['title']
  message_font_color = config['graph']['labels']['message']
  message_font_color = "green" if !message_font_color
  focus_font_color = config['graph']['labels']['focus']
  focus_font_color = "green" if !focus_font_color

  font_min_size = config['graph']['font_min_size'].to_f
  font_max_size = config['graph']['font_max_size'].to_f
  rating_max = 2.0
  rating_min = config['graph']['threshold'].to_f
  rating_min_features = config['limit']['features_threshold'].to_f
  rating_diff = rating_max - rating_min
  if (rating_diff <= 0.01)  # TODO: does a max function exist in standard ruby?
    rating_diff = 0.1
  end
  font_slope = (font_max_size - font_min_size)/ rating_diff
  # /   slash is emacs ruby-mode hack only
  font_size_zeropoint = font_min_size -  rating_min * font_slope

  #  foci = []
  foci= {}
  nodes= []
  # TODO: there is probably a more elegant ruby way of doing the following:
  #  node_pairs_weighted.each { | msg, rating, focus, focus_weight |
  #    nodes += [ msg, rating ]
  #    foci += [ focus, focus_weight ]
  #  }

  focus_count_max = 1
  node_pairs_weighted.each { | msg, rating, focus |
    nodes += [ [ msg, rating ] ]
    #    foci += [ [ focus ] ]
    if ( i = foci[ focus ] )
      foci.update( { focus => i+1 } )  # hash value = frequency of focus
      if( i+1 > focus_count_max)
        focus_count_max = i+1
      end
    else
      foci.update( { focus => 1 } ) # initial addition to hash table
    end
  }

  focus_count_min = 1
  focus_count_diff = focus_count_max - focus_count_min
  if (focus_count_diff <= 0.01)  # TODO: is there a max function in ruby?
    focus_count_diff = 0.1
  end
  font_slope_focus = (font_max_size - font_min_size)/ focus_count_diff
  # /   slash is emacs ruby-mode hack only
  font_size_zeropoint_focus = font_min_size -  focus_count_min *
    font_slope_focus






#  node_pairs_weighted.each { |n|
#    nodes += [ n[0], n[1] ]  # [ msg id number, rating ]
#    foci += [ n[2], n[3] ]   # [ focus id number, weighting ]
#  }

  #  nodes = node_pairs.flatten.uniq
  #  foci = foci.uniq

  nodes.each { |node, rating|
    label = ""
    add_label = rdf.get_property(node, 
'dc::title').to_s.strip.slice(0..title_length_max)
    if add_label
      label += add_label
    end

    fontsize =  (font_size_zeropoint + rating.to_f * font_slope).to_i.to_s
    if (rating.to_f > rating_min_features)
      fontcolor = message_font_color
    else
      fontcolor = "black"
    end
    g.add_node( node.to_s,
                "URL" => "/" + node.to_s,
                "label" => label,
                "fontcolor" => fontcolor,
                "fontsize" => fontsize
                ) }

  foci.each { |focus, focus_count|
    label = ""
    title = rdf.get_property(focus, 'dc::title')
    if(title)
      add_label = title.to_s.strip.slice(0..title_length_max)
    else
    # if this is a member, use his/her login (since there is no dc::title)
      add_label = rdf.get_property(focus, 's::login').to_s
    end
    if add_label
      label += add_label # + focus[1].to_s
    end

    fontsize =  (font_size_zeropoint_focus +
                   focus_count.to_f * font_slope_focus).to_i.to_s
    g.add_node( focus.to_s,
                "URL" => "/" + focus.to_s,
                "label" => label,
                "fontcolor" => focus_font_color,
                "fontsize" => fontsize
                ) }


  node_pairs_weighted.each { |node_pair| 
#        g.add_edge( node_pair[0].to_s, node_pair[2].to_s ) }
        g.add_edge( node_pair[0].to_s, node_pair[2].to_s ) }

  g.output( )

end


def message_graph_method_test(node_pairs)
  s = ""
  x = node_pairs.flatten.each { |n| s += n.to_s}  # test only
  s
end


def message_graph_method(node_pairs)

  graph_id = node_pairs[0][0].to_s   # arbitrary label - uses first node

  # png map
  png_file = "/var/www/imc-torun/"  # TODO: hardwired, MUST be fixed
  png_file += "./" + config.content_location + "/" + graph_id + ".png"
  png_uri = config.content_location + "/" + graph_id + ".png" # png map

  # client side html map
  map_file = "/var/www/imc-torun/"  # TODO: hardwired, MUST be fixed
  map_file += "./" + config.content_location + "/" + graph_id + ".map"

  png_file
  map_file


  output_one_graph(graph_id, node_pairs, "png",png_file.untaint)

  # The following line requires _cmapx_ to be included in graphviz/constants.rb
  # which is a patch relative to   ruby-graphviz_0.6.0
  output_one_graph(graph_id, node_pairs, "cmapx",map_file.untaint)
  # output_one_graph(graph_id, node_pairs, "dot",map_file.untaint)  ## test 
only ##

  cmd = "cat " + map_file
  f = IO.popen(cmd)   # TODO: avoid intermediary file: map_file
  x = '<IMG SRC="' + png_uri + '" USEMAP="' + graph_id  + '" />' + "\n" +
    f.readlines.to_s
  x

end


::::::::::::::
message_graph_samizdat.yaml
::::::::::::::
# Options for visualisation of message graph
graph:
  threshold: -0.2
  font_min_size: 10
  font_max_size: 20
  labels:
    message: blue
    focus: red


----------------------------------------------------------------------