Framework's Actionscript 3.0 Graph Data Structure

Constellation Framework has two classes for storing a graph: Graph and LinkedGraph. The difference between the two is the Graph class doesn't store node-to-edge or edge-to-node references so finding a node's neighbors requires a lookup.

The LinkedGraph class does store references so operations like finding a node's edges or retrieving a tree can be done more efficiently.

Both classes implement the IGraph interface but for the most part you will probably be using instances of LinkedGraph.

Basic Graph Data Manipulation

Here are some examples for changing and retrieving the contents of a graph. Adding nodes and edges

var g:LinkedGraph = new LinkedGraph();
 
// add a node with ID "n1"
var nodeID:String = "n1";
var nodeData:Object = {label: 'Node 1', value: 42};
var node1:INode =
  g.addNode(nodeID, nodeData);
 
// add a node with ID "n2"
var node2:INode =
  g.addNode("n2", {label: 'Node 2', value: 8});
 
// add an edge with ID "e1"
var edgeData:Object = {relationship:'containment'};
var e1:IEdge =
  g.addEdge("e1", "n1", "n2", edgeData);

// this statement will print "2"
trace(g.nodeLength);
 
// this statement will print "1"
trace(g.edgeLength);
 
// this statement will print "true"
trace(g.hasEdge("e1"));

//var node2:INode =
//  g.addNode("n2", {label: 'Node 2', value: 8});
 
node2 = g.getNodeByID("n2");
node2 = g.getNodeByDataProperty("value", 8);

//var edgeData:Object = {relationship:'containment'};
//var e1:IEdge =
//  g.addEdge("e1", "n1", "n2", edgeData);
 
e1 = g.getEdgeByID("e1");
e1 = g.getEdgeByDataProperty("relationship",
  "containment");
 
e1 = g.getEdgeByTailNodeID("n1");
e1 = g.getEdgeByHeadNodeID("n2");
 
e1 = g.getEdgeByNodeIDs("n1", "n2");
 
// note that the order must be tail then head node.
// the following returns null:
g.getEdgeByNodeIDs("n2", "n1");

The following examples show how to make use of the LinkedNode and LinkedEdge classes.

var lnode1:LinkedNode = node1 as LinkedNode;
 
// this prints "n1"
trace(lnode1.id);
 
// this prints "Node 1"
trace(lnode1.data.label);
 
// the number of edges related to this node, 1
trace(lnode1.degree);
 
// the following statement prints "true"
trace(lnode1.isLeaf);
 
// the following prints "e1"
trace(lnode1.edges[0].id);
 
// the following prints "n2"
var neighborNodes:Array = lnode1.getNeighborNodes();
trace(neighborNodes[0].id);
 
// the following prints true
trace(lnode1.hasNeighbor("n2"));

var ledge1:LinkedEdge = edge1 as LinkedEdge;
 
// the following statement prints "e1"
trace(ledge1.id);
 
// this statement prints "containment"
trace(ledge1.data.relationship);
 
// prints "n1 --> n2"
trace(ledge1.tailNodeID + " --> "
  + ledge1.headNodeID);
 
// this prints 'Node 2'
trace(ledge1.headNode.data.label);
 
// get a reference to the other node in an edge
node2 = ledge1.getOtherNode(node1);

// this would throw an error because the node is
// still connected to an edge.  the edge must be
// removed first
//g.removeNode(node1);
 
g.removeEdge(edge1);
g.removeNode(node1);
 
g.clear();

Graph Operations

These methods are used for more complex operations on a graph data structure.

LinkedGraph.getConnectedGraphs()

var graphs:Array = graph.getConnectedGraphs();
 
if (graphs.length > 1)
{
  var g:Graph = graphs[1];
 
  // print out the size of this graph
  trace(g.nodeLength + ' ' + g.edgeLength);
}

This method will break up a graph into its connected graphs.

A graph is connected when every node can be reached by starting at any other node and traversing the graph's edges. A simple graph with two nodes connected by an edge is connected whereas two nodes with no edges is not.

This method returns each connected graph as a separate element in an array. Orphan nodes would be returned as the only item in their graph. If this method is called on a connected graph, only one graph matching the original is returned.

LinkedNode.getPathToNode()

var appleNode:LinkedNode =
  foodGraph.getNodeByID("apple") as LinkedNode;
var shrimpNode:LinkedNode =
  foodGraph.getNodeByID("shrimp") as LinkedNode;
 
var path:Graph = appleNode.getPathToNode(shrimpNode);

This method fetches a new graph data structure containing all the nodes and edges which constitute the shortest path between two nodes.

LinkedNode.getTree()

var pinophytaNode:LinkedNode =
  plantGraph.getNodeByID('Pinophyta');
 
// fetches the pinophyta node, its neighbors, their
// neighbors, and any edges connecting those nodes
var tree:Graph = pinophytaNode.getTree(3);

The getTree() method fetches a new graph containing all the nodes within a certain number of hops from a particular node. The returned graph also contains any edges that relate those nodes.

The depth parameter controls the number of layers of nodes that are retrieved. For example, calling the method with a depth of 1 returns a graph containing only the given node. Using a depth of 2 returns the given node and its neighbors. A depth of 3 fetches the given node, its neighbors, and their neighbors.