3
\$\begingroup\$

So, I am not sure if I should have Vertex extend Point, because the equals() and compareTo() functions are already parameterized with Point. I guess I don't really need compare to...

Does this structure look good? I used a Map instead of a TreeMap because as3commons and the default flex packages do not have this structure defined. How easy will this be if I were to create it.

Things that I am in the process of working out now:

  • I know I need to add removeVertex() (and removeEdge()?)
  • If I want to create an Edge class, I supposed I would make the following changes:

    // Since this is undirected, do I need 2 edges, because I have src and dest?
    public class Edge {
        public var src:Vertex;
        public var dest:Vertex;
        public var data:Object;
    
        public function Edge(src:Vertex, dest:Vertex, data:Object=null) {
            // Set instance variables
        }
    }
    
    public class Graph {
        public var edges:IMap; // <Object, Edge>
    
        public function addEdge(from:Object, to:Object, data:Object):void {
            edges.add(data, new Edge(v, w));
        }
    }
    

My main gripe would be about juggling all of these data types.

  • public var adjList:IMap; // <Vertex, Set>
  • public var vertices:IMap; // <Object, Vertex>
  • public var edges:IMap; // <Object, Edge>

This may make if difficult to intelligently traverse the graph.


Reference classes and files:

Vertex.as

package core {
    import flash.geom.Point;

    public class Vertex extends Point {
        public var data:Object;

        public function Vertex(data:Object=null, x:Number=0, y:Number=0) {
            super(x, y);

            this.data = data;
        }

        // Implement...
        override public function clone():Point {
            return new Vertex(data, x, y);
        }

        override public function toString():String { 
            return data.toString();
        }

        // Implement...
        override public function equals(toCompare:Point):Boolean {
            return super.equals(toCompare) && this.compareTo(toCompare as Vertex) == 0;
        }

        // Implement...
        public function compareTo(other:Vertex):int {
            return 0;
        }
    }
}

Graph.as

package core {
    import org.as3commons.collections.Map;
    import org.as3commons.collections.Set;
    import org.as3commons.collections.framework.IMap;
    import org.as3commons.collections.framework.ISet;

    public class Graph {
        public var adjList:IMap; // <Vertex, Set>
        public var vertices:IMap; // <Object, Vertex>

        private static const EMPTY_SET:ISet = new Set();

        private var _numVertices:int;
        private var _numEdges:int;

        public function Graph() {
            adjList = new Map();
            vertices = new Map();
            _numVertices = _numEdges = 0;
        }

        public function addVertex(data:Object):Vertex {
            var v:Vertex = vertices.itemFor(data);

            if (v == null) {
                v = new Vertex(data);
                vertices.add(data, v);
                adjList.add(v, new Set());
                _numVertices++;
            }

            return v;
        }

        public function getVertex(data:Object):Vertex {
            return vertices.itemFor(data);
        }

        public function hasVertex(data:Object):Boolean {
            return vertices.hasKey(data);
        }

        public function hasEdge(from:Object, to:Object):Boolean {
            if (!hasVertex(from) || !hasVertex(to))
                return false;
            return (adjList.itemFor(vertices.itemFor(from)) as Set).has(vertices.itemFor(to));
        }

        public function addEdge(from:Object, to:Object):void {
            var v:Vertex, w:Vertex;
            if (hasEdge(from, to))
                return;
            _numEdges += 1;
            if ((v = getVertex(from)) == null)
                v = addVertex(from);
            if ((w = getVertex(to)) == null)
                w = addVertex(to);
            (adjList.itemFor(v) as Set).add(w);
            (adjList.itemFor(w) as Set).add(v);
        }

        public function adjacentTo(value:*):ISet {
            if (value is Object && hasVertex(value as Object)) {
                return adjList.itemFor(getVertex(value as Object)) as Set;
            }

            if (value is Vertex && adjList.has(value as Vertex)) {
                return adjList.itemFor(value as Vertex) as Set;
            }

            return EMPTY_SET;
        }

        public function getVertices():ISet {
            var set:ISet = new Set();
            for each (var v:Vertex in vertices.toArray()) {
                set.add(v);
            }
            return set;
        }

        public function numVertices():int {
            return _numVertices;
        }

        public function numEdges():int {
            return _numEdges;
        }

        public function toString():String {
            var s:String = "";
            for each (var v:Vertex in vertices.toArray()) {
                s += v + ": ";

                var set:ISet = adjList.itemFor(v) as Set;
                for each (var w:Vertex in set.toArray()) {
                    s += (w + " ");
                }
                s += "\n";
            }
            return s;
        }
    }
}

