r148:4e2581021300
Thu, 24 Apr 2008 11:56:44
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -33,154 +33,101 @@ |
| 33 | 33 |
#include <lemon/bits/alteration_notifier.h> |
| 34 | 34 |
#include <lemon/bits/default_map.h> |
| 35 | 35 |
|
| 36 | 36 |
///\ingroup gutils |
| 37 | 37 |
///\file |
| 38 | 38 |
///\brief Graph utilities. |
| 39 | 39 |
|
| 40 | 40 |
namespace lemon {
|
| 41 | 41 |
|
| 42 | 42 |
/// \addtogroup gutils |
| 43 | 43 |
/// @{
|
| 44 | 44 |
|
| 45 |
namespace _graph_utils_bits {
|
|
| 46 |
template <typename Graph> |
|
| 47 |
struct Node { typedef typename Graph::Node type; };
|
|
| 48 |
|
|
| 49 |
template <typename Graph> |
|
| 50 |
struct NodeIt { typedef typename Graph::NodeIt type; };
|
|
| 51 |
|
|
| 52 |
template <typename Graph> |
|
| 53 |
struct Arc { typedef typename Graph::Arc type; };
|
|
| 54 |
|
|
| 55 |
template <typename Graph> |
|
| 56 |
struct ArcIt { typedef typename Graph::ArcIt type; };
|
|
| 57 |
|
|
| 58 |
template <typename Graph> |
|
| 59 |
struct Edge { typedef typename Graph::Edge type; };
|
|
| 60 |
|
|
| 61 |
template <typename Graph> |
|
| 62 |
struct EdgeIt { typedef typename Graph::EdgeIt type; };
|
|
| 63 |
|
|
| 64 |
template <typename Graph> |
|
| 65 |
struct OutArcIt { typedef typename Graph::OutArcIt type; };
|
|
| 66 |
|
|
| 67 |
template <typename Graph> |
|
| 68 |
struct InArcIt { typedef typename Graph::InArcIt type; };
|
|
| 69 |
|
|
| 70 |
template <typename Graph> |
|
| 71 |
struct IncEdgeIt { typedef typename Graph::IncEdgeIt type; };
|
|
| 72 |
|
|
| 73 |
template <typename Graph> |
|
| 74 |
struct BoolNodeMap {
|
|
| 75 |
typedef typename Graph::template NodeMap<bool> type; |
|
| 76 |
}; |
|
| 77 |
|
|
| 78 |
template <typename Graph> |
|
| 79 |
struct IntNodeMap {
|
|
| 80 |
typedef typename Graph::template NodeMap<int> type; |
|
| 81 |
}; |
|
| 82 |
|
|
| 83 |
template <typename Graph> |
|
| 84 |
struct DoubleNodeMap {
|
|
| 85 |
typedef typename Graph::template NodeMap<double> type; |
|
| 86 |
}; |
|
| 87 |
|
|
| 88 |
template <typename Graph> |
|
| 89 |
struct BoolArcMap {
|
|
| 90 |
typedef typename Graph::template ArcMap<bool> type; |
|
| 91 |
}; |
|
| 92 |
|
|
| 93 |
template <typename Graph> |
|
| 94 |
struct IntArcMap {
|
|
| 95 |
typedef typename Graph::template ArcMap<int> type; |
|
| 96 |
}; |
|
| 97 |
|
|
| 98 |
template <typename Graph> |
|
| 99 |
struct DoubleArcMap {
|
|
| 100 |
typedef typename Graph::template ArcMap<double> type; |
|
| 101 |
}; |
|
| 102 |
|
|
| 103 |
template <typename Graph> |
|
| 104 |
struct BoolEdgeMap {
|
|
| 105 |
typedef typename Graph::template EdgeMap<bool> type; |
|
| 106 |
}; |
|
| 107 |
|
|
| 108 |
template <typename Graph> |
|
| 109 |
struct IntEdgeMap {
|
|
| 110 |
typedef typename Graph::template EdgeMap<int> type; |
|
| 111 |
}; |
|
| 112 |
|
|
| 113 |
template <typename Graph> |
|
| 114 |
struct DoubleEdgeMap {
|
|
| 115 |
typedef typename Graph::template EdgeMap<double> type; |
|
| 116 |
}; |
|
| 117 |
|
|
| 118 |
|
|
| 119 |
} |
|
| 120 |
|
|
| 121 | 45 |
///Creates convenience typedefs for the digraph types and iterators |
| 122 | 46 |
|
| 123 | 47 |
///This \c \#define creates convenience typedefs for the following types |
| 124 | 48 |
///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, |
| 125 | 49 |
///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
| 126 |
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
|
| 50 |
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
|
| 51 |
/// |
|
| 52 |
///\note If the graph type is a dependent type, ie. the graph type depend |
|
| 53 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
|
| 54 |
///macro. |
|
| 127 | 55 |
#define DIGRAPH_TYPEDEFS(Digraph) \ |
| 128 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 129 |
Node<Digraph>::type Node; \ |
|
| 130 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 131 |
NodeIt<Digraph>::type NodeIt; \ |
|
| 132 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 133 |
Arc<Digraph>::type Arc; \ |
|
| 134 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 135 |
ArcIt<Digraph>::type ArcIt; \ |
|
| 136 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 137 |
OutArcIt<Digraph>::type OutArcIt; \ |
|
| 138 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 139 |
InArcIt<Digraph>::type InArcIt; \ |
|
| 140 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 141 |
BoolNodeMap<Digraph>::type BoolNodeMap; \ |
|
| 142 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 143 |
IntNodeMap<Digraph>::type IntNodeMap; \ |
|
| 144 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 145 |
DoubleNodeMap<Digraph>::type DoubleNodeMap; \ |
|
| 146 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 147 |
BoolArcMap<Digraph>::type BoolArcMap; \ |
|
| 148 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 149 |
IntArcMap<Digraph>::type IntArcMap; \ |
|
| 150 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 151 |
DoubleArcMap<Digraph>::type DoubleArcMap |
|
| 56 |
typedef Digraph::Node Node; \ |
|
| 57 |
typedef Digraph::NodeIt NodeIt; \ |
|
| 58 |
typedef Digraph::Arc Arc; \ |
|
| 59 |
typedef Digraph::ArcIt ArcIt; \ |
|
| 60 |
typedef Digraph::InArcIt InArcIt; \ |
|
| 61 |
typedef Digraph::OutArcIt OutArcIt; \ |
|
| 62 |
typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
|
| 63 |
typedef Digraph::NodeMap<int> IntNodeMap; \ |
|
| 64 |
typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
|
| 65 |
typedef Digraph::ArcMap<bool> BoolArcMap; \ |
|
| 66 |
typedef Digraph::ArcMap<int> IntArcMap; \ |
|
| 67 |
typedef Digraph::ArcMap<double> DoubleArcMap |
|
| 152 | 68 |
|
| 69 |
///Creates convenience typedefs for the digraph types and iterators |
|
| 153 | 70 |
|
| 71 |
///\see DIGRAPH_TYPEDEFS |
|
| 72 |
/// |
|
| 73 |
///\note Use this macro, if the graph type is a dependent type, |
|
| 74 |
///ie. the graph type depend on a template parameter. |
|
| 75 |
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ |
|
| 76 |
typedef typename Digraph::Node Node; \ |
|
| 77 |
typedef typename Digraph::NodeIt NodeIt; \ |
|
| 78 |
typedef typename Digraph::Arc Arc; \ |
|
| 79 |
typedef typename Digraph::ArcIt ArcIt; \ |
|
| 80 |
typedef typename Digraph::InArcIt InArcIt; \ |
|
| 81 |
typedef typename Digraph::OutArcIt OutArcIt; \ |
|
| 82 |
typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
|
| 83 |
typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
|
| 84 |
typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
|
| 85 |
typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
|
| 86 |
typedef typename Digraph::template ArcMap<int> IntArcMap; \ |
|
| 87 |
typedef typename Digraph::template ArcMap<double> DoubleArcMap |
|
| 88 |
|
|
| 154 | 89 |
///Creates convenience typedefs for the graph types and iterators |
| 155 | 90 |
|
| 156 | 91 |
///This \c \#define creates the same convenience typedefs as defined |
| 157 | 92 |
///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates |
| 158 | 93 |
///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, |
| 159 | 94 |
///\c DoubleEdgeMap. |
| 95 |
/// |
|
| 96 |
///\note If the graph type is a dependent type, ie. the graph type depend |
|
| 97 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
|
| 98 |
///macro. |
|
| 160 | 99 |
#define GRAPH_TYPEDEFS(Graph) \ |
| 161 | 100 |
DIGRAPH_TYPEDEFS(Graph); \ |
| 162 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 163 |
Edge<Graph>::type Edge; \ |
|
| 164 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 165 |
EdgeIt<Graph>::type EdgeIt; \ |
|
| 166 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 167 |
IncEdgeIt<Graph>::type IncEdgeIt; \ |
|
| 168 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 169 |
BoolEdgeMap<Graph>::type BoolEdgeMap; \ |
|
| 170 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 171 |
IntEdgeMap<Graph>::type IntEdgeMap; \ |
|
| 172 |
typedef typename ::lemon::_graph_utils_bits:: \ |
|
| 173 |
DoubleEdgeMap<Graph>::type DoubleEdgeMap |
|
| 101 |
typedef Graph::Edge Edge; \ |
|
| 102 |
typedef Graph::EdgeIt EdgeIt; \ |
|
| 103 |
typedef Graph::IncEdgeIt IncEdgeIt; \ |
|
| 104 |
typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
|
| 105 |
typedef Graph::EdgeMap<int> IntEdgeMap; \ |
|
| 106 |
typedef Graph::EdgeMap<double> DoubleEdgeMap |
|
| 174 | 107 |
|
| 108 |
///Creates convenience typedefs for the graph types and iterators |
|
| 109 |
|
|
| 110 |
///\see GRAPH_TYPEDEFS |
|
| 111 |
/// |
|
| 112 |
///\note Use this macro, if the graph type is a dependent type, |
|
| 113 |
///ie. the graph type depend on a template parameter. |
|
| 114 |
#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ |
|
| 115 |
TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ |
|
| 116 |
typedef typename Graph::Edge Edge; \ |
|
| 117 |
typedef typename Graph::EdgeIt EdgeIt; \ |
|
| 118 |
typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
|
| 119 |
typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
|
| 120 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ |
|
| 121 |
typedef typename Graph::template EdgeMap<double> DoubleEdgeMap |
|
| 175 | 122 |
|
| 176 | 123 |
/// \brief Function to count the items in the graph. |
| 177 | 124 |
/// |
| 178 | 125 |
/// This function counts the items (nodes, arcs etc) in the graph. |
| 179 | 126 |
/// The complexity of the function is O(n) because |
| 180 | 127 |
/// it iterates on all of the items. |
| 181 | 128 |
template <typename Graph, typename Item> |
| 182 | 129 |
inline int countItems(const Graph& g) {
|
| 183 | 130 |
typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
| 184 | 131 |
int num = 0; |
| 185 | 132 |
for (ItemIt it(g); it != INVALID; ++it) {
|
| 186 | 133 |
++num; |
| ... | ... |
@@ -2152,25 +2099,25 @@ |
| 2152 | 2099 |
///\param G The type of the underlying digraph. |
| 2153 | 2100 |
/// |
| 2154 | 2101 |
///\sa ArcLookUp |
| 2155 | 2102 |
///\sa AllArcLookUp |
| 2156 | 2103 |
template<class G> |
| 2157 | 2104 |
class DynArcLookUp |
| 2158 | 2105 |
: protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase |
| 2159 | 2106 |
{
|
| 2160 | 2107 |
public: |
| 2161 | 2108 |
typedef typename ItemSetTraits<G, typename G::Arc> |
| 2162 | 2109 |
::ItemNotifier::ObserverBase Parent; |
| 2163 | 2110 |
|
| 2164 |
|
|
| 2111 |
TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
| 2165 | 2112 |
typedef G Digraph; |
| 2166 | 2113 |
|
| 2167 | 2114 |
protected: |
| 2168 | 2115 |
|
| 2169 | 2116 |
class AutoNodeMap : public DefaultMap<G, Node, Arc> {
|
| 2170 | 2117 |
public: |
| 2171 | 2118 |
|
| 2172 | 2119 |
typedef DefaultMap<G, Node, Arc> Parent; |
| 2173 | 2120 |
|
| 2174 | 2121 |
AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
|
| 2175 | 2122 |
|
| 2176 | 2123 |
virtual void add(const Node& node) {
|
| ... | ... |
@@ -2589,25 +2536,25 @@ |
| 2589 | 2536 |
///refresh(Node)) this data structure |
| 2590 | 2537 |
///whenever the digraph changes. This is a time consuming (superlinearly |
| 2591 | 2538 |
///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
| 2592 | 2539 |
/// |
| 2593 | 2540 |
///\param G The type of the underlying digraph. |
| 2594 | 2541 |
/// |
| 2595 | 2542 |
///\sa DynArcLookUp |
| 2596 | 2543 |
///\sa AllArcLookUp |
| 2597 | 2544 |
template<class G> |
| 2598 | 2545 |
class ArcLookUp |
| 2599 | 2546 |
{
|
| 2600 | 2547 |
public: |
| 2601 |
|
|
| 2548 |
TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
| 2602 | 2549 |
typedef G Digraph; |
| 2603 | 2550 |
|
| 2604 | 2551 |
protected: |
| 2605 | 2552 |
const Digraph &_g; |
| 2606 | 2553 |
typename Digraph::template NodeMap<Arc> _head; |
| 2607 | 2554 |
typename Digraph::template ArcMap<Arc> _left; |
| 2608 | 2555 |
typename Digraph::template ArcMap<Arc> _right; |
| 2609 | 2556 |
|
| 2610 | 2557 |
class ArcLess {
|
| 2611 | 2558 |
const Digraph &g; |
| 2612 | 2559 |
public: |
| 2613 | 2560 |
ArcLess(const Digraph &_g) : g(_g) {}
|
| ... | ... |
@@ -2706,25 +2653,25 @@ |
| 2706 | 2653 |
///\param G The type of the underlying digraph. |
| 2707 | 2654 |
/// |
| 2708 | 2655 |
///\sa DynArcLookUp |
| 2709 | 2656 |
///\sa ArcLookUp |
| 2710 | 2657 |
template<class G> |
| 2711 | 2658 |
class AllArcLookUp : public ArcLookUp<G> |
| 2712 | 2659 |
{
|
| 2713 | 2660 |
using ArcLookUp<G>::_g; |
| 2714 | 2661 |
using ArcLookUp<G>::_right; |
| 2715 | 2662 |
using ArcLookUp<G>::_left; |
| 2716 | 2663 |
using ArcLookUp<G>::_head; |
| 2717 | 2664 |
|
| 2718 |
|
|
| 2665 |
TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
| 2719 | 2666 |
typedef G Digraph; |
| 2720 | 2667 |
|
| 2721 | 2668 |
typename Digraph::template ArcMap<Arc> _next; |
| 2722 | 2669 |
|
| 2723 | 2670 |
Arc refreshNext(Arc head,Arc next=INVALID) |
| 2724 | 2671 |
{
|
| 2725 | 2672 |
if(head==INVALID) return next; |
| 2726 | 2673 |
else {
|
| 2727 | 2674 |
next=refreshNext(_right[head],next); |
| 2728 | 2675 |
// _next[head]=next; |
| 2729 | 2676 |
_next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) |
| 2730 | 2677 |
? next : INVALID; |
| ... | ... |
@@ -293,25 +293,25 @@ |
| 293 | 293 |
str = os.str(); |
| 294 | 294 |
return is; |
| 295 | 295 |
} |
| 296 | 296 |
|
| 297 | 297 |
} |
| 298 | 298 |
|
| 299 | 299 |
/// \e |
| 300 | 300 |
template <typename _Digraph> |
| 301 | 301 |
class DigraphReader {
|
| 302 | 302 |
public: |
| 303 | 303 |
|
| 304 | 304 |
typedef _Digraph Digraph; |
| 305 |
|
|
| 305 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 306 | 306 |
|
| 307 | 307 |
private: |
| 308 | 308 |
|
| 309 | 309 |
|
| 310 | 310 |
std::istream* _is; |
| 311 | 311 |
bool local_is; |
| 312 | 312 |
|
| 313 | 313 |
Digraph& _digraph; |
| 314 | 314 |
|
| 315 | 315 |
std::string _nodes_caption; |
| 316 | 316 |
std::string _arcs_caption; |
| 317 | 317 |
std::string _attributes_caption; |
| ... | ... |
@@ -228,25 +228,25 @@ |
| 228 | 228 |
} |
| 229 | 229 |
return os; |
| 230 | 230 |
} |
| 231 | 231 |
|
| 232 | 232 |
} |
| 233 | 233 |
|
| 234 | 234 |
/// \e |
| 235 | 235 |
template <typename _Digraph> |
| 236 | 236 |
class DigraphWriter {
|
| 237 | 237 |
public: |
| 238 | 238 |
|
| 239 | 239 |
typedef _Digraph Digraph; |
| 240 |
|
|
| 240 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 241 | 241 |
|
| 242 | 242 |
private: |
| 243 | 243 |
|
| 244 | 244 |
|
| 245 | 245 |
std::ostream* _os; |
| 246 | 246 |
bool local_os; |
| 247 | 247 |
|
| 248 | 248 |
Digraph& _digraph; |
| 249 | 249 |
|
| 250 | 250 |
std::string _nodes_caption; |
| 251 | 251 |
std::string _arcs_caption; |
| 252 | 252 |
std::string _attributes_caption; |
0 comments (0 inline)