Tcl Library Source Code

Check-in [bb9e30207b]
Login
Core Home Blog Docs Downloads Tickets Timeline Branches Tags Wiki

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:struct / struct::graph - Tkt [5edaf187fa] - Reworked the internal `CheckE` validation command for node filtering to treat words with a leading dash after -in, etc. as node names instead of invalid options, until a valid option is seen again, or the end of the command is reached, whichever comes first. This behaviour is now documented. Version bump 2.4.2 - (B) struct::graph - (T) struct::graph - (D) struct::graph
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: bb9e30207bc98ad56aab544131411ab361cf6050cf3187c5feeac03f586ad964
User & Date: aku 2019-04-13 03:36:23.428
References
2019-08-14
21:22
struct - graph - Tkt [5edaf187fa] - Followup on commit [bb9e30207b]. That commit fixed the Tcl implementation, failed to fix the C implemention. Fixed the C implementation now, completing the ticket. Closed-Leaf check-in: f47dac9903 user: aku tags: ak-tkt-6db9fe84d1-struct-graph-crash
2019-04-13
03:38 • Closed ticket [5edaf187fa]: struct::graph is inconsistent about the support of nodes starting with a dash plus 6 other changes artifact: 87591b9bc8 user: aku
Context
2019-04-15
19:22
virtchannel-base, tcl::chan::cat - Tkt [1975182bdd] Fixed non-functional event handling of the channel. Version bump 1.0.3 - B (tcl::chan::cat) - T (tcl::chan::cat, NEW) check-in: aeb3bec0da user: aku tags: trunk
2019-04-13
03:36
struct / struct::graph - Tkt [5edaf187fa] - Reworked the internal `CheckE` validation command for node filtering to treat words with a leading dash after -in, etc. as node names instead of invalid options, until a valid option is seen again, or the end of the command is reached, whichever comes first. This behaviour is now documented. Version bump 2.4.2 - (B) struct::graph - (T) struct::graph - (D) struct::graph check-in: bb9e30207b user: aku tags: trunk
2019-04-12
21:59
mime - Tkt [57909d2e1c] - Issue introduced with commit [913f7d92c5c35342]. Conversion of superfluous nested `expr` command forgot to convert braces to proper parens. This was able to break \r detection at the end of a line. - Further properly indented some of the code around this. - Lastly removed superflous reboxing of `mime::initializeaux` in `mime::initialize`. The command got boxed followed by immediate unboxing, making the whole thing superflous. Version bump 1.6.1 - (B) mime - (T) mime check-in: b2ae85b606 user: aku tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to embedded/md/tcllib/files/modules/struct/graph.md. 
1
2
3
4
5
6
7
8
9
10
11
12


