Changeset 38:236e7061b70d in lemon-tutorial

Timestamp:

02/21/10 15:07:35 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Extend the graphs section

File:

• graphs.dox (modified) (3 diffs)

graphs.dox

@@ -43 +43 @@
 of directed graphs (without any sensible implementation), while
 the \ref concepts::Graph "Graph concept" describes the undirected graphs.
-Any generic graph algorithm should only exploit the features of the
-corresponding graph concept. (It should compile with the
+A generic graph algorithm should only exploit the features of the
+corresponding graph concept so that it could be applied to any graph
+structure. (Such an algorithm should compile with the
 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
 but it will not run properly, of course.)
@@ -55 +56 @@
 according to its purpose.
 
+Another advantage of this design is that you can write your own graph classes,
+if you would like to.
+As long as they provide the interface defined in one of the graph concepts,
+all the LEMON algorithms and classes will work with them properly.
+
 
 [SEC]sec_digraph_types[SEC] Digraph Structures
 
 The already used \ref ListDigraph class is the most versatile directed
-graph structure. Apart from the general digraph functionalities, it
+graph structure. As its name suggests, it is based on linked lists,
+therefore iterating through its nodes and arcs is fast and it is quite
+flexible. Apart from the general digraph functionalities, it
 provides operations for adding and removing nodes and arcs, changing
 the source or target node of an arc, and contracting and splitting nodes
@@ -69 +77 @@
 removed from it.
 
+The \ref StaticDigraph structure is even more optimized for efficiency,
+but it is completely static. It requires less space in memory and
+provides faster item iteration than \ref ListDigraph and \ref
+SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
+"OutArcIt" iterators, since its arcs are stored in an appropriate order.
+However, it only provides \ref StaticDigraph::build() "build()" and
+\ref \ref StaticDigraph::clear() "clear()" functions and does not
+support any other modification of the digraph.
+ 
 \ref FullDigraph is an efficient implementation of a directed full graph.
-This structure is completely static, so you can neither add nor delete
-arcs or nodes, and the class needs constant space in memory.
+This structure is also completely static, so you can neither add nor delete
+arcs or nodes, moreover, the class needs constant space in memory.