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
|
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
/*
Sample data (edge_iterator_constructor.dat):
5
10
0 1
1 2
1 3
2 4
3 4
1 0
2 1
3 1
4 2
4 3
Sample output:
0 --> 1
1 --> 2 3 0
2 --> 4 1
3 --> 4 1
4 --> 2 3
*/
#include <boost/config.hpp>
#include <utility>
#include <iostream>
#include <fstream>
#include <iterator>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
class edge_stream_iterator
{
public:
typedef std::input_iterator_tag iterator_category;
typedef std::pair< int, int > value_type;
typedef std::ptrdiff_t difference_type;
typedef const value_type* pointer;
typedef const value_type& reference;
edge_stream_iterator() : m_stream(0), m_end_marker(false) {}
edge_stream_iterator(std::istream& s) : m_stream(&s) { m_read(); }
reference operator*() const { return m_edge; }
edge_stream_iterator& operator++()
{
m_read();
return *this;
}
edge_stream_iterator operator++(int)
{
edge_stream_iterator tmp = *this;
m_read();
return tmp;
}
protected:
std::istream* m_stream;
value_type m_edge;
bool m_end_marker;
void m_read()
{
m_end_marker = (*m_stream) ? true : false;
if (m_end_marker)
{
*m_stream >> m_edge.first >> m_edge.second;
}
m_end_marker = (*m_stream) ? true : false;
}
friend bool operator==(
const edge_stream_iterator& x, const edge_stream_iterator& y);
};
bool operator==(const edge_stream_iterator& x, const edge_stream_iterator& y)
{
return (x.m_stream == y.m_stream && x.m_end_marker == y.m_end_marker)
|| (x.m_end_marker == false && y.m_end_marker == false);
}
bool operator!=(const edge_stream_iterator& x, const edge_stream_iterator& y)
{
return !(x == y);
}
int main(int argc, const char** argv)
{
typedef boost::adjacency_list<> IteratorConstructibleGraph;
typedef boost::graph_traits< IteratorConstructibleGraph > Traits;
Traits::vertices_size_type size_V;
Traits::edges_size_type size_E;
std::ifstream f(argc >= 2 ? argv[1] : "edge_iterator_constructor.dat");
f >> size_V >> size_E;
edge_stream_iterator edge_iter(f), end;
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
// VC++ can't handle the iterator constructor
IteratorConstructibleGraph G(size_V);
while (edge_iter != end)
{
int i, j;
boost::tie(i, j) = *edge_iter++;
boost::add_edge(i, j, G);
}
#else
IteratorConstructibleGraph G(edge_iter, end, size_V);
#endif
boost::print_graph(G);
return 0;
}
|
