# Coverage details for edu.uci.ics.jung.algorithms.metrics.TriadicCensus

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `package edu.uci.ics.jung.algorithms.metrics;`
11 |  | ``
12 |  | `import java.util.HashSet;`
13 |  | `import java.util.Iterator;`
14 |  | `import java.util.Set;`
15 |  | ``
16 |  | `import org.apache.commons.collections.CollectionUtils;`
17 |  | ``
18 |  | `import edu.uci.ics.jung.graph.DirectedGraph;`
19 |  | `import edu.uci.ics.jung.graph.Vertex;`
20 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
21 |  | ``
22 |  | `/**`
23 |  | `* TriadicCensus is a standard social network tool that counts, for each of the`
24 |  | `* different possible configurations of three vertices, the number of times`
25 |  | `* that that configuration occurs in the given graph.`
26 |  | `* This may then be compared to the set of expected counts for this particular`
27 |  | `* graph or to an expected sample. This is often used in p* modeling.`
28 |  | `* <p>`
29 |  | `* To use this class,`
30 |  | `* <pre>`
31 |  | `* long[] triad_counts = TriadicCensus(dg);`
32 |  | `* </pre>`
33 |  | `* where <code>dg</code> is a <code>DirectedGraph</code>.`
34 |  | `* ith element of the array (for i in [1,16]) is the number of`
35 |  | `* occurrences of the corresponding triad type.`
36 |  | `* (The 0th element is not meaningful; this array is effectively 1-based.)`
37 |  | `* To get the name of the ith triad (e.g. "003"),`
38 |  | `* look at the global constant array c.TRIAD_NAMES[i]`
39 |  | `* <p>`
40 |  | `* Triads are named as`
41 |  | `* (number of pairs that are mutually tied)`
42 |  | `* (number of pairs that are one-way tied)`
43 |  | `* (number of non-tied pairs)`
44 |  | `* in the triple. Since there are be only three pairs, there is a finite`
45 |  | `* set of these possible triads.`
46 |  | `* <p>`
47 |  | `* In fact, there are exactly 16, conventionally sorted by the number of`
48 |  | `* realized edges in the triad:`
49 |  | `* <table>`
50 |  | `* <tr><th>Number</th> <th>Configuration</th> <th>Notes</th></tr>`
51 |  | `* <tr><td>1</td><td>003</td><td>The empty triad</td></tr>`
52 |  | `* <tr><td>2</td><td>012</td><td></td></tr>`
53 |  | `* <tr><td>3</td><td>102</td><td></td></tr>`
54 |  | `* <tr><td>4</td><td>021D</td><td>"Down": the directed edges point away</td></tr>`
55 |  | `* <tr><td>5</td><td>021U</td><td>"Up": the directed edges meet</td></tr>`
56 |  | `* <tr><td>6</td><td>021C</td><td>"Circle": one in, one out</td></tr>`
57 |  | `* <tr><td>7</td><td>111D</td><td>"Down": 021D but one edge is mutual</td></tr>`
58 |  | `* <tr><td>8</td><td>111U</td><td>"Up": 021U but one edge is mutual</td></tr>`
59 |  | `* <tr><td>9</td><td>030T</td><td>"Transitive": two point to the same vertex</td></tr>`
60 |  | `* <tr><td>10</td><td>030C</td><td>"Circle": A->B->C->A</td></tr>`
61 |  | `* <tr><td>11</td><td>201</td><td></td></tr>`
62 |  | `* <tr><td>12</td><td>120D</td><td>"Down": 021D but the third edge is mutual</td></tr>`
63 |  | `* <tr><td>13</td><td>120U</td><td>"Up": 021U but the third edge is mutual</td></tr>`
64 |  | `* <tr><td>14</td><td>120C</td><td>"Circle": 021C but the third edge is mutual</td></tr>`
65 |  | `* <tr><td>15</td><td>210</td><td></td></tr>`
66 |  | `* <tr><td>16</td><td>300</td><td>The complete</td></tr>`
67 |  | `* </table>`
68 |  | `* <p>`
69 |  | `* This implementation takes O( m ), m is the number of edges in the graph.`
70 |  | `* <br>`
71 |  | `* It is based on`
72 |  | `* <a href="http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf">`
73 |  | `* A subquadratic triad census algorithm for large sparse networks`
74 |  | `* with small maximum degree</a>`
75 |  | `* Vladimir Batagelj and Andrej Mrvar, University of Ljubljana`
76 |  | `* Published in Social Networks.`
77 |  | `* @author Danyel Fisher`
78 |  | `*`
79 |  | `*/`
80 | 0 | `public class TriadicCensus {`
81 |  | ``
82 |  | `// NOTE THAT THIS RETURNS STANDARD 1-16 COUNT!`
83 |  | ``
84 |  | `// and their types`
85 | 1 | `public static final String[] TRIAD_NAMES = { "N/A", "003", "012", "102", "021D",`
86 |  | `"021U", "021C", "111D", "111U", "030T", "030C", "201", "120D",`
87 |  | `"120U", "120C", "210", "300" };`
88 |  | ``
89 | 1 | `public static final int MAX_TRIADS = TRIAD_NAMES.length;`
90 |  | ``
91 |  | `/**`
92 |  | `* Returns an array whose ith element (for i in [1,16]) is the number of`
93 |  | `* occurrences of the corresponding triad type in <code>g</code>.`
94 |  | `* (The 0th element is not meaningful; this array is effectively 1-based.)`
95 |  | `*`
96 |  | `* @param g`
97 |  | `*/`
98 |  | `public static long[] getCounts(DirectedGraph g)`
99 |  | `{`
100 | 8 | `long[] count = new long[MAX_TRIADS];`
101 |  | ``
102 | 8 | `Indexer id = Indexer.getIndexer(g);`
103 |  | ``
104 |  | `// apply algorithm to each edge, one at at time`
105 | 28 | `for (int i_v = 0; i_v < g.numVertices(); i_v++) {`
106 | 20 | `Vertex v = (Vertex) id.getVertex(i_v);`
107 | 20 | `for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext();) {`
108 | 26 | `int triType = -1;`
109 | 26 | `Vertex u = (Vertex) iter.next();`
110 | 26 | `if (id.getIndex(u) <= i_v)`
111 | 13 | `continue;`
112 | 13 | `Set neighbors = new HashSet(CollectionUtils.union(u`
113 |  | `.getNeighbors(), v.getNeighbors()));`
114 | 13 | `neighbors.remove(u);`
115 | 13 | `neighbors.remove(v);`
116 | 13 | `if (u.isSuccessorOf(v) && v.isSuccessorOf(u)) {`
117 | 4 | `triType = 3;`
118 |  | `} else {`
119 | 9 | `triType = 2;`
120 |  | `}`
121 | 13 | `count[triType] += g.numVertices() - neighbors.size() - 2;`
122 | 13 | `for (Iterator iterator = neighbors.iterator(); iterator`
123 | 30 | `.hasNext();) {`
124 | 17 | `Vertex w = (Vertex) iterator.next();`
125 | 17 | `if (shouldCount(id, u, v, w)) {`
126 | 7 | `count [ triType ( triCode(u, v, w) ) ] ++;`
127 |  | `}`
128 |  | `}`
129 |  | `}`
130 |  | `}`
131 | 8 | `int sum = 0;`
132 | 128 | `for (int i = 2; i <= 16; i++) {`
133 | 120 | `sum += count[i];`
134 |  | `}`
135 | 8 | `int n = g.numVertices();`
136 | 8 | `count[1] = n * (n-1) * (n-2) / 6 - sum;`
137 | 8 | `return count;`
138 |  | `}`
139 |  | ``
140 |  | `/**`
141 |  | `* This is the core of the technique in the paper. Returns an int from 0 to`
142 |  | `* 65 based on: WU -> 32 UW -> 16 WV -> 8 VW -> 4 UV -> 2 VU -> 1`
143 |  | `*`
144 |  | `*/`
145 |  | `public static int triCode(Vertex u, Vertex v, Vertex w) {`
146 | 10 | `int i = 0;`
147 | 10 | `i += link( v, u ) ? 1 : 0;`
148 | 10 | `i += link( u, v ) ? 2 : 0;`
149 | 10 | `i += link( v, w ) ? 4 : 0;`
150 | 10 | `i += link( w, v ) ? 8 : 0;`
151 | 10 | `i += link( u, w ) ? 16 : 0;`
152 | 10 | `i += link( w, u ) ? 32 : 0;`
153 | 10 | `return i;`
154 |  | `}`
155 |  | ``
156 |  | `protected static boolean link( Vertex a, Vertex b) {`
157 | 60 | `return a.isPredecessorOf(b);`
158 |  | `}`
159 |  | ``
160 |  | ``
161 |  | `/**`
162 |  | `* Simply returns the triCode.`
163 |  | `* @param triCode`
164 |  | `* @return`
165 |  | `*/`
166 |  | `public static int triType( int triCode ) {`
167 | 10 | `return codeToType[ triCode ];`
168 |  | `}`
169 |  | ``
170 |  | `/**`
171 |  | `* For debugging purposes, this is copied straight out of the paper which`
172 |  | `* means that they refer to triad types 1-16.`
173 |  | `*/`
174 | 1 | `protected static final int[] codeToType = { 1, 2, 2, 3, 2, 4, 6, 8, 2, 6, 5, 7, 3, 8,`
175 |  | `7, 11, 2, 6, 4, 8, 5, 9, 9, 13, 6, 10, 9, 14, 7, 14, 12, 15, 2, 5,`
176 |  | `6, 7, 6, 9, 10, 14, 4, 9, 9, 12, 8, 13, 14, 15, 3, 7, 8, 11, 7, 12,`
177 |  | `14, 15, 8, 14, 13, 15, 11, 15, 15, 16 };`
178 |  | ``
179 |  | `/**`
180 |  | `* Make sure we have a canonical ordering: Returns true if u < w, or v < w <`
181 |  | `* u and v doesn't link to w`
182 |  | `*`
183 |  | `* @param id`
184 |  | `* @param u`
185 |  | `* @param v`
186 |  | `* @param w`
187 |  | `* @return`
188 |  | `*/`
189 |  | `protected static boolean shouldCount(Indexer id, Vertex u, Vertex v, Vertex w) {`
190 | 17 | `int i_u = id.getIndex(u);`
191 | 17 | `int i_w = id.getIndex(w);`
192 | 17 | `if (i_u < i_w)`
193 | 5 | `return true;`
194 | 12 | `int i_v = id.getIndex(v);`
195 | 12 | `if ((i_v < i_w) && (i_w < i_u) && (!v.isNeighborOf(w)))`
196 | 2 | `return true;`
197 | 10 | `return false;`
198 |  | `}`
199 |  | ``
200 |  | `// protected void initializeCounts() {`
201 |  | `// for (int i = 0; i < count.length; i++) {`
202 |  | `// count[i] = 0;`
203 |  | `// }`
204 |  | `// }`
205 |  | ``
206 |  | `// /**`
207 |  | `// * Once you've created a triad, here's the census for that number. A triad`
208 |  | `// * census looks a little like an array: n elements inside it`
209 |  | `// *`
210 |  | `// * @param i`
211 |  | `// * @return`
212 |  | `// */`
213 |  | `// public long getCount(int i) throws IllegalArgumentException {`
214 |  | `// if ( i < 1 || i > 16)`
215 |  | `// throw new IllegalArgumentException("TriType must be 1-16");`
216 |  | `// return count[i];`
217 |  | `// }`
218 |  | ``
219 |  | `}`

this report was generated by version 1.0.5 of jcoverage. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.