WSGraph
===========

WSGI graph server


Directed Graphs
===============

Storage
-------

A directed graph may be expressed as JSON::

 {'nodes': {'node1': {'metadata1': value, ...},
            'node2': {'metadata1': value, ...}}.
  'edges': {'node1': {'node2': {'metadata': value}, ...},
            ...},
  'graphmetadata': value,
  ...}

In languages like python, which can hash (key, value) pairs, the edges
may be more conveniently hashed::

 edges[('foo', 'bar')] = {'metadata': value}

A directed graph may be stored in a RDB::

Table: *nodes*

+----+---------+---------+---+
|node|metadata1|metadata2|...|
+====+=========+=========+===+
|foo |value    |value    |   |
+----+---------+---------+---+
|bar |value    |value    |   |
+----+---------+---------+---+

Table: *edges*

+-----+-----+---------+---------+---+
|node1|node2|metadata1|metadata2|...|
+=====+=====+=========+=========+===+
|foo  |bar  |value    |value    |   |
+-----+-----+---------+---------+---+

Note that the nodes table has unique keys, but the edges table has
rows identified only by the ordered set of two keys: node1 and node2.

Previous formats use a node and value hash of a string: the nodes have
a given name.  While this is convenient for human identification, a
more efficient hashing mechanism may be achieved by an algorithm.
Since a edge is a unique hash of two nodes, the nodes may be numbered
with an appropriate algorithm giving a unique hash per edge.


Higher Dimensionality
---------------------

* faces
* ...


Links
-----

Javascript:
* http://www.jgraph.com/mxgraph.html
  Interactive JavaScript HTML 5 Diagramming Library;
  demo at https://www.draw.io/
* http://www.graphdracula.net/
* http://thejit.org/
* http://marvl.infotech.monash.edu/webcola/ : cola.js
  Constraint-Based Layout in the Browser
* d3: http://d3js.org/
  * http://maxdemarzi.com/2012/02/13/visualizing-a-network-with-cypher/
  * https://github.com/ignacioola/insights
  * http://blog.nextgenetics.net/?e=7

Python:
* http://graph-tool.skewed.de/ :
  Graph-tool is an efficient Python module for manipulation and
  statistical analysis of graphs (a.k.a. networks).
* http://igraph.org/python

Graph DBs:
* https://pypi.python.org/pypi/ajgu : Graph database with several
  backends architecture in mind
* https://bitbucket.org/lcrees/graphalchemy : graphalchemy is a
  generic object to graph mapper for graph databases.

Applications:
* http://www.freebsd.org/cgi/man.cgi?query=netgraph&sektion=4 :
  netgraph -- graph based kernel networking subsystem

Ideas
-----

I work at automation and testing at Mozilla, but have been known to
don multiple hats, and, not surprisingly, I think a lot about how the
web works. So I just read Stuart's blog post and couldn't help but
feel that it plays somewhat in to my idea of mine.

Background....

The web is a directed graph (
http://en.wikipedia.org/wiki/Directed_graph ). The nodes of the
directed graphs are web pages and the edges of the directed graphs are
produced when you clicked on a link.  This gives a unique opportunity
to provide maps of the web.  There are a few components in this
visualization.

A site map.  This is a map that sits on a server.  When a visitor
clicks on a link, a new edge is added by reading HTTP REFERER.  A toy
example, no longer "live", is at http://k0s.org/map.svg . This gives
both the webmaster and visitors to see how the site is traveled: the
well worn routes as well as the dusty trails.  Note that the map
itself is an element on the map :) In addition, the map could be
embedded as a navigation aid on any page that desires it.  Obviously a
lot more could be done here than is shown in the toy example: nodes
could be collapsed into metanodes until expanded (that is
/pictures/mission/capp.jpg and /pictures/mission/cowboy.jpg might just
be /pictures/mission for the sake of easy navigation unless a user
clicked in for closer detail), etc.  The algorithm is really simple:
 - for each request (in middleware) read the path info and the HTTP
 referer
 - if this edge doesn't exist create it
 - if it does, add one to its count (and whatever other metadata you
 want....you have the whole request)
 - additionally, you need a handler to display this data
Some sites do this though I rarely see it presented this way and even
more rarely to the user.
In addition, you can make the system federated.  For instance, lets
say foo.org and bar.org both have maps (presumedly noted as <link
rel="" type=""> in their <HEAD>s).  If there is traffic from foo to
bar you can stitch these maps together at the points where they meet.
You have a federated map of the web!

The map of one's journey.  So the above is from the site's point of
view.  What about the user's point of view?  It would be easy to make
an addon that recorded your own map of how you traversed the web.  You
click on a link in any tab and, again, an edge is created (and
populated with whatever metadata you want). You can see how you use
the web as well as share your travels with friends.  This could also
link up with site maps when they are available.

Just some things I've been thinking of in the last two years.  I'm
happy to go into more detail or flush them out if there is interest.

https://groups.google.com/forum/?hl=en#!topic/mozilla-labs-pancake/TbRFpxvic6M
http://play.fxhome.mozillalabs.com:4322/lattice/oyiptong@mozilla.com/graph/vis.html


= Graph exchange formats =

[Planned] WSGraph should be able to import and export any of the
standard graph formats

* JSGN (native)
* http://en.wikipedia.org/wiki/Graph_Modelling_Language
* http://en.wikipedia.org/wiki/GraphML
* http://en.wikipedia.org/wiki/Trivial_Graph_Format
* http://www.gupro.de/GXL/ , http://en.wikipedia.org/wiki/GXL
* http://en.wikipedia.org/wiki/Dot_language (Graphviz)


= Resources =

Python packages related to graphs:

* graph-tool: http://en.wikipedia.org/wiki/Graph-tool ,
  https://pypi.python.org/pypi/graph-tool ,
  http://projects.skewed.de/graph-tool/

* http://igraph.sourceforge.net/

* http://networkx.github.io/

Javascript:

* http://sigmajs.org/
* graphdracula
* http://arborjs.org/


Other external libraries and tools:

* Graphviz: the old, the venerable, and still the king
* tulip: http://tulip.labri.fr/TulipDrupal/
* GUESS: http://graphexploration.cond.org/
* Java Universal Network/Graph Framework : http://jung.sourceforge.net/
* graphthing http://graph.seul.org/
* igraph http://igraph.sourceforge.net/
* blockdiag: imple diagram images generator; http://blockdiag.com/
* graphthing: http://graph.seul.org/
* gephi: http://gephi.org/ ; the open source graph visualizer

Let's not forget
* ganv: Ganv is an interactive Gtk canvas widget for graph-based
  interfaces;
  http://dev.drobilla.net/browser/trunk/ganv (though see also
  http://packages.ubuntu.com/source/quantal/libs/ganv and
  http://harryhaaren.blogspot.com/2012/12/getting-to-grips-with-flowcanvas.html
  )


See also http://k0s.org/links/?q=graph

(And what is
https://github.com/tinkerpop/blueprints/wiki/GraphML-Reader-and-Writer-Library ?)

Parallel Efforts
----------------

* http://k0s.org/hg/IntentMadeManifest/


TODO
----

* a tool to take graphml embedded in a webpage (or other suitable
  format) and generate a graph in the chosen form (e.g. <img
  src="_generated_graph.png"/> or whatevr we can hammer into HTML

----

Jeff Hammel

http://k0s.org/hg/WSGraph