A weighted graph
A graph is composed of GraphNode and GraphArc objects.
Example:
var o = new polygonal.ds.Graph<String>();
var a = o.addNode(o.createNode("a"));
var b = o.addNode(o.createNode("b"));
var c = o.addNode(o.createNode("c"));
o.addSingleArc(a, b);
o.addSingleArc(b, a);
o.addMutualArc(a, c);
trace(o); //outputs:
[ Graph size=3
c -> a
b -> a
a -> c,b
]
Constructor
Variables
autoClearMarks:Bool = false
If true, automatically clears the mark-flag on all graph nodes prior to starting a new traversal.
Default is false.
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
reuseIterator:Bool = false
If true, reuses the iterator object instead of allocating a new one when calling this.iterator().
The default is false.
If this value is true, nested iterations will fail as only one iteration is allowed at a time.
Methods
addMutualArc (source:GraphNode<T>, target:GraphNode<T>):Graph<T>
Creates an uni-directional link between two nodes.
This creates two arcs; an arc pointing from source to target and vv.
The newly created arcs can be accessed via source.arcList (pointing to target) and target.arcList (pointing to source).
addNode (node:GraphNode<T>):GraphNode<T>
Adds the node node to this graph and returns node.
Silently fails if the node was already added to this graph.
addSingleArc (source:GraphNode<T>, target:GraphNode<T>):Graph<T>
Creates an uni-directional link between two nodes.
This creates an arc pointing from source to target.
The newly created arc can be accessed via source.arcList.
arcIterator ():Itr<GraphArc<T>>
Returns a new GraphArcIterator object to iterate over all GraphArc objects in this graph.
The arcs are visited in a random order.
See:
bfs (preflight:Bool = false, ?seed:GraphNode<T>, ?process:GraphNode<T> ‑> Bool ‑> Dynamic ‑> Bool, ?userData:Dynamic):Graph<T>
Performs an iterative breadth-first search (BFS).
Parameters:
preflight | if true, an extra traversal is performed before the actual traversal runs.
The first pass visits all elements and calls |
|---|---|
seed | the starting point of the traversal. If omitted, the first node in the list of graph nodes is used. |
process | a function that is invoked for every traversed node.
process returns false, the traversal stops immediately and no further nodes are examined (termination condition).
If omitted, element.visit() is used.
In this case the elements of all nodes have to implement Visitable. |
userData | custom data that is passed to every visited node via |
clear (gc:Bool = false):Void
Removes all elements.
Parameters:
gc | if true, explicitly nullifies nodes and elements upon removal so the garbage collector can reclaim used memory. |
|---|
clearMarks ():Graph<T>
Clears the mark-flag on all graph nodes that were set in a BFS/DFS traversal.
Call this method to start a fresh traversal.
clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this graph.
If byRef is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.
dfs (preflight:Bool = false, ?seed:GraphNode<T>, ?process:GraphNode<T> ‑> Bool ‑> Dynamic ‑> Bool, ?userData:Dynamic, recursive:Bool = false):Graph<T>
Performs an iterative depth-first search (DFS).
Parameters:
preflight | if true, an extra traversal is performed before the actual traversal runs.
The first pass visits all elements and calls |
|---|---|
seed | the starting point of the traversal. If omitted, the first node in the list of graph nodes is used. |
process | a function that is invoked for every traversed node.
process returns false, the traversal stops immediately and no further nodes are examined (termination condition).
If omitted, element.visit() is used.
In this case the elements of all nodes have to implement Visitable. |
userData | custom data that is passed to every visited node via |
recursive | if true, performs a recursive traversal (default traversal style is iterative). |
dlbfs (maxDepth:Int, preflight:Bool = false, ?seed:GraphNode<T>, ?process:GraphNode<T> ‑> Bool ‑> Dynamic ‑> Bool, ?userData:Dynamic):Graph<T>
Performs an iterative depth-limited breadth-first search (DLBFS).
Parameters:
maxDepth | a |
|---|---|
preflight | if true, an extra traversal is performed before the actual traversal runs.
The first pass visits all elements and calls |
seed | the starting point of the traversal. If omitted, the first node in the list of graph nodes is used. |
process | a function that is invoked for every traversed node. The parameters are:
process returns false, the traversal stops immediately and no further nodes are examined (termination condition).
If omitted, element.visit() is used.
In this case the elements of all nodes have to implement Visitable. |
userData | custom data that is passed to every visited node via |
findNode (val:T):GraphNode<T>
Finds and returns the node storing val or null if such a node does not exist.
free ():Void
Destroys this object by explicitly nullifying all nodes, elements and pointers for GC'ing used resources.
Improves GC efficiency/performance (optional).
inlinegetNodeList ():GraphNode<T>
iterator ():Itr<T>
Returns a new GraphIterator object to iterate over all elements stored in the graph nodes of this graph.
The nodes are visited in a random order.
See:
nodeIterator ():Itr<GraphNode<T>>
Returns a new GraphNodeIterator object to iterate over all GraphNode objects in this graph.
The nodes are visited in a random order.
See:
remove (val:T):Bool
Removes all nodes storing val.
Nodes and elements are nullified.
Returns:
true if at least one node storing val was removed.
removeNode (node:GraphNode<T>):Graph<T>
Removes node from this graph.
This clears all outgoing and incoming arcs and removes node from the node list.
Silently fails if node was already removed from this graph.
serialize (getVal:T ‑> Dynamic):{vals:Array<Dynamic>, arcs:Array<Int>}
Serializes the graph, outputting two arrays: the first one stores all node values, while the second one contains a list of indices describing how the nodes are connected via arcs.
Example:
class Element {
public var name:String;
public function new(name:String) {
this.name = name;
}
}
...
var graph = new Graph<Element>();
var a = graph.createNode(new Element("a"));
var b = graph.createNode(new Element("b"));
var c = graph.createNode(new Element("c"));
graph.addNode(a);
graph.addNode(b);
graph.addNode(c);
graph.addMutualArc(a, b);
graph.addMutualArc(b, c);
graph.addMutualArc(a, c);
//serialize
var data = graph.serialize(function(nodeValue:Element) return nodeValue.name); //only store name property
trace(data.arcs); //[0,2,0,1,1,0,1,2,2,0,2,1]
trace(data.vals); //["c","b","a"]
//unserialize
var graph = new Graph<Element>();
graph.unserialize(data, function(val:String) return new Element(val));
toArray ():Array<T>
Returns an unordered array containing all elements stored in the graph nodes of this graph.
unlink (node:GraphNode<T>):GraphNode<T>
Isolates node from this graph by unlinking it from all outgoing and incoming arcs.
The size remains unchanged as the node is not removed from the graph.
Silently fails if node was not added to this graph.
Returns:
the disconnected graph node.
unserialize (data:{vals:Array<Dynamic>, arcs:Array<Int>}, setVal:Dynamic ‑> T):Void
See this.serialize.