# GetTaxonomy

## Final Protos

message Node {
  uint32 entity_type_id = 1; 
}

message Children {
  repeated Node nodes = 1;
}

message GetTaxonomyRequest {
  uint32 entity_type_id = 1; // if input is not given then the whole taxonomy
}

message GetTaxonomyResponse { // 
  Tree tree = 1;
}

message Tree {
  Node root = 1;
  map<uint32, Children> children = 2;
}

## Rough work

First way to represent a tree -:

Main challenge is in complex inheritance , foreg -: if the graph is -: parent -> child1, parent -> child2, child1 -> child2, what should be the output.

message GetTaxonomyResponse {
  EntityTypeNode taxonomy = 1;
}

message EntityTypeNode {
  string name = 1;
  uint32 entity_type_id = 2;
  repeated EntityTypeNode children = 3;
}

There can also be other ways to represent a tree -:

For eg -: adjacency lists

message Tree {
  repeated Vertex vertices = 1;
}

message Vertex {
  int32 vertex_id = 1;
  repeated int32 connections = 2;
}

The main difference between the two outputs is the way that the tree structure is represented. In the first example, the tree is represented using a hierarchical structure, where each node has a list of child nodes. This allows the client to easily traverse the tree to access the data. In the second example, the tree is represented using an adjacency list, where each node has a list of its child nodes' IDs. This representation is more compact, but it requires the client to process the data to construct the tree structure.

# Doubts

!! Krishna sir said for now don't think about multiple parents

1. How will our whole taxonomy look like ? Can it have multiple parents ?

Because for multiple parents it is not a conventional tree like structure, it's a DAG.


Both trees and DAGs are connected, directed, rooted, and have no cycles so this means that starting from any node and going up the parents you will eventually work your way up to the top (root).
However, since DAG nodes have multiple parents, there will be multiple paths on the way up (that eventually merge).
So Trees are DAGs with the restriction that a child can only have one parent.
**Another way to see it is Tree is like single class inheritance, and DAG is like multiple class inheritance.**

> *A tree is a DAG whose undirected version is still acyclic.*

What will the output of the following DAG look like for our taxonomy API ?

        digraph{
            "Parent" -> "Child 1"
            "Child 1" -> "Child 2"
            "Parent" -> "Child 2"
        }

2. Also is it necessary for every node to have a parent ? For eg -: if no parent, then connect to 'thing'
3.