topical media & game development

topical media & game development

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

lib-as-de-polygonal-ds-Graph.ax

lib-as-de-polygonal-ds-Graph.ax (swf ) [ flash ] flex

Copyright (c) Michael Baczynski 2007 http://lab.polygonal.de/ds/ This software is distributed under licence. Use of this software implies agreement with all terms and conditions of the accompanying software licence.


  
  package de.polygonal.ds
  {
          import de.polygonal.ds.@fileNode;

A linked uni-directional weighted graph structure. <p>The @ax-lib-as-de-polygonal-ds-Graph class manages all graph nodes. Each graph node has a linked list of arcs, pointing to different nodes.</p>


  
          public class @ax-lib-as-de-polygonal-ds-Graph
          {

An array containing all graph nodes.


  
                  public var nodes:Array;
                  
                  private var _nodeCount:int;
                  private var _maxSize:int;

Constructs an empty graph.
parameter: size The total number of nodes allowed.


  
                  public function @ax-lib-as-de-polygonal-ds-Graph(size:int)
                  {
                          nodes = new Array(_maxSize = size);
                          _nodeCount = 0;
                  }

Performs a depth-first traversal on the given node.
parameter: node The starting graph node.
parameter: process A function to apply to each traversed node.


  
                  public function depthFirst(node:@fileNode, process:Function):void
                  {
                          if (!node) return;
                          
                          process(node);
                          node.marked = true;
                          
                          var k:int = node.numArcs, t:@fileNode;
                          for (var i:int = 0; i < k; i++)
                          {
                                  t = node.arcs[i].node;
                                  if (!t.marked) depthFirst(t, process);
                          }
                  }

Performs a breadth-first traversal on the given node.
parameter: node The starting graph node.
parameter: process A function to apply to each traversed node.


  
                  public function breadthFirst(node:@fileNode, process:Function):void
                  {
                          if (!node) return;
                          
                          var que:Array = [];
                          que.push(node);
                          node.marked = true;
                          
                          var c:int = 1;
                          
                          var t:@fileNode, u:@fileNode;
                          while (c > 0)
                          {
                                  process(t = que[0]);
                                  
                                  var arcs:Array = t.arcs, k:int = t.numArcs;
                                  for (var i:int = 0; i < k; i++)
                                  {
                                          u = arcs[i].node;
                                          if (!u.marked)
                                          {
                                                  u.marked = true;
                                                  que.push(u);
                                                  c++;
                                          }
                                  }
                                  que.shift();
                                  c--;
                          }
                  }

Adds a node at a given index to the graph.
parameter: obj The data to store in the node.
parameter: i The index the node is stored at.
returns: True if successful, otherwise false.


  
                  public function addNode(obj:*, i:int):Boolean
                  {
                          if (nodes[i]) return false;
                          
                          nodes[i] = new @fileNode(obj);
                          _nodeCount++;
                          return true;
                  }

Removes a node from the graph at a given index.
parameter: index Index of the node to remove
returns: True if successful, otherwise false.


  
                  public function removeNode(i:int):Boolean
                  {
                          var node:@fileNode = nodes[i];
                          if(!node) return false;
                          
                          var arc:@fileArc;
                          for (var j:int = 0; j < _maxSize; j++)
                          {
                                  var t:@fileNode = nodes[j];
                                  if (t && t.getArc(node)) removeArc(j, i);
                          }
                          
                          nodes[i] = null;
                          _nodeCount--;
                          return true;
                  }

Finds an arc pointing to the node at the 'from' index to the node at the 'to' index.
parameter: from The originating graph node index.
parameter: to The ending graph node index.
returns: A @fileArc object or null if it doesn't exist.


  
                  public function getArc(from:int, to:int):@fileArc
                  {
                          var node0:@fileNode = nodes[from];
                          var node1:@fileNode = nodes[to];
                          if (node0 && node1) return node0.getArc(node1);
                          return null;
                  }

Adds an arc pointing to the node located at the 'from' index to the node at the 'to' index.
parameter: from The originating graph node index.
parameter: to The ending graph node index.
parameter: weight The arc's weight
returns: True if an arc was added, otherwise false.


  
                  public function addArc(from:int, to:int, weight:int = 1):Boolean
                  {
                          var node0:@fileNode = nodes[from];
                          var node1:@fileNode = nodes[to];
                          
                          if (node0 && node1)
                          {
                                  if (node0.getArc(node1)) return false;
                          
                                  node0.addArc(node1, weight);
                                  return true;
                          }
                          return false;
                  }

Removes an arc pointing to the node located at the 'from' index to the node at the 'to' index.
parameter: from The originating graph node index.
parameter: to The ending graph node index.
returns: True if an arc was removed, otherwise false.


  
                  public function removeArc(from:int, to:int):Boolean
                  {
                          var node0:@fileNode = nodes[from];
                          var node1:@fileNode = nodes[to];
                          
                          if (node0 && node1)
                          {
                                  node0.removeArc(node1);
                                  return true;
                          }
                          return false;
                  }

Clears the markers on all nodes in the graph so the breadth-first and depth-first traversal algorithms can 'see' the nodes.


  
                  public function clearMarks():void
                  {
                          for (var i:int = 0; i < _maxSize; i++)
                          {
                                  var node:@fileNode = nodes[i];
                                  if (node) node.marked = false;
                          }
                  }

The number of nodes in the graph.


  
                  public function get size():int
                  {
                          return _nodeCount;
                  }

The maximum number of nodes the graph can store.


  
                  public function get maxSize():int
                  {
                          return _maxSize;
                  }

Clears every node in the graph.


  
                  public function clear():void
                  {
                          nodes = new Array(_maxSize);
                          _nodeCount = 0;
                  }
          }
  }

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.