NodeBox | Graph

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.

Central concepts in graph theory are:

Node: a block of information in the network.
Edge: a connection between two nodes (can have a direction and a weight).
Centrality: determining the relative importance of a node.
Clustering: partitioning nodes into groups.

The NodeBox Graph library includes algorithms from NetworkX for betweenness centrality and eigenvector centrality, Connelly Barnes' implementation of Dijksta shortest paths (here) and the spring layout for JavaScript by Aslak Hellesoy and Dave Hoover (here). The goal of this library is visualization of small graphs (<200 elements), if you need something more robust we recommend using NetworkX.

For those of you looking for the old Graph library built on Boost, it can still be found here.

Download

graph.zip (32KB)
Last updated for NodeBox 1.9.5.6
Licensed under GPL
Author: Tom De Smedt

Documentation

graph-wordnet

The library has a cool example of a visual browser for WordNet.

How to get the library up and running

Put the graph 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/.

graph = ximport("graph")

Outside of NodeBox you can also just do import graph.

Creating a graph

create(iterations=1000, distance=1.0, layout="spring", depth=True)

The create() command returns a new graph object encompassing the drawing canvas. The network of connected nodes will originate from the center of the canvas. The distance parameter controls the spacing between nodes and hence the size of the graph.

By default, a spring force layout is used to visualize the graph. Each element in the graph (or node) will try to get away as far as possible from the others. This is the repulsive force in the network. At the same time, there are connections (or edges) that keep nodes together. The greater the weight of an edge the stronger it is in pulling two nodes together. This is the attractive force in the network. You can also set the layout parameter to "circle" to use a simple circle-based layout.

The forces in the network need to be calculated several times in order for the nodes' positions to stabilize. The higher the number of iterations the better (but slower) the layout.

When depth is set to True, the library will attempt to import the NodeBox Colors library for gradient and shadow effects.

The returned graph object has the following properties:

graph.nodes: a list of all the node objects in the graph.
graph.edges: a list of all the edge objects in the graph.
graph.leaves: a list of all the nodes with only one connection.
graph.root: the root node in the graph.
graph.done: True when the graph's layout is completely calculated.
graph.distance: the scale of the graph when drawn (usually a number between 0.5 and 2.0).

graph.density: a number between 0.0 and 1.0 indicating the number of connections.
graph.is_sparse: True when there are few connections in the graph (density is 0.35 or less).
graph.is_dense: True when there are a lot of connections (density is 0.65 or more).
graph.is_complete: True when all nodes are connected to all other nodes (density is 1.0).

graph.layout: the layout object used to calculate the graph.
graph.events: the event object used to monitor mouse dragging and clicking.
graph.styles: the styles object used to colorize and draw the graph.

Adding nodes and edges

graph.add_node(id, radius=8, style="default", category="", root=False)

graph.add_edge(id1, id2, weight=0.0, length=1.0, label="")

You can add nodes (e.g. blocks of information you want to connect) to the graph with the graph.add_node() method. The id parameter uniquely identifies each node, it will appear as a label on each node once the graph is visualized. When the root parameter is True it will set this node as the graph's root.

The graph.add_node() method returns a node object with the following properties:

node.id: the node's unique id.
node.r: the node's radius.
node.style: the name of the style used to colorize and draw the node.
node.category: a category this node belongs to.
node.label: displayed when the node is drawn (by default, its id).
node.x: the horizontal position of the node on the canvas.
node.y: the vertical position of the node on the canvas.

node.links: a list of all node objects connected to this one.
node.edges: a list of all edge objects this node is involved with.
node.is_leaf: True when the node has only one connection.

node.weight: a number between 0.0 and 1.0 reflecting the node's relevance in the graph.
node.traffic: a number between 0.0 and 1.0 reflecting the amount of shortest paths.
node.eigenvalue: identical to node.weight.
node.betweenness:identical to node.traffic.

We'll look at the details of a node's weight and traffic in the section on graph proximity.

You can connect two nodes with the graph.add_edge() method. It takes two node id's, an optional weight (ranging between 0.0 and 1.0) and an optional label to display near the edge when it is drawn.

An edge object is returned. It has the following properties:

edge.node1: the node object from which the connection originates.
edge.node2: the node object in which the connection ends.
edge.weight: the weight or strength of the connection.
edge.length: the individual length of the edge (1.0 by default).
edge.label: a label to display near the edge when drawn.

graph-create

graph =  ximport("graph")
g = graph.create(iterations=500, distance=0.8)
g.add_node("NodeBox")
g.add_node("Core Image", category="library")
g.add_edge("Core Image", "NodeBox")
g.solve()
g.