GODPAPER | All Packages | All Classes | Index | Frames No Frames |
Graph

Package | de.polygonal.ds
Class | public class Graph
Inheritance | Graph Object
Implements | Collection

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.

Public Properties

| Property | Defined By
--- | --- | ---
|  | maxSize : int [read-only] The number of nodes the graph can store. | Graph
|  | nodes : Array The graph's nodes. | Graph
|  | size : int [read-only] The total number of items. | Graph

Public Methods

| Method | Defined By
--- | --- | ---
|  | Graph(size:int) Creates an empty graph. | Graph
|  | 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. | Graph
|  | addNode(obj:*, i:int):Boolean Adds a node at a given index to the graph. | Graph
|  | breadthFirst(node:GraphNode, visit:Function):void Performs a breadth-first traversal starting at a given node. | Graph
|  | clear():void Clears all items. | Graph
|  | clearMarks():void Marks are used to keep track of the nodes that have been visited during a depth-first or breadth-first traversal. | Graph
|  | contains(obj:*):Boolean Determines if the collection contains a given item. | Graph
|  | depthFirst(node:GraphNode, visit:Function):void Performs an iterative depth-first traversal starting at a given node. | Graph
|  | getArc(from:int, to:int):GraphArc Finds an arc pointing to the node at the 'from' index to the node at the 'to' index. | Graph
|  | getIterator():Iterator Initializes an iterator object pointing to the first item in the collection. | Graph
|  | isEmpty():Boolean Checks if the collection is empty. | Graph
|  | removeArc(from:int, to:int):Boolean Removes an arc pointing to the node located at the 'from' index to the node at the 'to' index. | Graph
|  | removeNode(i:int):Boolean Removes a node from the graph at a given index. | Graph
|  | toArray():Array Converts the collection into an array. | Graph

Property Detail

maxSize | property

`maxSize:int` [read-only]

The number of nodes the graph can store.

Implementation
`public function get maxSize():int`

nodes | property |

`public var nodes:Array`

The graph's nodes.

size | property |

`size:int` [read-only]

The total number of items.

Implementation
`public function get size():int`
Constructor Detail

Graph | () | Constructor

`public function Graph(size:int)`

Creates an empty graph.

Parameters

| `size:int` — The total number of nodes the graph can hold.

Method Detail

addArc | () | method

`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.

Parameters

| `from:int` — The originating graph node index.
| `to:int` — The ending graph node index.
| `weight:int` (default = `1`)`` — The arc's weight

Returns

| `Boolean` — True if the arc was added, otherwise false.

addNode | () | method |

`public function addNode(obj:*, i:int):Boolean`

Adds a node at a given index to the graph.

Parameters

| `obj:*` — The data to store in the node.
| `i:int` — The index the node is stored at.

Returns

| `Boolean` — True if a node was added, otherwise false.

breadthFirst | () | method |

`public function breadthFirst(node:GraphNode, visit:Function):void`

Performs a breadth-first traversal starting at a given node.

Parameters

| `node:GraphNode` — The graph node at which the traversal starts.
| `visit:Function` — 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.

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.

             var visitNode:Function = function(node:GraphNode):Boolean
             {
                 if (node.data == 5)
                     return false; //terminate traversal
                 return true;
             }
             myGraph.breadthFirst(graph.nodes[0], visitNode);

clear | () | method |

`public function clear():void`

Clears all items.

clearMarks | () | method |

`public function clearMarks():void`

Marks are used to keep track of the nodes that have been visited during a depth-first or breadth-first traversal. You must call this method to clear all markers before starting a new traversal.

contains | () | method |

`public function contains(obj:*):Boolean`

Determines if the collection contains a given item.

Parameters

| `obj:*` — The item to search for.

Returns

| `Boolean` — True if the item exists, otherwise false.

depthFirst | () | method |

`public function depthFirst(node:GraphNode, visit:Function):void`

Performs an iterative depth-first traversal starting at a given node.

Parameters

| `node:GraphNode` — The graph node at which the traversal starts.
| `visit:Function` — 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.

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.

             var visitNode:Function = function(node:GraphNode):Boolean
             {
                 if (node.data == 5)
                     return false; //terminate traversal
                 return true;
             }
             myGraph.depthFirst(graph.nodes[0], visitNode);

getArc | () | method |

`public function getArc(from:int, to:int):GraphArc`

Finds an arc pointing to the node at the 'from' index to the node at the 'to' index.

Parameters

| `from:int` — The originating graph node index.
| `to:int` — The ending graph node index.

Returns

| `GraphArc` — A GraphArc object or null if it doesn't exist.

getIterator | () | method |

`public function getIterator():Iterator`

Initializes an iterator object pointing to the first item in the collection.

Returns

| `Iterator` — An iterator object.

isEmpty | () | method |

`public function isEmpty():Boolean`

Checks if the collection is empty.

Returns

| `Boolean` — True if empty, otherwise false.

removeArc | () | method |

`public function removeArc(from:int, to:int):Boolean`

Removes an arc pointing to the node located at the 'from' index to the node at the 'to' index.

Parameters

| `from:int` — The originating graph node index.
| `to:int` — The ending graph node index.

Returns

| `Boolean` — True if the arc was removed, otherwise false.

removeNode | () | method |

`public function removeNode(i:int):Boolean`

Removes a node from the graph at a given index.

Parameters

| `i:int` — The node's index.

Returns

| `Boolean` — True if removal was successful, otherwise false.

toArray | () | method |

`public function toArray():Array`

Converts the collection into an array.

Returns

| `Array` — An array.

Thu Jan 16 2014, 01:11 PM +08:00