Abstract Data Types - Page 5

Let's go over our Edge class. You will notice that our Edge class is noticeably smaller than the Node class you learned about in the previous page. Let's start with the constructor:

public function Edge(from:Node, to:Node, edgeName:String) {

nodeOne = from;

nodeTwo = to;

 

var edgeKey:String = from.getName() + to.getName();

var edgePair:Array = new Array();

 

edgePair.push(edgeKey);

edgePair.push(this);

edgeList.push(edgePair);

 

this.edgeName = edgeName;

currentEdge = this;

 

draw(nodeOne, nodeTwo);

}

The Edge constructor takes in, for its arguments, two nodes (from, to) and the name of your edge (edgeName). Because edges are linked to nodes, I need to be able to store both the edge and the names of the two nodes it is connecting. A simple way I was able to do that is by storing both the node names and the Edge in a single list.

var edgeKey:String = from.getName() + to.getName();

var edgePair:Array = new Array();

 

edgePair.push(edgeKey);

edgePair.push(this);

edgeList.push(edgePair);

For example, if you have have two nodes called "East" and "West", and you create an edge between them, your edgeList would look like the following:

((EastWest, [edge Object]))

If you added another edges between the West node and a South node, your edgeList would now look like this:

((EastWest, [edge Object]), (WestSouth, [edge Object]))

This format allows me to easily search for the correct Edge by simply inputting the two nodes. You will see how the searching works when I explain the getEdge method below.

Similar to the Node class, I store many of the values from our constructor as private variables outside our class:

private var edgeName:String;

private var nodeOne:Node;

private var nodeTwo:Node;

private var currentEdge:Edge;

private static var edgeList:Array = new Array();

Notice that our edgeList is defined as a static variable. It is static because I want to ensure that the edge and node connections are up-to-date among all of the edge objects.

Finally, I make a call to our private draw method that simply puts two lines between the nodes.

public function getName():String {

return edgeName;

}

This method simply returns the name of our edge. Because the edgeName variable is declared globally and initialized in the constructor, we can simply return the edgeName variable without doing anything else.

public function getDistance():Number {

var dx:Number = 0;

var dy:Number = 0;

 

dx = Math.abs(nodeOne.getX() - nodeTwo.getX());

dy = Math.abs(nodeOne.getY() - nodeTwo.getY());

 

return Math.round(Math.sqrt((dx*dx) + (dy*dy)));

}

This method returns the length of our edge or, in other words, the distance between the two nodes that make up our edge. In this implementation, I use the Pythagorean theorem to calculate distances because our edge is a straight line. If you use non-linear edges (such as a curve, for example), you will need to adjust this method accordingly.

public static function getEdgeList(node1:Node, node2:Node):Array {

var keyName:String = node1.getName() + node2.getName();

var gettingEdge:Array = new Array();

 

for (var i = 0; i < edgeList.length; i++) {

var itemList:Array = new Array();

itemList = edgeList[i];

 

if (itemList[0] == keyName) {

gettingEdge.push(itemList[1]);

}

}

return gettingEdge;

}

This method returns a list of edges that connect the two inputted nodes. In my description of the constructor, I provided an explanation as to how the nodes map to the edge object. This method essentially searches through our edgeList array structure and adds any instance of an edge it finds to our gettingEdge list.

Because the key is the combination of both node names, I search the first item in each nested array for a match. If a match is found, you automatically know that the second item in the nested array must be the Edge object you are searching for.

Conclusion
Designing and creating an ADT is time-consuming, but hopefully the time you will save using your ADT for repetitive tasks will be greater. Something that I chose not cover in this tutorial is Testing. Your ADT needs to work consistently, and testing is a good way to ensure that your ADT produces the right outputs for the inputs your provide. I felt it is too important of a topic to combine with an intro to ADT's, so I'll continue this discussion in a future tutorial.

Further Info

For more information on Abstract Data Types, the following link should be helpful: Lecture: Introduction to ADT's

The node/graph implementation is based partly on work that I did here.

1 | 2 | 3 | 4 | 5