NodeBox | Boost Graph

Boost Graph

Description

In mathematics and computer science, graph theory 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.

The Boost Graph library is a comprehensible wrapper for the graph functionalities in Boost. 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.

Also see the Graphing example in the Gallery for more information.

Does not work on NodeBox 1.9.2 or up, we recommend the newer Graph library.

Download

PowerPC |Intel (1.5MB)
Last updated for NodeBox 1.9.1.1
Author: Tom De Smedt

Documentation

graph3

How to get the library up and running

Put the boostgraph library folder in the same folder as your script so NodeBox can find the library. You can also put it in ~/Library/Application Support/NodeBox/.

boostgraph = ximport("boostgraph")

Note: you will see a file named libboost_python.dylib appear in the folder from which you are running your script. The graph library needs this file to operate properly.

Creating a network of connected nodes

create(x, y, w, h, style="default")

The create() command returns a new Graph object encompassing the area starting at position x, y and having width w and height h. With the optional style parameter you can control the visual look of the graph. You can supply the name of style stored in the /styles subfolder as a string, or your own customized Style object.

The returned Graph object has the following properties:

graph.nodes: a list of all Node objects in the graph.
graph.style: the Style object describing the visual style of the graph.

You can add nodes (e.g. blocks of information you want to connect) to the graph with the graph.add_node() method. You can connect two nodes with the graph.add_edge() method:

graph.add_node(id, type=None)

graph.add_edge(id1, id2)

The id parameters are string labels which uniquely identify each node. They will appear as labels on each node once the graph is visualized.

You can retrieve a Node object from the graph with the graph.find() method:

graph.find(id)

A Node object has number of useful properties:

node.id: the unique label for a node.
node.type: a style type from the Style.colors dictionary.
node.edge_from: a list of Node objects that link to this node.
node.edge_to: a list of Node objects this node links to.
node.edges: all of the Node objects this node is connected to.
node.strength: the relevance of this node in the entire graph.
node.bounds: a (left, top, right, bottom)-tuple with the node's coordinates.

Visualizing the graph network

A graph has four useful methods during visualization:

graph.trim()

graph.solve(k=10, overlapping=0.1, layout="spring")

graph.center()

graph.draw(orphans=False, centroid=True, clusters=True)

The graph.trim() 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.

The graph.solve() method does all the math. It assigns an x and y position to each node, and a strength based on the betweenness centrality. The k parameter controls the amount of space between nodes, less k makes the graph tighter. The overlapping parameter controls the percentage of nodes that are allowed to overlap each other. Allowing more overlapping is faster but looks less nice. You always need to solve the network first before you can visualize or analyze it. The layout parameter determines what the graph will look like. You can use either "spring" (for Fruchterman-Reingold spring graph layout) or "circle".

The graph.center() method ensures that the most important part of the network is displayed centrally in the graph area.

The graph.draw() method visualizes the network on the canvas. The orphans parameter controls if orphaned nodes are drawn, the centroid and clusters 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).

Analyzing the graph network

A graph is not only useful as a visualisation, but also to analyze the connections between the nodes. The Graph object has methods to discern pathways between nodes and important nodes that get a lot of traffic:

graph.shortest_paths(id)

graph.shortest_path(id1, id2)

graph.draw_path(path)

Dijkstra's shortest path algorithm 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.

The graph.shortest_paths() method returns a dictionary of node id's. Each of these id's links to a list of Node objects. These lists are the shortest path between the id you supplied and each of the keys in the dictionary.

The graph.shortest_path() method simply returns one list of Node objects connecting id1 to id2.

You can visualize a path with the graph.draw_path(path) method.

graph.strongest_nodes(treshold=0.0)

graph.centroid()

graph.hub_nodes(top=3)

The graph.strongest_nodes() method sorts all the nodes (strongest-first) in the network according to their strength. A list of Node objects is returned. The optional treshold parameter defines the minimum strength a node needs to get in the list.

The graph.centroid() returns an (x, y)-tuple that is the focus point in the network. This is the average point between the strongest nodes.

The graph.hub_nodes() returns a list of Node objects nearest to the graph's centroid. These nodes are not necessarily ranked high in graph.strongest_nodes(), however they are likely to occur frequently in longer paths because they connect to a lot of strong nodes.

Customizing the look and feel of a graph network

The graph.style property contains a Style object with settings for the visualization of the graph. You can create a new style from scratch with the style() command:

style(name="default")

This returns the Style with the given name. Look inside the /styles subfolder to see what names are available.

A Style object has the following properties that control how a graph looks:

style.font: the font used to display node labels.
style.fontsize: the font size for node labels.
style.background: the path to a background image for the graph network.
style.gradient: the path to a gradient background image.
style.colors: a dictionary of node colors. You can use each key in the dictionary as type parameter in the graph.add_node() method.

The style.colors dictionary has the following default keys:

style.CLUSTER: the color used to mark clusters of strong nodes
style.EDGE: the color used for connections between nodes
style.PATH: the color used by graph.draw_path() - i.e. to mark shortest paths.
"light": a light blue color.
"dark": a dark blue color.
"blue": a bright blue color.
"green": a green color.

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":

strongest = g.strongest_nodes()
hubs = g.hub_nodes()
for node in g.nodes:
    node.type = "light"
    if len(node.edges) > 1: node.type = "dark"
    if node in strongest[:6]: node.type = "blue"
    if node in hubs: node.type = "green"

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.