1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
// Copyright (C) 2012 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#ifndef DLIB_GENERAL_FLOW_GRaPH_H__
#define DLIB_GENERAL_FLOW_GRaPH_H__
#include "../graph_utils.h"
namespace dlib
{
// ----------------------------------------------------------------------------------------
namespace impl
{
template <
typename directed_graph_type
>
class general_flow_graph
{
/*!
this is a utility class used by dlib::min_cut to convert a directed_graph
into the kind of flow graph expected by the min_cut object's main block
of code.
!*/
directed_graph_type& g;
typedef typename directed_graph_type::node_type node_type;
typedef typename directed_graph_type::type node_label;
public:
general_flow_graph(
directed_graph_type& g_
) : g(g_)
{
}
class out_edge_iterator
{
friend class general_flow_graph;
unsigned long idx; // base node idx
unsigned long cnt; // count over the neighbors of idx
public:
out_edge_iterator(
):idx(0),cnt(0) {}
out_edge_iterator(
unsigned long idx_,
unsigned long cnt_
):idx(idx_),cnt(cnt_)
{}
bool operator!= (
const out_edge_iterator& item
) const { return cnt != item.cnt; }
out_edge_iterator& operator++(
)
{
++cnt;
return *this;
}
};
class in_edge_iterator
{
friend class general_flow_graph;
unsigned long idx; // base node idx
unsigned long cnt; // count over the neighbors of idx
public:
in_edge_iterator(
):idx(0),cnt(0) {}
in_edge_iterator(
unsigned long idx_,
unsigned long cnt_
):idx(idx_),cnt(cnt_)
{}
bool operator!= (
const in_edge_iterator& item
) const { return cnt != item.cnt; }
in_edge_iterator& operator++(
)
{
++cnt;
return *this;
}
};
unsigned long number_of_nodes (
) const { return g.number_of_nodes(); }
out_edge_iterator out_begin(
const unsigned long& it
) const { return out_edge_iterator(it, 0); }
in_edge_iterator in_begin(
const unsigned long& it
) const { return in_edge_iterator(it, 0); }
out_edge_iterator out_end(
const unsigned long& it
) const { return out_edge_iterator(it, g.node(it).number_of_children()); }
in_edge_iterator in_end(
const unsigned long& it
) const { return in_edge_iterator(it, g.node(it).number_of_parents()); }
unsigned long node_id (
const out_edge_iterator& it
) const { return g.node(it.idx).child(it.cnt).index(); }
unsigned long node_id (
const in_edge_iterator& it
) const { return g.node(it.idx).parent(it.cnt).index(); }
typedef typename directed_graph_type::edge_type edge_type;
edge_type get_flow (const unsigned long& it1, const unsigned long& it2) const
{
return edge(g, it1, it2);
}
edge_type get_flow (const out_edge_iterator& it) const
{
return g.node(it.idx).child_edge(it.cnt);
}
edge_type get_flow (const in_edge_iterator& it) const
{
return g.node(it.idx).parent_edge(it.cnt);
}
void adjust_flow (
const unsigned long& it1,
const unsigned long& it2,
const edge_type& value
)
{
edge(g, it1, it2) += value;
edge(g, it2, it1) -= value;
}
void set_label (
const unsigned long& it,
node_label value
)
{
g.node(it).data = value;
}
node_label get_label (
const unsigned long& it
) const
{
return g.node(it).data;
}
};
}
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_GENERAL_FLOW_GRaPH_H__
|
