Man Linux: Main Page and Category List

## NAME

```       gfx - standard graph module

```

## STANDARDGRAPHSERVICES

```       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)
assert 2   (edge:degree)
# add the edge to the graph and check
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))

```

## STANDARDGRAPHREFERENCE

```       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.
```