COIN-OR::LEMON - Graph Library

Changeset 38:236e7061b70d in lemon-tutorial


Ignore:
Timestamp:
02/21/10 15:07:35 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Extend the graphs section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • graphs.dox

    r32 r38  
    4343of directed graphs (without any sensible implementation), while 
    4444the \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 
     45A generic graph algorithm should only exploit the features of the 
     46corresponding graph concept so that it could be applied to any graph 
     47structure. (Such an algorithm should compile with the 
    4748\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type, 
    4849but it will not run properly, of course.) 
     
    5556according to its purpose. 
    5657 
     58Another advantage of this design is that you can write your own graph classes, 
     59if you would like to. 
     60As long as they provide the interface defined in one of the graph concepts, 
     61all the LEMON algorithms and classes will work with them properly. 
     62 
    5763 
    5864[SEC]sec_digraph_types[SEC] Digraph Structures 
    5965 
    6066The already used \ref ListDigraph class is the most versatile directed 
    61 graph structure. Apart from the general digraph functionalities, it 
     67graph structure. As its name suggests, it is based on linked lists, 
     68therefore iterating through its nodes and arcs is fast and it is quite 
     69flexible. Apart from the general digraph functionalities, it 
    6270provides operations for adding and removing nodes and arcs, changing 
    6371the source or target node of an arc, and contracting and splitting nodes 
     
    6977removed from it. 
    7078 
     79The \ref StaticDigraph structure is even more optimized for efficiency, 
     80but it is completely static. It requires less space in memory and 
     81provides faster item iteration than \ref ListDigraph and \ref 
     82SmartDigraph, especially using \ref concepts::Digraph::OutArcIt 
     83"OutArcIt" iterators, since its arcs are stored in an appropriate order. 
     84However, it only provides \ref StaticDigraph::build() "build()" and 
     85\ref \ref StaticDigraph::clear() "clear()" functions and does not 
     86support any other modification of the digraph. 
     87  
    7188\ref FullDigraph is an efficient implementation of a directed full graph. 
    72 This structure is completely static, so you can neither add nor delete 
    73 arcs or nodes, and the class needs constant space in memory. 
     89This structure is also completely static, so you can neither add nor delete 
     90arcs or nodes, moreover, the class needs constant space in memory. 
    7491 
    7592 
Note: See TracChangeset for help on using the changeset viewer.