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