kpeter@28
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@28
|
2 |
*
|
kpeter@28
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@28
|
4 |
*
|
kpeter@32
|
5 |
* Copyright (C) 2003-2010
|
kpeter@28
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@28
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@28
|
8 |
*
|
kpeter@28
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@28
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@28
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@28
|
12 |
*
|
kpeter@28
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@28
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@28
|
15 |
* purpose.
|
kpeter@28
|
16 |
*
|
kpeter@28
|
17 |
*/
|
kpeter@28
|
18 |
|
kpeter@28
|
19 |
namespace lemon {
|
kpeter@28
|
20 |
/**
|
kpeter@28
|
21 |
[PAGE]sec_graph_structures[PAGE] Graph Structures
|
kpeter@28
|
22 |
|
kpeter@28
|
23 |
The implementation of combinatorial algorithms heavily relies on
|
kpeter@28
|
24 |
efficient graph structures. Diverse applications require the
|
kpeter@28
|
25 |
usage of different physical graph storages.
|
kpeter@46
|
26 |
Until now, we used two general graph structures, \ref ListDigraph
|
kpeter@46
|
27 |
and \ref ListGraph. Apart from these types, LEMON also provides several
|
kpeter@28
|
28 |
other classes for handling directed and undirected graphs to meet the
|
kpeter@28
|
29 |
diverging requirements of the possible users. In order to save on running
|
kpeter@28
|
30 |
time or on memory usage, some structures may fail to support some graph
|
kpeter@28
|
31 |
features like node or arc/edge deletion.
|
kpeter@28
|
32 |
You are free to use the graph structure that fit your requirements the best,
|
kpeter@28
|
33 |
since most graph algorithms and auxiliary data structures can be used
|
kpeter@28
|
34 |
with any of them.
|
kpeter@28
|
35 |
|
kpeter@28
|
36 |
|
kpeter@28
|
37 |
[SEC]sec_graph_concepts[SEC] Graph Concepts
|
kpeter@28
|
38 |
|
kpeter@28
|
39 |
In LEMON, there are various graph types, which are rather different, but
|
kpeter@28
|
40 |
they all conform to the corresponding \ref graph_concepts "graph concept",
|
kpeter@32
|
41 |
which defines the common part of the graph interfaces.
|
kpeter@28
|
42 |
The \ref concepts::Digraph "Digraph concept" describes the common interface
|
kpeter@28
|
43 |
of directed graphs (without any sensible implementation), while
|
kpeter@28
|
44 |
the \ref concepts::Graph "Graph concept" describes the undirected graphs.
|
kpeter@38
|
45 |
A generic graph algorithm should only exploit the features of the
|
kpeter@38
|
46 |
corresponding graph concept so that it could be applied to any graph
|
kpeter@38
|
47 |
structure. (Such an algorithm should compile with the
|
kpeter@28
|
48 |
\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
|
kpeter@28
|
49 |
but it will not run properly, of course.)
|
kpeter@28
|
50 |
|
kpeter@28
|
51 |
The graph %concepts define the member classes for the iterators and maps
|
kpeter@28
|
52 |
along with some useful basic functions for obtaining the identifiers of
|
kpeter@28
|
53 |
the items, the end nodes of the arcs (or edges) and their iterators,
|
kpeter@32
|
54 |
etc.
|
kpeter@28
|
55 |
An actual graph implementation may have various additional functionalities
|
kpeter@28
|
56 |
according to its purpose.
|
kpeter@28
|
57 |
|
kpeter@38
|
58 |
Another advantage of this design is that you can write your own graph classes,
|
kpeter@38
|
59 |
if you would like to.
|
kpeter@38
|
60 |
As long as they provide the interface defined in one of the graph concepts,
|
kpeter@38
|
61 |
all the LEMON algorithms and classes will work with them properly.
|
kpeter@38
|
62 |
|
kpeter@28
|
63 |
|
kpeter@46
|
64 |
[SEC]sec_digraph_types[SEC] Directed Graph Structures
|
kpeter@28
|
65 |
|
kpeter@28
|
66 |
The already used \ref ListDigraph class is the most versatile directed
|
kpeter@38
|
67 |
graph structure. As its name suggests, it is based on linked lists,
|
kpeter@38
|
68 |
therefore iterating through its nodes and arcs is fast and it is quite
|
kpeter@38
|
69 |
flexible. Apart from the general digraph functionalities, it
|
kpeter@28
|
70 |
provides operations for adding and removing nodes and arcs, changing
|
kpeter@28
|
71 |
the source or target node of an arc, and contracting and splitting nodes
|
kpeter@28
|
72 |
or arcs.
|
kpeter@28
|
73 |
|
kpeter@28
|
74 |
\ref SmartDigraph is another general digraph implementation, which is
|
kpeter@28
|
75 |
significantly more efficient (both in terms of space and time), but it
|
kpeter@28
|
76 |
provides less functionality. For example, nodes and arcs cannot be
|
kpeter@32
|
77 |
removed from it.
|
kpeter@28
|
78 |
|
kpeter@38
|
79 |
The \ref StaticDigraph structure is even more optimized for efficiency,
|
kpeter@38
|
80 |
but it is completely static. It requires less space in memory and
|
kpeter@38
|
81 |
provides faster item iteration than \ref ListDigraph and \ref
|
kpeter@38
|
82 |
SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
|
kpeter@38
|
83 |
"OutArcIt" iterators, since its arcs are stored in an appropriate order.
|
kpeter@50
|
84 |
However, you can neither add nor delete arcs or nodes, the graph
|
kpeter@50
|
85 |
has to be built at once and other modifications are not supported.
|
kpeter@38
|
86 |
|
kpeter@28
|
87 |
\ref FullDigraph is an efficient implementation of a directed full graph.
|
kpeter@50
|
88 |
This structure is also completely static and it needs constant space
|
kpeter@50
|
89 |
in memory.
|
kpeter@28
|
90 |
|
kpeter@28
|
91 |
|
kpeter@46
|
92 |
[SEC]sec_graph_types[SEC] Undirected Graph Structures
|
kpeter@28
|
93 |
|
kpeter@46
|
94 |
The general undirected graph classes, \ref ListGraph and \ref SmartGraph
|
kpeter@46
|
95 |
have similar implementations as their directed variants.
|
kpeter@50
|
96 |
Therefore, \ref SmartGraph is more efficient, but \ref ListGraph provides
|
kpeter@46
|
97 |
more functionality.
|
kpeter@46
|
98 |
In addition to these general structures, LEMON also provides special purpose
|
kpeter@46
|
99 |
undirected graph types for handling \ref FullGraph "full graphs",
|
kpeter@46
|
100 |
\ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".
|
kpeter@28
|
101 |
|
kpeter@28
|
102 |
[TRAILER]
|
kpeter@28
|
103 |
*/
|
kpeter@28
|
104 |
}
|