struct::graph_v1(n)

📦
version 2.0 · 2 versions
, in fedora 43, fedora 44, nixos 26.05, nixpkgs unstable

okay so this is struct::graph_v1, and it lives in the Tcl Data Structures part of the manual (section n, iykyk) 💅

🦋 NAME 🦋

  • struct::graph_v1 — create and manipulate directed graph objects ✨ periodt.

🎀 SYNOPSIS 🎀

package require Tcl 8.5 9

package require struct::graph ?1.2.2?

graphName option ?arg arg ...?

graphName destroy

graphName arc append arc ?-key key? value
graphName arc delete arc ?arc ...?
graphName arc exists arc
graphName arc get arc ?-key key?
graphName arc getall arc
graphName arc keys arc
graphName arc keyexists arc ?-key key?
graphName arc insert start end ?child?
graphName arc lappend arc ?-key key? value
graphName arc set arc ?-key key? ?value?
graphName arc source arc
graphName arc target arc
graphName arc unset arc ?-key key?
graphName arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embedding nodelist?

graphName node append node ?-key key? value
graphName node degree ?-in|-out? node
graphName node delete node ?node ...?
graphName node exists node
graphName node get node ?-key key?
graphName node getall node
graphName node keys node
graphName node keyexists node ?-key key?
graphName node insert ?child?
graphName node lappend node ?-key key? value
graphName node opposite node arc
graphName node set node ?-key key? ?value?
graphName node unset node ?-key key?
graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embedding nodelist?

graphName get ?-key key?
graphName getall
graphName keys
graphName keyexists ?-key key?
graphName set ?-key key? ?value?
graphName swap node1 node2
graphName unset ?-key key?

graphName walk node ?-order order? ?-type type? ?-dir direction? -command cmd

💖 DESCRIPTION 💖

So the ::struct::graph command creates a brand new graph object with an associated global Tcl command, and the name of that command is graphName. You use that command to do literally every operation on the graph. The general shape of it is:

graphName option ?arg arg ...?

Where option and the args decide exactly what the command does. 💫

A directed graph is a structure holding two collections of elements, called nodes and arcs, plus a relation ("connectivity") that lays a general structure over those nodes and arcs.

Every arc is connected to two nodes: one is the source, the other is the target. That's what gives the arc a direction, and we say the arc goes from the source to the target. It's totally allowed for the source and target of an arc to be the same node — that arc is called a loop 🌀. Whenever a node is the source or the target of an arc, the two are said to be adjacent. And that extends into a node-to-node relation: if two nodes are connected through at least one arc, they're adjacent too, no cap.

Each node can be the source and the target for any number of arcs. The ones where it's the source are its outgoing arcs, the ones where it's the target are its incoming arcs. The number of edges in each set is called the in-degree resp. the out-degree of the node. 📊

On top of all that node-and-arc relationship maintenance, this graph implementation lets you attach any number of keyed values to each node and each arc. Obsessed honestly.

The following commands are possible for graph objects:

  • graphName destroy — Destroy the graph, including its storage space and its associated command. Gone. Poof. 💀
  • graphName arc append arc ?-key key? value — Appends a value to one of the keyed values associated with an arc. If you don't specify a key, the key data is assumed.
  • graphName arc delete arc ?arc ...? — Remove the specified arcs from the graph. Bye bestie 🫶
  • graphName arc exists arc — Returns true if the specified arc exists in the graph.
  • graphName arc get arc ?-key key? — Returns the value associated with the key key for the arc. No key given? Then the key data is assumed.
  • graphName arc getall arc — Returns a serialized list of key/value pairs (suitable for use with [array set]) for the arc. Very handy, lowkey iconic.
  • graphName arc keys arc — Returns a list of keys for the arc.
  • graphName arc keyexists arc ?-key key? — Returns true if the specified key exists for the arc. If you skip the key, the key data is assumed.
  • graphName arc insert start end ?child? — Insert an arc named child into the graph, starting at the node start and ending at the node end. If you don't name the new arc, the system generates a unique name of the form arcx. ✨
  • graphName arc lappend arc ?-key key? value — Appends a value (as a list) to one of the keyed values associated with an arc. No key specified? The key data is assumed.
  • graphName arc set arc ?-key key? ?value? — Set or get one of the keyed values associated with an arc. If no key is specified, the key data is assumed. Every arc added to a graph gets the empty string assigned to the key data automatically. An arc can have any number of keyed values attached. If value isn't given, this command returns the current value assigned to the key; if value is given, this command assigns that value to the key.
  • graphName arc source arc — Return the node the given arc begins at.
  • graphName arc target arc — Return the node the given arc ends at.
  • graphName arc unset arc ?-key key? — Remove a keyed value from the arc arc. If no key is specified, the key data is assumed.
  • graphName arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embedding nodelist? — Return a list of arcs in the graph. No restriction? Then you get a list containing all the arcs. Restrictions can narrow down that list based on the nodes the arc connects, on the keyed values associated with the arc, or both. Restrictions that involve connected nodes take a list of nodes as their argument, written right after the name of the restriction itself.
    • -in — Return a list of all arcs whose target is one of the nodes in the nodelist.
    • -out — Return a list of all arcs whose source is one of the nodes in the nodelist.
    • -adj — Return a list of all arcs adjacent to at least one of the nodes in the nodelist. This is the union of the nodes returned by -in and -out.
    • -inner — Return a list of all arcs adjacent to two of the nodes in the nodelist. This is the set of arcs in the subgraph spawned by the specified nodes.
    • -embedding — Return a list of all arcs adjacent to exactly one of the nodes in the nodelist. 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 — This restriction can only be used in combination with -key. It limits the list of returned arcs to those arcs whose associated key key has the value value.

