Where I explore designing a type definition of a Wiki, without code this time
I have a lot of wacky computer science ideas, more of which are going to be appearing as other blog posts in the future. This is the most recent one, and therefore, the least pickled.
What is a Multigraph, anyway?
This is a concept in Discrete Mathematics, and it is a more general form of a Graph. So, what is a graph?
I think that the best way to explain these kinds of graphs is to use a different term: network. Most people have heard of a network. A social network includes you and all of your friends and family, and all of their friends and family, and so on and so on. I’m going to borrow a picture from Wikipedia.
Imagine that each circle with a number is a person, and each line between them is a friendship. That means that 1 is friends with 2 and 5, while 6 is only friends with 4.
However, since graphs are more abstract than groups of friends, we can use them to represent many different things. And there are different kinds of graphs too! The multigraph is where the edges (those lines between the circles) can be different kinds of edges. In the picture below, they are different colors.
What I am theorizing is that a multigraph can represent wikis themselves.
How are Wikis Multigraphs?
Graph of Hyperlinks
Wikis have hyperlinks between documents. Here is a hyperlink to the Wikipedia page on hyperlinks. We can represent this kind of link between one bit of text with another in a graph. Let’s take a look at that first picture again:
Now imagine that each of those circles represent a Wikipedia page, and that the lines between them represent a hyperlink.
The Outline is a Directed Acyclic Graph
A Directed Acyclic Graph (DAG) is a type of graph where all the edges have a sense of direction (directed) and there are no loops (acyclic). A good, real life example of this is a family tree (from Wikipedia again).
This DAG can’t have loops in it because people cannot be a parent and a child to themselves, nor can you be your own grandpa (biologically anyway). The directed nature of this graph can go either way: you can say that the arrow points to parents, or to children. Typically, we want our DAGs to point to one particular thing, so we will say that the arrows point to parents.
Why am I bringing this up? Because I realized that the outline structure of a document is also a DAG. Each Heading has several blocks of text under it, like the children in the family tree. And each Heading itself is a subheading of a bigger Heading. The concept of the “document” itself can be seen as the Lucas Grey of our family tree. Each document in a wiki is a DAG.
So, you have a graph of text blocks that form DAGs of documents, but each of those text blocks can also connect up to other text blocks in other DAGs with hyperlinks. So, what if we had a graph with two kinds of edges, the Outline kind, and the Hyperlink kind? An entire wiki could be theoretically stored in a single multigraph of text blocks, with Outline DAGs encoding documents, and Hyperlink graphs representing the connections between all the documents.
I believe that the type definition of a Wiki would be a multigraph of text. I think that you could store an entire wiki inside of a graph database and have a really interesting architecture for a wiki engine. But that’s for next time 🙂