1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2005-2021 The igraph development team
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301 USA
20
21 */
22
23 #include "igraph_constructors.h"
24
25 #include "igraph_interface.h"
26
27 #include "core/interruption.h"
28
29 /* Note to self: tried using adjacency lists instead of igraph_incident queries,
30 * with minimal performance improvements on a graph with 70K vertices and 360K
31 * edges. (1.09s instead of 1.10s). I think it's not worth the fuss. */
igraph_i_linegraph_undirected(const igraph_t * graph,igraph_t * linegraph)32 static int igraph_i_linegraph_undirected(const igraph_t *graph, igraph_t *linegraph) {
33 long int no_of_edges = igraph_ecount(graph);
34 long int i, j, n;
35 igraph_vector_t adjedges, adjedges2;
36 igraph_vector_t edges;
37 long int prev = -1;
38
39 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
40 IGRAPH_VECTOR_INIT_FINALLY(&adjedges, 0);
41 IGRAPH_VECTOR_INIT_FINALLY(&adjedges2, 0);
42
43 for (i = 0; i < no_of_edges; i++) {
44 long int from = IGRAPH_FROM(graph, i);
45 long int to = IGRAPH_TO(graph, i);
46
47 IGRAPH_ALLOW_INTERRUPTION();
48
49 if (from != prev) {
50 IGRAPH_CHECK(igraph_incident(graph, &adjedges, (igraph_integer_t) from,
51 IGRAPH_ALL));
52 }
53 n = igraph_vector_size(&adjedges);
54 for (j = 0; j < n; j++) {
55 long int e = (long int) VECTOR(adjedges)[j];
56 if (e < i) {
57 IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
58 IGRAPH_CHECK(igraph_vector_push_back(&edges, e));
59 }
60 }
61
62 IGRAPH_CHECK(igraph_incident(graph, &adjedges2, (igraph_integer_t) to,
63 IGRAPH_ALL));
64 n = igraph_vector_size(&adjedges2);
65 for (j = 0; j < n; j++) {
66 long int e = (long int) VECTOR(adjedges2)[j];
67 if (e < i) {
68 IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
69 IGRAPH_CHECK(igraph_vector_push_back(&edges, e));
70 }
71 }
72
73 prev = from;
74 }
75
76 igraph_vector_destroy(&adjedges);
77 igraph_vector_destroy(&adjedges2);
78 IGRAPH_FINALLY_CLEAN(2);
79
80 igraph_create(linegraph, &edges, (igraph_integer_t) no_of_edges,
81 igraph_is_directed(graph));
82 igraph_vector_destroy(&edges);
83 IGRAPH_FINALLY_CLEAN(1);
84
85 return 0;
86 }
87
igraph_i_linegraph_directed(const igraph_t * graph,igraph_t * linegraph)88 static int igraph_i_linegraph_directed(const igraph_t *graph, igraph_t *linegraph) {
89 long int no_of_edges = igraph_ecount(graph);
90 long int i, j, n;
91 igraph_vector_t adjedges;
92 igraph_vector_t edges;
93 long int prev = -1;
94
95 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
96 IGRAPH_VECTOR_INIT_FINALLY(&adjedges, 0);
97
98 for (i = 0; i < no_of_edges; i++) {
99 long int from = IGRAPH_FROM(graph, i);
100
101 IGRAPH_ALLOW_INTERRUPTION();
102
103 if (from != prev) {
104 IGRAPH_CHECK(igraph_incident(graph, &adjedges, (igraph_integer_t) from,
105 IGRAPH_IN));
106 }
107 n = igraph_vector_size(&adjedges);
108 for (j = 0; j < n; j++) {
109 long int e = (long int) VECTOR(adjedges)[j];
110 IGRAPH_CHECK(igraph_vector_push_back(&edges, e));
111 IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
112 }
113
114 prev = from;
115 }
116
117 igraph_vector_destroy(&adjedges);
118 IGRAPH_FINALLY_CLEAN(1);
119 igraph_create(linegraph, &edges, (igraph_integer_t) no_of_edges, igraph_is_directed(graph));
120 igraph_vector_destroy(&edges);
121 IGRAPH_FINALLY_CLEAN(1);
122
123 return 0;
124 }
125
126 /**
127 * \function igraph_linegraph
128 * \brief Create the line graph of a graph.
129 *
130 * The line graph L(G) of a G undirected graph is defined as follows.
131 * L(G) has one vertex for each edge in G and two different vertices in L(G)
132 * are connected by an edge if their corresponding edges share an end point.
133 * In a multigraph, if two end points are shared, two edges are created.
134 * The vertex of a loop is counted as two end points.
135 *
136 * </para><para>
137 * The line graph L(G) of a G directed graph is slightly different,
138 * L(G) has one vertex for each edge in G and two vertices in L(G) are connected
139 * by a directed edge if the target of the first vertex's corresponding edge
140 * is the same as the source of the second vertex's corresponding edge.
141 *
142 * </para><para>
143 * Edge \em i in the original graph will correspond to vertex \em i
144 * in the line graph.
145 *
146 * </para><para>
147 * The first version of this function was contributed by Vincent Matossian,
148 * thanks.
149 * \param graph The input graph, may be directed or undirected.
150 * \param linegraph Pointer to an uninitialized graph object, the
151 * result is stored here.
152 * \return Error code.
153 *
154 * Time complexity: O(|V|+|E|), the number of edges plus the number of vertices.
155 */
156
igraph_linegraph(const igraph_t * graph,igraph_t * linegraph)157 int igraph_linegraph(const igraph_t *graph, igraph_t *linegraph) {
158
159 if (igraph_is_directed(graph)) {
160 return igraph_i_linegraph_directed(graph, linegraph);
161 } else {
162 return igraph_i_linegraph_undirected(graph, linegraph);
163 }
164 }
165