-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathGraph.html
More file actions
157 lines (136 loc) · 51.3 KB
/
Copy pathGraph.html
File metadata and controls
157 lines (136 loc) · 51.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
<html>
<head>
<title>NodeBox | Graph</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta http-equiv="imagetoolbar" content="no" />
<meta name="description" content="" />
<meta name="keywords" content="NodeBox, Graph" />
<link rel="canonical" href="https://www.nodebox.net/code/Graph" />
<link type="text/css" rel="stylesheet" media="screen" href="/media/css/nbar.css">
<script type="text/javascript" src="/code/js/pop.js"></script>
<script type="text/javascript" src="/code/js/confirm.js"></script>
<link href="/code/css/default.css" rel="stylesheet" type="text/css" />
<link href="/code/css/print.css" rel="stylesheet" type="text/css" media="print" />
</head>
<body id="body">
<div class="nbar">
<ol>
<li><a class="node" href="/code/Home">NodeBox 1<span class="nbar-arrow"></span></a>
<ol class="nbar-dropdown">
<li><a href="/">Homepage</a></li>
<li><a href="/node/">NodeBox 3<small>Node-based app for generative design and data visualization</small></a></li>
<li><a href="/opengl/">NodeBox OpenGL<small>Hardware-accelerated cross-platform graphics library</small></a></li>
<li><a href="/code/Home">NodeBox 1<small>Generate 2D visuals using Python code (Mac OS X only)</small></a></li>
</ol>
</li>
<li><a class="gallery" href="/gallery/">Gallery</a></li>
<li><a class="documentation" href="/code/Tutorial">Documentation</a></li>
<li><a class="forum" href="http://support.nodebox.net/discussions">Forum</a></li>
<li><a class="blog" href="/blog/">Blog</a></li>
</ol>
</div>
<div id="all">
<div id="header_and_navigation">
<div id="header">
<a href="/code/Home"><img id="header_image" src="/code/g/header-small.jpg" width="800" /></a></div>
<div id="title">
<a href="/code/Home"><h1>NodeBox</h1>
<strong><em>Create visual output with Python programming code</em></strong>
</a></div>
<div id="contextual">
<div id="languages">
</div>
<div id="search">
<form id="sf" method="get">
<input type="text" id="q" name="q" value="" />
<a href="javascript:document.getElementById('sf').submit();">GO</a>
</form>
</div>
</div>
<div id="navigation">
<div id="navigation_public">
<a href="/code/Home">Home</a>
<a href="/code/Download">Download</a>
<a href="/code/Reference">Reference</a>
<a href="/code/Tutorial">Tutorial</a>
<a href="/code/Library">Library</a>
<a href="/code/Gallery">Gallery</a>
<a href="/code/About">About</a>
</div>
</div>
</div>
<div id="content">
<div id="nodebox-link">
<a href="/code/Home"><img src="/code/g/transparent.gif" /></a>
</div>
<div class="inside">
<h3>Graph</h3>
<h2>Description</h2> <p>In mathematics and computer science, <a href="http://en.wikipedia.org/wiki/Graph_theory">graph theory</a> studies networks of connected nodes and their properties. A graph can be used to visualize related data, or to find the shortest path from one node to another node for example.</p><p>Central concepts in graph theory are:</p><ul><li><b>Node</b>: a block of information in the network.</li><li><b>Edge</b>: a connection between two nodes (can have a direction and a weight).</li><li><b>Centrality</b>: determining the relative importance of a node.</li><li><b>Clustering</b>: partitioning nodes into groups.</li></ul><p>The NodeBox Graph library includes algorithms from <a href="https://networkx.lanl.gov/wiki" target="_self">NetworkX</a> for betweenness centrality and eigenvector centrality, Connelly Barnes' implementation of Dijksta shortest paths (<a href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466" target="_self">here</a>) and the spring layout for JavaScript by Aslak Hellesoy and Dave Hoover (<a href="http://snipplr.com/view/1950/graph-javascript-framework-version-001/" target="_self">here</a>). The goal of this library is visualization of small graphs (<200 elements), if you need something more robust we recommend using NetworkX. </p><p><span class="pink_text">For those of you looking for the old Graph library built on Boost, it can still be found <a href="/code/Boost_Graph" target="_self">here</a>.</span><br /></p><h2>Download</h2> <table border="0"><tbody><tr><td><a href="https://nodebox.s3.amazonaws.com/code/data/media/graph.zip" target="_self"><img src="/code/data/media/download.gif" alt="download" /></a></td><td><a href="https://nodebox.s3.amazonaws.com/code/data/media/graph.zip" target="_self">graph.zip</a> (32KB) <br /> <i>Last updated for NodeBox 1.9.5.6<br /></i><i>Licensed under GPL</i><br /><i>Author: Tom De Smedt<br /></i></td></tr></tbody></table><h2>Documentation </h2><ul><li><a href="Graph.html#loading_the_library" target="_self">How to get the library up and running</a></li><li><a href="Graph.html#create" target="_self">Creating a graph</a></li><li><a href="Graph.html#add" target="_self">Adding nodes and edges<br /></a></li><li><a href="Graph.html#remove" target="_self">Retrieving/removing nodes and edges<br /></a></li><li><a href="Graph.html#draw" target="_self">Drawing the graph</a></li><li><a href="Graph.html#style" target="_self">Customizing styles and style rules</a></li><li><a href="Graph.html#interaction" target="_self">Interacting with the animated graph</a></li><li><a href="Graph.html#connectivity" target="_self">Connectivity</a><br /></li><li><a href="Graph.html#proximity" target="_self">Proximity</a></li><li><a href="Graph.html#clustering" target="_self">Clustering</a></li><li><a href="Graph.html#issues" target="_self">Known issues and limitations</a><br /></li></ul><p> </p><p><img src="/code/data/media/graph-wordnet.jpg" alt="graph-wordnet" /></p><p>The library has a cool example of a visual browser for WordNet. </p><p> </p><hr size="2" width="100%" /><h2><a name="loading_the_library" title="loading_the_library"></a>How to get the library up and running</h2> <p>Put the <i>graph</i> library folder in the same folder as your script so NodeBox can find the library. You can also put it in <i>~/Library/Application Support/NodeBox/.</i></p> <pre class="python">graph = <span style="color: #530035;">ximport</span><span style="">(</span><span style="color: #ff0080;">"graph"</span><span style="">)</span></pre></pre> <p><span class="small_text">Outside of NodeBox you can also just do <i>import graph.</i> </span></p><p> </p><hr size="2" width="100%" /><h2><a name="create" title="create"></a>Creating a graph<br /></h2><pre class="python">create<span style="">(</span>iterations=<span style="">1000</span>, distance=<span style="">1.0</span>, layout=<span style="color: #ff0080;">"spring"</span>, depth=<span style="color: #530035;">True</span><span style="">)</span></pre></pre><p>The <i>create()</i> command returns a new <i>graph</i> object encompassing the drawing canvas. The network of connected nodes will originate from the center of the canvas. The <i>distance</i> parameter controls the spacing between nodes and hence the size of the graph.<br /> </p><p>By default, a <a href="http://en.wikipedia.org/wiki/Force-based_algorithms" target="_self">spring force</a> <i>layout</i> is used to visualize the graph. Each element in the graph (or <b>node</b>) will try to get away as far as possible from the others. This is the <i>repulsive force</i> in the network. At the same time, there are connections (or <b>edges</b>) that keep nodes together. The greater the weight of an edge the stronger it is in pulling two nodes together. This is the <i>attractive force</i> in the network. You can also set the <i>layout</i> parameter to "circle" to use a simple circle-based layout. <br /></p><p>The forces in the network need to be calculated several times in order for the nodes' positions to stabilize. The higher the number of <i>iterations</i> the better (but slower) the layout.</p><table><tbody><tr><td><table><tbody><tr><td><img src="/code/data/media/graph-depth2.jpg" alt="graph-depth2" /></td><td><img src="/code/data/media/graph-depth1.jpg" alt="graph-depth1" /></td></tr></tbody></table></td><td>When <i>depth</i> is set to <i>True</i>, the library will attempt to import the NodeBox <a href="/code/Colors" target="_self">Colors</a> library for gradient and shadow effects.</td></tr></tbody></table><p> </p><p>The returned <i>graph</i> object has the following properties:</p><ul><li><i>graph.nodes</i>: a list of all the <i>node</i> objects in the graph.</li><li><i>graph.edges</i>: a list of all the <i>edge</i> objects in the graph.</li><li><i>graph.leaves</i>: a list of all the nodes with only one connection.<br /></li><li><i>graph.root</i>: the root node in the graph.</li><li><i>graph.done</i>: <i>True</i> when the graph's layout is completely calculated.</li><li><i>graph.distance</i>: the scale of the graph when drawn (usually a number between 0.5 and 2.0).<br /> </li></ul><br /><ul><li><i>graph.density</i>: a number between 0.0 and 1.0 indicating the number of connections. </li><li><i>graph.is_sparse</i>: <i>True</i> when there are few connections in the graph (density is 0.35 or less).</li><li><i>graph.is_dense</i>: <i>True</i> when there are a lot of connections (density is 0.65 or more).<br /> </li><li><i>graph.is_complete</i>: <i>True</i> when all nodes are connected to all other nodes (density is 1.0).</li></ul><br /><ul><li><i>graph.layout</i>: the <i>layout</i> object used to calculate the graph.</li><li><i>graph.events</i>: the <i>event</i> object used to monitor mouse dragging and clicking.</li><li><i>graph.styles</i>: the <i>styles</i> object used to colorize and draw the graph. </li></ul><p> </p><hr size="2" width="100%" /><h2><a title="add" name="add"></a>Adding nodes and edges </h2><pre class="python">graph.<span style="">add_node</span><span style="">(</span><span style="">id</span>, radius=<span style="">8</span>, style=<span style="color: #ff0080;">"default"</span>, category=<span style="color: #ff0080;">""</span>, root=<span style="color: #530035;">False</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">add_edge</span><span style="">(</span>id1, id2, weight=<span style="">0.0</span>, length=<span style="">1.0</span>, label=<span style="color: #ff0080;">""</span><span style="">)</span></pre></pre><p>You can add nodes (e.g. blocks of information you want to connect) to the graph with the <i>graph.add_node()</i> method. The <i>id</i> parameter <b>uniquely</b> identifies each node, it will appear as a label on each node once the graph is visualized. When the <i>root</i> parameter is <i>True</i> it will set this node as the graph's root.</p><p>The <i>graph.add_node()</i> method returns a node object with the following properties:</p><ul><li><i>node.id</i>: the node's unique id.</li><li><i>node.r</i>: the node's radius.<br /></li><li><i>node.style</i>: the name of the style used to colorize and draw the node.<br /></li><li><i>node.category</i>: a category this node belongs to.</li><li><i>node.label</i>: displayed when the node is drawn (by default, its id). </li><li><i>node.x</i>: the horizontal position of the node on the canvas.</li><li><i>node.y</i>: the vertical position of the node on the canvas.<br /></li></ul><ul><li><i>node.links</i>: a list of all <i>node</i> objects connected to this one.</li><li><i>node.edges</i>: a list of all <i>edge</i> objects this node is involved with.</li><li><i>node.is_leaf</i>: <i>True</i> when the node has only one connection. </li></ul><br /><ul><li><i>node.weight</i>: a number between 0.0 and 1.0 reflecting the node's relevance in the graph.</li><li><i>node.traffic</i>: a number between 0.0 and 1.0 reflecting the amount of shortest paths.</li><li><i>node.eigenvalue</i>: identical to <i>node.weight.</i></li><li><i>node.betweenness</i>:identical to <i>node.traffic</i>.<br /></li></ul><p>We'll look at the details of a node's weight and traffic in the section on <a href="Graph.html#proximity" target="_self">graph proximity</a>.</p><p>You can connect two nodes with the <i>graph.add_edge()</i> method. It takes two node id's, an optional <i>weight</i> (ranging between 0.0 and 1.0) and an optional <i>label</i> to display near the edge when it is drawn. <br /></p><p>An <i>edge</i> object is returned. It has the following properties:</p><ul><li><i>edge.node1</i>: the <i>node</i> object from which the connection originates.</li><li><i>edge.node2</i>: the <i>node</i> object in which the connection ends.</li><li><i>edge.weight</i>: the weight or strength of the connection.</li><li><i>edge.length</i>: the individual length of the edge (1.0 by default). </li><li><i>edge.label</i>: a label to display near the edge when drawn.</li></ul><br /><table><tbody><tr><td><p><img src="/code/data/media/graph-create.jpg" alt="graph-create" /><br /> </p></td><td><pre class="python">graph = <span style="color: #530035;">ximport</span><span style="">(</span><span style="color: #ff0080;">"graph"</span><span style="">)</span>
g = graph.<span style="">create</span><span style="">(</span>iterations=<span style="">500</span>, distance=<span style="">0.8</span><span style="">)</span>
g.<span style="">add_node</span><span style="">(</span><span style="color: #ff0080;">"NodeBox"</span><span style="">)</span>
g.<span style="">add_node</span><span style="">(</span><span style="color: #ff0080;">"Core Image"</span>, category=<span style="color: #ff0080;">"library"</span><span style="">)</span>
g.<span style="">add_edge</span><span style="">(</span><span style="color: #ff0080;">"Core Image"</span>, <span style="color: #ff0080;">"NodeBox"</span><span style="">)</span>
g.<span style="">solve</span><span style="">(</span><span style="">)</span>
g.<span style="">draw</span><span style="">(</span><span style="">)</span></pre></pre></td></tr></tbody></table><p> </p><hr size="2" width="100%" /><h2><a title="remove" name="remove"></a>Retrieving/removing nodes and edges </h2><p>The <i>graph</i> object has <i>graph.nodes</i> and <i>graph.edges</i> properties that list all of the nodes and connections it contains. It also has a <i>graph.node()</i> and a <i>graph.edge()</i> method that returns nodes and edges based on id's:</p><pre class="python">graph.<span style="">node</span><span style="">(</span><span style="">id</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">edge</span><span style="">(</span>id1, id2<span style="">)</span></pre></pre><p>Furthermore, a graph behaves as a dictionary with node id keys linking to node object:</p><pre class="python"><span style="color: #530035;">for</span> <span style="">id</span> <span style="color: #530035;">in</span> graph:
<span style="color: #530035;">print</span> graph<span style="">[</span><span style="">id</span><span style="">]</span>.<span style="">style</span></pre></pre><p>To remove nodes and edges you can use the methods below. The <i>graph.clear()</i> method removes all nodes and all edges and resets the graph's layout. This is useful when you want to dynamically reload a graph. </p><pre class="python">graph.<span style="">remove_node</span><span style="">(</span><span style="">id</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">remove_edge</span><span style="">(</span>id1, id2<span style="">)</span></pre></pre><pre class="python">graph.<span style="">clear</span><span style="">(</span><span style="">)</span></pre></pre><p>You can get access to all the nodes connected to a given node from the <i>node.links</i> list. This list also has a fast <i>node1.links.edge(node2)</i> method that retrieves the edge between two nodes.<br /></p><p> </p> <hr size="2" width="100%" /><h2><a title="draw" name="draw"></a>Drawing the graph </h2><p>Before we can draw the graph to the canvas, <b>we first need to calculate its layout</b>. This may take several seconds or more for graphs with many nodes. More nodes slow down the process, as do more visual elements like edge labels. The following methods are involved:</p><pre class="python">graph.<span style="">prune</span><span style="">(</span>depth=<span style="">0</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">update</span><span style="">(</span>iterations=<span style="">10</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">solve</span><span style="">(</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">draw</span><span style="">(</span>weighted=<span style="color: #530035;">False</span>, directed=<span style="color: #530035;">False</span>, highlight=<span style="">[</span><span style="">]</span>, traffic=<span style="color: #530035;">None</span><span style="">)</span></pre></pre><p>The <i>graph.prune()</i> method removes orphaned nodes that have no connections . If <i>depth</i> is 1 it removes nodes that have one ore less connections, and so on. Pruning is often a good idea, as the less nodes there are in a graph the faster the layout is calculated.</p><p>The <i>graph.update()</i> method calculates a portion the total iterations. This is useful in an animation when you want the graph to slowly unfold. When the entire layout has been calculated, the <i>graph.done</i> property will be <i>True</i>.</p><p>The <i>graph.solve()</i> method does all the iterations at once. If you're not running an animation you usually use this method before drawing the graph.</p><p>The <i>graph.draw()</i> method draws the graph to the canvas. It will originate from the canvas center (although you can nudge it horizontally or vertically with optional <i>dx</i> and <i>dy </i>parameters).</p><p> </p><table><tbody><tr><td><img src="/code/data/media/graph_draw1.jpg" alt="graph_draw1" /></td><td>The optional <i>weighted</i> parameter indicates an edge's weight by adding a subtle shadow to it when set to <i>True</i>. </td></tr><tr><td><img src="/code/data/media/graph_draw2.jpg" alt="graph_draw2" /></td><td>The optional <i>directed</i> parameters indicates an edge's direction with an arrow when set to <i>True</i>. </td></tr><tr><td><img src="/code/data/media/graph_draw3.jpg" alt="graph_draw3" /></td><td>The optional <i>highlight</i> parameter indicates a path between two nodes. Node id's in the path are supplied as a list. Usually this is a value returned from the <i>graph.shortest_path()</i> method. </td></tr><tr><td><img src="/code/data/media/graph_draw4.jpg" alt="graph_draw4" /></td><td>The optional <i>traffic</i> parameter can be a number, representing the amount of top-trafficked nodes to highlight. Nodes with a high traffic have a lot of shortest paths passing through them therefore have a central role in the network. </td></tr></tbody></table><p> </p><p><span class="grey_box">Layout</span> </p><p>If you're using the graph in an animation, you can use the <i>graph.layout.refresh()</i> method to trigger some new iterations. This is useful when you are for example dynamically adding new nodes after the layout has stopped. The <i>graph.layout.reset()</i> restarts the layout from scratch.</p><pre class="python">graph.<span style="">layout</span>.<span style="">refresh</span><span style="">(</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">layout</span>.<span style="color: #530035;">reset</span><span style="">(</span><span style="">)</span></pre></pre><p>When using the spring-force layout, <i>graph.layout </i>has a<i> tweak()</i> method that allows you to play around with the internals of the layout algorithm:</p><pre class="python">graph.<span style="">layout</span>.<span style="">tweak</span><span style="">(</span>k=<span style="">2</span>, m=<span style="">0.01</span>, w=<span style="">15</span>, d=<span style="">0.5</span>, r=<span style="">15</span><span style="">)</span></pre></pre><p>The <i>k </i>parameter is the force constant by which nodes are pushed away from each other, <i>m</i> is a dampener for the total attractive/repulsive force, <i>w is</i> a weight multiplier (so heavier edges have a bigger attraction), <i>d</i> is the maximum node movement per iterations and <i>r</i> is the radius of repulsive force originating from each node. </p><p>You may find the following layout properties easier to use:</p><ul><li><i>graph.layout.force</i>: the attractive/repulsive force in the layout (0.01 by default).</li><li><i>graph.layout.repulsion</i>: the repulsive radius originating from each node (15 by default).</li></ul><p>If you are using the circle layout, <i>graph.layout</i> has only one property:</p><ul><li><i>graph.layout.orbits</i>: the number of circles used in the layout (2 by default). </li></ul><p> </p><hr size="2" width="100%" /><h2><a title="style" name="style"></a>Customizing styles and style rules</h2><p>You can customize the look and feel of the graph down to the bottom. The <i>graph.styles</i> dictionary has different <b>styles</b> for different nodes. Each style has some color and font properties and a range of methods for drawing each element in the graph. The styles dictionary is accompanied by a <i>styleguide</i> containing <b>rules</b> that define how and when to apply the styles. You can easily modify existing styles, create new ones, and devise your own rules for how to apply them.</p><p> </p><p><span class="grey_box">Predefined styles</span> </p><p>Let's have a look at the different styles in a graph:</p><table><tbody><tr><td> <img src="/code/data/media/graph-style-default.jpg" alt="graph-style-default" /></td><td> <b>default</b>: this style is used for nodes that have no style defined.<br />Edges will always use the default stroke color.<br /> </td></tr><tr><td> <img src="/code/data/media/graph-style-light.jpg" alt="graph-style-light" /></td><td> <b>light</b>: a style with subtly highlighted nodes. <br />By default it is used for nodes directly connected to the root.<br /></td></tr><tr><td> <img src="/code/data/media/graph-style-back.jpg" alt="graph-style-back" /></td><td> <b>back</b>: a style with green colored nodes and curved edges. <br />By default it is used to indicate a previous root node (e.g. like a back button). </td></tr><tr><td> <img src="/code/data/media/graph-style-marked.jpg" alt="graph-style-marked" /></td><td> <b>marked</b>: a style that marks nodes with a dot.<br />By default it is used to indicate peers of the root node. </td></tr><tr><td> <img src="/code/data/media/graph-style-dark.jpg" alt="graph-style-dark" /></td><td> <b>dark</b>: a style with blue colored nodes.<br />By default it is used to indicate nodes with four or more connections. </td></tr><tr><td> <img src="/code/data/media/graph-style-important.jpg" alt="graph-style-important" /></td><td> <b>important</b>: a style with big blue colored nodes that get an extra outline.<br />By default it is used for nodes that have a weight of 0.75 or more.<br /></td></tr><tr><td> <img src="/code/data/media/graph-style-highlight.jpg" alt="graph-style-highlight" /></td><td> <b>highlight</b>: a style that marks paths in pink.<br />By default it is used to indicate the <i>highlight</i> path supplied to <i>graph.draw()</i>.</td></tr><tr><td> <img src="/code/data/media/graph-style-root.jpg" alt="graph-style-root" /></td><td> <b>root</b>: a style that marks the root node in the graph.<br /></td></tr></tbody></table><pre class="python"><span style="color: #530035;">print</span> graph.<span style="">styles</span>.<span style="">keys</span><span style="">(</span><span style="">)</span>
>>> <span style="">[</span><span style="color: #ff0080;">'default'</span>, <span style="color: #ff0080;">'light'</span>, <span style="color: #ff0080;">'back'</span>, <span style="color: #ff0080;">'marked'</span>, <span style="color: #ff0080;">'dark'</span>,
>>> <span style="color: #ff0080;">'important'</span>, <span style="color: #ff0080;">'highlight'</span>, <span style="color: #ff0080;">'root'</span><span style="">]</span></pre></pre><p>You can change the properties of each of the individual style objects:</p><pre class="python">graph.<span style="">styles</span>.<span style="">root</span>.<span style="color: #530035;">fontsize</span> = <span style="">20</span></pre></pre><p>Or set a property on all styles:</p><pre class="python">graph.<span style="">styles</span>.<span style="color: #530035;">stroke</span> = <span style="color: #530035;">color</span><span style="">(</span><span style="">1</span><span style="">)</span></pre></pre><p>Here's an example of how to add your own custom style:</p><pre class="python">s = g.<span style="">styles</span>.<span style="">create</span><span style="">(</span><span style="color: #ff0080;">"red"</span><span style="">)</span>
s.<span style="color: #530035;">fill</span> = <span style="color: #530035;">color</span><span style="">(</span><span style="">1</span>, <span style="">0</span>, <span style="">0.25</span>, <span style="">0.75</span><span style="">)</span></pre></pre> <p> </p> <p><span class="grey_box">Style properties</span> </p><p>A <i>style</i> object has the following properties:</p><ul><li><i>style.background</i>: graph background <a href="/code/Reference_|_color()" target="_self">color</a> (always picked from the default style).</li><li><i>style.fill</i>: fill color for nodes. The default fill is also used as backdrop on weighted edges.</li><li><i>style.stroke</i>: the stroke color for node outlines. The default stroke is used for all edges. </li><li><i>style.strokewidth</i>: the width of node outlines and edges.</li><li><i>style.text</i>: text color used for node and edge labels.</li><li><i>style.font</i>: font used for node and edge labels.</li><li><i>style.fontsize</i>: fontsize for node and edge labels.</li><li><i>style.textwidth</i>: if the label 's width exceeds this number it gets wrapped to the next line.</li><li><i>style.align</i>: aligns the node label either RIGHT or CENTER.<br /> </li><li><i>style.depth</i>: True when this style uses the Colors library to render dropshadows.</li></ul><p> </p><span class="grey_box">Styleguide</span><p>You can assign the name of a style to <i>node.style</i> and then when the network is drawn the node will be visualized using the style's properties and drawing methods. </p><p>You can assign styles by hand - for example, here's how to make all nodes with a weight of more than 0.6 "important":</p><pre class="python"><span style="color: #530035;">for</span> node <span style="color: #530035;">in</span> graph.<span style="">nodes</span>:
<span style="color: #530035;">if</span> node.<span style="">weight</span> > <span style="">0.6</span>:
node.<span style="">style</span> = <span style="color: #ff0080;">"important"</span></pre></pre><p>Rules like these (<i>"heavy nodes are important"</i>) can also be bundled in the styleguide dictionary:</p><pre class="python">graph.<span style="">styles</span>.<span style="">guide</span>.<span style="">append</span><span style="">(</span><span style="color: #ff0080;">"important"</span>, <span style="color: #530035;">lambda</span> graph, node: node.<span style="">weight</span> > <span style="">0.6</span><span style="">)</span></pre></pre><p>The default rules in the guide are:</p><pre class="python"><span style="">{</span> <span style="color: #ff0080;">"light"</span> : <span style="color: #530035;">lambda</span> graph, node: graph.<span style="">root</span> <span style="color: #530035;">in</span> node.<span style="">links</span>
<span style="color: #ff0080;">"dark"</span> : <span style="color: #530035;">lambda</span> graph, node: <span style="">len</span><span style="">(</span>node.<span style="">links</span><span style="">)</span> > <span style="">4</span>
<span style="color: #ff0080;">"important"</span> : <span style="color: #530035;">lambda</span> graph, node: node.<span style="">weight</span> > <span style="">0.75</span>
<span style="color: #ff0080;">"root"</span> : <span style="color: #530035;">lambda</span> graph, node: node == graph.<span style="">root</span>
<span style="color: #ff0080;">"back"</span> : <span style="color: #530035;">lambda</span> graph, node: node == graph.<span style="">events</span>.<span style="">clicked</span>
<span style="">}</span></pre></pre><ul><li>nodes directly connected to the root get the light-style</li><li>nodes with four or more connections get the dark-style</li><li>nodes with a weight greater than 0.75 get the important-style</li><li>the root node gets the root-style</li><li>the node that was last clicked gets the back-style</li></ul><p>Below is another interesting rule that keeps clusters of nodes together. The edges of nodes that have only one connection become shorter, all others become longer. The default styleguide uses a simpler version.<br /> </p><pre class="python"><span style="color: #530035;">def</span> <span style='color:rgb(255,0,50)'>cluster</span><span style="">(</span>graph, node<span style="">)</span>:
<span style="color: #530035;">if</span> node == graph.<span style="">nodes</span><span style="">[</span><span style="">0</span><span style="">]</span>:
<span style="color: #530035;">for</span> e <span style="color: #530035;">in</span> graph.<span style="">edges</span>: e.<span style="">length</span> = <span style="">4.0</span>
<span style="color: #530035;">if</span> <span style="">len</span><span style="">(</span>node.<span style="">links</span><span style="">)</span> == <span style="">1</span>:
graph.<span style="">edge</span><span style="">(</span>node.<span style="">id</span>, node.<span style="">links</span><span style="">[</span><span style="">0</span><span style="">]</span>.<span style="">id</span><span style="">)</span>.<span style="">length</span> = <span style="">0.2</span>
graph.<span style="">styles</span>.<span style="">guide</span>.<span style="">append</span><span style="">(</span><span style="color: #ff0080;">"cluster"</span>, cluster<span style="">)</span></pre></pre><p>To apply the styling rules to the network:</p><pre class="python">graph.<span style="">styles</span>.<span style="">apply</span><span style="">(</span><span style="">)</span></pre></pre><p>There's a <i>graph.styles.guide.order</i> property (which is a list of style names) that defines the sequence in which style rules will be applied. There's also a <i>graph.styles.clear()</i> method to remove all the rules. </p><p> </p><p><span class="grey_box">Style drawing methods</span> </p><p>A <i>style</i> has customizable drawing methods. We will only go into this briefly here. Developers can check the source code in the <i>style.py</i> file in the library. Here's a quick example of how we add our own custom patch for edges:</p><table><tbody><tr><td><p><img src="/code/data/media/graph-monkeypatch.jpg" alt="graph-monkeypatch" /> </p></td><td><pre class="python"><span style="color: #530035;">def</span> <span style='color:rgb(255,0,50)'>curly_edge</span><span style="">(</span>style, path, edge, alpha=<span style="">1.0</span><span style="">)</span>:
path.<span style="color: #530035;">moveto</span><span style="">(</span>edge.<span style="">node1</span>.<span style="">x</span>, edge.<span style="">node1</span>.<span style="">y</span><span style="">)</span>
path.<span style="color: #530035;">curveto</span><span style="">(</span>
edge.<span style="">node1</span>.<span style="">x</span> - <span style="">40</span>,
edge.<span style="">node1</span>.<span style="">y</span>,
edge.<span style="">node2</span>.<span style="">x</span> + <span style="">40</span>,
edge.<span style="">node2</span>.<span style="">y</span>,
edge.<span style="">node2</span>.<span style="">x</span>,
edge.<span style="">node2</span>.<span style="">y</span>,
<span style="">)</span>
graph.<span style="">styles</span>.<span style="">default</span>.<span style="">edge</span> = curly_edge
graph.<span style="">draw</span><span style="">(</span><span style="">)</span></pre></pre></td></tr></tbody></table><p> </p><hr size="2" width="100%" /><h2><a title="interaction" name="interaction"></a>Interacting with the animated graph</h2><p>You can use very small graphs (<100 nodes) in an animation and watch them unfold fluidly. The <i>graph</i> object has functionality for mouse interaction as well, bundled in the <i>graph.events</i> object. It has the following properties:</p><ul><li><i>graph.events.hovered</i>: <i>None</i> or the node over which the mouse hovers. </li><li><i>graph.events.pressed</i>: <i>None</i> or the node on which the mouse is pressing down. </li><li><i>graph.events.dragged</i>: <i>None</i> or the node being dragged.<br /> </li><li><i>graph.events.clicked</i>: <i>None</i> or the last node clicked.<br /></li><li><i>graph.events.popup</i>: when <i>True</i>, will display a popup window over the hovered node.</li></ul><p> </p><table><tbody><tr><td><p><img src="/code/data/media/graph-hover.jpg" alt="graph-hover" /></p><p><img src="/code/data/media/graph-drag.jpg" alt="graph-drag" /></p></td><td><p>When you hover over a node the <i>graph.events.hover()</i> method fires. It will try to display a description of the node's id from WordNet (if you have the <a href="/code/Linguistics" target="_self">Linguistics</a> or <a href="/code/WordNet" target="_self">WordNet</a> library installed). To display your own popup text for a given node, register it in the <i>graph.events.popup_text</i> dictionary: </p><pre class="python">graph.<span style="">events</span>.<span style="">popup_text</span><span style="">[</span><span style="color: #ff0080;">"organism"</span><span style="">]</span> = <span style="color: #ff0080;">"hello"</span></pre></pre><p> In an animation you can also simply press down on a node and drag it around to where you want it. The graph will stabilize by itself.</p><p>Last but not least, if you click on a node <i>graph.events.click()</i> will fire. This method takes one <i>node</i> parameter and does nothing by default, so if you want clicking behavior you'll have to assign your own command:</p><pre class="python"><span style="color: #530035;">def</span> <span style='color:rgb(255,0,50)'>click</span><span style="">(</span>node<span style="">)</span>: <span style="color: #530035;">print</span> node.<span style="">id</span>+<span style="color: #ff0080;">" clicked"</span>
graph.<span style="">events</span>.<span style="">click</span> = click</pre></pre></td></tr></tbody></table><p> </p><hr size="2" width="100%" /><h2><a title="connectivity" name="connectivity"></a>Connectivity</h2><p>Finding out if two nodes are connected (with zero or more other nodes in between them) is easy enough with the <i>node.can_reach()</i> method, which returns either <i>True</i> or <i>False</i>:<br /></p><pre class="python">node.<span style="">can_reach</span><span style="">(</span>node, traversable: <span style="color: #530035;">lambda</span> node, edge: <span style="color: #530035;">True</span><span style="">)</span></pre></pre><p>What is intriguing about this method is the optional <i>traversable</i> parameter. You can pass it a custom command. This command takes two parameters, a node and an edge, and returns <i>True</i> if the given node is allowed to travel over the given edge. </p><p>This allows for more elaborate searches. For example, in the <a href="/code/Perception" target="_self">Perception</a> library all edges have a type, like <i>is-part-of</i> or <i>is-related-to</i>. Traversables are used to check if two nodes are connected using only specific types of edges: an oak is a tree only if the oak node can reach the tree node using only <i>is-a</i> edges (and not, for example, <i>is-property-of</i>). </p><p> </p><hr size="2" width="100%" /><h2><a title="proximity" name="proximity"></a>Proximity</h2><p>Graphs are not only useful to visualize data, but to analyze it as well. Knowing what the shortest path is, how to get from one node to another, can tell us something of how those nodes relate to each other.</p><p><a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" target="_self">Dijkstra's shortest path algorithm</a> is a way to find the closest route from one node to another in the network. For example, if the nodes in the network represent cities and their strength represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities. </p><pre class="python">graph.<span style="">shortest_path</span><span style="">(</span>id1, id2, heuristic=<span style="color: #530035;">None</span>, directed=<span style="color: #530035;">False</span><span style="">)</span></pre></pre><p>The <i>graph.shortest_path()</i> method returns a list of node id's connecting the two nodes with the given id's. If no connection can be found it will return <i>None</i>.</p><pre class="python">path = graph.<span style="">shortest_path</span><span style="">(</span><span style="">119</span>, <span style="">381</span><span style="">)</span>
graph.<span style="">draw</span><span style="">(</span>highlight=path, weighted=<span style="color: #530035;">True</span><span style="">)</span>
<span style="color: #530035;">print</span> path
>>> <span style="">[</span><span style="">119</span>, <span style="">383</span>, <span style="">478</span>, <span style="">78</span>, <span style="">381</span><span style="">]</span></pre></pre><p><img src="/code/data/media/graph-dijkstra.jpg" alt="graph-dijkstra" /></p><p>When searching for a shortest route the <b>edge weight</b> becomes important. Edges with a higher weight represent shorter routes. You can think of an edge with a weight of 1.0 as a highway and an edge with a weight of 0.0 as a mountain trail. So even if an edge looks longer onscreen (because it yields a nicer layout for example) it might still be a better candidate to travel by. Likewise, a straight connection may be abandoned in favor of a detour on heavier edges.</p><p>Optionally you can also supply your own <a href="http://en.wikipedia.org/wiki/Heuristic" target="_self">heuristic</a> function to tweak the pathfinder. It is a command that takes two node id's as its parameters and returns a number (usually between -1 and +1). The lower this number gets the more <i>interesting</i> the connection between the two nodes becomes. For example, in a game environment you could use edge weight to represent the quality of a road through the world, and supply heuristic terrain penalties for mountains, swamps, oceans - to discourage AI-controlled characters from trying to cross the ocean or walk through walls to reach an enemy. <br /></p><p> </p><p><span class="grey_box">Centrality</span> </p><p>How a node is connected to other nodes influences its importance in the network. The Graph library uses two measurements to determine a node's importance: <a href="http://en.wikipedia.org/wiki/Centrality" target="_self">betweenness centrality</a> and <a href="http://en.wikipedia.org/wiki/Centrality" target="_self">eigenvector centrality</a>. </p><ul><li><b>Betweenness centrality</b>: nodes that occur on many shortest paths have a higher betweenness. You can think of such nodes as being hubs, landmarks, city centers and so on. The betweenness centrality of a node is represented in the <i>node.traffic </i>property as a number between 0.0 and 1.0.<br /><br /></li></ul><ul><li><b>Eigenvector centrality</b>: nodes that (indirectly) connect to high-scoring nodes get a better score themselves. In this case the edge direction plays an important role. Ideally, everyone is pointing at you and you are pointing at no-one - meaning you are at the top of hierarchy. The eigenvector centrality is represented in the <i>node.weight </i>property as a number between 0.0 and 1.0. </li></ul><p> </p><table><tbody><tr><td><p><img src="/code/data/media/graph-centrality1.jpg" alt="graph-centrality1" /><br /><br /><img src="/code/data/media/graph-centrality2.jpg" alt="graph-centrality2" /><br /></p></td><td><p>Consider a node that has eight connections to other nodes. Consider another node that has three connections that each connect to two other nodes.</p><p>An initial naive estimate would be to say that the node in the first case is more important because it has eight connections. However, the node in the second case has the <b>potential</b> to influence up to nine other nodes, and therefore it has a higher importance in the network.</p><p>The king of a country has only his advisors as direct connections, but his influence is obviously much higher than a post office secretary in the same country who may have hundreds of direct connections with his clients.</p><p>Eigenvalue centrality is what Google's PageRank algorithm uses to rank web pages. </p><p>Read some more interesting details on the <a href="http://20bits.com/2007/11/02/graph-theory-part-iii-facebook/" target="_self">20bits blog</a>. </p></td></tr></tbody></table><p><br />The graph has two methods that return a list of nodes sorted according to traffic or weight:</p><pre class="python">graph.<span style="">nodes_by_traffic</span><span style="">(</span>threshold=<span style="">0.0</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">nodes_by_weight</span><span style="">(</span>threshold=<span style="">0.0</span><span style="">)</span></pre></pre><p>If you dynamically add new nodes to the graph the balance can shift and you may want to recalculate the proximity values:</p><pre class="python">graph.<span style="">betweenness_centrality</span><span style="">(</span>directed=<span style="color: #530035;">False</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">eigenvector_centrality</span><span style="">(</span><span style="">reversed</span>=<span style="color: #530035;">True</span>, rating=<span style="">{</span><span style="">}</span>,
start=<span style="color: #530035;">None</span>, iterations=<span style="">100</span>, tolerance=<span style="">0.0001</span><span style="">)</span></pre></pre><p>Both methods recalculate a node's traffic/weight property and return a dictionary of node id's linked to a value between 0.0 and 1.0. You may also notice the optional <i>rating</i> parameter which is a dictionary of node id's linked to a score to influence it's weight (e.g. Google not only examines a web page's connections but also its contents - the score of a page's content could be reflected in the <i>ranking</i> dictionary). </p><p> </p><hr size="2" width="100%" /><h2><a title="clustering" name="clustering"></a>Clustering</h2><p><a href="http://en.wikipedia.org/wiki/Cluster_analysis" target="_self">Clustering</a> means the classification of objects into <b>different groups</b>, so that all the objects in a group share some common traits (e.g. a <i>rabbit</i> and a <i>bird</i> both belong to the <i>animal</i> group). Clustering is in part related to how you organize your graph, and in part to what analysis you can then perform on the graph. The Graph library has some simple tools for cluster analysis.</p><pre class="python">graph.<span style="">nodes_by_category</span><span style="">(</span>name<span style="">)</span></pre></pre><p>The <i>graph.nodes_by_category()</i> method returns a list of all nodes that have their <i>category</i> property equal to the given name.</p><pre class="python">graph.<span style="">fringe</span><span style="">(</span>depth=<span style="">2</span><span style="">)</span></pre></pre><p>The <i>graph.fringe()</i> method returns a list of nodes on the perimeter of the graph. With a <i>depth</i> of 1 it returns all the leaf nodes, with a <i>depth</i> of 2 all the leaf nodes and nodes connected to leaf nodes, etc. </p><pre class="python">graph.<span style="">sub</span><span style="">(</span><span style="">id</span>, distance=<span style="">1</span><span style="">)</span></pre></pre><p>The <i>graph.sub()</i> method returns a new <i>graph</i> object that is a subset of the given graph. If <i>distance</i> is 0, it will contain only the node with the given <i>id</i>. If distance is 1, it will contain the node and all nodes directly connected to that node. If <i>distance</i> is 2, it will also contain all nodes that are connected to nodes directly connected to the given node, and so on. You can also supply a list of id's instead of a single id.<br /></p><p>Yet another way to create a subgraph is to pass a <b>filtering function</b> instead of an id. For example:</p><pre class="python">graph = <span style="color: #530035;">ximport</span><span style="">(</span><span style="color: #ff0080;">"graph"</span><span style="">)</span>
g = graph.<span style="">create</span><span style="">(</span>iterations=<span style="">500</span>, distance=<span style="">0.8</span><span style="">)</span>
g.<span style="">add_node</span><span style="">(</span><span style="color: #ff0080;">"NodeBox"</span><span style="">)</span>
g.<span style="">add_node</span><span style="">(</span><span style="color: #ff0080;">"Linguistics"</span>, category=<span style="color: #ff0080;">"library"</span><span style="">)</span>
g.<span style="">add_node</span><span style="">(</span><span style="color: #ff0080;">"WordNet"</span>, category=<span style="color: #ff0080;">"library"</span><span style="">)</span>
g.<span style="">add_edge</span><span style="">(</span><span style="color: #ff0080;">"Linguistics"</span>, <span style="color: #ff0080;">"NodeBox"</span>, label=<span style="color: #ff0080;">"related-to"</span><span style="">)</span>
g.<span style="">add_edge</span><span style="">(</span><span style="color: #ff0080;">"WordNet"</span>, <span style="color: #ff0080;">"NodeBox"</span>, label=<span style="color: #ff0080;">"related-to"</span><span style="">)</span>
g.<span style="">add_edge</span><span style="">(</span><span style="color: #ff0080;">"WordNet"</span>, <span style="color: #ff0080;">"Linguistics"</span>, label=<span style="color: #ff0080;">"part-of"</span><span style="">)</span>
<span style="color: grey;"># subgraph containing only library nodes:</span>
g = g.<span style="">sub</span><span style="">(</span><span style="color: #530035;">lambda</span> node: node.<span style="">category</span> == <span style="color: #ff0080;">"library"</span>, distance=<span style="">0</span><span style="">)</span>
g.<span style="">distance</span> = <span style="">1.4</span>
g.<span style="">solve</span><span style="">(</span><span style="">)</span>
g.<span style="">draw</span><span style="">(</span>directed=<span style="color: #530035;">True</span><span style="">)</span></pre></pre> <br /><p><img src="/code/data/media/graph-sub.jpg" alt="graph-sub" /></p><p><u>Note</u>: remember that if you want to draw a subgraph, you need to recalculate the layout with the <i>update()</i> or <i>solve()</i> method. </p><p> </p><p><span class="grey_box">Subgraph set theory</span> </p><p><a href="http://en.wikipedia.org/wiki/Set_theory" target="_self">Set theory</a> deals with union, difference and intersection operations between sets of elements. You can compare subgraphs to find out which nodes they have in common (<i>intersection</i>), which nodes they do not have in common (<i>difference</i>) or which is the combined set of both subgraphs (<i>union</i>).</p><ul><li><b>Union</b>: all elements from A and all elements from B.</li><li><b>Difference</b>: elements that appear in A but not in B.</li><li><b>Intersection</b>: elements that appear in A as well as in B.</li></ul><p>The following methods will return a new subgraph based on set operations:</p><pre class="python">graph1.<span style="">join</span><span style="">(</span>graph2<span style="">)</span> <span style="color: grey;"># union, graph1 | graph2 also works</span></pre></pre><pre class="python">graph1.<span style="">subtract</span><span style="">(</span>graph2<span style="">)</span> <span style="color: grey;"># difference, graph1 - graph2 also works</span></pre></pre><pre class="python">graph1.<span style="">intersect</span><span style="">(</span>graph2<span style="">)</span> <span style="color: grey;"># intersection, graph1 & graphs2 also works</span></pre></pre></p> <p><span class="grey_box">Cliques</span> <br /></p><p>In graph theory, a <a href="http://en.wikipedia.org/wiki/Clique_%28graph_theory%29" target="_self">clique</a> is a graph in which each node is connected to all the other nodes. There's a <i>graph.is_clique</i> property that returns <i>True</i> when the graph is complete. Since each node is connected to every other node in a complete graph, its <i>density</i> will be 1.0. </p><pre class="python">graph.<span style="">clique</span><span style="">(</span><span style="">id</span>, distance=<span style="">0</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">cliques</span><span style="">(</span><span style="">id</span>, threshold=<span style="">3</span>, distance=<span style="">0</span><span style="">)</span></pre></pre><p>The <i>graph.clique()</i> method returns a subgraph of the biggest clique around the node with the given <i>id</i>. It takes an optional <i>distance</i> parameter which will also include other nodes connected to the nodes in the clique (see the <i>distance</i> parameter for the <i>graph.sub()</i> method).</p><p>The <i>graph.cliques()</i> method returns a list of subgraphs that are cliques of at least <i>threshold</i> nodes.</p><p> </p><p><span class="grey_box">Partitioning</span> </p><p>Finally, there's a powerful technique to split a graph into its <b>unconnected subgraphs.</b> Sometimes your graph may contain two or more clusters of nodes without connections between them (especially if you don't know where the data came from). The <i>graph.split()</i> method will return a list of unconnected subgraphs, sorted biggest-first:</p><pre class="python">subgraphs = graph.<span style="">split</span><span style="">(</span><span style="">)</span>
subgraphs<span style="">[</span><span style="">0</span><span style="">]</span>.<span style="">solve</span><span style="">(</span><span style="">)</span>
subgraphs<span style="">[</span><span style="">0</span><span style="">]</span>.<span style="">draw</span><span style="">(</span><span style="">)</span></pre></pre></p> <hr size="2" width="100%" /><a title="issues" name="issues"></a><h2>Known issues and limitations </h2><p>Exporting a graph as a PDF may crash NodeBox on some systems. <br />Disabling dropshadow and gradient effects should remedy this:</p><pre class="python">g = graph.<span style="">create</span><span style="">(</span>depth=<span style="color: #530035;">False</span><span style="">)</span></pre></pre>
</div>
</div>
<div id="footer">
Last modified: Dec 10 2009 | © 2004-2012 <a href="http://www.emrg.be/" class="noexternal">Experimental Media Research Group</a>
</div>
<img src="/code/g/footer.jpg" style="border:0" class="footer" width="800" height="334" />
</div>
<script>
try{e=document.getElementsByTagName("span");for(i=0;i<e.length;i++){if(e[i].className=="header_image"){src=e[i].getElementsByTagName("img")[0].src;document.getElementById("header_image").src=src;break;}}}catch(e){}
</script>
</body>
</html>