An
Edge
is a type of
Element.
An edge connects two node elements in a graph.
When creating an edge element, it is necessary to provide
existing node elements as the edge end-points.
An edge becomes a component of a
Graph
by assigning that
Graph
value to the edge's
parent
field.
The parent fields of the edge and its associated nodes need not be the
same, but they must be elements in the same overall graph.
Constants referred to here are contained in the
yoix.graph
dictionary.
The complete set of fields in an
Edge
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 an edge element,
the default attributes owned by its parent 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 edge attributes owned by the parent graph are accessed and so
on for its parent graph and up to the root graph, and failing all that the
global edge 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 edge attributes
owned by the parent graph 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.
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 in that case will cause an error.
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 edge elements are visited starting from the current edge element
with the connective relationship being determined by common nodes at
edge end-points.
If the graph is a directed graph, then to reach edge A from edge B, there
must be a common node that A is directed towards and that
B is directed away from.
The traversal can be restricted to a specified
depth
or distance out from the current edge.
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.
| | 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.
| | flags |
An
int
representing the bitwise-ORing of the basic characteristics of this
edge element, namely whether the direction of the edge is
FORWARD,
or
REVERSE,
both or none.
If the graph is directed, then the default
flag
is
FORWARD.
| | head |
A
Node
representing an end-point of the edge.
When direction counts, the head node is at the forward end of the edge.
| | 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.
| | parent |
The
Graph
which is the parent graph of this element.
Assigning to this value adds or removes elements from a graph.
| | root |
A read-only field that is the root
Graph
for this element.
| | tail |
A
Node
representing an end-point of the edge.
When direction counts, the tail node is at the reverse end of the edge.
| | 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([Function func], [Object args, ...]) |
This
Builtin
traverses the graph in the manner of a natural walk starting at the current
element.
For an edge element, however, that simply means visiting the edge itself.
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.
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 from an XML graph description
and dumps it back out.
Then it does a breadth-first search looking for the color "gray", which
is not found.
Finally, it does another breadth-first search looking for the color "red",
which it finds and stops the search at that point.
The traversals are anchored on the
edge_1_4
element.
import yoix.graph.*;
import yoix.stdio.*;
graph_str = "\
<graph name=g directed=1 strict=1 color=white label=Example>\n\
<node_attributes color=blue />\n\
<node name=node_0 color=red />\n\
<node name=node_1 />\n\
<node name=node_2 color=green />\n\
<node name=node_3 />\n\
<node name=node_4 color=orange />\n\
<edge name=edge_3_0 tail=node_3 head=node_0 \
color=yellow />\n\
<edge name=edge_0_2 tail=node_0 head=node_2 color=green />\n\
<edge name=edge_2_0 tail=node_2 head=node_0 color=red />\n\
<edge name=edge_1_2 tail=node_1 head=node_2 color=blue />\n\
<edge name=edge_4_0 tail=node_4 head=node_0 color=red />\n\
<edge name=edge_1_4 tail=node_1 head=node_4 color=blue />\n\
</graph>\n\
";
g = xmlGraph(graph_str);
stdout.nextline = g.text();
stopColor(String col) {
String color = attribute("color");
printf("%s is %s\n", name, color);
if(color === col) {
printf("Found %s... stopping.\n", col);
return(true);
}
}
e = g.element("edge_1_4");
printf("First try 'gray':\n");
e.bfs(stopColor, "gray");
printf("Second try 'red':\n");
e.bfs(stopColor, "red");
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>
First try 'gray':
edge_1_4 is blue
edge_4_0 is red
edge_0_2 is green
edge_2_0 is red
Second try 'red':
edge_1_4 is blue
edge_4_0 is red
Found red... stopping.
| | |
| See Also: |
countElements,
Graph,
Element,
Node,
listElements,
xmlGraph
|
|
