[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:
README.html
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 @@
<html><head><title>
-LIBDGL -- a Directed Graph Library implementation
+DGLib -- a Directed Graph Library implementation
</title></head><body BGCOLOR=#FFFFFF>
-<pre>
-LIBDGL -- a Directed Graph Library implementation
+<h2>
+DGLib -- a Directed Graph Library implementation
+</h2>
+
+<pre>
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.
+</pre>
+<hr>
---------------------------------------------------------------------------
-
- 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.
+<p>
+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.
+<p>
+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).
+<p>
+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.
+<p>
+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.
+<p>
+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.
+<p>
+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>.
+<p>
+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.
+<p>
+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).
+<p>
+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
+more.
+<p>
+<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>
+<p>
+<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>
+<p>
-</pre>
+<DIV ALIGN=right><font size=-1><i>Last change:
+$Date$
+</i></font></DIV>
</body>
</html>
More information about the grass-web
mailing list