[//000000001]: # (struct::graph \- Tcl Data Structures)
[//000000002]: # (Generated from file 'graph\.man' by tcllib/doctools with format 'markdown')
[//000000003]: # (Copyright &copy; 2002\-2009 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>)
[//000000004]: # (struct::graph\(n\) 2\.4\.1 tcllib "Tcl Data Structures")

<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> &#124; <a
href="../../../toc.md">Table Of Contents</a> &#124; <a
href="../../../../index.md">Keyword Index</a> &#124; <a
href="../../../../toc0.md">Categories</a> &#124; <a
href="../../../../toc1.md">Modules</a> &#124; <a
href="../../../../toc2.md">Applications</a> ] <hr>




|
|








1
2
3
4
5
6
7
8
9
10
11
12


[//000000001]: # (struct::graph \- Tcl Data Structures)
[//000000002]: # (Generated from file 'graph\.man' by tcllib/doctools with format 'markdown')
[//000000003]: # (Copyright &copy; 2002\-2009,2019 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>)
[//000000004]: # (struct::graph\(n\) 2\.4\.2 tcllib "Tcl Data Structures")

<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> &#124; <a
href="../../../toc.md">Table Of Contents</a> &#124; <a
href="../../../../index.md">Keyword Index</a> &#124; <a
href="../../../../toc0.md">Categories</a> &#124; <a
href="../../../../toc1.md">Modules</a> &#124; <a
href="../../../../toc2.md">Applications</a> ] <hr>
︙︙
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

  - [Category](#category)

  - [Copyright](#copyright)

# <a name='synopsis'></a>SYNOPSIS

package require Tcl 8\.4  
package require struct::graph ?2\.4\.1?  
package require struct::list ?1\.5?  
package require struct::set ?2\.2\.3?  

[__::struct::graph__ ?*graphName*? ?__=__&#124;__:=__&#124;__as__&#124;__deserialize__ *source*?](#1)  
[__graphName__ *option* ?*arg arg \.\.\.*?](#2)  
[*graphName* __=__ *sourcegraph*](#3)  
[*graphName* __\-\->__ *destgraph*](#4)  








|








32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

  - [Category](#category)

  - [Copyright](#copyright)

# <a name='synopsis'></a>SYNOPSIS

package require Tcl 8\.4  
package require struct::graph ?2\.4\.2?  
package require struct::list ?1\.5?  
package require struct::set ?2\.2\.3?  

[__::struct::graph__ ?*graphName*? ?__=__&#124;__:=__&#124;__as__&#124;__deserialize__ *source*?](#1)  
[__graphName__ *option* ?*arg arg \.\.\.*?](#2)  
[*graphName* __=__ *sourcegraph*](#3)  
[*graphName* __\-\->__ *destgraph*](#4)
︙︙
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

    containing all arcs is returned\. Restrictions can limit the list of returned
    arcs based on the nodes that are connected by the arc, on the keyed values
    associated with the arc, or both\. A general filter command can be used as
    well\. The restrictions that involve connected nodes take a variable number
    of nodes as argument, specified after the name of the restriction itself\.

    The restrictions imposed by either __\-in__, __\-out__, __\-adj__,
    __\-inner__, or __\-embedded__ are applied first\. Specifying more than
    one of them is illegal\.

    After that the restrictions set via __\-key__ \(and __\-value__\) are
    applied\. Specifying more than one __\-key__ \(and __\-value__\) is
    illegal\. Specifying __\-value__ alone, without __\-key__ is illegal as
    well\.

    Any restriction set through __\-filter__ is applied last\. Specifying more








|
|








405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

    containing all arcs is returned\. Restrictions can limit the list of returned
    arcs based on the nodes that are connected by the arc, on the keyed values
    associated with the arc, or both\. A general filter command can be used as
    well\. The restrictions that involve connected nodes take a variable number
    of nodes as argument, specified after the name of the restriction itself\.

    The restrictions imposed by either __\-in__, __\-out__, __\-adj__,
    __\-inner__, or __\-embedding__ are applied first\. Specifying more
    than one of them is illegal\.

    After that the restrictions set via __\-key__ \(and __\-value__\) are
    applied\. Specifying more than one __\-key__ \(and __\-value__\) is
    illegal\. Specifying __\-value__ alone, without __\-key__ is illegal as
    well\.

    Any restriction set through __\-filter__ is applied last\. Specifying more
︙︙
448
449
450
451
452
453
454








455
456
457
458
459
460
461

        nodes\.

      * __\-embedding__

        Return a list of all arcs adjacent to exactly one of the nodes in the
        set\. This is the set of arcs connecting the subgraph spawned by the
        specified nodes to the rest of the graph\.









      * __\-key__ *key*

        Limit the list of arcs that are returned to those arcs that have an
        associated key *key*\.

      * __\-value__ *value*








>
>
>
>
>
>
>
>








448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469

        nodes\.

      * __\-embedding__

        Return a list of all arcs adjacent to exactly one of the nodes in the
        set\. This is the set of arcs connecting the subgraph spawned by the
        specified nodes to the rest of the graph\.

    *Attention*: After the above options any word with a leading dash which is
    not a valid option is treated as a node name instead of an invalid option to
    error out on\. This condition holds until either a valid option terminates
    the list of nodes, or the end of the command is reached, whichever comes
    first\.

    The remaining filter options are:

      * __\-key__ *key*

        Limit the list of arcs that are returned to those arcs that have an
        associated key *key*\.

      * __\-value__ *value*
︙︙
590
591
592
593
594
595
596
597
598



599
600
601
602
603
604
605
606


    Return a list of nodes in the graph\. Restrictions can limit the list of
    returned nodes based on neighboring nodes, or based on the keyed values
    associated with the node\. The restrictions that involve neighboring nodes
    have a list of nodes as argument, specified after the name of the
    restriction itself\.

    The possible restrictions are the same as for method __arcs__\. The exact
    meanings change slightly, as they operate on nodes instead of arcs\. The



    command recognizes:

      * __\-in__

        Return a list of all nodes with at least one outgoing arc ending in a
        node found in the specified set of nodes\. Alternatively specified as the
        set of source nodes for the __\-in__ arcs of the node set\. The
        *incoming neighbours*\.








|
|
>
>
>
|








598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617


    Return a list of nodes in the graph\. Restrictions can limit the list of
    returned nodes based on neighboring nodes, or based on the keyed values
    associated with the node\. The restrictions that involve neighboring nodes
    have a list of nodes as argument, specified after the name of the
    restriction itself\.

    The possible restrictions are the same as for method __arcs__\. Note that
    while the exact meanings change slightly, as they operate on nodes instead
    of arcs, the general behaviour is the same, especially when it comes to the
    handling of words with a leading dash in node lists\.

    The command recognizes:

      * __\-in__

        Return a list of all nodes with at least one outgoing arc ending in a
        node found in the specified set of nodes\. Alternatively specified as the
        set of source nodes for the __\-in__ arcs of the node set\. The
        *incoming neighbours*\.
︙︙
869
870
871
872
873
874
875
876


# <a name='category'></a>CATEGORY

Data structures

# <a name='copyright'></a>COPYRIGHT

Copyright &copy; 2002\-2009 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>








|

880
881
882
883
884
885
886
887


# <a name='category'></a>CATEGORY

Data structures

# <a name='copyright'></a>COPYRIGHT

Copyright &copy; 2002\-2009,2019 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>
Changes to idoc/man/files/modules/struct/graph.n. 
1
2
3
4
5
6
7
8
9
10
11
12

'\"
'\" Generated from file 'graph\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2002-2009 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "struct::graph" n 2\&.4\&.1 tcllib "Tcl Data Structures"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,



|

|








1
2
3
4
5
6
7
8
9
10
11
12

'\"
'\" Generated from file 'graph\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2002-2009,2019 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "struct::graph" n 2\&.4\&.2 tcllib "Tcl Data Structures"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
︙︙
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

..
.BS
.SH NAME
struct::graph \- Create and manipulate directed graph objects
.SH SYNOPSIS
package require \fBTcl  8\&.4\fR
.sp
package require \fBstruct::graph  ?2\&.4\&.1?\fR
.sp
package require \fBstruct::list  ?1\&.5?\fR
.sp
package require \fBstruct::set  ?2\&.2\&.3?\fR
.sp
\fB::struct::graph\fR ?\fIgraphName\fR? ?\fB=\fR|\fB:=\fR|\fBas\fR|\fBdeserialize\fR \fIsource\fR?
.sp








|








272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

..
.BS
.SH NAME
struct::graph \- Create and manipulate directed graph objects
.SH SYNOPSIS
package require \fBTcl  8\&.4\fR
.sp
package require \fBstruct::graph  ?2\&.4\&.2?\fR
.sp
package require \fBstruct::list  ?1\&.5?\fR
.sp
package require \fBstruct::set  ?2\&.2\&.3?\fR
.sp
\fB::struct::graph\fR ?\fIgraphName\fR? ?\fB=\fR|\fB:=\fR|\fBas\fR|\fBdeserialize\fR \fIsource\fR?
.sp
︙︙
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737

of returned arcs based on the nodes that are connected by the arc, on
the keyed values associated with the arc, or both\&. A general filter
command can be used as well\&. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself\&.
.sp
The restrictions imposed by either \fB-in\fR, \fB-out\fR,
\fB-adj\fR, \fB-inner\fR, or \fB-embedded\fR are applied
first\&. Specifying more than one of them is illegal\&.
.sp
After that the restrictions set via \fB-key\fR (and
\fB-value\fR) are applied\&. Specifying more than one \fB-key\fR
(and \fB-value\fR) is illegal\&. Specifying \fB-value\fR alone,
without \fB-key\fR is illegal as well\&.
.sp








|








723
724
725
726
727
728
729
730
731
732
733
734
735
736
737

of returned arcs based on the nodes that are connected by the arc, on
the keyed values associated with the arc, or both\&. A general filter
command can be used as well\&. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself\&.
.sp
The restrictions imposed by either \fB-in\fR, \fB-out\fR,
\fB-adj\fR, \fB-inner\fR, or \fB-embedding\fR are applied
first\&. Specifying more than one of them is illegal\&.
.sp
After that the restrictions set via \fB-key\fR (and
\fB-value\fR) are applied\&. Specifying more than one \fB-key\fR
(and \fB-value\fR) is illegal\&. Specifying \fB-value\fR alone,
without \fB-key\fR is illegal as well\&.
.sp
︙︙
762
763
764
765
766
767
768











769
770
771
772
773
774
775

the set\&. This is the set of arcs in the subgraph spawned by the
specified nodes\&.
.TP
\fB-embedding\fR
Return a list of all arcs adjacent to exactly one of the nodes in the
set\&. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph\&.











.TP
\fB-key\fR \fIkey\fR
Limit the list of arcs that are returned to those arcs that have an
associated key \fIkey\fR\&.
.TP
\fB-value\fR \fIvalue\fR
This restriction can only be used in combination with








>
>
>
>
>
>
>
>
>
>
>








762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786

the set\&. This is the set of arcs in the subgraph spawned by the
specified nodes\&.
.TP
\fB-embedding\fR
Return a list of all arcs adjacent to exactly one of the nodes in the
set\&. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph\&.
.RE
.IP
\fIAttention\fR: After the above options any word with a leading dash
which is not a valid option is treated as a node name instead of an
invalid option to error out on\&. This condition holds until either a
valid option terminates the list of nodes, or the end of the command
is reached, whichever comes first\&.
.sp
The remaining filter options are:
.sp
.RS
.TP
\fB-key\fR \fIkey\fR
Limit the list of arcs that are returned to those arcs that have an
associated key \fIkey\fR\&.
.TP
\fB-value\fR \fIvalue\fR
This restriction can only be used in combination with
︙︙
892
893
894
895
896
897
898
899
900




901
902
903
904
905
906
907
908

\fIgraphName\fR \fBnodes\fR ?-key \fIkey\fR? ?-value \fIvalue\fR? ?-filter \fIcmdprefix\fR? ?-in|-out|-adj|-inner|-embedding \fInode\fR \fInode\fR\&.\&.\&.?
Return a list of nodes in the graph\&. Restrictions can limit the list
of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node\&. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself\&.
.sp
The possible restrictions are the same as for method
\fBarcs\fR\&. The exact meanings change slightly, as they operate on




nodes instead of arcs\&. The command recognizes:
.RS
.TP
\fB-in\fR
Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes\&. Alternatively specified as
the set of source nodes for the \fB-in\fR arcs of the node set\&. The
\fIincoming neighbours\fR\&.








|
|
>
>
>
>
|








903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923

\fIgraphName\fR \fBnodes\fR ?-key \fIkey\fR? ?-value \fIvalue\fR? ?-filter \fIcmdprefix\fR? ?-in|-out|-adj|-inner|-embedding \fInode\fR \fInode\fR\&.\&.\&.?
Return a list of nodes in the graph\&. Restrictions can limit the list
of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node\&. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself\&.
.sp
The possible restrictions are the same as for method \fBarcs\fR\&.
Note that while the exact meanings change slightly, as they operate on
nodes instead of arcs, the general behaviour is the same, especially
when it comes to the handling of words with a leading dash in node
lists\&.
.sp
The command recognizes:
.RS
.TP
\fB-in\fR
Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes\&. Alternatively specified as
the set of source nodes for the \fB-in\fR arcs of the node set\&. The
\fIincoming neighbours\fR\&.
︙︙
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169

left-most button in the secondary navigation bar\&.
.SH KEYWORDS
adjacent, arc, cgraph, degree, edge, graph, loop, neighbour, node, serialization, subgraph, vertex
.SH CATEGORY
Data structures
.SH COPYRIGHT
.nf
Copyright (c) 2002-2009 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>

.fi








|



1175
1176
1177
1178
1179
1180
1181
1182
1183
1184

left-most button in the secondary navigation bar\&.
.SH KEYWORDS
adjacent, arc, cgraph, degree, edge, graph, loop, neighbour, node, serialization, subgraph, vertex
.SH CATEGORY
Data structures
.SH COPYRIGHT
.nf
Copyright (c) 2002-2009,2019 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>

.fi
Changes to idoc/www/tcllib/files/modules/struct/graph.html.
︙︙
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'graph.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2002-2009 Andreas Kupries &amp;lt;[email protected]&amp;gt;
   -->
<!-- struct::graph.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">struct::graph(n) 2.4.1 tcllib &quot;Tcl Data Structures&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>struct::graph - Create and manipulate directed graph objects</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">Changes for 2.0</a></li>
<li class="doctools_section"><a href="#section3">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="doctools_synopsis">
<ul class="doctools_requirements">
<li>package require <b class="pkgname">Tcl 8.4</b></li>
<li>package require <b class="pkgname">struct::graph <span class="opt">?2.4.1?</span></b></li>
<li>package require <b class="pkgname">struct::list <span class="opt">?1.5?</span></b></li>
<li>package require <b class="pkgname">struct::set <span class="opt">?2.2.3?</span></b></li>
</ul>
<ul class="doctools_syntax">
<li><a href="#1"><b class="cmd">::struct::graph</b> <span class="opt">?<i class="arg">graphName</i>?</span> <span class="opt">?<b class="const">=</b>|<b class="const">:=</b>|<b class="const">as</b>|<b class="const">deserialize</b> <i class="arg">source</i>?</span></a></li>
<li><a href="#2"><b class="cmd">graphName</b> <i class="arg">option</i> <span class="opt">?<i class="arg">arg arg ...</i>?</span></a></li>
<li><a href="#3"><i class="arg">graphName</i> <b class="method">=</b> <i class="arg">sourcegraph</i></a></li>








|













|



















|








89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'graph.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2002-2009,2019 Andreas Kupries &amp;lt;[email protected]&amp;gt;
   -->
<!-- struct::graph.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">struct::graph(n) 2.4.2 tcllib &quot;Tcl Data Structures&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>struct::graph - Create and manipulate directed graph objects</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">Changes for 2.0</a></li>
<li class="doctools_section"><a href="#section3">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="doctools_synopsis">
<ul class="doctools_requirements">
<li>package require <b class="pkgname">Tcl 8.4</b></li>
<li>package require <b class="pkgname">struct::graph <span class="opt">?2.4.2?</span></b></li>
<li>package require <b class="pkgname">struct::list <span class="opt">?1.5?</span></b></li>
<li>package require <b class="pkgname">struct::set <span class="opt">?2.2.3?</span></b></li>
</ul>
<ul class="doctools_syntax">
<li><a href="#1"><b class="cmd">::struct::graph</b> <span class="opt">?<i class="arg">graphName</i>?</span> <span class="opt">?<b class="const">=</b>|<b class="const">:=</b>|<b class="const">as</b>|<b class="const">deserialize</b> <i class="arg">source</i>?</span></a></li>
<li><a href="#2"><b class="cmd">graphName</b> <i class="arg">option</i> <span class="opt">?<i class="arg">arg arg ...</i>?</span></a></li>
<li><a href="#3"><i class="arg">graphName</i> <b class="method">=</b> <i class="arg">sourcegraph</i></a></li>
︙︙
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441

list containing all arcs is returned. Restrictions can limit the list
of returned arcs based on the nodes that are connected by the arc, on
the keyed values associated with the arc, or both. A general filter
command can be used as well. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself.</p>
<p>The restrictions imposed by either <b class="option">-in</b>, <b class="option">-out</b>,
<b class="option">-adj</b>, <b class="option">-inner</b>, or <b class="option">-embedded</b> are applied
first. Specifying more than one of them is illegal.</p>
<p>After that the restrictions set via <b class="option">-key</b> (and
<b class="option">-value</b>) are applied. Specifying more than one <b class="option">-key</b>
(and <b class="option">-value</b>) is illegal. Specifying <b class="option">-value</b> alone,
without <b class="option">-key</b> is illegal as well.</p>
<p>Any restriction set through <b class="option">-filter</b> is applied
last. Specifying more than one <b class="option">-filter</b> is illegal.</p>








|








427
428
429
430
431
432
433
434
435
436
437
438
439
440
441

list containing all arcs is returned. Restrictions can limit the list
of returned arcs based on the nodes that are connected by the arc, on
the keyed values associated with the arc, or both. A general filter
command can be used as well. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself.</p>
<p>The restrictions imposed by either <b class="option">-in</b>, <b class="option">-out</b>,
<b class="option">-adj</b>, <b class="option">-inner</b>, or <b class="option">-embedding</b> are applied
first. Specifying more than one of them is illegal.</p>
<p>After that the restrictions set via <b class="option">-key</b> (and
<b class="option">-value</b>) are applied. Specifying more than one <b class="option">-key</b>
(and <b class="option">-value</b>) is illegal. Specifying <b class="option">-value</b> alone,
without <b class="option">-key</b> is illegal as well.</p>
<p>Any restriction set through <b class="option">-filter</b> is applied
last. Specifying more than one <b class="option">-filter</b> is illegal.</p>
︙︙
458
459
460
461
462
463
464








465
466
467
468
469
470
471

<dd><p>Return a list of all arcs which are adjacent to two of the nodes in
the set. This is the set of arcs in the subgraph spawned by the
specified nodes.</p></dd>
<dt><b class="option">-embedding</b></dt>
<dd><p>Return a list of all arcs adjacent to exactly one of the nodes in the
set. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph.</p></dd>








<dt><b class="option">-key</b> <i class="arg">key</i></dt>
<dd><p>Limit the list of arcs that are returned to those arcs that have an
associated key <i class="arg">key</i>.</p></dd>
<dt><b class="option">-value</b> <i class="arg">value</i></dt>
<dd><p>This restriction can only be used in combination with
<b class="option">-key</b>. It limits the list of arcs that are returned to those
arcs whose associated key <i class="arg">key</i> has the value <i class="arg">value</i>.</p></dd>








>
>
>
>
>
>
>
>








458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479

<dd><p>Return a list of all arcs which are adjacent to two of the nodes in
the set. This is the set of arcs in the subgraph spawned by the
specified nodes.</p></dd>
<dt><b class="option">-embedding</b></dt>
<dd><p>Return a list of all arcs adjacent to exactly one of the nodes in the
set. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph.</p></dd>
</dl>
<p><em>Attention</em>: After the above options any word with a leading dash
which is not a valid option is treated as a node name instead of an
invalid option to error out on. This condition holds until either a
valid option terminates the list of nodes, or the end of the command
is reached, whichever comes first.</p>
<p>The remaining filter options are:</p>
<dl class="doctools_definitions">
<dt><b class="option">-key</b> <i class="arg">key</i></dt>
<dd><p>Limit the list of arcs that are returned to those arcs that have an
associated key <i class="arg">key</i>.</p></dd>
<dt><b class="option">-value</b> <i class="arg">value</i></dt>
<dd><p>This restriction can only be used in combination with
<b class="option">-key</b>. It limits the list of arcs that are returned to those
arcs whose associated key <i class="arg">key</i> has the value <i class="arg">value</i>.</p></dd>
︙︙
561
562
563
564
565
566
567
568
569



570
571
572
573
574
575
576
577

nothing if the <i class="arg">key</i> does not exist.</p></dd>
<dt><a name="58"><i class="arg">graphName</i> <b class="method">nodes</b> <span class="opt">?-key <i class="arg">key</i>?</span> <span class="opt">?-value <i class="arg">value</i>?</span> <span class="opt">?-filter <i class="arg">cmdprefix</i>?</span> <span class="opt">?-in|-out|-adj|-inner|-embedding <i class="arg">node</i> <i class="arg">node</i>...?</span></a></dt>
<dd><p>Return a list of nodes in the graph. Restrictions can limit the list
of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself.</p>
<p>The possible restrictions are the same as for method
<b class="method">arcs</b>. The exact meanings change slightly, as they operate on



nodes instead of arcs. The command recognizes:</p>
<dl class="doctools_definitions">
<dt><b class="option">-in</b></dt>
<dd><p>Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes. Alternatively specified as
the set of source nodes for the <b class="option">-in</b> arcs of the node set. The
<i class="term">incoming neighbours</i>.</p></dd>
<dt><b class="option">-out</b></dt>








|
|
>
>
>
|








569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588

nothing if the <i class="arg">key</i> does not exist.</p></dd>
<dt><a name="58"><i class="arg">graphName</i> <b class="method">nodes</b> <span class="opt">?-key <i class="arg">key</i>?</span> <span class="opt">?-value <i class="arg">value</i>?</span> <span class="opt">?-filter <i class="arg">cmdprefix</i>?</span> <span class="opt">?-in|-out|-adj|-inner|-embedding <i class="arg">node</i> <i class="arg">node</i>...?</span></a></dt>
<dd><p>Return a list of nodes in the graph. Restrictions can limit the list
of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself.</p>
<p>The possible restrictions are the same as for method <b class="method">arcs</b>.
Note that while the exact meanings change slightly, as they operate on
nodes instead of arcs, the general behaviour is the same, especially
when it comes to the handling of words with a leading dash in node
lists.</p>
<p>The command recognizes:</p>
<dl class="doctools_definitions">
<dt><b class="option">-in</b></dt>
<dd><p>Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes. Alternatively specified as
the set of source nodes for the <b class="option">-in</b> arcs of the node set. The
<i class="term">incoming neighbours</i>.</p></dd>
<dt><b class="option">-out</b></dt>
︙︙
784
785
786
787
788
789
790
791
792
793

<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#adjacent">adjacent</a>, <a href="../../../../index.html#arc">arc</a>, <a href="../../../../index.html#cgraph">cgraph</a>, <a href="../../../../index.html#degree">degree</a>, <a href="../../../../index.html#edge">edge</a>, <a href="../../../../index.html#graph">graph</a>, <a href="../../../../index.html#loop">loop</a>, <a href="../../../../index.html#neighbour">neighbour</a>, <a href="../../../../index.html#node">node</a>, <a href="../../../../index.html#serialization">serialization</a>, <a href="../../../../index.html#subgraph">subgraph</a>, <a href="../../../../index.html#vertex">vertex</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Data structures</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2002-2009 Andreas Kupries &lt;[email protected]&gt;</p>
</div>
</div></body></html>








|



795
796
797
798
799
800
801
802
803
804

<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#adjacent">adjacent</a>, <a href="../../../../index.html#arc">arc</a>, <a href="../../../../index.html#cgraph">cgraph</a>, <a href="../../../../index.html#degree">degree</a>, <a href="../../../../index.html#edge">edge</a>, <a href="../../../../index.html#graph">graph</a>, <a href="../../../../index.html#loop">loop</a>, <a href="../../../../index.html#neighbour">neighbour</a>, <a href="../../../../index.html#node">node</a>, <a href="../../../../index.html#serialization">serialization</a>, <a href="../../../../index.html#subgraph">subgraph</a>, <a href="../../../../index.html#vertex">vertex</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Data structures</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2002-2009,2019 Andreas Kupries &lt;[email protected]&gt;</p>
</div>
</div></body></html>
Changes to modules/struct/graph.man. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

[comment {-*- tcl -*-}][vset VERSION 2.4.1]
[manpage_begin struct::graph n [vset VERSION]]
[keywords adjacent]
[keywords arc]
[keywords cgraph]
[keywords degree]
[keywords edge]
[keywords graph]
[keywords loop]
[keywords neighbour]
[keywords node]
[keywords serialization]
[keywords subgraph]
[keywords vertex]
[copyright {2002-2009 Andreas Kupries <[email protected]>}]
[moddesc   {Tcl Data Structures}]
[titledesc {Create and manipulate directed graph objects}]
[category  {Data structures}]
[require Tcl 8.4]
[require struct::graph [opt  [vset VERSION]]]
[require struct::list  [opt 1.5]]
[require struct::set   [opt 2.2.3]]

|













|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

[comment {-*- tcl -*-}][vset VERSION 2.4.2]
[manpage_begin struct::graph n [vset VERSION]]
[keywords adjacent]
[keywords arc]
[keywords cgraph]
[keywords degree]
[keywords edge]
[keywords graph]
[keywords loop]
[keywords neighbour]
[keywords node]
[keywords serialization]
[keywords subgraph]
[keywords vertex]
[copyright {2002-2009,2019 Andreas Kupries <[email protected]>}]
[moddesc   {Tcl Data Structures}]
[titledesc {Create and manipulate directed graph objects}]
[category  {Data structures}]
[require Tcl 8.4]
[require struct::graph [opt  [vset VERSION]]]
[require struct::list  [opt 1.5]]
[require struct::set   [opt 2.2.3]]
︙︙
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407

command can be used as well. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself.

[para]

The restrictions imposed by either [option -in], [option -out],
[option -adj], [option -inner], or [option -embedded] are applied
first. Specifying more than one of them is illegal.

[para]

After that the restrictions set via [option -key] (and
[option -value]) are applied. Specifying more than one [option -key]
(and [option -value]) is illegal. Specifying [option -value] alone,








|








393
394
395
396
397
398
399
400
401
402
403
404
405
406
407

command can be used as well. The restrictions that involve connected
nodes take a variable number of nodes as argument, specified after the
name of the restriction itself.

[para]

The restrictions imposed by either [option -in], [option -out],
[option -adj], [option -inner], or [option -embedding] are applied
first. Specifying more than one of them is illegal.

[para]

After that the restrictions set via [option -key] (and
[option -value]) are applied. Specifying more than one [option -key]
(and [option -value]) is illegal. Specifying [option -value] alone,
︙︙
444
445
446
447
448
449
450
















451
452
453
454
455
456
457


[def [option -embedding]]

Return a list of all arcs adjacent to exactly one of the nodes in the
set. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph.

















[def "[option -key] [arg key]"]

Limit the list of arcs that are returned to those arcs that have an
associated key [arg key].

[def "[option -value] [arg value]"]









>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>








444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473


[def [option -embedding]]

Return a list of all arcs adjacent to exactly one of the nodes in the
set. This is the set of arcs connecting the subgraph spawned by the
specified nodes to the rest of the graph.

[list_end]

[emph Attention]: After the above options any word with a leading dash
which is not a valid option is treated as a node name instead of an
invalid option to error out on. This condition holds until either a
valid option terminates the list of nodes, or the end of the command
is reached, whichever comes first.

[para]

The remaining filter options are:

[para]

[list_begin definitions]

[def "[option -key] [arg key]"]

Limit the list of arcs that are returned to those arcs that have an
associated key [arg key].

[def "[option -value] [arg value]"]
︙︙
605
606
607
608
609
610
611
612

613





614
615
616
617
618
619
620
621

of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself.

[para]

The possible restrictions are the same as for method

[method arcs]. The exact meanings change slightly, as they operate on





nodes instead of arcs. The command recognizes:

[list_begin definitions]
[def [option -in]]

Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes. Alternatively specified as
the set of source nodes for the [option -in] arcs of the node set. The








|
>
|
>
>
>
>
>
|








621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643

of returned nodes based on neighboring nodes, or based on the keyed
values associated with the node. The restrictions that involve
neighboring nodes have a list of nodes as argument, specified after
the name of the restriction itself.

[para]

The possible restrictions are the same as for method [method arcs].

Note that while the exact meanings change slightly, as they operate on
nodes instead of arcs, the general behaviour is the same, especially
when it comes to the handling of words with a leading dash in node
lists.

[para]
The command recognizes:

[list_begin definitions]
[def [option -in]]

Return a list of all nodes with at least one outgoing arc ending in a
node found in the specified set of nodes. Alternatively specified as
the set of source nodes for the [option -in] arcs of the node set. The
︙︙
Changes to modules/struct/graph.tcl.
︙︙
173
174
175
176
177
178
179
180

## Ready

namespace eval ::struct {
    # Export the constructor command.
    namespace export graph
}

package provide struct::graph 2.4.1








|

173
174
175
176
177
178
179
180

## Ready

namespace eval ::struct {
    # Export the constructor command.
    namespace export graph
}

package provide struct::graph 2.4.2
Changes to modules/struct/graph.test. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# -*- tcl -*-
# graph.test:  tests for the graph structure.
#
# This file contains a collection of tests for one or more of the Tcl
# built-in commands.  Sourcing this file into Tcl runs the tests and
# generates output for errors.  No output means no errors were found.
#
# Copyright (c) 1998-2000 by Ajuba Solutions.
# Copyright (c) 2017-2017 Andreas Kupries
# All rights reserved.
#
# RCS: @(#) $Id: graph.test,v 1.27 2007/04/12 03:01:54 andreas_kupries Exp $

# -------------------------------------------------------------------------

source [file join \
	[file dirname [file dirname [file join [pwd] [info script]]]] \
	devtools testutilities.tcl]










|

<
<








1
2
3
4
5
6
7
8
9
10


11
12
13
14
15
16
17

# -*- tcl -*-
# graph.test:  tests for the graph structure.
#
# This file contains a collection of tests for one or more of the Tcl
# built-in commands.  Sourcing this file into Tcl runs the tests and
# generates output for errors.  No output means no errors were found.
#
# Copyright (c) 1998-2000 by Ajuba Solutions.
# Copyright (c) 2017,2019 Andreas Kupries
# All rights reserved.



# -------------------------------------------------------------------------

source [file join \
	[file dirname [file dirname [file join [pwd] [info script]]]] \
	devtools testutilities.tcl]
︙︙
Changes to modules/struct/graph/tests/nodes.test.
︙︙
11
12
13
14
15
16
17





18
19
20
21
22
23
24

# (3)     graph nodes -in       NODE...
#         graph nodes -out      NODE...
#         graph nodes -adj      NODE...
#         graph nodes -inner    NODE...
#         graph nodes -embedded NODE...

# We can use one in each group (1,2,3)






# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

# Cannot have missing arguments (zero is fine),
# except when switches are in use. That however
# is tested with the switches. Ditto for too many








>
>
>
>
>








11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# (3)     graph nodes -in       NODE...
#         graph nodes -out      NODE...
#         graph nodes -adj      NODE...
#         graph nodes -inner    NODE...
#         graph nodes -embedded NODE...

# We can use one in each group (1,2,3)

# Note: node names may have a leading dash ('-').

# Heuristics: Unknown options after (3) are considered node names
# until we reach a valid option.

# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

# Cannot have missing arguments (zero is fine),
# except when switches are in use. That however
# is tested with the switches. Ditto for too many
︙︙
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258





259


260
261









262
263
264
265
266
267
268
269

270
271
272

273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291


292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

307
308
309
310
311
312
313

}

# -------------------------------------------------------------------------
# Ok arguments.

set n 0
foreach {switch nodes expected} {
    -in        {1 2 3} {1 2 3 4 5 6}    -in        {4 5 6} {}
    -out       {1 2 3} {1 2 3}          -out       {4 5 6} {1 2 3}
    -adj       {1 2 3} {1 2 3 4 5 6}    -adj       {4 5 6} {1 2 3}
    -inner     {1 2 3} {1 2 3}          -inner     {4 5 6} {}
    -embedding {1 2 3} {4 5 6}          -embedding {4 5 6} {1 2 3}
    -in        {1 2}   {1 3 4 5}        -in        {4 5}   {}
    -out       {1 2}   {2 3}            -out       {4 5}   {1 2}
    -adj       {1 2}   {1 2 3 4 5}      -adj       {4 5}   {1 2}
    -inner     {1 2}   {1 2}            -inner     {4 5}   {}
    -embedding {1 2}   {3 4 5}          -embedding {4 5}   {1 2}
    -in        {1}     {3 4}            -in        {4}     {}
    -out       {1}     {2}              -out       {4}     {1}
    -adj       {1}     {2 3 4}          -adj       {4}     {1}
    -inner     {1}     {}               -inner     {4}     {}
    -embedding {1}     {2 3 4}          -embedding {4}     {1}
    -in        {1 4}   {3 4}            -in        {4 2}   {1 5}
    -out       {1 4}   {1 2}            -out       {4 2}   {1 3}
    -adj       {1 4}   {1 2 3 4}        -adj       {4 2}   {1 3 5}
    -inner     {1 4}   {1 4}            -inner     {4 2}   {}
    -embedding {1 4}   {2 3}            -embedding {4 2}   {1 3 5}





} {


    test graph-${impl}-${setimpl}-nodes-ioaie-3.$n "nodes, $switch" {
	SETUP










	mygraph node insert 1 2 3 4 5 6
	mygraph arc  insert 4 1 A
	mygraph arc  insert 5 2 B
	mygraph arc  insert 6 3 C
	mygraph arc  insert 3 1 D
	mygraph arc  insert 1 2 E
	mygraph arc  insert 2 3 F


	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy

	set result
    } $expected ; # {}

    incr n
}

# ---------------------------------------------------
# Test with many parallel arcs, beyond the number of nodes, i.e. lots
# of duplicates sources and destinations, to check that the dup
# removal works correctly. See bug [SF 1923685].

set n 0
foreach {switch nodes expected} {
    -in        2       1
    -out       2       3
    -adj       2       {1 3}
    -inner     {1 2 3} {1 2 3}
    -embedding 2       {1 3}
} {


    test graph-${impl}-${setimpl}-nodes-parallel-ioaie-bug1923685-4.$n "nodes, $switch, parallel arcs, bug 1923685" {
	SETUP

	mygraph node insert 1 2 3 4
	mygraph arc  insert 1 2 A ; mygraph arc  insert 2 3 A.
	mygraph arc  insert 1 2 B ; mygraph arc  insert 2 3 B.
	mygraph arc  insert 1 2 C ; mygraph arc  insert 2 3 C.
	mygraph arc  insert 1 2 D ; mygraph arc  insert 2 3 D.
	mygraph arc  insert 1 2 E ; mygraph arc  insert 2 3 E.
	mygraph arc  insert 1 2 F ; mygraph arc  insert 2 3 F.
	mygraph arc  insert 1 2 G ; mygraph arc  insert 2 3 G.
	mygraph arc  insert 1 2 H ; mygraph arc  insert 2 3 H.

	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy

	set result
    } $expected ; # {}

    incr n
}

# ---------------------------------------------------








|

|

|
|

|

|





|

|

|
>
>
>
>
>

>
>


>
>
>
>
>
>
>
>
>
|
|






>



>








|










>
>















>








237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339

}

# -------------------------------------------------------------------------
# Ok arguments.

set n 0
foreach {switch nodes expected} {
    -in        {1 2 3} {-1 1 2 3 4 5 6} -in        {4 5 6} {}
    -out       {1 2 3} {1 2 3}          -out       {4 5 6} {1 2 3}
    -adj       {1 2 3} {-1 1 2 3 4 5 6} -adj       {4 5 6} {1 2 3}
    -inner     {1 2 3} {1 2 3}          -inner     {4 5 6} {}
    -embedding {1 2 3} {-1 4 5 6}       -embedding {4 5 6} {1 2 3}
    -in        {1 2}   {-1 1 3 4 5}     -in        {4 5}   {}
    -out       {1 2}   {2 3}            -out       {4 5}   {1 2}
    -adj       {1 2}   {-1 1 2 3 4 5}   -adj       {4 5}   {1 2}
    -inner     {1 2}   {1 2}            -inner     {4 5}   {}
    -embedding {1 2}   {-1 3 4 5}       -embedding {4 5}   {1 2}
    -in        {1}     {3 4}            -in        {4}     {}
    -out       {1}     {2}              -out       {4}     {1}
    -adj       {1}     {2 3 4}          -adj       {4}     {1}
    -inner     {1}     {}               -inner     {4}     {}
    -embedding {1}     {2 3 4}          -embedding {4}     {1}
    -in        {1 4}   {3 4}            -in        {4 2}   {-1 1 5}
    -out       {1 4}   {1 2}            -out       {4 2}   {1 3}
    -adj       {1 4}   {1 2 3 4}        -adj       {4 2}   {-1 1 3 5}
    -inner     {1 4}   {1 4}            -inner     {4 2}   {}
    -embedding {1 4}   {2 3}            -embedding {4 2}   {-1 1 3 5}
    -in        {1 -1}  {3 4}
    -out       {1 -1}  2
    -adj       {1 -1}  {2 3 4}
    -inner     {1 -1}  {}
    -embedding {1 -1}  {2 3 4}
} {
    lappend expected $switch $nodes

    test graph-${impl}-${setimpl}-nodes-ioaie-3.$n "nodes, $switch" {
	SETUP
	# Nodes (digits -1,1-6) and arcs (letters A-G), no direction
	#        4
	#        |A
	#        1     -1
	#      D/ \   /G
	#      /   \E/
	#     3 --- 2
	#   C/  F    \B
	#   6         5
	
	mygraph node insert 1 2 3 4 5 6 -1
	mygraph arc  insert 4 1 A
	mygraph arc  insert 5 2 B
	mygraph arc  insert 6 3 C
	mygraph arc  insert 3 1 D
	mygraph arc  insert 1 2 E
	mygraph arc  insert 2 3 F
	mygraph arc  insert -1 2 G

	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy
	lappend result $switch $nodes
	set result
    } $expected ; # {}

    incr n
}

# ---------------------------------------------------
# Test with many parallel arcs, beyond the number of nodes, i.e. lots
# of duplicated sources and destinations, to check that the dup
# removal works correctly. See bug [SF 1923685].

set n 0
foreach {switch nodes expected} {
    -in        2       1
    -out       2       3
    -adj       2       {1 3}
    -inner     {1 2 3} {1 2 3}
    -embedding 2       {1 3}
} {
    lappend expected $switch $nodes

    test graph-${impl}-${setimpl}-nodes-parallel-ioaie-bug1923685-4.$n "nodes, $switch, parallel arcs, bug 1923685" {
	SETUP

	mygraph node insert 1 2 3 4
	mygraph arc  insert 1 2 A ; mygraph arc  insert 2 3 A.
	mygraph arc  insert 1 2 B ; mygraph arc  insert 2 3 B.
	mygraph arc  insert 1 2 C ; mygraph arc  insert 2 3 C.
	mygraph arc  insert 1 2 D ; mygraph arc  insert 2 3 D.
	mygraph arc  insert 1 2 E ; mygraph arc  insert 2 3 E.
	mygraph arc  insert 1 2 F ; mygraph arc  insert 2 3 F.
	mygraph arc  insert 1 2 G ; mygraph arc  insert 2 3 G.
	mygraph arc  insert 1 2 H ; mygraph arc  insert 2 3 H.

	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy
	lappend result $switch $nodes
	set result
    } $expected ; # {}

    incr n
}

# ---------------------------------------------------
Changes to modules/struct/graph_tcl.tcl. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# graph_tcl.tcl --
#
#	Implementation of a graph data structure for Tcl.
#
# Copyright (c) 2000-2009 by Andreas Kupries <[email protected]>
# Copyright (c) 2008      by Alejandro Paz <[email protected]>
#
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
# 
# RCS: @(#) $Id: graph_tcl.tcl,v 1.5 2009/11/26 04:42:16 andreas_kupries Exp $

package require Tcl 8.4
package require struct::list
package require struct::set

namespace eval ::struct::graph {
    # Data storage in the graph module





|
|



<
<








1
2
3
4
5
6
7
8
9


10
11
12
13
14
15
16

# graph_tcl.tcl --
#
#	Implementation of a graph data structure for Tcl.
#
# Copyright (c) 2000-2009,2019 by Andreas Kupries <[email protected]>
# Copyright (c) 2008           by Alejandro Paz <[email protected]>
#
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.



package require Tcl 8.4
package require struct::list
package require struct::set

namespace eval ::struct::graph {
    # Data storage in the graph module
︙︙
2997
2998
2999
3000
3001
3002
3003

3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020

3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032

3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044

3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056

3057
3058



3059
3060

3061
3062
3063
3064
3065
3066
3067

    upvar 1 value      value      ; set value      {}
    upvar 1 haveFilter haveFilter ; set haveFilter 0
    upvar 1 fcmd       fcmd       ; set fcmd       {}
    upvar 1 cond       cond       ; set cond       "none"
    upvar 1 condNodes  condNodes  ; set condNodes  {}

    set wa_usage "wrong # args: should be \"$name $what ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\""


    for {set i 0} {$i < [llength $arguments]} {incr i} {
	set arg [lindex $arguments $i]
	switch -glob -- $arg {
	    -in -
	    -out -
	    -adj -
	    -inner -
	    -embedding {
		if {$haveCond} {
		    return -code error "invalid restriction:\
			    illegal multiple use of\
			    \"-in\"|\"-out\"|\"-adj\"|\"-inner\"|\"-embedding\""
		}

		set haveCond 1
		set cond [string range $arg 1 end]

	    }
	    -key {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveKey} {
		    return -code error {invalid restriction: illegal multiple use of "-key"}
		}

		incr i
		set key [lindex $arguments $i]
		set haveKey 1

	    }
	    -value {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveValue} {
		    return -code error {invalid restriction: illegal multiple use of "-value"}
		}

		incr i
		set value [lindex $arguments $i]
		set haveValue 1

	    }
	    -filter {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveFilter} {
		    return -code error {invalid restriction: illegal multiple use of "-filter"}
		}

		incr i
		set fcmd [lindex $arguments $i]
		set haveFilter 1

	    }
	    -* {



		return -code error "bad restriction \"$arg\": must be -adj, -embedding,\
			-filter, -in, -inner, -key, -out, or -value"

	    }
	    default {
		lappend condNodes $arg
	    }
	}
    }









>
|
















>












>












>












>


>
>
>
|

>








2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074

    upvar 1 value      value      ; set value      {}
    upvar 1 haveFilter haveFilter ; set haveFilter 0
    upvar 1 fcmd       fcmd       ; set fcmd       {}
    upvar 1 cond       cond       ; set cond       "none"
    upvar 1 condNodes  condNodes  ; set condNodes  {}

    set wa_usage "wrong # args: should be \"$name $what ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\""
    set seenodes 0
    
    for {set i 0} {$i < [llength $arguments]} {incr i} {
	set arg [lindex $arguments $i]
	switch -glob -- $arg {
	    -in -
	    -out -
	    -adj -
	    -inner -
	    -embedding {
		if {$haveCond} {
		    return -code error "invalid restriction:\
			    illegal multiple use of\
			    \"-in\"|\"-out\"|\"-adj\"|\"-inner\"|\"-embedding\""
		}

		set haveCond 1
		set cond [string range $arg 1 end]
		set seenodes 1
	    }
	    -key {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveKey} {
		    return -code error {invalid restriction: illegal multiple use of "-key"}
		}

		incr i
		set key [lindex $arguments $i]
		set haveKey 1
		set seenodes 0
	    }
	    -value {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveValue} {
		    return -code error {invalid restriction: illegal multiple use of "-value"}
		}

		incr i
		set value [lindex $arguments $i]
		set haveValue 1
		set seenodes 0
	    }
	    -filter {
		if {($i + 1) == [llength $arguments]} {
		    return -code error $wa_usage
		}
		if {$haveFilter} {
		    return -code error {invalid restriction: illegal multiple use of "-filter"}
		}

		incr i
		set fcmd [lindex $arguments $i]
		set haveFilter 1
		set seenodes 0
	    }
	    -* {
		if {$seenodes} {
		    lappend condNodes $arg
		} else {
		    return -code error "bad restriction \"$arg\": must be -adj, -embedding,\
			-filter, -in, -inner, -key, -out, or -value"
		}
	    }
	    default {
		lappend condNodes $arg
	    }
	}
    }
︙︙
Changes to modules/struct/pkgIndex.tcl.
︙︙
14
15
16
17
18
19
20
21
22
23
24
25
26
27


package ifneeded struct::graph     1.2.1 [list source [file join $dir graph1.tcl]]
package ifneeded struct::tree      1.2.2 [list source [file join $dir tree1.tcl]]
package ifneeded struct::matrix    1.2.1 [list source [file join $dir matrix1.tcl]]

if {![package vsatisfies [package provide Tcl] 8.4]} {return}
package ifneeded struct::list      1.8.4  [list source [file join $dir list.tcl]]
package ifneeded struct::graph     2.4.1  [list source [file join $dir graph.tcl]]

if {![package vsatisfies [package provide Tcl] 8.5]} {return}

if {![package vsatisfies [package provide Tcl] 8.6]} {return}
package ifneeded struct::disjointset 1.1 [list source [file join $dir disjointset.tcl]]
package ifneeded struct::graph::op 0.11.3 [list source [file join $dir graphops.tcl]]








|







14
15
16
17
18
19
20
21
22
23
24
25
26
27


package ifneeded struct::graph     1.2.1 [list source [file join $dir graph1.tcl]]
package ifneeded struct::tree      1.2.2 [list source [file join $dir tree1.tcl]]
package ifneeded struct::matrix    1.2.1 [list source [file join $dir matrix1.tcl]]

if {![package vsatisfies [package provide Tcl] 8.4]} {return}
package ifneeded struct::list      1.8.4  [list source [file join $dir list.tcl]]
package ifneeded struct::graph     2.4.2  [list source [file join $dir graph.tcl]]

if {![package vsatisfies [package provide Tcl] 8.5]} {return}

if {![package vsatisfies [package provide Tcl] 8.6]} {return}
package ifneeded struct::disjointset 1.1 [list source [file join $dir disjointset.tcl]]
package ifneeded struct::graph::op 0.11.3 [list source [file join $dir graphops.tcl]]
This page was generated in about 0.023s by Fossil 2.27 [a6d506ecc4] 2025-07-09 13:52:53