can be maintained automatically, given the right software, and the right metadata. The problem is choosing the right trade-off between features and metadata maintenance efforts.
On the rest of this page, we're going to talk about a hierarchy of nodes. Every node except for the top node has exactly one parent, if this is a tree. If a node can have several parents, this is a semi-lattice, and cannot be trivially linearized. Orphans are nodes without a parent. A parent node has zero to n child nodes. These child nodes are siblings. If the child nodes are ordered, then every node has a next and a previous sibling.
Linearization is the process of arranging all the nodes in a linear fashion. The most obvious example would be printing a wiki as a book, or assembling all the wiki pages into one monolithic web page.
Child has a Pointer to the Parent
The simplest kind of metadata to maintain is to have each node point to its parent.
- Benefit: Users only have to edit one page to "move" it from one parent to another.
- Benefit: When creating the page, assigning a parent can happen at the same time.
- Benefit: Specifying a parent can be mandatory when saving the page.
- Benefit: Specifying not more than one parent can be enforced when saving the page.
- Feature: Using this information, you can show "where in the hierarchy" the current node is, by listing all the parent nodes up to the top node.
- Drawback: The child nodes are not ordered, or ordered arbitrarily, eg. alphabetically. Linearization will therefore be somewhat arbitrary.
- Drawback: The children cannot be grouped without more metadata.
Parent has Pointers to the Children
An alternative is the reverse situation: Every parent node has a "menu" -- an ordered list of child nodes.
- Drawback: Users has to edit two pages to "move" it from one parent to another.
- Maybe a drawback: When creating the page, assigning a parent is impossible. CommunityExpectation can require users to create a link to new pages on the parent node first, however, thus facilitating the process.
- Maybe a benefit: Specifying not more than one parent is trivial; just list the node in several menus. More often, preventing a semi-lattice involves additional checking when saving menus.
- Drawback: Specifying a parent cannot be enforced.
- Drawback: It is hard to know "where in the hierarchy" the current node is, unless you cache the information or do repeated searches (search for all category pages linking to the current page, then search for all category pages linking to them, and repeat until you get to the top node).
- Feature: Using this information, you automatically determine the next and previous siblings for a node. Linearization will be trivial; all you need to determine is how to deal with multiple parents and orphans. One trivial solution to this problem is to just print the node the first time it occurs and skip it from then on. Next and previous links will however be suboptimal for later occurences, since they point to children of the first parent only. This is only a problem if you use a semi-lattice structure, however.
- Feature: The menu with the children need not be a plain list; it may involve grouping and subheadings.
I'd be interesting in trying this one day. -- AlexSchroeder
Specify Linearization Separately
The GNU texinfo  documentation system produces various output formats; one of them is the Info file that can be browsed using an Info-browser, another one is the TeX file which can be used to print a book. This involves linearization of the nodes. For the Info file, parents have both menus and parent, next, and previous pointers (there is software support to generate the parent menu using the three pointers). For the TeX file, every node specifies its structure level (chapter, section, subsection), and all the nodes are printed in the order they appear in the file.
Here is what the manual has to say about it, however:
- You can use node pointers and menus to structure an Info file any way you want; and you can write a Texinfo file so that its Info output has a different structure than its printed output. However, virtually all Texinfo files are written such that the structure for the Info output corresponds to the structure for the printed output. It is neither convenient nor understandable to the reader to do otherwise.
Clearly, this approach involves maintaining a lot of metadata, and the benefits are not very clear.