Arborescence

This web is a grab bag of code and commentary, centered around Arborescences (ie, tree-shaped data structures) and their use in software development. The approach is much more pragmatic than theoretical, though I do provide occasional text from and/or links to supporting Wikipedia pages, eg:

In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v.

Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

-- Arborescence (graph theory) (WP)

Most modern programming languages support arrays (ie, indexable lists) and hashes (ie, associative arrays, dictionaries, maps). Dynamic programming languages such as Perl and Ruby generally allow these collections to be heterogeneous.

Arborescences (ie, trees) of these collection types are commonly used for semi-structured data (eg, configuration settings, abstract syntax trees). The leaf nodes for these data structures may contain assorted scalars (eg, booleans, floats, integers, references, symbols). Using references as leaf nodes, these trees can represent arbitrary graphs.

Topics

  • Overview

    a bit more background information

  • Serialization

    encoding graphs (etc) as bit streams can be a challenge

  • Tree Globbing

    tidy traversal of arborescences (mostly YAML and Ruby)


This wiki page is maintained by Rich Morin, an independent consultant specializing in software design, development, and documentation. Please feel free to email comments, inquiries, suggestions, etc!

Topic revision: r52 - 18 Mar 2014, RichMorin
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding CFCL Wiki? Send feedback