Data Structures: Wikipedia-like Tree

Question

I am currently in the process of developing an ontology, a web hierarchy of categories of everything (think persons, places, things). The finished product should be something that allows me to navigate from Technology->Computers->Laptops->USB Ports, but also from Movies->Minority Report->Computers->etc. I need an efficient data structure to group these. I need a tree-like graph, but a special tree that allows child nodes to have multiple parent nodes. In thinking over this, I have realized that Wikipedia is an imperfect model for this. In fact, they have a hierarchy starting here that is essentially exactly what I need. I see that they used a directed graph, but I am wondering what the differences/drawbacks between this directed graph, a directed acyclic graph, and a polytree are. I have tried researching it, but I don't quite understand the differences. Any help would be greatly appreciated. Thank you!

Answer 1

I think the articles at Wikipedia give a good overview:

• A directed graph is a set of nodes connected by edges which have a direction associated with them.
• A directed acyclic graph (DAG) is a directed graph with no directed cycles.
• A polytree (also called directed tree) is a directed graph with exactly one undirected path between any two vertices. In other words, a polytree is a directed graph whose underlying undirected graph is a tree, or equivalently, a connected directed acyclic graph for which there are no undirected cycles either.

So I think you search for a connected directed acyclic graph. Altough the Wikipedia category system allows cycles, they are unwanted.