|
A
Graph
is a type of
Element.
It is used to organize a collection of
Node,
Edge
and other
Graph
(i.e., subgraph) elements.
An element is assigned to a graph by assigning the graph to the element's
parent
field.
The top-most or root graph of a collection of elements can always be
determined by examining the
root
field of any element in that collection.
Graphs can be traversed in several ways to gather information
about the connectedness and the inter-relationships of their elements.
All graph elements can have attributes, or name-value pairs, associated
with them.
Default graph, node and edge attributes are assigned at the graph
(or subgraph) level and provide default values for elements of the appropriate
type (graph, node or edge) beginning with the graph in which they are defined
and extending to all contained elements including those in nested subgraphs,
no matter how deeply nested.
Default attributes override attributes of the same name inherited from
any graphs that contain the current graph (super-graphs).
Element attributes apply only to the element in which they are defined and
override any inherited attributes having the same name.
There are also graph, node and edge global attributes which act as
default attributes at the top-most (i.e., above root graphs) level and
apply to all graphs during a Yoix session.
In cases where one wants to refer strictly to attributes defined within an
element, the term
local
is used; when inherited attributes are to be included, the term
scoped
is used.
Constants referred to here are contained in the
yoix.graph
dictionary.
The complete set of fields in a
Graph
are:
| attribute([int flags], [Object name[, Object value]]) |
A
Builtin
that allows one to add, change, delete or retrieve any type of attribute.
The
flags
argument, when present, specifies the desired action, action scope and the
target attribute type.
The various values described below can be combined by bitwise-OR to specify the
flags
argument.
The default action is either retrieval or replacement, depending on
the context (see below).
The following actions can be indicated specifically:
CREATE,
DELETE,
or
REPLACE
CREATE
is for creating new attributes, but otherwise generates a
badvalue
error when an existing attribute with the same name is accessible.
Using
REPLACE
avoids this check.
A
DELETE
action is ignored when the requested attribute does not already exist.
The default action scope is local, but can be specified as
SCOPED,
which means that any default attributes that are inherited will be
accessible along with the locally defined attributes.
Otherwise, only the locally defined attributes will be accessed.
By default, the target attributes type are the element's attributes, but
specific default attributes to access can be specified using
NODEDFLT,
EDGEDFLT,
or
GRAPHDFLT.
When working with the local scope, requesting any action (retrieval, creation,
deletion or replacement) and targeting element attributes, the attributes
defined as part of the current element are accessed (i.e., defaults do
not come into play at all).
When working with the local scope, requesting any action (retrieval, creation,
deletion or replacement) and targeting a default attribute
type (graph, node or edge), the default attributes
accessed depends on the current element.
For a graph element,
the default attributes owned by it are accessed.
When scoping and retrieval are in effect and the element is targeted,
then first this element's own attributes are accessed, failing that the
default graph attributes owned by this graph element are accessed and so
on for its parent graph and up to the root graph, and failing all that the
global graph attributes are accessed, if any.
When a specific default
type is specified, the search is the same as above except that this
element's own attributes are skipped and that the attribute type searched
is determined by the flags supplied instead of by the element's type.
When scoping and creation, deletion or replacement are in effect and
the element attributes are targeted, then the default graph attributes
owned by this element are accessed.
Finally, when a specific default
type is specified, the behavior is the same as above except that the
attribute type searched is determined by the flags supplied instead of
by the element's type. Moreover, the global attributes are accessed,
in this case, if the element is the root graph.
When no
value
is supplied, only retrieval or deletion actions are allowed,
with retrieval being the default.
If a
name
is also absent, then the deletion action clears all targeted attributes.
A supplied
name
can be a
String,
Array
or
Dictionary.
When it is a
Dictionary,
it is treated as supplying names and values and specifically supplying a
value
argument will cause an error in this case.
When a
value
is supplied, either explicitly or through a
name
argument
Dictionary,
then the default action is replacement.
Return values are either the requested retrievals, the replaced values or
NULL,
as appropriate.
Multiple values are returned in an
Array.
| | attributes |
After initialization, this field is read-only.
It provides a
Dictionary
of the local attributes of this element and is
equivalent to using the above built-in with no arguments.
| | bfs([int depth], [Function func], [Object args, ...]) |
A
Builtin
for traversing graphs in a breadth-first search manner.
Only other graph elements are visited starting from the current graph
element with the connective relationship being determined by the
parent
field links.
The traversal can be restricted to a specified
depth.
If
func
is supplied,
it is called each time an element is traversed and in the context of that
element.
If one or more
args
are supplied, they are used as arguments to
func.
The function need not return a value, but if it does return a non-zero value,
it will cause the traversal to stop at that element.
The defaults are to have no limit on depth and no function provided.
An array of visited elements is returned.
Note that
| | dfs([int depth], [Function func], [Object args, ...]) |
This
Builtin
is the same as the bfs built-in, described above, except that
the traversal of the graph is in the manner of a depth-first search.
| | edgedefaults |
A
Dictionary
containing the edge default attributes owned by this graph element.
Assigning to this field entirely replaces the current set of values.
| | element(String name) |
A
Builtin
that returns the
Element
corresponding to the supplied name if it is within the root graph of this
element, otherwise
NULL
is returned.
| | flags |
An
int
representing the bitwise-ORing of the basic characteristics of this
graph element, namely whether it is a directed graph
DIRECTED),
or a strict graph
STRICT)
or both.
Currently, after initialization, this field cannot be modified.
| | graphdefaults |
A
Dictionary
containing the graph default attributes owned by this graph element.
Assigning to this field entirely replaces the current set of values.
| | name |
A
String
that is the current name of this element.
Assigning to this field changes the name of this element.
If
name
is currently assigned to another element within the
graph containing this element, a
nameclash
error results.
| | nodedefaults |
A
Dictionary
containing the node default attributes owned by this graph element.
Assigning to this field entirely replaces the current set of values.
| | parent |
The
Graph
which is the parent graph of this element or
NULL
if this element is the root graph.
Assigning to this value adds or removes elements from a graph.
| | root |
A read-only field that is the root
Graph
for this element.
| | text([int format[, int mode[, int depth[, String prefix]]]]) |
A
Builtin
that returns a
String
representation of the current graph.
Current
format
values are either
XML,
which results in XML output (see http://www.w3c.org/), or
DOT,
which results in dot output (see http://www.research.att.com/sw/tools/graphviz/).
The default is XML output.
Setting
mode
determines how the graph is traversed and possible values are:
BFS,
for breadth-first search mode,
DFS,
for depth-first search mode, and
WALK,
for a natural walk of the graph.
The default is a natural walk.
See the walk built-in below for a description of a natural walk.
The
depth
argument limits traversal to the specified number of layers.
A negative value, which is the default, indicates no limit.
A
prefix
may be applied to each line of output to allow special marking or indentation
of all the text lines.
The default is to have no prefix.
| | walk([int depth], [String types], [Function func], [Object args, ...]) |
This
Builtin
traverses the graph in the manner of a natural walk, namely
first the current element, which may be the root graph or a subgraph,
is visited, then the nodes in it, followed by the edges in it and the process
is repeated for each subgraph in it in turn.
Note that unlike the bfs and dfs
built-ins, this traversal visits all types of elements, though the
types visited can be restricted by means of the
types
argument.
The allowed element types are specified by using the words
graph,
node
or
edge
separated by any non-character delimiter.
Note that only the first letter of each word is examined in determining
the type and it is case insensitive.
The remaining arguments serve the same functions as described for the
bfs built-in above.
An array of visited elements is returned.
|
Several permanent fields have not been documented and should not be
used in Yoix applications.
| |
| Example: |
The following code sample builds a graph and dumps it in XML format to
the standard output:
import yoix.graph.*;
import yoix.stdio.*;
import yoix.string.*;
int i, j, k;
Node n;
Edge e;
int nodes = 5;
int skip = 2;
int inner = 2;
Array colors = {
"red",
"blue",
"green",
"yellow",
"orange",
"purple",
"brown",
"gray",
"lightgray",
"darkgray"
};
Graph g = new Graph {
String name = "g";
int flags = STRICT|DIRECTED;
Dictionary attributes = {
String color = "white";
String label = "Example";
};
Dictionary nodedefaults = {
String color = "blue";
};
};
for(i=0; i<nodes; i++) {
n = new Node {
String name = strfmt("node_%04d", i);
Graph parent = g;
};
if(i%2 == 0) {
n.attribute("color", colors[i%10]);
}
}
for(i=0; i<nodes; i+=skip) {
for(j=0; j<inner; j++) {
do {
if((k = (nodes - 1) * yoix.math.random()) == i)
continue;
try {
if(k%2 == 0) {
e = new Edge {
String name = strfmt("edge_%04d_%04d", i, k);
Node tail = g.element(strfmt("node_%04d",i));
Node head = g.element(strfmt("node_%04d",k));
Graph parent = g;
Dictionary attributes = {
String color = colors[k%10];
};
};
} else {
e = new Edge {
String name = strfmt("edge_%04d_%04d", k, i);
Node tail = g.element(strfmt("node_%04d",k));
Node head = g.element(strfmt("node_%04d",i));
Graph parent = g;
Dictionary attributes = {
String color = colors[k%10];
};
};
}
}
catch(e) {
k = -1;
return(true);
}
} while(k < 0);
}
}
stdout.nextbuf = g.text();
One possible result on standard output looks like:
<graph name=g directed=1 strict=1 color=white label=Example>
<node_attributes color=blue />
<node name=node_0 color=red />
<node name=node_1 />
<node name=node_2 color=green />
<node name=node_3 />
<node name=node_4 color=orange />
<edge name=edge_3_0 tail=node_3 head=node_0 color=yellow />
<edge name=edge_0_2 tail=node_0 head=node_2 color=green />
<edge name=edge_2_0 tail=node_2 head=node_0 color=red />
<edge name=edge_1_2 tail=node_1 head=node_2 color=blue />
<edge name=edge_4_0 tail=node_4 head=node_0 color=red />
<edge name=edge_1_4 tail=node_1 head=node_4 color=blue />
</graph>
| | |
| See Also: |
countElements,
Edge,
Element,
listElements,
Node,
xmlGraph
|
|
