graph_line_graph.cc 8.4 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
8
9
10
11
12
13
14
15
// of the License, or (at your option) any later version.
//
// This program 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
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18
19
20
#include "graph_filtering.hh"
#include "graph.hh"
#include "graph_properties.hh"
21
22
23
24
25

#include <tr1/unordered_set>
#include <iostream>
#include <iomanip>
#include <boost/graph/graphviz.hpp>
26
#include <boost/graph/graphml.hpp>
27
28
29
30
31
#include <boost/algorithm/string.hpp>
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/filter/gzip.hpp>
#include <boost/iostreams/filter/bzip2.hpp>
#include <boost/iostreams/device/file.hpp>
32
33
34
35
36
37
38
39
40
41

using namespace std;
using namespace boost;
using namespace graph_tool;

// retrieves the line graph

struct get_line_graph
{
    template <class Graph, class EdgeIndexMap>
42
43
    void operator()(const Graph* pg, EdgeIndexMap edge_index,
                    dynamic_properties& properties,  string file,
44
                    string format) const
45
    {
46
        const Graph& g = *pg;
47
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
48
        typedef boost::property<edge_index_t, size_t> EdgeProperty;
49

50
51
52
        typedef adjacency_list <vecS, // edges
                                vecS, // vertices
                                undirectedS,
53
                                no_property,
54
                                EdgeProperty > line_graph_t;
55

56
57
        line_graph_t line_graph;

58
        typedef typename property_map<line_graph_t, vertex_index_t>::type
59
            line_vertex_index_map_t;
60
        line_vertex_index_map_t line_vertex_index(get(vertex_index,
61
                                                      line_graph));
62

63
        typedef HashedDescriptorMap
64
            <line_vertex_index_map_t,
65
66
            typename graph_traits
                <typename Graph::original_graph_t>::edge_descriptor> edge_map_t;
67
68
        edge_map_t edge_map(line_vertex_index);

69
        typedef HashedDescriptorMap
70
71
            <EdgeIndexMap,
            typename graph_traits<line_graph_t>::vertex_descriptor>
72
                edge_to_vertex_map_t;
73
74
75
76
77
78
79
80
81
82
83
        edge_to_vertex_map_t edge_to_vertex_map(edge_index);

        typename graph_traits<Graph>::edge_iterator e, e_end;
        for (tie(e, e_end) = edges(g); e != e_end; ++e)
        {
            typename graph_traits<line_graph_t>::vertex_descriptor v;
            v = add_vertex(line_graph);
            edge_to_vertex_map[*e] = v;
            edge_map[v] = *e;
        }

84
        typedef typename property_map<line_graph_t,edge_index_t>::type
85
            line_edge_index_map_t;
86
87
        line_edge_index_map_t line_edge_index(get(edge_index_t(), line_graph));

88
        typedef HashedDescriptorMap<line_edge_index_map_t,vertex_t>
89
            vertex_map_t;
90
91
92
93
94
95
96
97
        vertex_map_t vertex_map(line_edge_index);

        size_t e_index = 0;
        typename graph_traits<Graph>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(g); v != v_end; ++v)
        {
            typename graph_traits<Graph>::out_edge_iterator e1, e2, e_end;
            for (tie(e1, e_end) = out_edges(*v, g); e1 != e_end; ++e1)
Tiago Peixoto's avatar
Tiago Peixoto committed
98
                for (e2 = e1; e2 != e_end; ++e2)
99
                    if (*e1 != *e2)
100
                    {
101
                        typename graph_traits<line_graph_t>::edge_descriptor
102
                            new_edge;
103
104
                        new_edge = add_edge(edge_to_vertex_map[*e1],
                                            edge_to_vertex_map[*e2],
105
                                            line_graph).first;
106
107
108
                        line_edge_index[new_edge] = e_index++;
                        vertex_map[new_edge] = *v;
                    }
109
110
111
        }

