A graph is a data structure composed of nodes connected by edges.
Description
If one node in a pair of connected nodes in a graph is considered the origin, and the other the destination, the link is directed. In a directed graph, if there is no path leading from a node to any of its parent nodes, the node is acyclic. A graph for which these two properties is true of every node is called a directed acyclic graph, or DAG.
In visual representations of a graphs, nodes are usually rendered as circles, and edges are usually rendered as lines or arrows.
See Also
- cgraph
- Implements the Tcllib graph API, but with the expectation of improved performance.
- e4graph
- A C++ and Java library for persistent storage of graph-like data. Includes a Tcl binding and uses metakit for storage.
- Graph theory in Tcl, by RS
- Graph Manipulations
- A Gsoc project.
- More graph theory
- tDOM
- Not just for XML, tDOM is an efficient and performant general-purpose tool for building and manipulating graphs. Use dom setNameCheck to alow arbitrary node names, and use asList to create Tcl list representation of the graph. In the list output, a three-element list indicates a node, and a two-element list indicates a leaf.
- Tcllib graph
- A Tcllib module for building graph structures of nodes and edges.
- TkMaze, by bbh
- Based on ideas from Graph theory in Tcl.
Demos
- GOBLIN
- A full-featured tool chain for handling graphs. Nearly all algorithms described in textbooks on graph optimization are implemented. Implemented in C++, with I/O written in Tcl, and Tcl bindings for the library.
Types of Graphs
- binary tree
- A directed graph in which all nodes have zero, one, or two successors, one node, the root, has no predecessor, and all others have exactly one predecessor.
- Tree
- A directed graph in which one node, the root, has no predecessor, and all other nodes have exactly one predecessor.
Tools
- Graph editors
- GraphViz
- Set of graph drawing tools and libraries, supporting hierarchical and mass-spring drawings. Tools include dot, neato, twopi, lefty, dotty, lneato, tcldot, gpr, ccomps, colorize, gc, nop, prune, sccmap, tred, unflatten, grappa. Includes support for Tcl/Tk.
- ASDOT
- converts struct::graph structures to graphviz .dot format.
- DGA
- Adds some algorithms to struct::graph.
- tcldg
- The dynamic graph layout libraries from the graphviz package.
Toys
- A graph generator
- A procedure that produces a graph description.
- Simple tree layout by RS