graph_line_graph.cc 3.52 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2017 Tiago de Paula Peixoto <tiago@skewed.de>
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
//
// This program 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
// 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
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include "graph_filtering.hh"
#include "graph.hh"
#include "graph_properties.hh"

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

// retrieves the line graph

struct get_line_graph
{
    template <class Graph, class VertexIndex, class LineGraph,
              class EdgeIndexMap, class LGVertexIndex>
32
    void operator()(const Graph& g, VertexIndex,
33
34
35
36
37
38
39
40
41
42
                    LineGraph& line_graph, EdgeIndexMap edge_index,
                    LGVertexIndex vmap) const
    {
        typedef typename graph_traits<LineGraph>::vertex_descriptor lg_vertex_t;
        typedef HashedDescriptorMap<EdgeIndexMap,lg_vertex_t>
            edge_to_vertex_map_t;
        edge_to_vertex_map_t edge_to_vertex_map(edge_index);

        typename LGVertexIndex::checked_t vertex_map = vmap.get_checked();

43
        for (auto e : edges_range(g))
44
        {
45
46
47
            auto v = add_vertex(line_graph);
            edge_to_vertex_map[e] = v;
            vertex_map[v] = edge_index[e];
48
49
        }

50
        if (graph_tool::is_directed(g))
51
        {
52
            for (auto v : vertices_range(g))
53
            {
54
                for (auto e1 : out_edges_range(v, g))
55
                {
56
                    for (auto e2 : out_edges_range(target(e1, g), g))
57
                    {
58
59
60
                        add_edge(edge_to_vertex_map[e1],
                                 edge_to_vertex_map[e2],
                                 line_graph);
61
62
63
64
65
66
                    }
                }
            }
        }
        else
        {
67
            for (auto v : vertices_range(g))
68
69
            {
                typename graph_traits<Graph>::out_edge_iterator e1, e2, e_end;
70
71
                for (tie(e1, e_end) = out_edges(v, g); e1 != e_end; ++e1)
                {
72
                    for (e2 = e1; e2 != e_end; ++e2)
73
                    {
74
75
                        if (*e1 != *e2)
                        {
76
77
                            add_edge(edge_to_vertex_map[*e1],
                                     edge_to_vertex_map[*e2],
78
                                     line_graph);
79
                        }
80
81
                    }
                }
82
83
84
85
86
87
88
89
            }
        }
    }
};

void line_graph(GraphInterface& gi, GraphInterface& lgi,
                boost::any edge_index)
{
Tiago Peixoto's avatar
Tiago Peixoto committed
90
    typedef property_map_types::apply<boost::mpl::vector<int64_t>,
91
                                      GraphInterface::vertex_index_map_t,
Tiago Peixoto's avatar
Tiago Peixoto committed
92
                                      boost::mpl::false_>::type
93
94
        vertex_properties;

95
    run_action<>()(gi, std::bind(get_line_graph(), std::placeholders::_1,
96
97
                                 gi.get_vertex_index(),
                                 std::ref(lgi.get_graph()), lgi.get_edge_index(),
98
                                 std::placeholders::_2),
Tiago Peixoto's avatar
Tiago Peixoto committed
99
                   vertex_properties())(edge_index);
100
}