[GRASSweb-list]markus: web/dglib index.html,NONE,1.1 README.html,1.3,NONE

grass at intevation.de grass at intevation.de
Thu Feb 20 09:26:39 EST 2003

Author: markus

Update of /grassrepository/web/dglib
In directory doto:/tmp/cvs-serv345

Added Files:
Removed Files:
Log Message:
renamed README to index.html

--- NEW FILE: index.html ---
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   <title>DGLib -- a Directed Graph Library implementation</title>
   <DEFANGED_meta name="robots" content="index,follow">
   <DEFANGED_META Name="description" Content="DGLib -- a Directed Graph Library implementation">
   <DEFANGED_META Name="keywords" Content="gis, GIS, GRASS, open source, free
         software, network, vector, DGLib, direct graph">
   <DEFANGED_meta name="Author" content="(c) Roberto Micarelli">
   <DEFANGED_meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   <DEFANGED_link rel="stylesheet" type="text/css" href="sitestyle.css">

DGLib -- a Directed Graph Library implementation

Copyright (C) 2002 Roberto Micarelli
                    mi.ro at iol.it

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.


<a href="source/">Download source code</a>

The Directed Graph Library or DGLib (Micarelli 2002) provides
functionality for vector network analysis. This library released under GPL
is hosted by the GRASS project (in the CVS server). As stand-alone library
it may also be used by other software project.
A graph is a system of logical connections between a collection of objects
called vertices. Graphs are usually represented by a picture, so that each
vertex is shown as a point, with the connections shown as line segments.
These vertices are also commonly referred to as nodes, edges referred to as
arcs. A directed graph (digraph) consists of a finite set of vertices, and a
finite set of edges, where an edge is an ordered pair of vertices. A
directed graph has the property that edges have a direction, this is the
reason for defining an edge as an <i>ordered</i> pair of vertices often
referred to as the <i>head</i> and the <i>tail</i> of the edge.
The original design idea behind DGLib was to support middle sized graphs in
RAM with a near-static structure that doesn't need to be dynamically
modified by the user program; ability to read graphs from input streams and
process them with no needle to rebuild internal trees.  A representation has
been defined, where graph data is stored in 32bit word arrays and each
element pointer is converted to a relative offset.  This representation is
<i>serializable</i> from/to input/output streams and allows fast
load-and-use processing.  Graphs need to be de-serialized in order to be
edited.  In further refactorings the library has evolved to support dynamic
changes and state-independent algorithm (algorithms can be run on both
serializable or editable graphs).
DGLib defines a serializable graph as being in FLAT state and a editable
graph as being in TREE state. The implementation makes intensive use of
<i>libavl</i> (http://www.msu.edu/~pfaffben/avl/) AVL data structures to
support TREE state.
So far DGLib defines three different graph versions, version 1 supports
directed graph with a weak concept of the edge, it can support many
applications where one doesn't need to know about the input edges of a node
(in-degree) and where there is no requirement to directly retrieve edges by
their identifier but only by head/tail combinations. Version 2 adds
in-degree support and a true edge addressing, yet supporting directed graph. 
Version 3 uses the same internal representation of version 2 but activates
code branches to support undirected graphs.
The DGLib user can control a number of static features and can attach a
arbitrary amount of data to each node (node-attributes) and each edge
(edge-attributes). Attributes are not considered to be part of the graph
structure and can be edited also when the graph is in FLAT state.
Graph traversal in neither recursive nor hook (callback) based, but built on
the use of <i>traversers</i> for nodes and edges. By default, traversal is
ordered by node and edge identifiers but can optionally be ordered by other
means. For example, it is often useful to visit edges on a <i>weight</i>
  order} basis (greedy algorithm), this is possible via <i>prioritizers</i>
that are activated by setting specific <i>graph options</i>.
Both preemptive (blocking) and non-preemptive (non-blocking/multiplexed) I/O
is supported, although GRASS does not actually use graph storage it may be
easily required by any other library user. Thread safety is so far ensured
by a data separation design that keeps all application context states into
stack containers, whose life cycle is controlled by the user program. Each
graph is a separate container and two or more graphs never conflict. In
addition algorithms (ie. shortest path) can safely share the same graph,
while concurrent editing on the same graph is unsafe.
As DGLib is under development, only a bunch of polynomial time algorithms
have been implemented, and the basic structure is being stressed to be a
mature core to possibly time wasting computations. Current algorithms are:
<i>shortest path</i>, <i>depth spanning</i>, and <i>minimum spanning</i>. 
Spanning algorithms silently behave as arborescenses when applied to
directed graphs. A clip callback function, optionally supplied by the user,
comes called by the library while traversing the graph in order to alter
default algorithm behavior (i.e. user can control access to specific graph
segments while computing shortest path).
The Directed Graph Library library provides functionality to assign costs to
lines and/or nodes. That means that costs can be accumulated while traveling
along polylines. The user can assign individual costs to all lines and/or
nodes of a vector map and later calculate shortest path connections based on
the accumulated costs. Applications are transport analysis, connectivity and
<i> Text cited from:</i><br>

R. Blazek, M. Neteler, R. Micarelli (2002): The new GRASS 5.1 vector
architecture. Proc. Open source GIS -- GRASS users conference 2002, Trento,
Italy, 11-13 September 2002 (<a href=http://www.ing.unitn.it/~grass/conferences/GRASS2002/proceedings/proceedings/pdfs/Blazek_Radim.pdf>PDF</a>)

<a href=http://mpa.itc.it/radim/g51/d.path.jpg>Screenshot of DGLib usage</a> in <a href=http://grass.itc.it/grass51/>GRASS 5.1</a>


<DIV ALIGN=right><font size=-1><i>Last change:
$Date: 2003/02/20 14:26:37 $

--- README.html DELETED ---

More information about the grass-web mailing list