Mercurial > hg > WSGraph

comparison README.txt @ 41:194ea1428156

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
from http://k0s.org/portfolio/directed-graph.txt
author Jeff Hammel <jhammel@mozilla.com>
date Thu, 11 Apr 2013 15:31:38 -0700
parents 00aee7b82657
children 1cc89badc5c6
comparison
equal deleted inserted replaced
40:00aee7b82657 41:194ea1428156
1 WSGraph 1 WSGraph
2 =========== 2 ===========
3 3
4 WSGI graph server 4 WSGI graph server
5
6
7 Directed Graphs
8 ===============
9
10 Storage
11 -------
12
13 A directed graph may be expressed as JSON::
14
15 {'nodes': {'node1': {'metadata1': value, ...},
16 'node2': {'metadata1': value, ...}}.
17 'edges': {'node1': {'node2': {'metadata': value}, ...},
18 ...},
19 'graphmetadata': value,
20 ...}
21
22 In languages like python, which can hash (key, value) pairs, the edges
23 may be more conveniently hashed::
24
25 edges[('foo', 'bar')] = {'metadata': value}
26
27 A directed graph may be stored in a RDB::
28
29 Table: *nodes*
30
31 +----+---------+---------+---+
32 |node|metadata1|metadata2|...|
33 +====+=========+=========+===+
34 |foo |value |value | |
35 +----+---------+---------+---+
36 |bar |value |value | |
37 +----+---------+---------+---+
38
39 Table: *edges*
40
41 +-----+-----+---------+---------+---+
42 |node1|node2|metadata1|metadata2|...|
43 +=====+=====+=========+=========+===+
44 |foo |bar |value |value | |
45 +-----+-----+---------+---------+---+
46
47 Note that the nodes table has unique keys, but the edges table has
48 rows identified only by the ordered set of two keys: node1 and node2.
49
50 Previous formats use a node and value hash of a string: the nodes have
51 a given name. While this is convenient for human identification, a
52 more efficient hashing mechanism may be achieved by an algorithm.
53 Since a edge is a unique hash of two nodes, the nodes may be numbered
54 with an appropriate algorithm giving a unique hash per edge.
55
56
57 Higher Dimensionality
58 ---------------------
59
60 * faces
61 * ...
62
63
64 Links
65 -----
66
67 * http://www.graphdracula.net/
68 * http://thejit.org/
69
70 Ideas
71 -----
72
73 I work at automation and testing at Mozilla, but have been known to
74 don multiple hats, and, not surprisingly, I think a lot about how the
75 web works. So I just read Stuart's blog post and couldn't help but
76 feel that it plays somewhat in to my idea of mine.
77
78 Background....
79
80 The web is a directed graph (
81 http://en.wikipedia.org/wiki/Directed_graph ). The nodes of the
82 directed graphs are web pages and the edges of the directed graphs are
83 produced when you clicked on a link. This gives a unique opportunity
84 to provide maps of the web. There are a few components in this
85 visualization.
86
87 A site map. This is a map that sits on a server. When a visitor
88 clicks on a link, a new edge is added by reading HTTP REFERER. A toy
89 example, no longer "live", is at http://k0s.org/map.svg . This gives
90 both the webmaster and visitors to see how the site is traveled: the
91 well worn routes as well as the dusty trails. Note that the map
92 itself is an element on the map :) In addition, the map could be
93 embedded as a navigation aid on any page that desires it. Obviously a
94 lot more could be done here than is shown in the toy example: nodes
95 could be collapsed into metanodes until expanded (that is
96 /pictures/mission/capp.jpg and /pictures/mission/cowboy.jpg might just
97 be /pictures/mission for the sake of easy navigation unless a user
98 clicked in for closer detail), etc. The algorithm is really simple:
99 - for each request (in middleware) read the path info and the HTTP
100 referer
101 - if this edge doesn't exist create it
102 - if it does, add one to its count (and whatever other metadata you
103 want....you have the whole request)
104 - additionally, you need a handler to display this data
105 Some sites do this though I rarely see it presented this way and even
106 more rarely to the user.
107 In addition, you can make the system federated. For instance, lets
108 say foo.org and bar.org both have maps (presumedly noted as <link
109 rel="" type=""> in their <HEAD>s). If there is traffic from foo to
110 bar you can stitch these maps together at the points where they meet.
111 You have a federated map of the web!
112
113 The map of one's journey. So the above is from the site's point of
114 view. What about the user's point of view? It would be easy to make
115 an addon that recorded your own map of how you traversed the web. You
116 click on a link in any tab and, again, an edge is created (and
117 populated with whatever metadata you want). You can see how you use
118 the web as well as share your travels with friends. This could also
119 link up with site maps when they are available.
120
121 Just some things I've been thinking of in the last two years. I'm
122 happy to go into more detail or flush them out if there is interest.
123
124 https://groups.google.com/forum/?hl=en#!topic/mozilla-labs-pancake/TbRFpxvic6M
125 http://play.fxhome.mozillalabs.com:4322/lattice/oyiptong@mozilla.com/graph/vis.html
126
5 127
6 128
7 Graph exchange formats: 129 Graph exchange formats:
8 130
9 * http://en.wikipedia.org/wiki/Graph_Modelling_Language 131 * http://en.wikipedia.org/wiki/Graph_Modelling_Language