NAME
gfx - standard graph module
STANDARD GRAPH SERVICES
This chapter covers the graph facilities available in the standard
graph module. The basic operations are related to edge, vertices and
graph manipulations. All AFNIX standard graph objects are located in
the afnix-gfx module. This module must be loaded prior any operation.
Multiple calls to the module initialization routine are harmless. The
interpreter method module loads a specific module by name. When the
module has been loaded, the object are available in the afnix:gfx
nameset.
interp:library "afnix-gfx"
Graph concepts
The afnix-gfx provides the support for manipulating graphs. Formally a
graph is a collection of edges and vertices. In a normal graph, an edge
connects two vertices. On the other hand, a vertex can have several
edges. When an edge connects several vertices, it is called an
hyperedge and the resulting structure is called an hypergraph.
Edge class
The Edge class is a class used for a graph construction in association
with the Vertex class. An edge is used to connect vertices. Normally,
an edge connects two vertices. The number of vertices attached to an
edge is called the cardinality of that edge. When the edge cardinality
is one, the edge is called a self-loop. This mean that the edge
connects the vertex to itself. This last point is merely a definition
but present the advantage of defining an hyperedge as a set of
vertices.
Vertex class
The Vertex is the other class used for the graph construction. and
operates with the edge class. A vertex is used to reference edges. the
number of edges referenced by a vertex is called the degree of that
vertex.
Graph
The Graph class is class that represent either a graph or a hypergraph.
By definition, a graph is collection of edges and vertices. There are
numerous property attached to graph. Formally, a graph consists of a
set of edges, a set of vertices and the associated endpoints. However,
the implementation is designed in a way so that each edge and vertex
carry its associated objects. This method ensures that the graph is
fully defined by only its two sets.
Graph construction
The graph construction is quite simple and proceed by adding edges and
vertices. The base system does not enforce rules on the graph
structure. it is possible to add con connected vertices as well as
unreferenced edges.
Edge construction
An edge is constructed by simply invoking the default constructor.
Optionally, a client object can be attached to the edge.
# create a default edge
const edge (afnix:gfx:Edge)
# create an edge with a client object
const hello (afnix:gfx:Edge "hello")
The edge-p predicate can be used to check for the object type. When an
edge is created with client object, the get-client method can be used
to access that object.
Vertex construction
A vertex is constructed a way similar to the Edge> object. The vertex
is constructed by simply invoking the default constructor. Optionally,
a client object can be attached to the edge.
# create a default vertex
const vrtx (afnix:gfx:Vertex)
# create an vertex with a client object
const world (afnix:gfx:Vertex "world")
The vertex-p predicate can be used to check for the object type. When a
vertex is created with a client object, the get-client method can be
used to access that object.
Graph construction
A graph is constructed by simply adding edges and vertices to it. The
graph-p predicate can be use to assert the graph type. the graph class
also supports the concept of client object which can be attached at
construction or with the set-client method.
const graph (afnix:gfx:Graph)
The add method can be used to add edges or vertices to the graph. The
important point is that during the construction process, the graph
structure is updated with the proper number of edge and vertices.
# create a graph
const g (afnix:gfx:Graph)
assert true (afnix:gfx:graph-p g)
# create an edge and add vertices
const edge (afnix:gfx:Edge)
edge:add (afnix:gfx:Vertex "hello")
edge:add (afnix:gfx:Vertex "world")
assert 2 (edge:degree)
# add the edge to the graph and check
g:add edge
assert 1 (g:number-of-edges)
assert 2 (g:number-of-vertices)
# check for nodes and edges
assert true (afnix:gfx:edge-p (g:get-edge 0))
assert true (afnix:gfx:vertex-p (g:get-vertex 0))
assert true (afnix:gfx:vertex-p (g:get-vertex 1))
STANDARD GRAPH REFERENCE
This appendix is a reference of the AFNIX standard graph module.
Symbol Description
afnix-gfx module
afnix:gfx nameset
Edge
The Edge class is a class used for a graph construction in association
with the Vertex class. An edge is used to connect vertices. Normally,
an edge connects two vertices. The number of vertices attached to an
edge is called the cardinality of that edge. A client object can also
be attached to the class.
Predicate
edge-p
Inheritance
Object
Constructors
Edge (none)
The Edge constructor create an empty edge.
Edge (Object)
The Edge constructor create an edge with a client object.
Methods
reset -> none (none)
The reset method reset all vertices attached to the edge.
cardinality -> Integer (none)
The cardinality method returns the cardinality of the edge. The
cardinality of an edge is the number of attached vertices.
add -> Vertex (Vertex)
The add method attach a vertex to this edge. The method return
the argument vertex.
get -> Vertex (Integer)
The get method returns the attached vertex by index. If the
index is out-of range, and exception is raised.
get-client -> Object (none)
The get-client method returns the edge client object. If the
client object is not set, nil is returned.
set-client -> Object (Object)
The set-client method sets the edge client object. The object is
returned by this method.
Vertex
The Vertex class is a class used for a graph construction in
association with the Edge class. An vertex is an edge node. The number
of edges referenced by a vertex is called the degree of that vertex. A
client object can also be attached to the object.
Predicate
vertex-p
Inheritance
Object
Constructors
Vertex (none)
The Vertex constructor create an empty vertex.
Vertex (Object)
The Vertex constructor create a vertex with a client object.
Methods
reset -> none (none)
The reset method reset all edges attached to the vertex.
degree -> Integer (none)
The degree method returns the degree of the vertex. The degree
of a vertex is the number of referenced edges.
add -> Edge (Edge)
The add method references an edge with this vertex. The method
return the argument edge.
get -> Edge (Integer)
The get method returns the referenced edge by index. If the
index is out-of range, and exception is raised.
get-client -> Object (none)
The get-client method returns the vertex client object. If the
client object is not set, nil is returned.
set-client -> Object (Object)
The set-client method sets the vertex client object. The object
is returned by this method.
Graph
The Graph object is a general graph class that manages a set of edges
and vertices. The graph operates by adding edges and vertices to it.
The graph object also accepts a client object in a way similar to the
Edge and Vertex classes
Predicate
graph-p
Inheritance
Object
Constructors
Graph (none)
The Graph constructor create an empty graph.
Graph (Object)
The Graph constructor create a graph with a client object.
Methods
reset -> none (none)
The reset method reset the graph
reset-edges -> none (none)
The reset-edges method reset all edges attached to the graph.
reset-vertices -> none (none)
The reset-vertices method reset all vertices attached to the
graph.
add -> Object (Vertex|Edge)
The add method adds a vertex or an edge to the graph. When
adding an edge, the methods check that the source and target
vertices are also part of the graph.
exists -> Boolean (Vertex|Edge)
The exists method returns true if the vertex or edge argument
exists in the graph.
get-edge -> Edge (Integer)
The get-edge method returns an edge by index. If the index is
out-of-range, an exception is raised.
get-vertex -> Vertex (Integer)
The get-vertex method returns a vertex by index. If the index is
out-of-range, an exception is raised.
number-of-vertices -> Integer (none)
The number-of-vertices methods returns the number of vertices in
the graph.
number-of-edges -> Integer (none)
The number-of-edges methods returns the number of edges in the
graph.
get-client -> Object (none)
The get-client method returns the graph client object. If the
client object is not set, nil is returned.
set-client -> Object (Object)
The set-client method sets the graph client object. The object
is returned by this method.