kpeter@28: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@28:  *
kpeter@28:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@28:  *
kpeter@32:  * Copyright (C) 2003-2010
kpeter@28:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@28:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@28:  *
kpeter@28:  * Permission to use, modify and distribute this software is granted
kpeter@28:  * provided that this copyright notice appears in all copies. For
kpeter@28:  * precise terms see the accompanying LICENSE file.
kpeter@28:  *
kpeter@28:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@28:  * express or implied, and with no claim as to its suitability for any
kpeter@28:  * purpose.
kpeter@28:  *
kpeter@28:  */
kpeter@28: 
kpeter@28: namespace lemon {
kpeter@28: /**
kpeter@28: [PAGE]sec_graph_structures[PAGE] Graph Structures
kpeter@28: 
kpeter@28: The implementation of combinatorial algorithms heavily relies on
kpeter@28: efficient graph structures. Diverse applications require the
kpeter@28: usage of different physical graph storages.
kpeter@46: Until now, we used two general graph structures, \ref ListDigraph
kpeter@46: and \ref ListGraph. Apart from these types, LEMON also provides several
kpeter@28: other classes for handling directed and undirected graphs to meet the
kpeter@28: diverging requirements of the possible users. In order to save on running
kpeter@28: time or on memory usage, some structures may fail to support some graph
kpeter@28: features like node or arc/edge deletion.
kpeter@28: You are free to use the graph structure that fit your requirements the best,
kpeter@28: since most graph algorithms and auxiliary data structures can be used
kpeter@28: with any of them.
kpeter@28: 
kpeter@28: 
kpeter@28: [SEC]sec_graph_concepts[SEC] Graph Concepts
kpeter@28: 
kpeter@28: In LEMON, there are various graph types, which are rather different, but
kpeter@28: they all conform to the corresponding \ref graph_concepts "graph concept",
kpeter@32: which defines the common part of the graph interfaces.
kpeter@28: The \ref concepts::Digraph "Digraph concept" describes the common interface
kpeter@28: of directed graphs (without any sensible implementation), while
kpeter@28: the \ref concepts::Graph "Graph concept" describes the undirected graphs.
kpeter@38: A generic graph algorithm should only exploit the features of the
kpeter@38: corresponding graph concept so that it could be applied to any graph
kpeter@38: structure. (Such an algorithm should compile with the
kpeter@28: \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
kpeter@28: but it will not run properly, of course.)
kpeter@28: 
kpeter@28: The graph %concepts define the member classes for the iterators and maps
kpeter@28: along with some useful basic functions for obtaining the identifiers of
kpeter@28: the items, the end nodes of the arcs (or edges) and their iterators,
kpeter@32: etc.
kpeter@28: An actual graph implementation may have various additional functionalities
kpeter@28: according to its purpose.
kpeter@28: 
kpeter@38: Another advantage of this design is that you can write your own graph classes,
kpeter@38: if you would like to.
kpeter@38: As long as they provide the interface defined in one of the graph concepts,
kpeter@38: all the LEMON algorithms and classes will work with them properly.
kpeter@38: 
kpeter@28: 
kpeter@46: [SEC]sec_digraph_types[SEC] Directed Graph Structures
kpeter@28: 
kpeter@28: The already used \ref ListDigraph class is the most versatile directed
kpeter@38: graph structure. As its name suggests, it is based on linked lists,
kpeter@38: therefore iterating through its nodes and arcs is fast and it is quite
kpeter@38: flexible. Apart from the general digraph functionalities, it
kpeter@28: provides operations for adding and removing nodes and arcs, changing
kpeter@28: the source or target node of an arc, and contracting and splitting nodes
kpeter@28: or arcs.
kpeter@28: 
kpeter@28: \ref SmartDigraph is another general digraph implementation, which is
kpeter@28: significantly more efficient (both in terms of space and time), but it
kpeter@28: provides less functionality. For example, nodes and arcs cannot be
kpeter@32: removed from it.
kpeter@28: 
kpeter@38: The \ref StaticDigraph structure is even more optimized for efficiency,
kpeter@38: but it is completely static. It requires less space in memory and
kpeter@38: provides faster item iteration than \ref ListDigraph and \ref
kpeter@38: SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
kpeter@38: "OutArcIt" iterators, since its arcs are stored in an appropriate order.
kpeter@50: However, you can neither add nor delete arcs or nodes, the graph
kpeter@50: has to be built at once and other modifications are not supported.
kpeter@38:  
kpeter@28: \ref FullDigraph is an efficient implementation of a directed full graph.
kpeter@50: This structure is also completely static and it needs constant space
kpeter@50: in memory.
kpeter@28: 
kpeter@28: 
kpeter@46: [SEC]sec_graph_types[SEC] Undirected Graph Structures
kpeter@28: 
kpeter@46: The general undirected graph classes, \ref ListGraph and \ref SmartGraph
kpeter@46: have similar implementations as their directed variants.
kpeter@50: Therefore, \ref SmartGraph is more efficient, but \ref ListGraph provides
kpeter@46: more functionality.
kpeter@46: In addition to these general structures, LEMON also provides special purpose
kpeter@46: undirected graph types for handling \ref FullGraph "full graphs",
kpeter@46: \ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".
kpeter@28: 
kpeter@28: [TRAILER]
kpeter@28: */
kpeter@28: }