Tcl Library Source Code


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]


struct::graph - Create and manipulate directed graph objects

Table Of Contents


package require Tcl 8.5 9
package require struct::graph ?2.4.3?
package require struct::list ?1.5?
package require struct::set ?2.2.3?

::struct::graph ?graphName? ?=|:=|as|deserialize source?
graphName option ?arg arg ...?
graphName = sourcegraph
graphName --> destgraph
graphName append key value
graphName deserialize serialization
graphName destroy
graphName arc append arc key value
graphName arc attr key
graphName arc attr key -arcs list
graphName arc attr key -glob globpattern
graphName arc attr key -regexp repattern
graphName arc delete arc ?arc ...?
graphName arc exists arc
graphName arc flip arc
graphName arc get arc key
graphName arc getall arc ?pattern?
graphName arc getunweighted
graphName arc getweight arc
graphName arc keys arc ?pattern?
graphName arc keyexists arc key
graphName arc insert start end ?child?
graphName arc lappend arc key value
graphName arc rename arc newname
graphName arc set arc key ?value?
graphName arc setunweighted ?weight?
graphName arc setweight arc weight
graphName arc unsetweight arc
graphName arc hasweight arc
graphName arc source arc
graphName arc target arc
graphName arc nodes arc
graphName arc move-source arc newsource
graphName arc move-target arc newtarget
graphName arc move arc newsource newtarget
graphName arc unset arc key
graphName arc weights
graphName arcs ?-key key? ?-value value? ?-filter cmdprefix? ?-in|-out|-adj|-inner|-embedding node node...?
graphName lappend key value
graphName node append node key value
graphName node attr key
graphName node attr key -nodes list
graphName node attr key -glob globpattern
graphName node attr key -regexp repattern
graphName node degree ?-in|-out? node
graphName node delete node ?node...?
graphName node exists node
graphName node get node key
graphName node getall node ?pattern?
graphName node keys node ?pattern?
graphName node keyexists node key
graphName node insert ?node...?
graphName node lappend node key value
graphName node opposite node arc
graphName node rename node newname
graphName node set node key ?value?
graphName node unset node key
graphName nodes ?-key key? ?-value value? ?-filter cmdprefix? ?-in|-out|-adj|-inner|-embedding node node...?
graphName get key
graphName getall ?pattern?
graphName keys ?pattern?
graphName keyexists key
graphName serialize ?node...?
graphName set key ?value?
graphName swap node1 node2
graphName unset key
graphName walk node ?-order order? ?-type type? ?-dir direction? -command cmd


A directed graph is a structure containing two collections of elements, called nodes and arcs respectively, together with a relation ("connectivity") that places a general structure upon the nodes and arcs.

Each arc is connected to two nodes, one of which is called the source and the other the target. This imposes a direction upon the arc, which is said to go from the source to the target. It is allowed that source and target of an arc are the same node. Such an arc is called a loop. Whenever a node is either the source or target of an arc both are said to be adjacent. This extends into a relation between nodes, i.e. if two nodes are connected through at least one arc they are said to be adjacent too.

Each node can be the source and target for any number of arcs. The former are called the outgoing arcs of the node, the latter the incoming arcs of the node. The number of arcs in either set is called the in-degree resp. the out-degree of the node.

In addition to maintaining the node and arc relationships, this graph implementation allows any number of named attributes to be associated with the graph itself, and each node or arc.

Note: The major version of the package struct has been changed to version 2.0, due to backward incompatible changes in the API of this module. Please read the section Changes for 2.0 for a full list of all changes, incompatible and otherwise.

Note: A C-implementation of the command can be had from the location See also This implementation uses a bit less memory than the tcl version provided here directly, and is faster. Its support is limited to versions of the package before 2.0.

As of version 2.2 of this package a critcl based C implementation is available from here as well. This implementation however requires Tcl 8.4 to run.

The main command of the package is:

The following commands are possible for graph objects:

Changes for 2.0

The following noteworthy changes have occurred:

  1. The API for accessing attributes and their values has been simplified.

    All functionality regarding the default attribute "data" has been removed. This default attribute does not exist anymore. All accesses to attributes have to specify the name of the attribute in question. This backward incompatible change allowed us to simplify the signature of all methods handling attributes.

    Especially the flag -key is not required anymore, even more, its use is now forbidden. Please read the documentation for the arc and node methods set, get, getall, unset, append, lappend, keyexists and keys for a description of the new API's.

  2. The methods keys and getall now take an optional pattern argument and will return only attribute data for keys matching this pattern.

  3. Arcs and nodes can now be renamed. See the documentation for the methods arc rename and node rename.

  4. The structure has been extended with API's for the serialization and deserialization of graph objects, and a number of operations based on them (graph assignment, copy construction).

    Please read the documentation for the methods serialize, deserialize, =, and -->, and the documentation on the construction of graph objects.

    Beyond the copying of whole graph objects these new API's also enable the transfer of graph objects over arbitrary channels and for easy persistence.

  5. A new method, attr, was added to both arc and node allowing the query and retrieval of attribute data without regard to arc and node relationships.

  6. Both methods arcs and nodes have been extended with the ability to select arcs and nodes based on an arbitrary filtering criterium.

Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category struct :: graph of the Tcllib Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.


adjacent, arc, cgraph, degree, edge, graph, loop, neighbour, node, serialization, subgraph, vertex


Data structures


Copyright © 2002-2009,2019 Andreas Kupries