The restrictions imposed by either -in, -out, -adj, -inner, or -embedded are applied first.

🚨 Specifying more than one of them is illegal.

At last, the restrictions set via -key (and -value) are applied.

🚨 Specifying more than one -key (and -value) is illegal.
  • graphName node append node ?-key key? value — Appends a value to one of the keyed values associated with a node. If no key is specified, the key data is assumed.
  • graphName node degree ?-in|-out? node — Return the number of arcs adjacent to the specified node. If one of the restrictions -in or -out is given, only the incoming resp. outgoing arcs are counted. 🧮
  • graphName node delete node ?node ...? — Remove the specified nodes from the graph. All of the nodes' arcs will be removed as well, so you never end up with unconnected arcs. Important.
  • graphName node exists node — Return true if the specified node exists in the graph.
  • graphName node get node ?-key key? — Return the value associated with the key key for the node. If no key is specified, the key data is assumed.
  • graphName node getall node — Returns a serialized list of key/value pairs (suitable for use with [array set]) for the node.
  • graphName node keys node — Returns a list of keys for the node.
  • graphName node keyexists node ?-key key? — Return true if the specified key exists for the node. If no key is specified, the key data is assumed.
  • graphName node insert ?child? — Insert a node named child into the graph. The node has no arcs connected to it. If you don't name the new child, the system generates a unique name of the form nodex. 🌱
  • graphName node lappend node ?-key key? value — Appends a value (as a list) to one of the keyed values associated with a node. If no key is specified, the key data is assumed.
  • graphName node opposite node arc — Return the node at the other end of the specified arc, which has to be adjacent to the given node.
  • graphName node set node ?-key key? ?value? — Set or get one of the keyed values associated with a node. If no key is specified, the key data is assumed. Every node added to a graph gets the empty string assigned to the key data automatically. A node can have any number of keyed values attached. If value isn't specified, this command returns the current value assigned to the key; if value is specified, this command assigns that value to the key.
  • graphName node unset node ?-key key? — Remove a keyed value from the node node. If no key is specified, the key data is assumed.
  • graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embedding nodelist? — 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.

okay so continuing from where we left off — the possible restrictions are the same as for method arcs. the set of nodes to return is computed as the union of all source and target nodes for all the arcs satisfying the restriction as defined for arcs. no cap, that's just how it is 💅

so here are the rest of the methods, and they're literally so useful 💖

  • graphName get ?-key key? — returns the value associated with the key key for the graph. if no key is specified, the key data is assumed. 💅
  • graphName getall — returns a serialized list of key/value pairs (suitable for use with [array set]) for the whole graph. it's giving data dump energy ✨
  • graphName keys — returns a list of keys for the whole graph. all the keys, bestie 🔑
  • graphName keyexists ?-key key? — returns true if the specified key exists for the whole graph. if no key is specified, the key data is assumed. vibe check on your keys 👀
  • graphName set ?-key key? ?value? — set or get one of the keyed values associated with a graph. if no key is specified, the key data is assumed. each graph has the empty string assigned to the key data automatically. a graph may have any number of keyed values associated with it. if value is not specified, this command returns the current value assigned to the key; if value is specified, this command assigns that value to the key. slay 💅
  • graphName swap node1 node2 — swaps the position of node1 and node2 in the graph. trade offer accepted 🤝
  • graphName unset ?-key key? — removes a keyed value from the graph. if no key is specified, the key data is assumed. bye bye 👋
  • graphName walk node ?-order order? ?-type type? ?-dir direction? -command cmd — perform a breadth-first or depth-first walk of the graph starting at the node node going in either the direction of outgoing or opposite to the incoming arcs.

the type of walk, breadth-first or depth-first, is determined by the value of type; bfs indicates breadth-first, dfs indicates depth-first. depth-first is the default.

the order of the walk, pre-order, post-order or both-order is determined by the value of order; pre indicates pre-order, post indicates post-order, both indicates both-order. pre-order is the default. pre-order walking means that a node is visited before any of its neighbors (as defined by the direction, see below). post-order walking means that a parent is visited after any of its neighbors. both-order walking means that a node is visited before and after any of its neighbors. the combination of a bread-first walk with post- or both-order is illegal. 🚫

the direction of the walk is determined by the value of dir; backward indicates the direction opposite to the incoming arcs, forward indicates the direction of the outgoing arcs.

as the walk progresses, the command cmd will be evaluated at each node, with the mode of the call (enter or leave) and values graphName and the name of the current node appended. for a pre-order walk, all nodes are entered, for a post-order all nodes are left. in a both-order walk the first visit of a node enters it, the second visit leaves it.

🐛 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 http://core.tcl.tk/tcllib/reportlist. please also report any ideas for enhancements you may have for either package and/or documentation. we love feedback, bestie 🫶

when proposing code changes, please provide unified diffs, i.e the output of diff -u. no cap, that's the way.

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. okay? slay.

🔑 KEYWORDS

  • cgraph
  • graph

📂 CATEGORY

Data structures

Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>

and that's a wrap! this was struct::graph_v1(n) from tcllib version 1.2.2. mwah 💋

📦 where this page comes from