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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
/* -*- c++ -*- */
/*
* Copyright 2006,2007 Free Software Foundation, Inc.
*
* This file is part of GNU Radio
*
* GNU Radio is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3, or (at your option)
* any later version.
*
* GNU Radio is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with GNU Radio; see the file COPYING. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street,
* Boston, MA 02110-1301, USA.
*/
#ifndef INCLUDED_GR_FLOWGRAPH_H
#define INCLUDED_GR_FLOWGRAPH_H
#include <gr_basic_block.h>
#include <iostream>
/*!
*\brief Class representing a specific input or output graph endpoint
* \ingroup internal
*
*/
class gr_endpoint
{
private:
gr_basic_block_sptr d_basic_block;
int d_port;
public:
gr_endpoint() : d_basic_block(), d_port(0) { }
gr_endpoint(gr_basic_block_sptr block, int port) { d_basic_block = block; d_port = port; }
gr_basic_block_sptr block() const { return d_basic_block; }
int port() const { return d_port; }
bool operator==(const gr_endpoint &other) const;
};
inline bool gr_endpoint::operator==(const gr_endpoint &other) const
{
return (d_basic_block == other.d_basic_block &&
d_port == other.d_port);
}
// Hold vectors of gr_endpoint objects
typedef std::vector<gr_endpoint> gr_endpoint_vector_t;
typedef std::vector<gr_endpoint>::iterator gr_endpoint_viter_t;
/*!
*\brief Class representing a connection between to graph endpoints
*
*/
class gr_edge
{
public:
gr_edge() : d_src(), d_dst() { };
gr_edge(const gr_endpoint &src, const gr_endpoint &dst) : d_src(src), d_dst(dst) { }
~gr_edge();
const gr_endpoint &src() const { return d_src; }
const gr_endpoint &dst() const { return d_dst; }
private:
gr_endpoint d_src;
gr_endpoint d_dst;
};
// Hold vectors of gr_edge objects
typedef std::vector<gr_edge> gr_edge_vector_t;
typedef std::vector<gr_edge>::iterator gr_edge_viter_t;
// Create a shared pointer to a heap allocated flowgraph
// (types defined in gr_runtime_types.h)
gr_flowgraph_sptr gr_make_flowgraph();
/*!
*\brief Class representing a directed, acyclic graph of basic blocks
*
*/
class gr_flowgraph
{
public:
friend gr_flowgraph_sptr gr_make_flowgraph();
// Destruct an arbitrary flowgraph
~gr_flowgraph();
// Connect two endpoints
void connect(const gr_endpoint &src, const gr_endpoint &dst);
// Disconnect two endpoints
void disconnect(const gr_endpoint &src, const gr_endpoint &dst);
// Connect an output port to an input port (convenience)
void connect(gr_basic_block_sptr src_block, int src_port,
gr_basic_block_sptr dst_block, int dst_port);
// Disconnect an input port from an output port (convenience)
void disconnect(gr_basic_block_sptr src_block, int src_port,
gr_basic_block_sptr dst_block, int dst_port);
// Validate connectivity, raise exception if invalid
void validate();
// Clear existing flowgraph
void clear();
// Return vector of edges
const gr_edge_vector_t &edges() const { return d_edges; }
// Return vector of connected blocks
gr_basic_block_vector_t calc_used_blocks();
// Return toplogically sorted vector of blocks. All the sources come first.
gr_basic_block_vector_t topological_sort(gr_basic_block_vector_t &blocks);
// Return vector of vectors of disjointly connected blocks, topologically
// sorted.
std::vector<gr_basic_block_vector_t> partition();
protected:
gr_basic_block_vector_t d_blocks;
gr_edge_vector_t d_edges;
gr_flowgraph();
std::vector<int> calc_used_ports(gr_basic_block_sptr block, bool check_inputs);
gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block, int port);
gr_edge_vector_t calc_upstream_edges(gr_basic_block_sptr block);
bool has_block_p(gr_basic_block_sptr block);
gr_edge calc_upstream_edge(gr_basic_block_sptr block, int port);
private:
void check_valid_port(gr_io_signature_sptr sig, int port);
void check_dst_not_used(const gr_endpoint &dst);
void check_type_match(const gr_endpoint &src, const gr_endpoint &dst);
gr_edge_vector_t calc_connections(gr_basic_block_sptr block, bool check_inputs); // false=use outputs
void check_contiguity(gr_basic_block_sptr block, const std::vector<int> &used_ports, bool check_inputs);
gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block);
gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
void reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
gr_basic_block_vector_t calc_adjacent_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks);
bool source_p(gr_basic_block_sptr block);
void topological_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &output);
};
// Convenience functions
inline
void gr_flowgraph::connect(gr_basic_block_sptr src_block, int src_port,
gr_basic_block_sptr dst_block, int dst_port)
{
connect(gr_endpoint(src_block, src_port),
gr_endpoint(dst_block, dst_port));
}
inline
void gr_flowgraph::disconnect(gr_basic_block_sptr src_block, int src_port,
gr_basic_block_sptr dst_block, int dst_port)
{
disconnect(gr_endpoint(src_block, src_port),
gr_endpoint(dst_block, dst_port));
}
inline std::ostream&
operator <<(std::ostream &os, const gr_endpoint endp)
{
os << endp.block() << ":" << endp.port();
return os;
}
inline std::ostream&
operator <<(std::ostream &os, const gr_edge edge)
{
os << edge.src() << "->" << edge.dst();
return os;
}
#endif /* INCLUDED_GR_FLOWGRAPH_H */
|
