-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathBoost_Graph.html
More file actions
107 lines (86 loc) · 16.7 KB
/
Copy pathBoost_Graph.html
File metadata and controls
107 lines (86 loc) · 16.7 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
<html>
<head>
<title>NodeBox | Boost 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, Boost Graph" />
<link rel="canonical" href="https://www.nodebox.net/code/Boost_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>Boost 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>The Boost Graph library is a comprehensible wrapper for the graph functionalities in <a href="http://www.boost.org/libs/graph/doc/">Boost</a>. Boost is a large C++ project with various useful libraries. The library offers the Boost graphing functions for small networks to people that are used to NodeBox code. The library is bundled with the BGL code files.</p> <p>Also see the <a href="/code/Graphing">Graphing</a> example in the Gallery for more information.</p><p><span class="pink_text">Does not work on NodeBox 1.9.2 or up, we recommend the newer <a href="/code/Graph" target="_self">Graph</a> library.</span><br /></p> <h2>Download</h2> <table border="0"><tbody><tr><td><img src="/code/data/media/download.gif" alt="download" /></td><td><a href="https://nodebox.s3.amazonaws.com/code/data/media/boostgraph-ppc.zip" target="_self">PowerPC</a> |<a href="https://nodebox.s3.amazonaws.com/code/data/media/boostgraph-intel.zip" target="_self">Intel</a> (1.5MB) <br /> <i>Last updated for NodeBox 1.9.1.1<br /></i><i>Author: Tom De Smedt<br /></i></td></tr></tbody></table><h2>Documentation </h2><ul><li><a href="Boost_Graph.html#loading_the_library" target="_self">How to get the library up and running</a></li><li><a href="Boost_Graph.html#create" target="_self">Creating a network of connected nodes</a></li><li><a href="Boost_Graph.html#visualize" target="_self">Visualizing the graph network</a></li><li><a href="Boost_Graph.html#analyze" target="_self">Analyzing the graph network</a></li><li><a href="Boost_Graph.html#customize" target="_self">Customizing the look and feel of a graph network</a><br /></li></ul> <p> </p><p> <span class="image_border"><img src="/code/data/media/graph3.jpg" alt="graph3" /></span></p><p> </p> <hr /> <p><a name="loading_the_library" title="loading_the_library"></a></p> <h2>How to get the library up and running</h2> <p>Put the <i>boostgraph</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">boostgraph = <span style="color: #530035;">ximport</span><span style="">(</span><span style="color: #ff0080;">"boostgraph"</span><span style="">)</span></pre></pre><p class="small_text">Note: you will see a file named <i>libboost_python.dylib</i> appear in the folder from which you are running your script. The graph library needs this file to operate properly.</p><p> </p> <hr /><h2><a name="create" title="create"></a>Creating a network of connected nodes </h2><pre class="python">create<span style="">(</span>x, y, w, h, style=<span style="color: #ff0080;">"default"</span><span style="">)</span></pre></pre><p>The <i>create()</i> command returns a new <i>Graph</i> object encompassing the area starting at position <i>x</i>, <i>y </i>and having width <i>w</i> and height <i>h</i>. With the optional <i>style</i> parameter you can control the visual look of the graph. You can supply the name of style stored in the <i>/styles</i> subfolder as a string, or your own customized <i>Style</i> object.</p><p>The returned <i>Graph</i> object has the following properties:</p><ul><li><i>graph.nodes</i>: a list of all <i>Node</i> objects in the graph.</li><li><i>graph.style</i>: the <i>Style</i> object describing the visual style of the graph. </li></ul><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. You can connect two nodes with the <i>graph.add_edge()</i> method:<br /></p><pre class="python">graph.<span style="">add_node</span><span style="">(</span><span style="">id</span>, <span style="">type</span>=<span style="color: #530035;">None</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">add_edge</span><span style="">(</span>id1, id2<span style="">)</span></pre></pre><p>The <i>id</i> parameters are string labels which <b>uniquely</b> identify each node. They will appear as labels on each node once the graph is visualized.<br /></p><p>You can retrieve a <i>Node</i> object from the graph with the <i>graph.find()</i> method: </p><pre class="python">graph.<span style="">find</span><span style="">(</span><span style="">id</span><span style="">)</span></pre></pre><p>A <i>Node</i> object has number of useful properties:</p><ul><li><i>node.id</i>: the unique label for a node.</li><li><i>node.type</i>: a style type from the <i>Style.colors</i> dictionary.<br /></li><li><i>node.edge_from</i>: a list of <i>Node</i> objects that link to this node.</li><li><i>node.edge_to</i>: a list of <i>Node</i> objects this node links to.</li><li><i>node.edges</i>: all of the <i>Node</i> objects this node is connected to. </li><li><i>node.strength</i>: the relevance of this node in the entire graph.</li><li><i>node.bounds:</i> a (left, top, right, bottom)-tuple with the node's coordinates.</li></ul><p> </p><hr /><h2><a name="visualize" title="visualize"></a>Visualizing the graph network</h2><p>A graph has four useful methods during visualization:</p><pre class="python">graph.<span style="">trim</span><span style="">(</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">solve</span><span style="">(</span>k=<span style="">10</span>, overlapping=<span style="">0.1</span>, layout=<span style="color: #ff0080;">"spring"</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">center</span><span style="">(</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">draw</span><span style="">(</span>orphans=<span style="color: #530035;">False</span>, centroid=<span style="color: #530035;">True</span>, clusters=<span style="color: #530035;">True</span><span style="">)</span></pre></pre><p>The <i>graph.trim()</i> method removes orphaned nodes that have no connections from the network. This speeds up calculations and simplifies the visualization. It's a good idea to trim the network before you solve it.</p><p>The <i>graph.solve()</i> method does all the math. It assigns an x and y position to each node, and a strength based on the <a href="http://en.wikipedia.org/wiki/Betweenness_centrality" target="_self">betweenness centrality</a>. The <i>k</i> parameter controls the amount of space between nodes, less <i>k</i> makes the graph tighter. The <i>overlapping</i> parameter controls the percentage of nodes that are allowed to overlap each other. Allowing more overlapping is faster but looks less nice. <b>You always need to solve the network first before you can visualize or analyze it</b>. The <i>layout</i> parameter determines what the graph will look like. You can use either "<i>spring</i>" (for Fruchterman-Reingold spring graph layout) or "<i>circle</i>". </p><p>The <i>graph.center()</i> method ensures that the most important part of the network is displayed centrally in the graph area. </p><p>The <i>graph.draw()</i> method visualizes the network on the canvas. The <i>orphans</i> parameter controls if orphaned nodes are drawn, the <i>centroid</i> and <i>clusters</i> parameters control whether important parts in the network will be accented (e.g. the centroid of the graph and tight groups of strong nodes respectively).</p><p> </p><hr /><h2><a name="analyze" title="analyze"></a>Analyzing the graph network</h2><p>A graph is not only useful as a visualisation, but also to analyze the connections between the nodes. The <i>Graph</i> object has methods to discern pathways between nodes and important nodes that get a lot of traffic:</p><pre class="python">graph.<span style="">shortest_paths</span><span style="">(</span><span style="">id</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">shortest_path</span><span style="">(</span>id1, id2<span style="">)</span></pre></pre><pre class="python">graph.<span style="">draw_path</span><span style="">(</span>path<span style="">)</span></pre></pre><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 to get 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><p>The <i>graph.shortest_paths()</i> method returns a dictionary of node id's. Each of these id's links to a list of <i>Node</i> objects. These lists are the shortest path between the id you supplied and each of the keys in the dictionary.</p><p>The <i>graph.shortest_path()</i> method simply returns one list of <i>Node</i> objects connecting <i>id1</i> to <i>id2</i>. </p><p>You can visualize a path with the <i>graph.draw_path(path)</i> method.</p><pre class="python">graph.<span style="">strongest_nodes</span><span style="">(</span>treshold=<span style="">0.0</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">centroid</span><span style="">(</span><span style="">)</span></pre></pre><pre class="python">graph.<span style="">hub_nodes</span><span style="">(</span>top=<span style="">3</span><span style="">)</span></pre></pre><p>The <i>graph.strongest_nodes()</i> method sorts all the nodes (strongest-first) in the network according to their strength. A list of Node objects is returned. The optional <i>treshold</i> parameter defines the minimum strength a node needs to get in the list.</p><p>The <i>graph.centroid()</i> returns an (x, y)-tuple that is the focus point in the network. This is the average point between the strongest nodes. </p><p>The <i>graph.hub_nodes()</i> returns a list of <i>Node</i> objects nearest to the graph's centroid. These nodes are not necessarily ranked high in <i>graph.strongest_nodes()</i>, however they are likely to occur frequently in longer paths because they connect to a lot of strong nodes.</p><p> </p><hr /><h2><a name="customize" title="customize"></a>Customizing the look and feel of a graph network</h2> <p>The <i>graph.style</i> property contains a <i>Style</i> object with settings for the visualization of the graph. You can create a new style from scratch with the <i>style()</i> command:</p><pre class="python">style<span style="">(</span>name=<span style="color: #ff0080;">"default"</span><span style="">)</span></pre></pre><p>This returns the <i>Style</i> with the given name. Look inside the <i>/styles</i> subfolder to see what names are available. </p><p>A <i>Style</i> object has the following properties that control how a graph looks:</p><ul><li><i>style.font</i>: the font used to display node labels.</li><li><i>style.fontsize</i>: the font size for node labels.</li><li><i>style.background</i>: the path to a background image for the graph network.</li><li><i>style.gradient</i>: the path to a gradient background image.</li><li><i>style.colors</i>: a dictionary of node colors. You can use each key in the dictionary as <i>type</i> parameter in the <i>graph.add_node()</i> method.</li></ul><p>The <i>style.colors</i> dictionary has the following default keys:</p><ul><li><i>style.CLUSTER</i>: the color used to mark clusters of strong nodes</li><li><i>style.EDGE</i>: the color used for connections between nodes</li><li><i>style.PATH</i>: the color used by <i>graph.draw_path() </i>- i.e. to mark shortest paths. <br /></li><li>"light": a light blue <a href="/code/Reference_|_color()" target="_self">color</a>.<br /></li><li>"dark": a dark blue color.</li><li>"blue": a bright blue color.<br /></li><li>"green": a green color.<br /></li></ul><p> </p><p>The following script shows how you can assign colors to different types of nodes. Nodes with only one connection get the "light" color, nodes with more colors the "dark" color and strong nodes the bright "blue" color. Transit nodes are colored in "green":</p><pre class="python">strongest = g.<span style="">strongest_nodes</span><span style="">(</span><span style="">)</span>
hubs = g.<span style="">hub_nodes</span><span style="">(</span><span style="">)</span>
<span style="color: #530035;">for</span> node <span style="color: #530035;">in</span> g.<span style="">nodes</span>:
node.<span style="">type</span> = <span style="color: #ff0080;">"light"</span>
<span style="color: #530035;">if</span> <span style="">len</span><span style="">(</span>node.<span style="">edges</span><span style="">)</span> > <span style="">1</span>: node.<span style="">type</span> = <span style="color: #ff0080;">"dark"</span>
<span style="color: #530035;">if</span> node <span style="color: #530035;">in</span> strongest<span style="">[</span>:<span style="">6</span><span style="">]</span>: node.<span style="">type</span> = <span style="color: #ff0080;">"blue"</span>
<span style="color: #530035;">if</span> node <span style="color: #530035;">in</span> hubs: node.<span style="">type</span> = <span style="color: #ff0080;">"green"</span></pre></pre><p>Note: you need to set the graph's font and fontsize before you add nodes to the graph. When you add a new node it's size is calculated according to the current font and fontsize. </p> <p> </p>
</div>
</div>
<div id="footer">
Last modified: Jan 10 2008 | © 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>