Changeset 38:236e7061b70d in lemontutorial for graphs.dox
 Timestamp:
 02/21/10 15:07:35 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

graphs.dox
r32 r38 43 43 of directed graphs (without any sensible implementation), while 44 44 the \ref concepts::Graph "Graph concept" describes the undirected graphs. 45 Any generic graph algorithm should only exploit the features of the 46 corresponding graph concept. (It should compile with the 45 A generic graph algorithm should only exploit the features of the 46 corresponding graph concept so that it could be applied to any graph 47 structure. (Such an algorithm should compile with the 47 48 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type, 48 49 but it will not run properly, of course.) … … 55 56 according to its purpose. 56 57 58 Another advantage of this design is that you can write your own graph classes, 59 if you would like to. 60 As long as they provide the interface defined in one of the graph concepts, 61 all the LEMON algorithms and classes will work with them properly. 62 57 63 58 64 [SEC]sec_digraph_types[SEC] Digraph Structures 59 65 60 66 The already used \ref ListDigraph class is the most versatile directed 61 graph structure. Apart from the general digraph functionalities, it 67 graph structure. As its name suggests, it is based on linked lists, 68 therefore iterating through its nodes and arcs is fast and it is quite 69 flexible. Apart from the general digraph functionalities, it 62 70 provides operations for adding and removing nodes and arcs, changing 63 71 the source or target node of an arc, and contracting and splitting nodes … … 69 77 removed from it. 70 78 79 The \ref StaticDigraph structure is even more optimized for efficiency, 80 but it is completely static. It requires less space in memory and 81 provides faster item iteration than \ref ListDigraph and \ref 82 SmartDigraph, especially using \ref concepts::Digraph::OutArcIt 83 "OutArcIt" iterators, since its arcs are stored in an appropriate order. 84 However, it only provides \ref StaticDigraph::build() "build()" and 85 \ref \ref StaticDigraph::clear() "clear()" functions and does not 86 support any other modification of the digraph. 87 71 88 \ref FullDigraph is an efficient implementation of a directed full graph. 72 This structure is completely static, so you can neither add nor delete73 arcs or nodes, andthe class needs constant space in memory.89 This structure is also completely static, so you can neither add nor delete 90 arcs or nodes, moreover, the class needs constant space in memory. 74 91 75 92
Note: See TracChangeset
for help on using the changeset viewer.