1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2008-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include <igraph.h>
25 #include <stdlib.h>
26
check_projection(const igraph_t * graph,const igraph_vector_bool_t * types,const igraph_t * proj1,const igraph_t * proj2)27 int check_projection(const igraph_t *graph,
28 const igraph_vector_bool_t *types,
29 const igraph_t *proj1,
30 const igraph_t *proj2) {
31 igraph_integer_t vcount1, ecount1, vcount2, ecount2;
32 igraph_bipartite_projection_size(graph, types, &vcount1, &ecount1,
33 &vcount2, &ecount2);
34 if (proj1 && igraph_vcount(proj1) != vcount1) {
35 exit(10);
36 }
37 if (proj1 && igraph_ecount(proj1) != ecount1) {
38 exit(11);
39 }
40 if (proj2 && igraph_vcount(proj2) != vcount2) {
41 exit(12);
42 }
43 if (proj2 && igraph_ecount(proj2) != ecount2) {
44 exit(13);
45 }
46 return 0;
47 }
48
main()49 int main() {
50
51 igraph_t g, p1, p2, full, ring;
52 igraph_vector_bool_t types;
53 igraph_bool_t iso;
54 long int i, m2 = 0, w, f, t;
55 igraph_vector_t mult1, mult2;
56
57 /*******************************************************/
58 /* Full bipartite graph -> full graphs */
59 /*******************************************************/
60
61 igraph_vector_bool_init(&types, 0);
62 igraph_full_bipartite(&g, &types, 5, 3, /*directed=*/ 0,
63 /*mode=*/ IGRAPH_ALL);
64
65 /* Get both projections */
66 igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
67 check_projection(&g, &types, &p1, &p2);
68
69 /* Check first projection */
70 igraph_full(&full, igraph_vcount(&p1), /*directed=*/0, /*loops=*/0);
71 igraph_isomorphic_bliss(&p1, &full, 0, 0, &iso, 0, 0,
72 IGRAPH_BLISS_FM, 0, 0);
73 if (!iso) {
74 return 1;
75 }
76 igraph_destroy(&full);
77
78 /* Check second projection */
79 igraph_full(&full, igraph_vcount(&p2), /*directed=*/0, /*loops=*/0);
80 igraph_isomorphic_bliss(&p2, &full, 0, 0, &iso, 0, 0,
81 IGRAPH_BLISS_FM, 0, 0);
82 if (!iso) {
83 return 2;
84 }
85 igraph_destroy(&full);
86
87 igraph_destroy(&p1);
88 igraph_destroy(&p2);
89 igraph_destroy(&g);
90 igraph_vector_bool_destroy(&types);
91
92 /*******************************************************/
93 /* More sophisticated test */
94 /*******************************************************/
95
96 igraph_ring(&g, 100, /*directed=*/ 1, /*mutual=*/ 1,
97 /*circular=*/ 1);
98 igraph_vector_bool_init(&types, igraph_vcount(&g));
99 for (i = 0; i < igraph_vector_bool_size(&types); i++) {
100 VECTOR(types)[i] = i % 2 ? 0 : 1;
101 }
102
103 /* Get both projections */
104 igraph_bipartite_projection(&g, &types, &p1, &p2, 0, 0, /*probe1=*/ -1);
105 check_projection(&g, &types, &p1, &p2);
106
107 /* Check first projection */
108 igraph_ring(&ring, igraph_vcount(&g) / 2, /*directed=*/ 0,
109 /*mutual=*/ 0, /*circular=*/ 1);
110 igraph_isomorphic_bliss(&p1, &ring, 0, 0, &iso, 0, 0,
111 IGRAPH_BLISS_FM, 0, 0);
112 if (!iso) {
113 return 1;
114 }
115
116 /* Check second projection */
117 igraph_isomorphic_bliss(&p2, &ring, 0, 0, &iso, 0, 0,
118 IGRAPH_BLISS_FM, 0, 0);
119 if (!iso) {
120 return 2;
121 }
122 igraph_destroy(&ring);
123
124 igraph_destroy(&p1);
125 igraph_destroy(&p2);
126 igraph_destroy(&g);
127 igraph_vector_bool_destroy(&types);
128
129 /*******************************************************/
130 /* Multiplicity test */
131 /*******************************************************/
132
133 igraph_small(&g, 10, IGRAPH_UNDIRECTED,
134 0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 4, 9, 5, 9, 6, 9, 7, 9, 0, 9,
135 -1);
136 igraph_vector_bool_init(&types, igraph_vcount(&g));
137 igraph_vector_bool_fill(&types, 1);
138 VECTOR(types)[8] = VECTOR(types)[9] = 0;
139
140 igraph_vector_init(&mult1, 0);
141 igraph_vector_init(&mult2, 0);
142 igraph_bipartite_projection(&g, &types, &p1, &p2, &mult1, &mult2,
143 /*probe=*/ -1);
144 check_projection(&g, &types, &p1, &p2);
145
146 if (igraph_vector_size(&mult1) != igraph_ecount(&p1)) {
147 return 21;
148 }
149 if (igraph_vector_size(&mult2) != igraph_ecount(&p2)) {
150 return 22;
151 }
152 if (VECTOR(mult1)[0] != 2) {
153 return 23;
154 }
155 for (i = 0; i < igraph_vector_size(&mult2); i++) {
156 if (VECTOR(mult2)[i] != 1 && VECTOR(mult2)[i] != 2) {
157 return 24;
158 }
159 if (VECTOR(mult2)[i] == 2) {
160 m2++;
161 w = i;
162 }
163 }
164 if (m2 != 1) {
165 return 25;
166 }
167 f = IGRAPH_FROM(&p2, w);
168 t = IGRAPH_TO(&p2, w);
169 if (fmin(f, t) != 0 || fmax(f, t) != 4) {
170 return 26;
171 }
172
173 igraph_vector_destroy(&mult1);
174 igraph_vector_destroy(&mult2);
175 igraph_destroy(&p1);
176 igraph_destroy(&p2);
177 igraph_destroy(&g);
178 igraph_vector_bool_destroy(&types);
179
180 return 0;
181 }
182