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 trees%|%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.

   [Package ASDOT%|%ASDOT]:   converts [Tcllib graph%|%struct::graph] structures to graphviz `.dot` format.

   [Package DGA%|%DGA]:   Adds some algorithms to [Tcllib graph%|%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]:   


----