1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2010-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 <stdio.h>
26
main()27 int main() {
28
29 igraph_t g, domtree;
30 igraph_vector_t dom, leftout;
31
32 igraph_vector_init(&dom, 0);
33 igraph_small(&g, 13, IGRAPH_DIRECTED,
34 0, 1, 0, 7, 0, 10,
35 1, 2, 1, 5,
36 2, 3,
37 3, 4,
38 4, 3, 4, 0,
39 5, 3, 5, 6,
40 6, 3,
41 7, 8, 7, 10, 7, 11,
42 8, 9,
43 9, 4, 9, 8,
44 10, 11,
45 11, 12,
46 12, 9,
47 -1);
48
49 /* Check NULL vector arguments */
50 igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0,
51 /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);
52
53 /* Proper calculation */
54 igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0,
55 /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);
56 igraph_vector_print(&dom);
57
58 /* Tree calculation */
59 igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree,
60 /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);
61 igraph_write_graph_edgelist(&domtree, stdout);
62
63 igraph_vector_destroy(&dom);
64 igraph_destroy(&domtree);
65 igraph_destroy(&g);
66
67 /* -------------------------------------------------------------------*/
68
69 igraph_vector_init(&dom, 0);
70 igraph_small(&g, 13, IGRAPH_DIRECTED,
71 1, 0, 2, 0, 3, 0,
72 4, 1,
73 1, 2, 4, 2, 5, 2,
74 6, 3, 7, 3,
75 12, 4,
76 8, 5,
77 9, 6,
78 9, 7, 10, 7,
79 5, 8, 11, 8,
80 11, 9,
81 9, 10,
82 9, 11, 0, 11,
83 8, 12,
84 -1);
85
86 /* Check NULL vector arguments */
87 igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0,
88 /*leftout=*/ 0, /*mode=*/ IGRAPH_IN);
89
90 /* Proper calculation */
91 igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0,
92 /*leftout=*/ 0, /*mode=*/ IGRAPH_IN);
93 igraph_vector_print(&dom);
94
95 /* Tree calculation */
96 igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree,
97 /*leftout=*/ 0, /*mode=*/ IGRAPH_IN);
98 igraph_write_graph_edgelist(&domtree, stdout);
99
100 igraph_vector_destroy(&dom);
101 igraph_destroy(&domtree);
102 igraph_destroy(&g);
103
104 /* -------------------------------------------------------------------*/
105
106 igraph_vector_init(&dom, 0);
107 igraph_vector_init(&leftout, 0);
108
109 /* Check a graph with more components */
110 igraph_small(&g, 20, IGRAPH_DIRECTED,
111 0, 1, 0, 2, 0, 3,
112 1, 4,
113 2, 1, 2, 4, 2, 8,
114 3, 9, 3, 10,
115 4, 15,
116 8, 11,
117 9, 12,
118 10, 12, 10, 13,
119 11, 8, 11, 14,
120 12, 14,
121 13, 12,
122 14, 12, 14, 0,
123 15, 11,
124 -1);
125
126 igraph_dominator_tree(&g, /*root=*/ 0, &dom, &domtree,
127 &leftout, /*mode=*/ IGRAPH_OUT);
128 igraph_vector_print(&dom);
129 igraph_vector_print(&leftout);
130 igraph_write_graph_edgelist(&domtree, stdout);
131
132 igraph_vector_destroy(&dom);
133 igraph_vector_destroy(&leftout);
134 igraph_destroy(&domtree);
135 igraph_destroy(&g);
136
137 /* -------------------------------------------------------------------*/
138
139 igraph_vector_init(&dom, 0);
140 igraph_vector_init(&leftout, 0);
141
142 igraph_small(&g, 10, IGRAPH_DIRECTED,
143 0, 9,
144 1, 0, 1, 2,
145 2, 3, 2, 7,
146 3, 1,
147 4, 1, 4, 3,
148 5, 2, 5, 3, 5, 4, 5, 8,
149 6, 5, 6, 9,
150 8, 7,
151 -1);
152
153 igraph_dominator_tree(&g, /*root=*/ 9, &dom, &domtree,
154 &leftout, /*mode=*/ IGRAPH_IN);
155 igraph_vector_print(&dom);
156 igraph_vector_print(&leftout);
157 igraph_write_graph_edgelist(&domtree, stdout);
158
159 igraph_vector_destroy(&dom);
160 igraph_vector_destroy(&leftout);
161 igraph_destroy(&domtree);
162 igraph_destroy(&g);
163
164 return 0;
165 }
166