| blob | 2487be326c4b80e82732d275912b616263a8eeb3 |
1 <!-- This file is part of Shapes. -->
2 <!-- -->
3 <!-- Shapes is free software: you can redistribute it and/or modify -->
4 <!-- it under the terms of the GNU General Public License as published by -->
5 <!-- the Free Software Foundation, either version 3 of the License, or -->
6 <!-- any later version. -->
7 <!-- -->
8 <!-- Shapes is distributed in the hope that it will be useful, -->
9 <!-- but WITHOUT ANY WARRANTY; without even the implied warranty of -->
10 <!-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -->
11 <!-- GNU General Public License for more details. -->
12 <!-- -->
13 <!-- You should have received a copy of the GNU General Public License -->
14 <!-- along with Shapes. If not, see <http://www.gnu.org/licenses/>. -->
15 <!-- -->
16 <!-- Copyright 2013, 2014 Henrik Tidefelt -->
18 <section id="types/graphs">
19 <title>Graphs</title>
20 <top>
21 <p>A graph is a data structure with nodes and edges. They can be modeled in many ways, but <str-Shapes /> comes with one set built-in types that define the preferred way of representing graphs in <str-Shapes />. Since the types are built-in, the allow for a more efficient implementation than would could be obtained with user-defined types. The need for a graph data structure is discussed in the <a part="tutorial" id="chap-graphs" />.</p>
22 </top>
24 <coretype name="GraphKey">
25 <abstraction>
26 <p>A key identifying some entity in a graph, like a node or a graph partition.</p>
27 </abstraction>
28 <definition>
29 <union-type><named-type name="Symbol" /><named-type name="Integer" /></union-type>
30 </definition>
31 </coretype>
33 <coretype name="Node">
34 <type-parameters>
35 <parameter name="N">
36 <description>
37 <p>Type of node values.</p>
38 </description>
39 </parameter>
40 <parameter name="E">
41 <description>
42 <p>Type of edge values.</p>
43 </description>
44 </parameter>
45 </type-parameters>
46 <abstraction>
47 <p>The <self /> type is a reference to a node belonging to a particular graph. It gives constant time access to the referenced graph node.</p>
48 </abstraction>
49 <see-also>
50 <named-type name="Edge" /> <named-type name="Graph" /> <named-type name="NodeData" />
51 </see-also>
52 <construction>
53 </construction>
54 <fields>
55 <type-field name="value">
56 <type><parameter-type name="N" /></type>
57 <description><p>The value associated with the node.</p></description>
58 </type-field>
59 <type-field name="key">
60 <type><named-type name="GraphKey" /></type>
61 <description><p>The key used to retrieve the <self /> from the <named-type name="Graph" />.</p></description>
62 </type-field>
63 <type-field name="partition">
64 <type><union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type></type>
65 <description>
66 <p>Graph partition. Unless <value-the-void />, the node will not be adjacent to other nodes in the same partition.</p>
67 </description>
68 </type-field>
69 <type-field name="index">
70 <type><named-type name="Integer" /></type>
71 <description><p>Each node in the graph has a unique value in a range starting from zero. It is generally not identical to the <field name="key" /> even if all keys are of type <named-type name="Integer" />.</p></description>
72 </type-field>
73 <type-field name="u_degree">
74 <type><named-type name="Integer" /></type>
75 <description><p>Number of undirected edges incident to the node. Loop edges count twice.</p></description>
76 </type-field>
77 <type-field name="d_degree_in">
78 <type><named-type name="Integer" /></type>
79 <description><p>Number of directed edges with target at the node.</p></description>
80 </type-field>
81 <type-field name="d_degree_out">
82 <type><named-type name="Integer" /></type>
83 <description><p>Number of directed edges with source at the node.</p></description>
84 </type-field>
85 <type-field name="d_degree">
86 <type><named-type name="Integer" /></type>
87 <description><p>The sum of <field name="d_degree_in" /> and <field name="d_degree_out" />. Note that loop edges will count twice.</p></description>
88 </type-field>
89 <type-field name="degree">
90 <type><named-type name="Integer" /></type>
91 <description><p>The sum of <field name="u_degree" /> and <field name="d_degree" />.</p></description>
92 </type-field>
93 <type-field name="u_loop_count">
94 <type><named-type name="Integer" /></type>
95 <description><p>Number of undirected loop edges incident to the node. Each loop counts once.</p></description>
96 </type-field>
97 <type-field name="d_loop_count">
98 <type><named-type name="Integer" /></type>
99 <description><p>Number of directed loop edges incident to the node. Each loop counts once.</p></description>
100 </type-field>
101 <type-field name="loop_count">
102 <type><named-type name="Integer" /></type>
103 <description><p>The sum of <field name="u_loop_count"/> and <field name="d_loop_count"/>.</p></description>
104 </type-field>
105 <type-method name="u_edges">
106 <function>
107 <case>
108 <arguments>
109 <arg identifier="loops">
110 <type><named-type name="Boolean"/></type>
111 <default><value-the-true /></default>
112 </arg>
113 </arguments>
114 <result>
115 <type>
116 <parameterized-type name="Seq">
117 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
118 </parameterized-type>
119 </type>
120 </result>
121 <description>
122 <p>Finds all incident undirected edges. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />. Loop edges are only included once.</p>
123 </description>
124 </case>
125 </function>
126 </type-method>
127 <type-method name="u_multiedges">
128 <function>
129 <case>
130 <arguments>
131 <arg identifier="loops">
132 <type><named-type name="Boolean"/></type>
133 <default><value-the-true /></default>
134 </arg>
135 </arguments>
136 <result>
137 <type>
138 <parameterized-type name="Seq">
139 <parameterized-type name="UMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
140 </parameterized-type>
141 </type>
142 </result>
143 <description>
144 <p>Similar to <field name="u_edges" />, but with parallel edges grouped as multiedges.</p>
145 </description>
146 </case>
147 </function>
148 </type-method>
149 <type-method name="d_edges_in">
150 <function>
151 <case>
152 <arguments>
153 <arg identifier="loops">
154 <type><named-type name="Boolean"/></type>
155 <default><value-the-true /></default>
156 </arg>
157 </arguments>
158 <result>
159 <type>
160 <parameterized-type name="Seq">
161 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
162 </parameterized-type>
163 </type>
164 </result>
165 <description>
166 <p>Finds all incident directed edges with target at the current node. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />.</p>
167 </description>
168 </case>
169 </function>
170 </type-method>
171 <type-method name="d_multiedges_in">
172 <function>
173 <case>
174 <arguments>
175 <arg identifier="loops">
176 <type><named-type name="Boolean"/></type>
177 <default><value-the-true /></default>
178 </arg>
179 </arguments>
180 <result>
181 <type>
182 <parameterized-type name="Seq">
183 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
184 </parameterized-type>
185 </type>
186 </result>
187 <description>
188 <p>Similar to <field name="d_edges_in" />, but with parallel edges grouped as multiedges.</p>
189 </description>
190 </case>
191 </function>
192 </type-method>
193 <type-method name="d_edges_out">
194 <function>
195 <case>
196 <arguments>
197 <arg identifier="loops">
198 <type><named-type name="Boolean"/></type>
199 <default><value-the-true /></default>
200 </arg>
201 </arguments>
202 <result>
203 <type>
204 <parameterized-type name="Seq">
205 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
206 </parameterized-type>
207 </type>
208 </result>
209 <description>
210 <p>Finds all incident directed edges with source at the curret node. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />.</p>
211 </description>
212 </case>
213 </function>
214 </type-method>
215 <type-method name="d_multiedges_out">
216 <function>
217 <case>
218 <arguments>
219 <arg identifier="loops">
220 <type><named-type name="Boolean"/></type>
221 <default><value-the-true /></default>
222 </arg>
223 </arguments>
224 <result>
225 <type>
226 <parameterized-type name="Seq">
227 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
228 </parameterized-type>
229 </type>
230 </result>
231 <description>
232 <p>Similar to <field name="d_edges_out" />, but with parallel edges grouped as multiedges.</p>
233 </description>
234 </case>
235 </function>
236 </type-method>
237 <type-method name="edges_in">
238 <function>
239 <case>
240 <arguments>
241 <arg identifier="loops">
242 <type><named-type name="Boolean"/></type>
243 <default><value-the-true /></default>
244 </arg>
245 </arguments>
246 <result>
247 <type>
248 <parameterized-type name="Seq">
249 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
250 </parameterized-type>
251 </type>
252 </result>
253 <description>
254 <p>The union of edges obtained with <field name="u_edges" /> and <field name="d_edges_in" />.</p>
255 </description>
256 </case>
257 </function>
258 </type-method>
259 <type-method name="multiedges_in">
260 <function>
261 <case>
262 <arguments>
263 <arg identifier="loops">
264 <type><named-type name="Boolean"/></type>
265 <default><value-the-true /></default>
266 </arg>
267 </arguments>
268 <result>
269 <type>
270 <parameterized-type name="Seq">
271 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
272 </parameterized-type>
273 </type>
274 </result>
275 <description>
276 <p>Similar to <field name="edges_in" />, but with parallel edges grouped as multiedges.</p>
277 </description>
278 </case>
279 </function>
280 </type-method>
281 <type-method name="edges_out">
282 <function>
283 <case>
284 <arguments>
285 <arg identifier="loops">
286 <type><named-type name="Boolean"/></type>
287 <default><value-the-true /></default>
288 </arg>
289 </arguments>
290 <result>
291 <type>
292 <parameterized-type name="Seq">
293 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
294 </parameterized-type>
295 </type>
296 </result>
297 <description>
298 <p>The union of edges obtained with <field name="u_edges" /> and <field name="d_edges_out" />.</p>
299 </description>
300 </case>
301 </function>
302 </type-method>
303 <type-method name="multiedges_out">
304 <function>
305 <case>
306 <arguments>
307 <arg identifier="loops">
308 <type><named-type name="Boolean"/></type>
309 <default><value-the-true /></default>
310 </arg>
311 </arguments>
312 <result>
313 <type>
314 <parameterized-type name="Seq">
315 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
316 </parameterized-type>
317 </type>
318 </result>
319 <description>
320 <p>Similar to <field name="edges_out" />, but with parallel edges grouped as multiedges.</p>
321 </description>
322 </case>
323 </function>
324 </type-method>
325 <type-method name="edges">
326 <function>
327 <case>
328 <arguments>
329 <arg identifier="loops">
330 <type><named-type name="Boolean"/></type>
331 <default><value-the-true /></default>
332 </arg>
333 </arguments>
334 <result>
335 <type>
336 <parameterized-type name="Seq">
337 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
338 </parameterized-type>
339 </type>
340 </result>
341 <description>
342 <p>The results of <field name="u_edges" />, <field name="d_edges_in" />, and <field name="d_edges_out" /> taken together, except for directed loops that are only included once.</p>
343 </description>
344 </case>
345 </function>
346 </type-method>
347 <type-method name="multiedges">
348 <function>
349 <case>
350 <arguments>
351 <arg identifier="loops">
352 <type><named-type name="Boolean"/></type>
353 <default><value-the-true /></default>
354 </arg>
355 </arguments>
356 <result>
357 <type>
358 <parameterized-type name="Seq">
359 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
360 </parameterized-type>
361 </type>
362 </result>
363 <description>
364 <p>Similar to <field name="multiedges" />, but with parallel edges grouped as multiedges.</p>
365 </description>
366 </case>
367 </function>
368 </type-method>
369 <type-method name="u_loops">
370 <function>
371 <case>
372 <arguments>
373 </arguments>
374 <result>
375 <type>
376 <parameterized-type name="Seq">
377 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
378 </parameterized-type>
379 </type>
380 </result>
381 <description>
382 <p>All undirected loop edges incident to the node. Each loop edge is only included once.</p>
383 </description>
384 </case>
385 </function>
386 </type-method>
387 <type-method name="u_multiloops">
388 <function>
389 <case>
390 <arguments>
391 </arguments>
392 <result>
393 <type>
394 <parameterized-type name="Seq">
395 <parameterized-type name="UMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
396 </parameterized-type>
397 </type>
398 </result>
399 <description>
400 <p>Similar to <field name="u_loops" />, but with parallel edges grouped as multiedges. Note that the returned sequence will contain at most one element.</p>
401 </description>
402 </case>
403 </function>
404 </type-method>
405 <type-method name="d_loops">
406 <function>
407 <case>
408 <arguments>
409 </arguments>
410 <result>
411 <type>
412 <parameterized-type name="Seq">
413 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
414 </parameterized-type>
415 </type>
416 </result>
417 <description>
418 <p>All directed loop edges incident to the node. Each loop edge is only included once.</p>
419 </description>
420 </case>
421 </function>
422 </type-method>
423 <type-method name="d_multiloops">
424 <function>
425 <case>
426 <arguments>
427 </arguments>
428 <result>
429 <type>
430 <parameterized-type name="Seq">
431 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
432 </parameterized-type>
433 </type>
434 </result>
435 <description>
436 <p>Similar to <field name="d_loops" />, but with parallel edges grouped as multiedges. Note that the returned sequence will contain at most one element.</p>
437 </description>
438 </case>
439 </function>
440 </type-method>
441 <type-method name="loops">
442 <function>
443 <case>
444 <arguments>
445 </arguments>
446 <result>
447 <type>
448 <parameterized-type name="Seq">
449 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
450 </parameterized-type>
451 </type>
452 </result>
453 <description>
454 <p>The union of edges obtained with <field name="u_loops" /> and <field name="d_loops" />.</p>
455 </description>
456 </case>
457 </function>
458 </type-method>
459 <type-method name="multiloops">
460 <function>
461 <case>
462 <arguments>
463 </arguments>
464 <result>
465 <type>
466 <parameterized-type name="Seq">
467 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
468 </parameterized-type>
469 </type>
470 </result>
471 <description>
472 <p>The union of multiedges obtained with <field name="u_multiloops" /> and <field name="d_multiloops" />.</p>
473 </description>
474 </case>
475 </function>
476 </type-method>
477 <type-method name="trace">
478 <function>
479 <case>
480 <arguments>
481 <arg identifier="edge">
482 <type>
483 <union-type>
484 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
485 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
486 </union-type>
487 </type>
488 </arg>
489 </arguments>
490 <result>
491 <type>
492 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
493 </type>
494 </result>
495 <description>
496 <p>Get the <named-type name="Node" /> on the other side of <arg name="edge" />. It is an error if <arg name="edge" /> is not incident to the current node, or if <arg name="edge"/> is directed but does not have the current node as source.</p>
497 </description>
498 </case>
499 </function>
500 </type-method>
501 <type-method name="backtrace">
502 <function>
503 <case>
504 <arguments>
505 <arg identifier="edge">
506 <type>
507 <union-type>
508 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
509 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
510 </union-type>
511 </type>
512 </arg>
513 </arguments>
514 <result>
515 <type>
516 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
517 </type>
518 </result>
519 <description>
520 <p>Get the <named-type name="Node" /> on the other side of <arg name="edge" />. It is an error if <arg name="edge" /> is not incident to the current node, or if <arg name="edge"/> is directed but does not have the current node as target.</p>
521 </description>
522 </case>
523 </function>
524 </type-method>
525 <type-method name="u_neighbors">
526 <function>
527 <case>
528 <arguments>
529 <arg identifier="loops">
530 <type><named-type name="Boolean"/></type>
531 <default><value-the-true /></default>
532 </arg>
533 <arg identifier="parallel">
534 <type><named-type name="Boolean"/></type>
535 <default><value-the-true /></default>
536 </arg>
537 </arguments>
538 <result>
539 <type>
540 <parameterized-type name="Seq">
541 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
542 </parameterized-type>
543 </type>
544 </result>
545 <description>
546 <p>All nodes on the other side of an undirected edge incident to the current node. Loop edges count twice, and each parallel edge counts once. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
547 </description>
548 </case>
549 </function>
550 </type-method>
551 <type-method name="d_neighbors_in">
552 <function>
553 <case>
554 <arguments>
555 <arg identifier="loops">
556 <type><named-type name="Boolean"/></type>
557 <default><value-the-true /></default>
558 </arg>
559 <arg identifier="parallel">
560 <type><named-type name="Boolean"/></type>
561 <default><value-the-true /></default>
562 </arg>
563 </arguments>
564 <result>
565 <type>
566 <parameterized-type name="Seq">
567 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
568 </parameterized-type>
569 </type>
570 </result>
571 <description>
572 <p>All nodes on the other side of a directed edge with target at the current node. Each parallel edge counts once, as do loop edges. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
573 </description>
574 </case>
575 </function>
576 </type-method>
577 <type-method name="d_neighbors_out">
578 <function>
579 <case>
580 <arguments>
581 <arg identifier="loops">
582 <type><named-type name="Boolean"/></type>
583 <default><value-the-true /></default>
584 </arg>
585 <arg identifier="parallel">
586 <type><named-type name="Boolean"/></type>
587 <default><value-the-true /></default>
588 </arg>
589 </arguments>
590 <result>
591 <type>
592 <parameterized-type name="Seq">
593 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
594 </parameterized-type>
595 </type>
596 </result>
597 <description>
598 <p>All nodes on the other side of a directed edge with source at the current node. Each parallel edge counts once, as do loop edges. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
599 </description>
600 </case>
601 </function>
602 </type-method>
603 <type-method name="neighbors_in">
604 <function>
605 <case>
606 <arguments>
607 <arg identifier="loops">
608 <type><named-type name="Boolean"/></type>
609 <default><value-the-true /></default>
610 </arg>
611 <arg identifier="parallel">
612 <type><named-type name="Boolean"/></type>
613 <default><value-the-true /></default>
614 </arg>
615 </arguments>
616 <result>
617 <type>
618 <parameterized-type name="Seq">
619 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
620 </parameterized-type>
621 </type>
622 </result>
623 <description>
624 <p>The results of <field name="u_neighbors"/> and <field name="d_neighbors_in"/> taken together. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
625 </description>
626 </case>
627 </function>
628 </type-method>
629 <type-method name="neighbors_out">
630 <function>
631 <case>
632 <arguments>
633 <arg identifier="loops">
634 <type><named-type name="Boolean"/></type>
635 <default><value-the-true /></default>
636 </arg>
637 <arg identifier="parallel">
638 <type><named-type name="Boolean"/></type>
639 <default><value-the-true /></default>
640 </arg>
641 </arguments>
642 <result>
643 <type>
644 <parameterized-type name="Seq">
645 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
646 </parameterized-type>
647 </type>
648 </result>
649 <description>
650 <p>The results of <field name="u_neighbors"/> and <field name="d_neighbors_out"/> taken together. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
651 </description>
652 </case>
653 </function>
654 </type-method>
655 <type-method name="neighbors">
656 <function>
657 <case>
658 <arguments>
659 <arg identifier="loops">
660 <type><named-type name="Boolean"/></type>
661 <default><value-the-true /></default>
662 </arg>
663 <arg identifier="parallel">
664 <type><named-type name="Boolean"/></type>
665 <default><value-the-true /></default>
666 </arg>
667 </arguments>
668 <result>
669 <type>
670 <parameterized-type name="Seq">
671 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
672 </parameterized-type>
673 </type>
674 </result>
675 <description>
676 <p>The results of <field name="u_neighbors"/>, <field name="d_neighbors_in"/>, and <field name="d_neighbors_out"/> taken together. Loops can be excluded by setting <arg name="loops" /> to <value-the-false />, and setting <arg name="parallel"/> to <value-the-false /> gives only unique nodes in the result.</p>
677 </description>
678 </case>
679 </function>
680 </type-method>
681 <type-method name="get_graph">
682 <function>
683 <case>
684 <arguments>
685 </arguments>
686 <result>
687 <type>
688 <parameterized-type name="Graph">
689 <parameter-type name="N"/><parameter-type name="E"/>
690 </parameterized-type>
691 </type>
692 </result>
693 <description>
694 <p>Get the graph to which the node belongs.</p>
695 </description>
696 </case>
697 </function>
698 </type-method>
699 </fields>
700 </coretype>
702 <coretype name="Edge">
703 <type-parameters>
704 <parameter name="N">
705 <description>
706 <p>Type of node values.</p>
707 </description>
708 </parameter>
709 <parameter name="E">
710 <description>
711 <p>Type of edge values.</p>
712 </description>
713 </parameter>
714 </type-parameters>
715 <abstraction>
716 <p>The <self /> type is a reference to an edge belonging to a particular graph. It gives constant time access to the referenced graph edge.</p>
717 </abstraction>
718 <see-also>
719 <named-type name="Node" /> <named-type name="Graph" /> <named-type name="EdgeData" />
720 </see-also>
721 <construction>
722 </construction>
723 <fields>
724 <type-field name="directed?">
725 <type><named-type name="Boolean" /></type>
726 <description><p>Whether the edge is directed or undirected.</p></description>
727 </type-field>
728 <type-field name="source">
729 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
730 <description><p>The source of a directed edge, or one of the nodes incident to an undirected edge. <field name="source" /> and <field name="target"/> are only identical for undirected edges in case of loops.</p></description>
731 </type-field>
732 <type-field name="target">
733 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
734 <description><p>The target of a directed edge, or one of the nodes incident to an undirected edge. <field name="source" /> and <field name="target"/> are only identical for undirected edges in case of loops.</p></description>
735 </type-field>
736 <type-field name="value">
737 <type><parameter-type name="E" /></type>
738 <description><p>The value associated with the edge.</p></description>
739 </type-field>
740 <type-field name="label">
741 <type><named-type name="GraphKey" /></type>
742 <description><p>A label which may be used in combination with <field name="source" /> and <field name="target" /> to identify the edge. Note that, in general, the label does not have to be unique, even for a given pair of <field name="source" /> and <field name="target" />.</p></description>
743 </type-field>
744 <type-field name="index">
745 <type><named-type name="Integer" /></type>
746 <description><p>Each edge in the graph has a unique value in a range starting from zero.</p></description>
747 </type-field>
748 <type-method name="get_graph">
749 <function>
750 <case>
751 <arguments>
752 </arguments>
753 <result>
754 <type>
755 <parameterized-type name="Graph">
756 <parameter-type name="N"/><parameter-type name="E"/>
757 </parameterized-type>
758 </type>
759 </result>
760 <description>
761 <p>Get the graph to which the edge belongs.</p>
762 </description>
763 </case>
764 </function>
765 </type-method>
766 </fields>
767 </coretype>
769 <coretype name="UEdge">
770 <type-parameters>
771 <parameter name="N">
772 <description>
773 <p>Type of node values.</p>
774 </description>
775 </parameter>
776 <parameter name="E">
777 <description>
778 <p>Type of edge values.</p>
779 </description>
780 </parameter>
781 </type-parameters>
782 <abstraction>
783 <p>An undirected edge.</p>
784 </abstraction>
785 <definition>
786 <intersection-type>
787 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
788 <structure-type>
789 <field name="directed?">
790 <type><singleton-type><value-the-false /></singleton-type></type>
791 </field>
792 </structure-type>
793 </intersection-type>
794 </definition>
795 </coretype>
797 <coretype name="DEdge">
798 <type-parameters>
799 <parameter name="N">
800 <description>
801 <p>Type of node values.</p>
802 </description>
803 </parameter>
804 <parameter name="E">
805 <description>
806 <p>Type of edge values.</p>
807 </description>
808 </parameter>
809 </type-parameters>
810 <abstraction>
811 <p>A directed edge.</p>
812 </abstraction>
813 <definition>
814 <intersection-type>
815 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
816 <structure-type>
817 <field name="directed?">
818 <type><singleton-type><value-the-true /></singleton-type></type>
819 </field>
820 </structure-type>
821 </intersection-type>
822 </definition>
823 </coretype>
825 <coretype name="MultiEdge">
826 <type-parameters>
827 <parameter name="N">
828 <description>
829 <p>Type of node values.</p>
830 </description>
831 </parameter>
832 <parameter name="E">
833 <description>
834 <p>Type of edge values.</p>
835 </description>
836 </parameter>
837 </type-parameters>
838 <abstraction>
839 <p>The <self /> type is set of parallel edges. It provides a simplified way of working with multigraphs when one is not interested in the multiplicity of parallel edges. Two edges (compare <named-type name="Edge" />) are parallel if and only if they are both directed or both undirected, and have the same source and target nodes.</p>
840 </abstraction>
841 <see-also>
842 <named-type name="Edge" /> <named-type name="Graph" />
843 </see-also>
844 <construction>
845 </construction>
846 <fields>
847 <type-field name="directed?">
848 <type><named-type name="Boolean" /></type>
849 <description><p>Whether the parallel edges are directed or undirected.</p></description>
850 </type-field>
851 <type-field name="source">
852 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
853 <description><p>The common source node of the parallel edges.</p></description>
854 </type-field>
855 <type-field name="target">
856 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
857 <description><p>The common target node of the parallel edges.</p></description>
858 </type-field>
859 <type-field name="count">
860 <type><named-type name="Integer" /></type>
861 <description><p>The multiplicity of the parallel edges. That is, the length of <field name="edges" />, which is always positive.</p></description>
862 </type-field>
863 <type-field name="edges">
864 <type>
865 <parameterized-type name="Seq">
866 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
867 </parameterized-type>
868 </type>
869 <description>
870 <p>The individual parallel edges, ordered by their <field name="index"/>.</p>
871 <p>There is always at least one edge in the sequence.</p>
872 </description>
873 </type-field>
874 <type-field name="u_edges">
875 <type>
876 <parameterized-type name="Seq">
877 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
878 </parameterized-type>
879 </type>
880 <description><p>Identical to <field name="edges" />, except that it is only allowed when the parallel edges are undirected.</p></description>
881 </type-field>
882 <type-field name="d_edges">
883 <type>
884 <parameterized-type name="Seq">
885 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
886 </parameterized-type>
887 </type>
888 <description><p>Identical to <field name="edges" />, except that it is only allowed when the parallel edges are directed.</p></description>
889 </type-field>
890 <type-method name="get_graph">
891 <function>
892 <case>
893 <arguments>
894 </arguments>
895 <result>
896 <type>
897 <parameterized-type name="Graph">
898 <parameter-type name="N"/><parameter-type name="E"/>
899 </parameterized-type>
900 </type>
901 </result>
902 <description>
903 <p>Get the graph to which the parallel edges belongs.</p>
904 </description>
905 </case>
906 </function>
907 </type-method>
908 </fields>
909 </coretype>
911 <coretype name="UMultiEdge">
912 <type-parameters>
913 <parameter name="N">
914 <description>
915 <p>Type of node values.</p>
916 </description>
917 </parameter>
918 <parameter name="E">
919 <description>
920 <p>Type of edge values.</p>
921 </description>
922 </parameter>
923 </type-parameters>
924 <abstraction>
925 <p>An undirected multiedge.</p>
926 </abstraction>
927 <definition>
928 <intersection-type>
929 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
930 <structure-type>
931 <field name="directed?">
932 <type><singleton-type><value-the-false /></singleton-type></type>
933 </field>
934 </structure-type>
935 </intersection-type>
936 </definition>
937 </coretype>
939 <coretype name="DMultiEdge">
940 <type-parameters>
941 <parameter name="N">
942 <description>
943 <p>Type of node values.</p>
944 </description>
945 </parameter>
946 <parameter name="E">
947 <description>
948 <p>Type of edge values.</p>
949 </description>
950 </parameter>
951 </type-parameters>
952 <abstraction>
953 <p>A directed multiedge.</p>
954 </abstraction>
955 <definition>
956 <intersection-type>
957 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
958 <structure-type>
959 <field name="directed?">
960 <type><singleton-type><value-the-true /></singleton-type></type>
961 </field>
962 </structure-type>
963 </intersection-type>
964 </definition>
965 </coretype>
967 <coretype name="Graph">
968 <type-parameters>
969 <parameter name="N">
970 <description>
971 <p>Type of node values.</p>
972 </description>
973 </parameter>
974 <parameter name="E">
975 <description>
976 <p>Type of edge values.</p>
977 </description>
978 </parameter>
979 </type-parameters>
980 <abstraction>
981 <p>Graph of nodes and edges.</p>
982 </abstraction>
983 <see-also>
984 <named-type name="Walk" />
985 </see-also>
986 <construction>
987 </construction>
988 <fields>
989 <type-field name="undirected?">
990 <type><named-type name="Boolean"/></type>
991 <description><p>Whether <em>directed</em> edges are <em>not</em> allowed in the graph's domain.</p></description>
992 </type-field>
993 <type-field name="directed?">
994 <type><named-type name="Boolean"/></type>
995 <description><p>Whether <em>undirected</em> edges are <em>not</em> allowed in the graph's domain.</p></description>
996 </type-field>
997 <type-field name="mixed?">
998 <type><named-type name="Boolean"/></type>
999 <description><p>Whether both undirected and directed edges are allowed in the graph's domain. That is, the graph's domain is neither directed nor undirected.</p></description>
1000 </type-field>
1001 <type-field name="loops?">
1002 <type><named-type name="Boolean"/></type>
1003 <description><p>Whether loop edges are allowed in the graph's domain.</p></description>
1004 </type-field>
1005 <type-field name="parallel?">
1006 <type><named-type name="Boolean"/></type>
1007 <description><p>Whether parallel edges are allowed in the graph's domain.</p></description>
1008 </type-field>
1009 <type-field name="partitioned?">
1010 <type><named-type name="Boolean"/></type>
1011 <description><p>Whether the graph's domain requires each node to belong to a partition.</p></description>
1012 </type-field>
1014 <type-field name="key_is_index?">
1015 <type><named-type name="Boolean"/></type>
1016 <description><p>Whether node keys coincide with node indices.</p></description>
1017 </type-field>
1018 <type-field name="key_is_range?">
1019 <type><named-type name="Boolean"/></type>
1020 <description><p>Whether node keys coincide with node indices plus <field name="key_offset" />.</p></description>
1021 </type-field>
1022 <type-field name="key_offset">
1023 <type><named-type name="Integer"/></type>
1024 <description><p>Node key of node with index zero. It is an error to access this field unless <field name="key_is_range?" />.</p></description>
1025 </type-field>
1026 <type-field name="partition_count">
1027 <type><named-type name="Integer"/></type>
1028 <description><p>Number of partitions, that is, the length of <field name="partitions" />. Note that a graph without any partitions may still contain nodes as long as it is not <field name="partitioned?"/>.</p></description>
1029 </type-field>
1030 <type-field name="partitions">
1031 <type>
1032 <parameterized-type name="Seq">
1033 <named-type name="GraphKey" />
1034 </parameterized-type>
1035 </type>
1036 <description><p>The keys identifying the partitions of the graph, or empty if the graph is not <field name="partitioned?" />.</p></description>
1037 </type-field>
1039 <type-field name="node_count">
1040 <type><named-type name="Integer"/></type>
1041 <description><p>Number of nodes.</p></description>
1042 </type-field>
1043 <type-field name="u_edge_count">
1044 <type><named-type name="Integer"/></type>
1045 <description><p>Number of undirected edges, including loop edges.</p></description>
1046 </type-field>
1047 <type-field name="d_edge_count">
1048 <type><named-type name="Integer"/></type>
1049 <description><p>Number of directed edges, including loop edges.</p></description>
1050 </type-field>
1051 <type-field name="edge_count">
1052 <type><named-type name="Integer"/></type>
1053 <description><p>The sum of <field name="u_edge_count"/> and <field name="d_edge_count"/>.</p></description>
1054 </type-field>
1055 <type-field name="u_loop_count">
1056 <type><named-type name="Integer"/></type>
1057 <description><p>Number of undirected loop edges.</p></description>
1058 </type-field>
1059 <type-field name="d_loop_count">
1060 <type><named-type name="Integer"/></type>
1061 <description><p>Number of directed loop edges.</p></description>
1062 </type-field>
1063 <type-field name="loop_count">
1064 <type><named-type name="Integer"/></type>
1065 <description><p>The sum of <field name="u_loop_count"/> and <field name="d_loop_count"/>.</p></description>
1066 </type-field>
1067 <type-field name="nodes">
1068 <type>
1069 <parameterized-type name="Seq">
1070 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1071 </parameterized-type>
1072 </type>
1073 <description><p>All nodes in the graph, with each node appearing at the position given by its <field name="index"/>.</p></description>
1074 </type-field>
1075 <type-field name="u_edges">
1076 <type>
1077 <parameterized-type name="Seq">
1078 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1079 </parameterized-type>
1080 </type>
1081 <description><p>All undirected edges in the graph. If the graph is undirected, each edge will appear at the position given by its <field name="index"/>.</p></description>
1082 </type-field>
1083 <type-field name="d_edges">
1084 <type>
1085 <parameterized-type name="Seq">
1086 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1087 </parameterized-type>
1088 </type>
1089 <description><p>All directed edges in the graph. If the graph is directed, each edge will appear at the position given by its <field name="index"/>.</p></description>
1090 </type-field>
1091 <type-field name="edges">
1092 <type>
1093 <parameterized-type name="Seq">
1094 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1095 </parameterized-type>
1096 </type>
1097 <description><p>All edges in the graph, with each edge appearing at the position given by its <field name="index"/>.</p></description>
1098 </type-field>
1099 <type-field name="u_multiedges">
1100 <type>
1101 <parameterized-type name="Seq">
1102 <parameterized-type name="UMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1103 </parameterized-type>
1104 </type>
1105 <description><p>All undirected multiedges in the graph.</p></description>
1106 </type-field>
1107 <type-field name="d_multiedges">
1108 <type>
1109 <parameterized-type name="Seq">
1110 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1111 </parameterized-type>
1112 </type>
1113 <description><p>All directed multiedges in the graph.</p></description>
1114 </type-field>
1115 <type-field name="multiedges">
1116 <type>
1117 <parameterized-type name="Seq">
1118 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1119 </parameterized-type>
1120 </type>
1121 <description><p>All multiedges in the graph.</p></description>
1122 </type-field>
1123 <type-method name="partition">
1124 <function>
1125 <case>
1126 <arguments>
1127 <arg identifier="key">
1128 <type>
1129 <named-type name="GraphKey" />
1130 </type>
1131 </arg>
1132 </arguments>
1133 <result>
1134 <type>
1135 <parameterized-type name="Seq">
1136 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1137 </parameterized-type>
1138 </type>
1139 </result>
1140 <description>
1141 <p>All nodes in the given partition.</p>
1142 </description>
1143 </case>
1144 </function>
1145 </type-method>
1146 <type-method name="partition_node_count">
1147 <function>
1148 <case>
1149 <arguments>
1150 <arg identifier="key">
1151 <type>
1152 <named-type name="GraphKey" />
1153 </type>
1154 </arg>
1155 </arguments>
1156 <result>
1157 <type><named-type name="Integer"/></type>
1158 </result>
1159 <description>
1160 <p>The number of nodes in the given partition.</p>
1161 </description>
1162 </case>
1163 </function>
1164 </type-method>
1166 <type-method name="item?">
1167 <function>
1168 <case>
1169 <arguments>
1170 <arg identifier="item">
1171 <type>
1172 <union-type>
1173 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1174 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1175 <parameterized-type name="MultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1176 </union-type>
1177 </type>
1178 </arg>
1179 </arguments>
1180 <result>
1181 <type>
1182 <named-type name="Boolean"/>
1183 </type>
1184 </result>
1185 <description>
1186 <p>Test if an item such as a node, an edge, or a multiedge belongs to the graph.</p>
1187 </description>
1188 </case>
1189 </function>
1190 </type-method>
1191 <type-method name="key?">
1192 <function>
1193 <case>
1194 <arguments>
1195 <arg identifier="key">
1196 <type><named-type name="GraphKey" /></type>
1197 </arg>
1198 </arguments>
1199 <result>
1200 <type>
1201 <named-type name="Boolean"/>
1202 </type>
1203 </result>
1204 <description>
1205 <p>Test if a node key is present in the graph.</p>
1206 </description>
1207 </case>
1208 </function>
1209 </type-method>
1211 <type-method name="index_node">
1212 <function>
1213 <case>
1214 <arguments>
1215 <arg identifier="index">
1216 <type><named-type name="Integer" /></type>
1217 </arg>
1218 </arguments>
1219 <result>
1220 <type>
1221 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1222 </type>
1223 </result>
1224 <description>
1225 <p>Retrieves a node in the graph identified by its index.</p>
1226 </description>
1227 </case>
1228 </function>
1229 </type-method>
1230 <type-method name="index_edge">
1231 <function>
1232 <case>
1233 <arguments>
1234 <arg identifier="index">
1235 <type><named-type name="Integer" /></type>
1236 </arg>
1237 </arguments>
1238 <result>
1239 <type>
1240 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1241 </type>
1242 </result>
1243 <description>
1244 <p>Retrieves an edge in the graph identified by its index.</p>
1245 </description>
1246 </case>
1247 </function>
1248 </type-method>
1250 <type-method name="find_node">
1251 <function>
1252 <case>
1253 <arguments>
1254 <arg identifier="key">
1255 <type><named-type name="GraphKey" /></type>
1256 </arg>
1257 </arguments>
1258 <result>
1259 <type>
1260 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1261 </type>
1262 </result>
1263 <description>
1264 <p>Finds a node in the graph identified by its key.</p>
1265 </description>
1266 </case>
1267 </function>
1268 </type-method>
1269 <type-method name="find_u_edges">
1270 <function>
1271 <case>
1272 <arguments>
1273 <arg identifier="source">
1274 <type>
1275 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1276 </type>
1277 <default><value-the-void /></default>
1278 </arg>
1279 <arg identifier="target">
1280 <type>
1281 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1282 </type>
1283 <default><value-the-void /></default>
1284 </arg>
1285 <arg identifier="label">
1286 <type>
1287 <union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1288 </type>
1289 <default><value-the-void /></default>
1290 </arg>
1291 <arg identifier="loops">
1292 <type><named-type name="Boolean"/></type>
1293 <default><value-the-true /></default>
1294 </arg>
1295 </arguments>
1296 <result>
1297 <type>
1298 <parameterized-type name="Seq">
1299 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1300 </parameterized-type>
1301 </type>
1302 </result>
1303 <description>
1304 <p>Finds all undirected edges that are incident to both <arg name="source" /> and <arg name="target"/>. The default value means any node.</p>
1305 <p>If <arg name="label" /> is a <named-type name="GraphKey" />, only edges with that label are returned. If <arg name="label" /> is <value-the-void />, any edge label will match; there is no way to only return edges that do not have a label (that is, the label being <value-the-void />).</p>
1306 <p>Loops can be excluded by setting <arg name="loops" /> to <value-the-false />. Loop edges are only included once.</p>
1307 </description>
1308 </case>
1309 </function>
1310 </type-method>
1311 <type-method name="find_d_edges">
1312 <function>
1313 <case>
1314 <arguments>
1315 <arg identifier="source">
1316 <type>
1317 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1318 </type>
1319 <default><value-the-void /></default>
1320 </arg>
1321 <arg identifier="target">
1322 <type>
1323 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1324 </type>
1325 <default><value-the-void /></default>
1326 </arg>
1327 <arg identifier="label">
1328 <type>
1329 <union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1330 </type>
1331 <default><value-the-void /></default>
1332 </arg>
1333 <arg identifier="loops">
1334 <type><named-type name="Boolean"/></type>
1335 <default><value-the-true /></default>
1336 </arg>
1337 </arguments>
1338 <result>
1339 <type>
1340 <parameterized-type name="Seq">
1341 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1342 </parameterized-type>
1343 </type>
1344 </result>
1345 <description>
1346 <p>Finds all directed edges from <arg name="source" /> to <arg name="target"/>. Analogous to <field name="find_u_edges"/>.</p>
1347 </description>
1348 </case>
1349 </function>
1350 </type-method>
1351 <type-method name="find_u_multiedges">
1352 <function>
1353 <case>
1354 <arguments>
1355 <arg identifier="source">
1356 <type>
1357 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1358 </type>
1359 <default><value-the-void /></default>
1360 </arg>
1361 <arg identifier="target">
1362 <type>
1363 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1364 </type>
1365 <default><value-the-void /></default>
1366 </arg>
1367 <arg identifier="loops">
1368 <type><named-type name="Boolean"/></type>
1369 <default><value-the-true /></default>
1370 </arg>
1371 </arguments>
1372 <result>
1373 <type>
1374 <parameterized-type name="Seq">
1375 <parameterized-type name="UMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1376 </parameterized-type>
1377 </type>
1378 </result>
1379 <description>
1380 <p>Finds all undirected multiedges that are incident to both <arg name="source" /> and <arg name="target"/>. The default value means any node.</p>
1381 <p>Unlike <field name="find_u_edges" />, it is not possible to specify an edge label; a <named-type name="MultiEdge" /> will always contain all parallel edges.</p>
1382 <p>Loops can be excluded by setting <arg name="loops" /> to <value-the-false />. Loop edges are only included once.</p>
1383 </description>
1384 </case>
1385 </function>
1386 </type-method>
1387 <type-method name="find_d_multiedges">
1388 <function>
1389 <case>
1390 <arguments>
1391 <arg identifier="source">
1392 <type>
1393 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1394 </type>
1395 <default><value-the-void /></default>
1396 </arg>
1397 <arg identifier="target">
1398 <type>
1399 <union-type><named-type name="Node" /><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1400 </type>
1401 <default><value-the-void /></default>
1402 </arg>
1403 <arg identifier="loops">
1404 <type><named-type name="Boolean"/></type>
1405 <default><value-the-true /></default>
1406 </arg>
1407 </arguments>
1408 <result>
1409 <type>
1410 <parameterized-type name="Seq">
1411 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1412 </parameterized-type>
1413 </type>
1414 </result>
1415 <description>
1416 <p>Finds all directed multiedges from <arg name="source" /> to <arg name="target"/>. Analogous to <field name="find_u_multiedges"/>.</p>
1417 </description>
1418 </case>
1419 </function>
1420 </type-method>
1421 <type-method name="the_u_edge">
1422 <function>
1423 <case>
1424 <arguments>
1425 <arg identifier="source">
1426 <type>
1427 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1428 </type>
1429 </arg>
1430 <arg identifier="target">
1431 <type>
1432 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1433 </type>
1434 </arg>
1435 <arg identifier="label">
1436 <type>
1437 <union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1438 </type>
1439 <default><value-the-void /></default>
1440 </arg>
1441 </arguments>
1442 <result>
1443 <type>
1444 <parameterized-type name="UEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1445 </type>
1446 </result>
1447 <description>
1448 <p>Returns the only undirected edge incident to both <arg name="source" /> and <arg name="target"/>.</p>
1449 <p>If <arg name="label" /> is a <named-type name="GraphKey" />, only edges with that label are considered. If <arg name="label" /> is <value-the-void />, any edge label will match.</p>
1450 <p>It is an error if there is not exactly one matching edge.</p>
1451 </description>
1452 </case>
1453 </function>
1454 </type-method>
1455 <type-method name="the_d_edge">
1456 <function>
1457 <case>
1458 <arguments>
1459 <arg identifier="source">
1460 <type>
1461 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1462 </type>
1463 </arg>
1464 <arg identifier="target">
1465 <type>
1466 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1467 </type>
1468 </arg>
1469 <arg identifier="label">
1470 <type>
1471 <union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type>
1472 </type>
1473 <default><value-the-void /></default>
1474 </arg>
1475 </arguments>
1476 <result>
1477 <type>
1478 <parameterized-type name="DEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1479 </type>
1480 </result>
1481 <description>
1482 <p>Returns the only directed edge from <arg name="source" /> to <arg name="target"/>. Analogous to <field name="the_u_edge" />.</p>
1483 </description>
1484 </case>
1485 </function>
1486 </type-method>
1487 <type-method name="the_u_multiedge">
1488 <function>
1489 <case>
1490 <arguments>
1491 <arg identifier="source">
1492 <type>
1493 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1494 </type>
1495 </arg>
1496 <arg identifier="target">
1497 <type>
1498 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1499 </type>
1500 </arg>
1501 </arguments>
1502 <result>
1503 <type>
1504 <parameterized-type name="UMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1505 </type>
1506 </result>
1507 <description>
1508 <p>Returns the undirected multiedge incident to both <arg name="source" /> and <arg name="target"/>.</p>
1509 <p>It is an error if there is no matching edge.</p>
1510 </description>
1511 </case>
1512 </function>
1513 </type-method>
1514 <type-method name="the_d_multiedge">
1515 <function>
1516 <case>
1517 <arguments>
1518 <arg identifier="source">
1519 <type>
1520 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1521 </type>
1522 </arg>
1523 <arg identifier="target">
1524 <type>
1525 <union-type><named-type name="Node" /><named-type name="GraphKey" /></union-type>
1526 </type>
1527 </arg>
1528 </arguments>
1529 <result>
1530 <type>
1531 <parameterized-type name="DMultiEdge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1532 </type>
1533 </result>
1534 <description>
1535 <p>Returns the directed multiedge from <arg name="source" /> to <arg name="target"/>. Analogous to <field name="the_u_multiedge" />.</p>
1536 </description>
1537 </case>
1538 </function>
1539 </type-method>
1540 <type-method name="rekey_with_index">
1541 <function>
1542 <case>
1543 <arguments>
1544 <arg identifier="offset">
1545 <type>
1546 <named-type name="Integer"/>
1547 </type>
1548 <default><inline>'0</inline></default>
1549 </arg>
1550 </arguments>
1551 <result>
1552 <type>
1553 <parameterized-type name="Graph">
1554 <parameter-type name="N"/><parameter-type name="E"/>
1555 </parameterized-type>
1556 </type>
1557 </result>
1558 <description>
1559 <p>Constructs a graph where each new node key is obtained by adding <arg name="offset"/> to the current node's <field name="index"/>. If <arg name="index" /> is left at its default, this will generate a graph where the node keys coincide with the node indices.</p>
1560 </description>
1561 </case>
1562 </function>
1563 </type-method>
1564 <type-method name="with_node_values">
1565 <function>
1566 <case>
1567 <arguments>
1568 <arg identifier="values">
1569 <type>
1570 <parameterized-type name="Seq">
1571 <named-type name="Value"/>
1572 </parameterized-type>
1573 </type>
1574 </arg>
1575 </arguments>
1576 <result>
1577 <type>
1578 <parameterized-type name="Graph">
1579 <parameter-type name="N"/><parameter-type name="E"/>
1580 </parameterized-type>
1581 </type>
1582 </result>
1583 <description>
1584 <p>Constructs a graph with node values given by <arg name="values"/>. The order in <arg name="value" /> corresponds to node indices.</p>
1585 <p>The resulting graph will share most of its data except the node values with the original graph..</p>
1586 </description>
1587 </case>
1588 </function>
1589 </type-method>
1590 <type-method name="with_edge_values">
1591 <function>
1592 <case>
1593 <arguments>
1594 <arg identifier="values">
1595 <type>
1596 <parameterized-type name="Seq">
1597 <named-type name="Value"/>
1598 </parameterized-type>
1599 </type>
1600 </arg>
1601 </arguments>
1602 <result>
1603 <type>
1604 <parameterized-type name="Graph">
1605 <parameter-type name="N"/><parameter-type name="E"/>
1606 </parameterized-type>
1607 </type>
1608 </result>
1609 <description>
1610 <p>Constructs a graph with edge values given by <arg name="values"/>. The order in <arg name="value" /> corresponds to edge indices.</p>
1611 <p>The resulting graph will share most of its data except the edge values with the original graph..</p>
1612 </description>
1613 </case>
1614 </function>
1615 </type-method>
1616 <type-method name="induced_subgraph">
1617 <function>
1618 <case>
1619 <arguments>
1620 <arg identifier="nodes">
1621 <type>
1622 <parameterized-type name="Seq">
1623 <parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1624 </parameterized-type>
1625 </type>
1626 </arg>
1627 </arguments>
1628 <result>
1629 <type>
1630 <parameterized-type name="Graph">
1631 <parameter-type name="N"/><parameter-type name="E"/>
1632 </parameterized-type>
1633 </type>
1634 </result>
1635 <description>
1636 <p>Constructs the subgraph indiced by the specified nodes.</p>
1637 <p>The node indices in the resulting graph will correspond to the positions in <arg name="nodes" />. To just reorder the nodes of a graph, use this method with all nodes in <arg name="nodes"/>.</p>
1638 </description>
1639 </case>
1640 </function>
1641 </type-method>
1642 <type-method name="spanning_subgraph">
1643 <function>
1644 <case>
1645 <arguments>
1646 <arg identifier="edges">
1647 <type>
1648 <parameterized-type name="Seq">
1649 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1650 </parameterized-type>
1651 </type>
1652 </arg>
1653 </arguments>
1654 <result>
1655 <type>
1656 <parameterized-type name="Graph">
1657 <parameter-type name="N"/><parameter-type name="E"/>
1658 </parameterized-type>
1659 </type>
1660 </result>
1661 <description>
1662 <p>Constructs the spanning subgraph with the specified edges.</p>
1663 <p>The nodes of the resulting graph are identical to those of the original graph (including their indices).</p>
1664 </description>
1665 </case>
1666 </function>
1667 </type-method>
1668 </fields>
1669 <description>
1670 <p>The <self /> data structure is designed to fill the gap created by the functional language's restriction to non-recursive data structures. A recursive data structure is when a value either directly or indirectly contains a reference to itself, like a node with a reference to its neighbor, which in turn has a reference back to the first node. In an imperative language, it is possible to have nodes containing references to their adjacent nodes, and this is often the most natural and efficient way of modeling a graph.</p>
1671 <p>Since <str-Shapes /> is functional, however, there cannot be recursive data structures, and so one has to model graphs in a non-recursive manner. Of course, there are many such representations, one of the most common being some kind of adjacency matrix, where each non-zero entry in the matrix represents an edge in the graph, with the row in the matrix corresponding to the source node, and the column in the matrix corresponding to the target node. While such a matrix representation may be good for representing the graph structure alone, it is rather inconvenient when one wants values associated with the nodes and edges, and it may also be inefficient for certain operations depending on the details of the matrix representation.</p>
1672 <p><str-Shapes /> uses function calls to break the cycles that would otherwise result in recursive data structures. This sometimes turns out as member functions that are often called with no arguments, but that could still not be plain non-function fields.</p>
1673 </description>
1674 </coretype>
1676 <coretype name="Walk">
1677 <type-parameters>
1678 <parameter name="N">
1679 <description>
1680 <p>Type of node values.</p>
1681 </description>
1682 </parameter>
1683 <parameter name="E">
1684 <description>
1685 <p>Type of edge values.</p>
1686 </description>
1687 </parameter>
1688 </type-parameters>
1689 <abstraction>
1690 <p>The <self /> type is a walk in a particular graph. A walk has a start and an end node, and a sequence of edges that can be traced in order to get from the start node to the end node.</p>
1691 </abstraction>
1692 <see-also>
1693 <named-type name="Graph" />
1694 </see-also>
1695 <construction>
1696 </construction>
1697 <fields>
1698 <type-field name="start">
1699 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
1700 <description><p>The start node of the walk.</p></description>
1701 </type-field>
1702 <type-field name="end">
1703 <type><parameterized-type name="Node"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type></type>
1704 <description><p>The end node of the walk.</p></description>
1705 </type-field>
1706 <type-field name="edges">
1707 <type>
1708 <parameterized-type name="Seq">
1709 <parameterized-type name="Edge"><parameter-type name="N"/><parameter-type name="E"/></parameterized-type>
1710 </parameterized-type>
1711 </type>
1712 <description><p>The edges of the walk.</p></description>
1713 </type-field>
1714 <type-field name="edge_count">
1715 <type><named-type name="Integer" /></type>
1716 <description><p>Number of edges in the walk, also known as the <em>length</em> of the walk.</p></description>
1717 </type-field>
1719 <type-field name="closed?">
1720 <type><named-type name="Boolean" /></type>
1721 <description><p>The walk is closed if the start and end nodes are the same, that is, the opposite of being open.</p></description>
1722 </type-field>
1723 <type-field name="open?">
1724 <type><named-type name="Boolean" /></type>
1725 <description><p>The walk is open if the start and end nodes are different, that is, the opposite of being closed.</p></description>
1726 </type-field>
1727 <type-field name="simple?">
1728 <type><named-type name="Boolean" /></type>
1729 <description><p>The walk is simple if all nodes along the walk are distinct, except that the start and end nodes may be the same.</p></description>
1730 </type-field>
1731 <type-field name="trail?">
1732 <type><named-type name="Boolean" /></type>
1733 <description><p>The walk is a trail if all edges are distinct.</p></description>
1734 </type-field>
1735 <type-field name="node_cover?">
1736 <type><named-type name="Boolean" /></type>
1737 <description>
1738 <p>The walk is a node cover if it visits every node of the graph it belongs to.</p>
1739 <p>For example, a Hamiltonian walk is a simple node cover.</p>
1740 </description>
1741 </type-field>
1742 <type-field name="edge_cover?">
1743 <type><named-type name="Boolean" /></type>
1744 <description>
1745 <p>The walk is an edge cover if it traverses every edge of the graph it belongs to.</p>
1746 <p>Note that an Eulerian cycle is a closed trail that is also an edge cover.</p>
1747 </description>
1748 </type-field>
1749 <type-field name="graph">
1750 <type>
1751 <parameterized-type name="Graph">
1752 <parameter-type name="N"/><parameter-type name="E"/>
1753 </parameterized-type>
1754 </type>
1755 <description>
1756 <p>Graph to which the walk belongs.</p>
1757 </description>
1758 </type-field>
1759 </fields>
1760 <description>
1761 <p>A <self /> is the representation of a traversal of a graph along its edges. In general, nodes and edges may be visited zero or more times along the walk, but by placing constraints on the <named-type name="Boolean" /> properties of the walk, one obtains more specialized types of walks, such as trails or Eulerian cycles.</p>
1762 <example-with-output title="Graph walks" internal-id="types/graph-walk">
1763 <source file="doc/graph-walk.blank">
1764 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/graph-walk.blank" -->]]>
1765 </source>
1766 <stdout>
1767 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/graph-walk.stdout" -->]]>
1768 </stdout>
1769 <caption>
1770 <p>Examining the properties and iterating over a <named-type name="Walk" />.</p>
1771 </caption>
1772 </example-with-output>
1773 </description>
1774 </coretype>
1776 <coretype name="NodeData">
1777 <type-parameters>
1778 <parameter name="N">
1779 <description>
1780 <p>Type of node values.</p>
1781 </description>
1782 </parameter>
1783 </type-parameters>
1784 <abstraction>
1785 <p>The <self /> type is a structure holding data used to define a node during graph construction.</p>
1786 <p>Strictly speaking, the type only consists of the field <field name="key" />, since the other field may be omitted where <self /> is used to construct graphs. </p>
1787 </abstraction>
1788 <see-also>
1789 <named-type name="Node" /> <value namespace="..Shapes..Data" name="graph" /> <named-type name="EdgeData" />
1790 </see-also>
1791 <construction>
1792 </construction>
1793 <fields>
1794 <type-field name="key">
1795 <type><named-type name="GraphKey" /></type>
1796 <description><p>Node key.</p></description>
1797 </type-field>
1798 <type-field name="value">
1799 <type><parameter-type name="N" /></type>
1800 <description><p>The value associated with the node.</p></description>
1801 </type-field>
1802 <type-field name="partition">
1803 <type><union-type><named-type name="GraphKey" /><named-type name="Void" /></union-type></type>
1804 <description><p>Graph partition. Unless <value-the-void />, the node may not be connected to other nodes in the same partition.</p></description>
1805 </type-field>
1806 </fields>
1807 </coretype>
1809 <coretype name="EdgeData">
1810 <type-parameters>
1811 <parameter name="E">
1812 <description>
1813 <p>Type of edge values.</p>
1814 </description>
1815 </parameter>
1816 </type-parameters>
1817 <abstraction>
1818 <p>The <self /> type is a structure holding data used to define an edge during graph construction.</p>
1819 <p>Strictly speaking, the type only consists of the fields <field name="source" /> and <field name="target" />, since the other fields have default values where <self /> is used to construct graphs. </p>
1820 </abstraction>
1821 <see-also>
1822 <named-type name="Edge" /> <value namespace="..Shapes..Data" name="graph" /> <named-type name="NodeData" />
1823 </see-also>
1824 <construction>
1825 </construction>
1826 <fields>
1827 <type-field name="source">
1828 <type><named-type name="GraphKey" /></type>
1829 <description><p>The source of a directed edge, or one of the nodes incident to an undirected edge.</p></description>
1830 </type-field>
1831 <type-field name="target">
1832 <type><named-type name="GraphKey" /></type>
1833 <description><p>The target of a directed edge, or one of the nodes incident to an undirected edge.</p></description>
1834 </type-field>
1835 <type-field name="value">
1836 <type><parameter-type name="E" /></type>
1837 <description><p>The value associated with the edge.</p></description>
1838 </type-field>
1839 <type-field name="label">
1840 <type><named-type name="GraphKey" /></type>
1841 <description><p>A label which may be used in combination with <field name="source" /> and <field name="target" /> to identify the edge. Note that, in general, the label does not have to be unique, even for a given pair of <field name="source" /> and <field name="target" />.</p></description>
1842 </type-field>
1843 <type-field name="directed">
1844 <type><named-type name="Boolean" /></type>
1845 <description><p>Whether the edge is directed or undirected.</p></description>
1846 </type-field>
1847 </fields>
1848 </coretype>
1850 </section>