Mercurial > hg > WSGraph
changeset 41:194ea1428156
from http://k0s.org/portfolio/directed-graph.txt
author | Jeff Hammel <jhammel@mozilla.com> |
---|---|
date | Thu, 11 Apr 2013 15:31:38 -0700 (2013-04-11) |
parents | 00aee7b82657 |
children | 1cc89badc5c6 |
files | README.txt |
diffstat | 1 files changed, 122 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/README.txt Thu Apr 11 13:50:51 2013 -0700 +++ b/README.txt Thu Apr 11 15:31:38 2013 -0700 @@ -4,6 +4,128 @@ 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 +----- + +* http://www.graphdracula.net/ +* http://thejit.org/ + +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: * http://en.wikipedia.org/wiki/Graph_Modelling_Language