1.1 --- a/graphs.dox Sat Feb 20 21:54:52 2010 +0100
1.2 +++ b/graphs.dox Sun Feb 21 15:07:35 2010 +0100
1.3 @@ -42,8 +42,9 @@
1.4 The \ref concepts::Digraph "Digraph concept" describes the common interface
1.5 of directed graphs (without any sensible implementation), while
1.6 the \ref concepts::Graph "Graph concept" describes the undirected graphs.
1.7 -Any generic graph algorithm should only exploit the features of the
1.8 -corresponding graph concept. (It should compile with the
1.9 +A generic graph algorithm should only exploit the features of the
1.10 +corresponding graph concept so that it could be applied to any graph
1.11 +structure. (Such an algorithm should compile with the
1.12 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
1.13 but it will not run properly, of course.)
1.14
1.15 @@ -54,11 +55,18 @@
1.16 An actual graph implementation may have various additional functionalities
1.17 according to its purpose.
1.18
1.19 +Another advantage of this design is that you can write your own graph classes,
1.20 +if you would like to.
1.21 +As long as they provide the interface defined in one of the graph concepts,
1.22 +all the LEMON algorithms and classes will work with them properly.
1.23 +
1.24
1.25 [SEC]sec_digraph_types[SEC] Digraph Structures
1.26
1.27 The already used \ref ListDigraph class is the most versatile directed
1.28 -graph structure. Apart from the general digraph functionalities, it
1.29 +graph structure. As its name suggests, it is based on linked lists,
1.30 +therefore iterating through its nodes and arcs is fast and it is quite
1.31 +flexible. Apart from the general digraph functionalities, it
1.32 provides operations for adding and removing nodes and arcs, changing
1.33 the source or target node of an arc, and contracting and splitting nodes
1.34 or arcs.
1.35 @@ -68,9 +76,18 @@
1.36 provides less functionality. For example, nodes and arcs cannot be
1.37 removed from it.
1.38
1.39 +The \ref StaticDigraph structure is even more optimized for efficiency,
1.40 +but it is completely static. It requires less space in memory and
1.41 +provides faster item iteration than \ref ListDigraph and \ref
1.42 +SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
1.43 +"OutArcIt" iterators, since its arcs are stored in an appropriate order.
1.44 +However, it only provides \ref StaticDigraph::build() "build()" and
1.45 +\ref \ref StaticDigraph::clear() "clear()" functions and does not
1.46 +support any other modification of the digraph.
1.47 +
1.48 \ref FullDigraph is an efficient implementation of a directed full graph.
1.49 -This structure is completely static, so you can neither add nor delete
1.50 -arcs or nodes, and the class needs constant space in memory.
1.51 +This structure is also completely static, so you can neither add nor delete
1.52 +arcs or nodes, moreover, the class needs constant space in memory.
1.53
1.54
1.55 [SEC]sec_undir_graphs[SEC] Undirected Graphs