App.mxml

<?xml version="1.0" encoding="utf-8"?>
<s:Application xmlns:fx="http://ns.adobe.com/mxml/2009" 
    xmlns:s="library://ns.adobe.com/flex/spark" 
    xmlns:mx="library://ns.adobe.com/flex/mx"
    creationComplete="onComplete(event)">
    <fx:Script>
        <![CDATA[
            import core.Graph;
            import core.Vertex;

            import mx.events.FlexEvent;

            protected function onComplete(event:FlexEvent):void {
                main();
            }

            public static function main(args:Vector.<String>=null):void {
                var G:Graph = new Graph();

                G.addEdge("A", "B");
                G.addEdge("A", "C");
                G.addEdge("C", "D");
                G.addEdge("D", "E");
                G.addEdge("D", "G");
                G.addEdge("E", "G");
                G.addVertex("H");
                // print out graph
                trace(G);

                trace('Verticies:', G.numVertices());
                trace('Edges    :', G.numEdges());
                trace();

                // print out graph again by iterating over vertices and edges
                for each (var v:Vertex in G.getVertices().toArray()) {
                    var str:String = v + ": ";
                    for each (var w:Vertex in G.adjacentTo(v.data).toArray()) {
                        str += w + " ";
                    }
                    trace(str);
                }
            }
        ]]>
    </fx:Script>
</s:Application>
\$\endgroup\$
  • \$\begingroup\$ After doing some research, I found that the best answer for this question: SO: How do I properly extend the AS3 Point class? states that the point class should be a delegate of the class that, in theory, extends it. \$\endgroup\$ – Mr. Polywhirl Feb 20 '14 at 11:35
  • \$\begingroup\$ Typically graphs are represented by adjacency table. This would save you some place, and would be less surprising for the reader. This also makes Edge class unnecessary. You would be only storing vertices. But this may depend on your use case. For graphs with labeled edges it might make sense to actually create such a class, or maybe to extend the adjacency table to have triples rather than tuples. \$\endgroup\$ – wvxvw Jan 2 '15 at 15:18
2
\$\begingroup\$

adjList needs a more descriptive name. Specifically as a class member variable, it deserves the few extra characters it would take to be called adjacencyList.

Additionally, you have extended Point, but do not use any of Point's functions. Does Point even provide functions? (Yes, it does.)

I'd have gone with a Vertex class that contains a Point, not extends it. You pointed this out yourself in a comment as well.


    public function adjacentTo(value:*):ISet {
        if (value is Object && hasVertex(value as Object)) {
            return adjList.itemFor(getVertex(value as Object)) as Set;
        }

        if (value is Vertex && adjList.has(value as Vertex)) {
            return adjList.itemFor(value as Vertex) as Set;
        }

        return EMPTY_SET;
    }

This is a nasty bit of code. I wanted to say that you should swap the two checks, as any Vertex is also an Object, and you end up always checking if any of your vertices has value as data. But if you were to have a Vertex which has another Vertex as data then swapping the two would make the function fail to perform properly. A comment along these lines would go a long way towards not shooting yourself in the foot later.

    public function addVertex(data:Object):Vertex {
        var v:Vertex = vertices.itemFor(data);
        //codes
    }

    public function getVertex(data:Object):Vertex {
        return vertices.itemFor(data);
    }

Reuse your functions where you can; like that you allow code to be read at a semantic level, rather than a syntactical level. Logical reasoning likes to work with semantics and not bother so much with the syntax. In this case, you can reuse getVertex:

    public function addVertex(data:Object):Vertex {
        var v:Vertex = getVertex(data);
        //codes
    }
\$\endgroup\$
  • \$\begingroup\$ adjList == Adjacency List \$\endgroup\$ – Mr. Polywhirl Jan 27 '15 at 10:51
  • \$\begingroup\$ @Mr.Polywhirl rephrased the sentence and expanded a bit \$\endgroup\$ – Pimgd Jan 27 '15 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.