21. Knowledge Organization¶

The “nice” mathematical way: a tree, a forest. Universal and more realistic (but still mathematical): a graph. Also mathematical, but useless: Venn diagrams.

21.1. Trees¶

21.1.1. Definition of a Tree¶

The most useful definition of a tree, comes from graph theory, where

a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa. A forest is a disjoint union of trees, or equivalently an acyclic graph that is not necessarily connected.

Strangely enough, many examples on Wikipedia use numbered nodes, which implies some kind of order. That is an invalid generalization from the set of “unfounded brain-dead assumptions”

Mathematically, graph theory identifies all kinds of different trees with fancy names and classifications. Then there is a whole lot of more fancy properties for trees in computer science. Most of these differences are members of the set of “distinctions that the world don’t need”.

E.g., a rooted tree is defined as “a tree in which one vertex has been designated the root”. It is easy to see, that in a tree graph, any node can be designated as root. So, there is really nothing special about a rooted tree or a root node.

The distcinction between undirected and directed graphs is pretty much useless and therefore in the set of “distinctions that the world don’t need”.

21.1.2. Walking Around a Tree¶

Using a rooted tree, there are two basic ways for tree traversal:

depth-first search and
breadth-first search.

There are many variations and combinations of these two basic tree walks, which are also in the set of “distinctions that the world don’t need”.

21.1.2.1. Depth-First search¶

The most common way to walk around a tree is a depth-first search. This tree traversal is also presented with an implicit order of nodes, which is unnecessary and therefore belongs to the set of unfounded brain-dead assumptions.

Here are some valid examples of unordered depth-first searches, solid lines signify the first visit, dashed lines signify backtracking:

21.1.2.2. Breadth-First search¶

Here are is an examples of an unordered breadth-first search, solid lines signify the first visit, dashed lines signify backtracking:

21.1.2.3. Illustrative Video¶

There is a YouTube video, which illustrates Depth First Search vs Breadth First Search using a stack and a queue for backtracking. The local copy (subtitles) is copyright 2017 by ONeillCode on YouTube:

Connect with me on LinkedIn! https://www.linkedin.com/in/stephenaoneill/

This video will go over Depth First Search vs Breadth First Search of a graph. It will explore how stacks and queues are used in the two algorithms and walk through it.

If you like the video, give it a thumbs up! If you want to see more videos from me hit the subscribe button! All code can be found here: https://github.com/oneillcode/Youtube-Tutorials

ONeill Code’s purpose is to provide in-depth tutorials on a wide range of programming material. It can focus on interview questions or simple algorithms depending on the user requests. If you have any video requests please let me!

21.1.3. Books¶

The organization of knowledge in books is equivalent to an ordered depth-first search.

which results in a document outline of:


1.
2.
3.
3.1.
3.2.
4.

1.
2.

1.
2.

Additional pathes, which violate the tree conditions can be introduced with cross-references:

21.1.4. Mindmaps¶

The popular mindmap also follows a tree structure. For a quick introduction see the online services MindMup (can store on Google Drive), Mindmap erstellen kostenlos - ohne Anmeldung. The application freemind(1) (/srv/install/freemind, java application) is quite popular with mindmap fans. Mindmaps also allow to connect nodes directly, just like books with their cross-references.

The fact, that a mindmap is nothing but a simple tree, presented in a different manner can be visualized by using a circular layout engine for the book example:

21.2. Generalization¶

Given an example with 6 sections, where each section shares a subset of information with at least 2 other sections and at most 3 other sections:

A -> B;
A -> F;
A -> D;
B -> C;
B -> F;
C -> D;
C -> E;
D -> F;
E -> F;

graphviz dot(1) draws an acceptable graph, which is quite tree like:

When some restrictions are introduced, which request certain sections to be of equal importance:

subgraph { rank = same; A; F; }
subgraph { rank = same; B; D; }
subgraph { rank = same; C; E; }

the graph looks less like a tree and more like a graph:

With one additonal restriction:

subgraph { rank = same; A; F; }
subgraph { rank = same; B; D; }
subgraph { rank = same; C; E; }
subgraph { rank = same; B; F; }

the faint resemblance of a tree is gone:

21.2.1. Circular Graphs¶

Giving up on trees, the most obvious layout to accomodate arbitrary graphs with any structure is a circular one:

The graph for the very simple example might still convey some interesting structural information. The general case, however, really does not help much in visualizing structural relations, although it does visualize the exponentiality of all possible pathes quite nicely (see Total number of Spanning Trees in a Graph):

21.2.2. Venn Diagrams¶

Represent the simple example as a Venn diagram:

<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="http://benfred.github.io/venn.js/examples/../venn.js"></script>
<script>
// define sets and set set intersections
var sets = [
      {sets: ['A'], size: 12},
      {sets: ['B'], size: 12},
      {sets: ['C'], size: 12},
      {sets: ['D'], size: 12},
      {sets: ['E'], size: 12},
      {sets: ['F'], size: 12},
      {sets: ['A','B'], size: 2},
      {sets: ['A','F'], size: 2},
      {sets: ['A','D'], size: 2},
      {sets: ['B','C'], size: 2},
      {sets: ['B','F'], size: 2},
      {sets: ['C','D'], size: 2},
      {sets: ['C','E'], size: 2},
      {sets: ['D','F'], size: 2},
      {sets: ['E','F'], size: 2}
      ];
var chart = venn.VennDiagram();
d3.select("#venn").datum(sets).call(chart);
</script>

the algorithm for Venn diagrams implemented in benfred/venn.js: Area proportional Venn and Euler diagrams in JavaScript renders nice graphics:

However, it cannot draw all of the common subsections:

WARNING: area C,D not represented on screen venn.js:1737:17

WARNING: area E,F not represented on screen venn.js:1737:17

This makes Venn diagrams practically useless for representing complex matters.

21.3. Conclusion¶

The fallacy of trees is the assumption that knowledge does indeed have some magical structure. This assumptions does of course belong to the set of unfounded brain-dead assumptions.

The example of a language reference, which is essentially a dictionary, shows that there is only a superficially useful categorization possible. Beyond that, the possiblities of constructing programs (sentences) are far too numerous to be captured in a book.

The same is true for any attempt of describing good practices or tips and tricks. This includes the current chapter as well as the entire documentation treatise.

Therefore, most mapping efforts trying to impose a rigorous tree structure are usually futile.

As for programming, this means that “object oriented” is not the ultimate answer. Especially things like Java, C#, strong typing in general are far too inflexible for interconnected designs. This is where Lisp, Python, Javascript are exponentially better suited for the task.

Summarily, the collection of knowledge in books is better than nothing, but with the possibilities of digital information storage it appears very antiquated. It is indeed really hard to grep(1) through a paper book.