        dynamic_properties dp;
112
        for (typeof(properties.begin()) iter = properties.begin();
113
             iter != properties.end(); ++iter)
114
        {
115
116
            if (iter->second->key() != typeid(graph_property_tag))
            {
117
                if (iter->second->key() == typeid(vertex_t))
118
                    dp.insert(iter->first,
119
120
121
                              auto_ptr<dynamic_property_map>
                              (new dynamic_property_map_wrap<vertex_map_t>
                               (vertex_map, *iter->second)));
122
123
                else
                    dp.insert(iter->first,
124
125
126
                              auto_ptr<dynamic_property_map>
                              (new dynamic_property_map_wrap<edge_map_t>
                               (edge_map, *iter->second)));
127
            }
128
            else
129
            {
130
                dp.insert(iter->first,
131
                          auto_ptr<dynamic_property_map>(iter->second));
132
            }
133
134
135
136
        }

        bool graphviz = false;
        if (format == "")
137
            graphviz = ends_with(file,".dot") || ends_with(file,".dot.gz")
138
                || ends_with(file,".dot.bz2");
139
140
141
        else if (format == "dot")
            graphviz = true;
        else if (format != "xml")
142
            throw GraphException("error writing to file '" + file +
143
144
                                 "': requested invalid format '" +
                                 format + "'");
145
146
147
148
149
        try
        {
            iostreams::filtering_stream<iostreams::output> stream;
            ofstream file_stream;
            if (file == "-")
150
                stream.push(cout);
151
152
            else
            {
153
                file_stream.open(file.c_str(), ios_base::out |
154
                                 ios_base::binary);
155
156
157
158
159
160
                file_stream.exceptions(ios_base::badbit | ios_base::failbit);
                if (ends_with(file,".gz"))
                    stream.push(iostreams::gzip_compressor());
                if (ends_with(file,".bz2"))
                    stream.push(iostreams::bzip2_compressor());
                stream.push(file_stream);
161
162
            }
            stream.exceptions(ios_base::badbit | ios_base::failbit);
163

164
165
            if (graphviz)
            {
166
167
                dp.property("vertex_id", line_vertex_index);
                write_graphviz(stream, line_graph, dp, string("vertex_id"));
168
169
170
            }
            else
            {
171
                write_graphml(stream, line_graph, line_vertex_index, dp, true);
172
173
174
175
176
            }
            stream.reset();
        }
        catch (ios_base::failure &e)
        {
177
            throw GraphException("error writing to file '" + file + "':" +
178
                                 e.what());
179
        }
180
181
182
183

        for (typeof(dp.begin()) iter = dp.begin(); iter != dp.end(); ++iter)
            if (iter->second->key() == typeid(graph_property_tag))
                iter->second = 0;
184
185
186
187
188
189
    }

    template <class DescriptorMap>
    class dynamic_property_map_wrap: public dynamic_property_map
    {
    public:
190
        dynamic_property_map_wrap(DescriptorMap& edge_map,
191
192
                                  dynamic_property_map& dm)
            : _descriptor_map(edge_map), _dm(dm) {}
193
        any get(const any& key)
194
        {
195
            key_t k = any_cast<key_t>(key);
196
            return _dm.get(_descriptor_map[k]);
197
198
199
200
        }

        string get_string(const any& key)
        {
201
            key_t k = any_cast<key_t>(key);
202
            return _dm.get_string(_descriptor_map[k]);
203
204
205
206
        }

        void put(const any& key, const any& value)
        {
207
            return _dm.put(_descriptor_map[any_cast<key_t>(key)], value);
208
209
210
211
        }

        const type_info& key() const
        {
212
            return typeid(key_t);
213
214
215
216
217
218
        }

        const type_info& value() const
        {
            return _dm.value();
        }
219
    private:
220
        DescriptorMap& _descriptor_map;
221
        typedef typename property_traits<DescriptorMap>::key_type key_t;
222
        dynamic_property_map& _dm;
223
224
225
226
227
228
229
230
    };

};

void GraphInterface::GetLineGraph(string out_file, string format)
{
    bool directed = _directed;
    _directed = false;
231
    run_action<detail::never_directed>()
232
        (*this, bind<void>(get_line_graph(), _1, var(_edge_index),
233
                           var(_properties), out_file, format))();
234
235
    _directed = directed;
}