Graph |
A linked uni-directional weighted graph structure.
The Graph class manages all graph nodes. Each graph node has an array of arcs, pointing to different nodes.
Graph | A linked uni-directional weighted graph structure. |
Variables | |
nodes | The graph’s nodes. |
Functions and Properties | |
Graph | Creates an empty graph. |
maxSize | The number of nodes the graph can store. |
depthFirst | Performs an iterative depth-first traversal starting at a given node. |
breadthFirst | Performs a breadth-first traversal starting at a given node. |
addNode | Adds a node at a given index to the graph. |
removeNode | Removes a node from the graph at a given index. |
getArc | Finds an arc pointing to the node at the ‘from’ index to the node at the ‘to’ index. |
addArc | Adds an arc pointing to the node located at the ‘from’ index to the node at the ‘to’ index. |
removeArc | Removes an arc pointing to the node located at the ‘from’ index to the node at the ‘to’ index. |
clearMarks | Marks are used to keep track of the nodes that have been visited during a depth-first or breadth-first traversal. |
contains | @inheritDoc |
clear | @inheritDoc |
getIterator | @inheritDoc |
size | @inheritDoc |
isEmpty | @inheritDoc |
toArray | @inheritDoc |
public function depthFirst( node: GraphNode, visit: Function ):void
Performs an iterative depth-first traversal starting at a given node. @example The following code shows an example callback function. The graph traversal runs until the value ‘5’ is found in the data property of a node instance. <listing version=”3.0”> var visitNode:Function = function(node:GraphNode):Boolean { if (node.data == 5) return false; //terminate traversal return true; } myGraph.depthFirst(graph.nodes[0], visitNode); </listing>
node | The graph node at which the traversal starts. |
visit | A callback function which is invoked every time a node is visited. The visited node is accessible through the function’s first argument. You can terminate the traversal by returning false in the callback function. |
public function breadthFirst( node: GraphNode, visit: Function ):void
Performs a breadth-first traversal starting at a given node. @example The following code shows an example callback function. The graph traversal runs until the value ‘5’ is found in the data property of a node instance. <listing version=”3.0”> var visitNode:Function = function(node:GraphNode):Boolean { if (node.data == 5) return false; //terminate traversal return true; } myGraph.breadthFirst(graph.nodes[0], visitNode); </listing>
node | The graph node at which the traversal starts. |
visit | A callback function which is invoked every time a node is visited. The visited node is accessible through the function’s first argument. You can terminate the traversal by returning false in the callback function. |
public function addArc( from: int, to: int, weight: int = 1 ):Boolean
Adds an arc pointing to the node located at the ‘from’ index to the node at the ‘to’ index.
from | The originating graph node index. |
to | The ending graph node index. |
weight | The arc’s weight |
True if the arc was added, otherwise false.
The graph’s nodes.
public var nodes: Array
Creates an empty graph.
public function Graph( size: int )
The number of nodes the graph can store.
public function get maxSize():int
Performs an iterative depth-first traversal starting at a given node.
public function depthFirst( node: GraphNode, visit: Function ):void
Performs a breadth-first traversal starting at a given node.
public function breadthFirst( node: GraphNode, visit: Function ):void
Adds a node at a given index to the graph.
public function addNode( obj: *, i: int ):Boolean
Removes a node from the graph at a given index.
public function removeNode( i: int ):Boolean
Finds an arc pointing to the node at the ‘from’ index to the node at the ‘to’ index.
public function getArc( from: int, to: int ):GraphArc
Adds an arc pointing to the node located at the ‘from’ index to the node at the ‘to’ index.
public function addArc( from: int, to: int, weight: int = 1 ):Boolean
Removes an arc pointing to the node located at the ‘from’ index to the node at the ‘to’ index.
public function removeArc( from: int, to: int ):Boolean
Marks are used to keep track of the nodes that have been visited during a depth-first or breadth-first traversal.
public function clearMarks():void
@inheritDoc
public function contains( obj: * ):Boolean
@inheritDoc
public function clear():void
@inheritDoc
public function getIterator():Iterator
@inheritDoc
public function get size():int
@inheritDoc
public function isEmpty():Boolean
@inheritDoc
public function toArray():Array