repl.txt (7388B)
1 2 {{alias}}( N ) 3 Compact adjacency matrix constructor. 4 5 Parameters 6 ---------- 7 N: integer 8 Number of vertices. 9 10 Returns 11 ------- 12 adj: Object 13 Compact adjacency matrix. 14 15 Examples 16 -------- 17 > var adj = {{alias}}( 4 ); 18 > adj.addEdge( 0, 1 ); 19 > adj.addEdge( 1, 2 ); 20 > adj.addEdge( 2, 3 ); 21 > adj.edges 22 [ [ 0, 1 ], [ 1, 2 ], [ 2, 3 ] ] 23 24 25 {{alias}}.fromAdjacencyList( list[, clbk[, thisArg]] ) 26 Creates a compact adjacency matrix from an adjacency list. 27 28 A callback function is provided two arguments: 29 30 - value: list element. 31 - i: list element index. 32 33 A callback function must return a list of vertices. 34 35 Parameters 36 ---------- 37 list: ArrayLikeObject|Iterable 38 Adjacency list. 39 40 clbk: Function (optional) 41 Callback to invoke for each list element. 42 43 thisArg: any (optional) 44 Callback execution context. 45 46 Returns 47 ------- 48 adj: Object 49 Compact adjacency matrix. 50 51 Examples 52 -------- 53 > var list = [ [ 1, 2 ], [ 2 ], [ 3 ], [] ]; 54 > var adj = {{alias}}.fromAdjacencyList( list ); 55 > adj.edges 56 [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ], [ 2, 3 ] ] 57 58 59 {{alias}}.fromEdges( N, edges[, clbk[, thisArg]] ) 60 Creates a compact adjacency matrix from a list of edges. 61 62 A callback function is provided two arguments: 63 64 - value: list element. 65 - i: list element index. 66 67 A callback function must return a list of vertices specifying a directed 68 edge. 69 70 Parameters 71 ---------- 72 N: integer 73 Number of vertices. 74 75 edges: ArrayLikeObject 76 List of edges. 77 78 clbk: Function (optional) 79 Callback to invoke for each list element. 80 81 thisArg: any (optional) 82 Callback execution context. 83 84 Returns 85 ------- 86 adj: Object 87 Compact adjacency matrix. 88 89 Examples 90 -------- 91 > var edges = [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ], [ 2, 3 ] ]; 92 > var adj = {{alias}}.fromEdges( 4, edges ); 93 > var bool = adj.hasEdge( 0, 2 ) 94 true 95 96 97 {{alias}}.prototype.addEdge( i, j ) 98 Adds a directed edge between two vertices. 99 100 Parameters 101 ---------- 102 i: integer 103 Starting vertex. 104 105 j: integer 106 Ending vertex. 107 108 Returns 109 ------- 110 adj: Object 111 Adjacency matrix instance. 112 113 Examples 114 -------- 115 > var adj = {{alias}}( 4 ); 116 > adj.addEdge( 0, 1 ); 117 118 119 {{alias}}.prototype.edges 120 Returns the list of all edges. 121 122 Returns 123 ------- 124 list: Array<Array> 125 List of edges. 126 127 Examples 128 -------- 129 > var adj = {{alias}}( 4 ); 130 > adj.addEdge( 0, 1 ); 131 > adj.addEdge( 0, 2 ); 132 > adj.addEdge( 1, 2 ); 133 > adj.edges 134 [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ] 135 136 137 {{alias}}.prototype.hasEdge( i, j ) 138 Checks whether a directed edge exists between two vertices. 139 140 Parameters 141 ---------- 142 i: integer 143 Starting vertex. 144 145 j: integer 146 Ending vertex. 147 148 Returns 149 ------- 150 bool: boolean 151 Boolean indicating if an edge exists. 152 153 Examples 154 -------- 155 > var adj = {{alias}}( 4 ); 156 > adj.addEdge( 0, 1 ); 157 > var bool = adj.hasEdge( 0, 1 ) 158 true 159 160 161 {{alias}}.prototype.inDegree( i ) 162 Returns the indegree of a vertex (i.e., number of edges ending at a vertex). 163 164 Parameters 165 ---------- 166 i: integer 167 Vertex. 168 169 Returns 170 ------- 171 v: integer 172 Indegree. 173 174 Examples 175 -------- 176 > var adj = {{alias}}( 4 ); 177 > adj.addEdge( 0, 1 ); 178 > adj.addEdge( 0, 2 ); 179 > adj.addEdge( 1, 2 ); 180 > adj.addEdge( 2, 3 ); 181 > var v = adj.inDegree( 2 ) 182 2 183 184 185 {{alias}}.prototype.inEdges( i ) 186 Returns a list of vertices having edges ending at a specified vertex. 187 188 Parameters 189 ---------- 190 i: integer 191 Vertex. 192 193 Returns 194 ------- 195 out: Array<integer> 196 List of vertices. 197 198 Examples 199 -------- 200 > var adj = {{alias}}( 4 ); 201 > adj.addEdge( 0, 1 ); 202 > adj.addEdge( 0, 2 ); 203 > adj.addEdge( 1, 2 ); 204 > adj.addEdge( 2, 3 ); 205 > var out = adj.inEdges( 2 ) 206 [ 0, 1 ] 207 208 209 {{alias}}.prototype.nedges 210 Returns the total number of edges. 211 212 Returns 213 ------- 214 v: integer 215 Total number of edges. 216 217 Examples 218 -------- 219 > var adj = {{alias}}( 4 ); 220 > adj.addEdge( 0, 1 ); 221 > adj.addEdge( 0, 2 ); 222 > adj.addEdge( 1, 2 ); 223 > var out = adj.nedges 224 3 225 226 227 {{alias}}.prototype.nvertices 228 Returns the total number of vertices. 229 230 Returns 231 ------- 232 v: integer 233 Total number of vertices. 234 235 Examples 236 -------- 237 > var adj = {{alias}}( 4 ); 238 > adj.addEdge( 0, 1 ); 239 > adj.addEdge( 0, 2 ); 240 > adj.addEdge( 1, 2 ); 241 > var out = adj.nvertices 242 4 243 244 245 {{alias}}.prototype.outDegree( i ) 246 Returns the outdegree of a vertex (i.e., number of edges starting at a 247 vertex). 248 249 Parameters 250 ---------- 251 i: integer 252 Vertex. 253 254 Returns 255 ------- 256 v: integer 257 Outdegree. 258 259 Examples 260 -------- 261 > var adj = {{alias}}( 4 ); 262 > adj.addEdge( 0, 1 ); 263 > adj.addEdge( 0, 2 ); 264 > adj.addEdge( 1, 2 ); 265 > adj.addEdge( 2, 3 ); 266 > var v = adj.outDegree( 2 ) 267 1 268 269 270 {{alias}}.prototype.outEdges( i ) 271 Returns a list of vertices having edges starting at a specified vertex. 272 273 Parameters 274 ---------- 275 i: integer 276 Vertex. 277 278 Returns 279 ------- 280 out: Array<integer> 281 List of vertices. 282 283 Examples 284 -------- 285 > var adj = {{alias}}( 4 ); 286 > adj.addEdge( 0, 1 ); 287 > adj.addEdge( 0, 2 ); 288 > adj.addEdge( 1, 2 ); 289 > adj.addEdge( 2, 3 ); 290 > var out = adj.outEdges( 2 ) 291 [ 3 ] 292 293 294 {{alias}}.prototype.removeEdge( i, j ) 295 Removes a directed edge between two vertices. 296 297 Parameters 298 ---------- 299 i: integer 300 Starting vertex. 301 302 j: integer 303 Ending vertex. 304 305 Returns 306 ------- 307 adj: Object 308 Adjacency matrix instance. 309 310 Examples 311 -------- 312 > var adj = {{alias}}( 4 ); 313 > adj.addEdge( 0, 1 ); 314 > adj.edges 315 316 317 {{alias}}.prototype.toAdjacencyList() 318 Returns an adjacency list representation. 319 320 Returns 321 ------- 322 out: Array<Array> 323 Adjacency list. 324 325 Examples 326 -------- 327 > var adj = {{alias}}( 4 ); 328 > adj.addEdge( 0, 1 ); 329 > adj.addEdge( 0, 2 ); 330 > adj.addEdge( 1, 2 ); 331 > adj.addEdge( 2, 3 ); 332 > var out = adj.toAdjacencyList() 333 [ [ 1, 2 ], [ 2 ], [ 3 ], [] ] 334 335 336 {{alias}}.prototype.toposort() 337 Returns a topological ordering of the directed graph. 338 339 The function returns a two-element array. 340 341 If the function is able to compute a topological ordering, the first array 342 element is the topological ordering and the second element is `null`. 343 344 If a topological ordering cannot be achieved (e.g., due to the graph not 345 being a directed acyclic graph (DAG)), the first array element is `null` and 346 the second element is the first encountered cycle. 347 348 Returns 349 ------- 350 out: Array 351 Results. 352 353 Examples 354 -------- 355 > var adj = {{alias}}( 4 ); 356 > adj.addEdge( 1, 0 ); 357 > adj.addEdge( 1, 2 ); 358 > adj.addEdge( 0, 2 ); 359 > adj.addEdge( 2, 3 ); 360 > var results = adj.toposort(); 361 > var o = results[ 0 ] 362 [ 1, 0, 2, 3 ] 363 > var c = results[ 1 ] 364 null 365 > adj.addEdge( 3, 1 ); 366 > results = adj.toposort(); 367 > o = results[ 0 ] 368 null 369 > var c = results[ 1 ] 370 [ 0, 1, 3, 2, 0 ] 371 372 See Also 373 -------- 374