[GRASSweb-list]markus: web/dglib README.html,1.1,1.2

grass at intevation.de grass at intevation.de
Thu Oct 10 11:05:28 EDT 2002

Author: markus

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

Modified Files:
Log Message:
new DGLib page, taken from our paper

Index: README.html
RCS file: /grassrepository/web/dglib/README.html,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- README.html	14 Jun 2002 15:45:19 -0000	1.1
+++ README.html	10 Oct 2002 15:05:25 -0000	1.2
@@ -1,9 +1,12 @@
-LIBDGL -- a Directed Graph Library implementation
+DGLib -- a Directed Graph Library implementation
 </title></head><body BGCOLOR=#FFFFFF>
-LIBDGL -- a Directed Graph Library implementation
+DGLib -- a Directed Graph Library implementation
 Copyright (C) 2002 Roberto Micarelli
                     mi.ro at iol.it
@@ -20,62 +23,102 @@
  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.
- Dglib (Directed Graph Library) aims at giving support to network analysis. 
- Each graph is stored in a graph-context of type gnGrpGraph_s.  At any given
- point in time a graph can be in one of three states: EMPTY, TREE, FLAT.  We
- take a look of what these states mean:
- 1) EMPTY state 
-        This is the state of a graph after initialization and before any
-        network data is put into it. In EMPTY state the only reasonable
-        thing to do with the graph is to add links (also called arcs) into
-        it. This is done by gnGrpAddLink().  After the first link has been
-        added the state of the graph changes to TREE.
- 2) TREE state
-	This is the state optimized to support graph modifications, since
-	all data is kept internally stored in binary search trees. The
-	operations that can be performed on a TREE graph are:
-	- gnGrpAddLink() - add links;
-	- gnGrpFlatten() - convert the graph to FLAT state;
-	- gnGrp{Set|Get}NodeAttr() - set/get extended attributes for a node;
-	- gnGrp{Set|Get}LinkAttr() - set/get extended attributes for a link;
-	- gnGrpGetNode() - return pointer to a node
-	- gnGrpGetLinkArea() - return pointer to a link-area 
-	- gnGrpGetLink() - return pointer to a link
-	- gnGrpRelease() - release graph's resources.
- 3) FLAT state
-	In this state the graph is 'serializable', which is: it can be
-	written to a file or a stream. The binaru tree data representation
-	is transformed into arrays of 32 bit words with pointers stored as
-	offsets.  Network analysis functions apply to FLAT state graphs.
-	When a FLAT graph is read from a file or stream it is ready for
-	analisys with no further initialization.
-	The operations that can be performed on a FLAT graph are:
-	- gnGrpUnflatten() - convert the graph back to TREE state;
-	- gnGrpWrite() - write the graph to a user supplied file descriptor;
-	- gnGrpRead() - read the graph from a user supplied file descriptor;
-	- gnGrp{Set|Get}NodeAttr() - set/get extended attributes for a node;
-	- gnGrp{Set|Get}LinkAttr() - set/get extended attributes for a link;
-	- gnGrpShortestPath() - perform a shortest path search;
-	- gnGrpGetNode() - return pointer to a node
-	- gnGrpGetLinkArea() - return pointer to a link-area 
-	- gnGrpGetLink() - return pointer to a link
-	- gnGrpRelease() - discard the graph.
+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/proceedings/proceedings/pdfs/Blazek_Radim.pdf>PDF</a>)
-<a href=http://mpa.itc.it/radim/g51/d.path.jpg>Screenshot</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>
-DGLib users:
-- GRASS 5.1
-  <a href=http://grass.itc.it/grass51/>http://grass.itc.it/grass51/</a>
+<DIV ALIGN=right><font size=-1><i>Last change:

More information about the grass-web mailing list