Skip to content

Instantly share code, notes, and snippets.

@audhiaprilliant

audhiaprilliant/bfs_dfs_tree_transversal.ipynb

Created October 24, 2021 15:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save audhiaprilliant/8bbe5ebb32e20a3ee42032cad68d613f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save audhiaprilliant/8bbe5ebb32e20a3ee42032cad68d613f to your computer and use it in GitHub Desktop.
Download ZIP
Breadth-First Search and Depth-First Search
Display the source blob
Display the rendered blob
Raw
bfs_dfs_tree_transversal.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "caroline-energy",
"metadata": {},
"source": [
"# BFS and DFS Implementation for Searching File System"
]
},
{
"cell_type": "markdown",
"id": "invisible-necklace",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"id": "changed-necessity",
"metadata": {},
"source": [
"## Import packages"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "qualified-disease",
"metadata": {},
"outputs": [],
"source": [
"# Provides different types of containers\n",
"import collections"
]
},
{
"cell_type": "markdown",
"id": "grave-consultation",
"metadata": {},
"source": [
"## Breadth-First Search"
]
},
{
"cell_type": "markdown",
"id": "processed-magnet",
"metadata": {},
"source": [
"### Algorithm"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "functional-disability",
"metadata": {},
"outputs": [],
"source": [
"# BFS algorithm\n",
"def BreadthFirstSearch(graph, node):\n",
" vertices = []\n",
" visited, queue = set(), collections.deque([node])\n",
" visited.add(node)\n",
"\n",
" while queue:\n",
" # Dequeue a vertex from queue\n",
" vertex = queue.popleft()\n",
" vertices.append(vertex)\n",
" \n",
" # If not visited, mark it as visited, and enqueue it\n",
" for idx in range(len(graph[vertex])):\n",
" neighbour = sorted(graph[vertex])[idx]\n",
" if neighbour not in visited:\n",
" visited.add(neighbour)\n",
" queue.append(neighbour)\n",
" \n",
" # Return visited value\n",
" return vertices"
]
},
{
"cell_type": "markdown",
"id": "prompt-affairs",
"metadata": {},
"source": [
"### Implementation"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "apparent-bunny",
"metadata": {},
"outputs": [],
"source": [
"# Graph data\n",
"graph = {\n",
" 'A': set(['B', 'C']),\n",
" 'B': set(['D', 'E']),\n",
" 'D': set([]),\n",
" 'E': set([]),\n",
" 'C': set(['F', 'G', 'H']),\n",
" 'G': set([]),\n",
" 'H': set([]),\n",
" 'F': set(['I', 'J']),\n",
" 'I': set([]),\n",
" 'J': set([])\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "rolled-wagon",
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"{'A': {'B', 'C'},\n",
" 'B': {'D', 'E'},\n",
" 'D': set(),\n",
" 'E': set(),\n",
" 'C': {'F', 'G', 'H'},\n",
" 'G': set(),\n",
" 'H': set(),\n",
" 'F': {'I', 'J'},\n",
" 'I': set(),\n",
" 'J': set()}"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Look the data\n",
"graph"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "average-deposit",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Following is Breadth-First Traversal\n"
]
},
{
"data": {
"text/plain": [
"['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print('Following is Breadth-First Traversal')\n",
"BreadthFirstSearch(graph, 'A')"
]
},
{
"cell_type": "markdown",
"id": "coastal-procedure",
"metadata": {},
"source": [
"## Depth First Search"
]
},
{
"cell_type": "markdown",
"id": "arbitrary-macro",
"metadata": {},
"source": [
"### Algorithm"
]
},
{
"cell_type": "code",
"execution_count": 118,
"id": "august-gregory",
"metadata": {},
"outputs": [],
"source": [
"# DFS algorithm\n",
"def dfs(visited, graph, node):\n",
" if node not in visited:\n",
" visited.add(node)\n",
" # Store the node\n",
" vertices.append(node)\n",
" \n",
" for idx in range(len(graph[node])):\n",
" neighbour = sorted(graph[node])[idx]\n",
" dfs(visited, graph, neighbour)"
]
},
{
"cell_type": "code",
"execution_count": 119,
"id": "latest-harassment",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['A', 'B', 'D', 'E', 'C', 'F', 'I', 'J', 'G', 'H']"
]
},
"execution_count": 119,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"vertices = []\n",
"visited = set()\n",
"dfs(visited, graph, 'A')\n",
"vertices"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "essential-neighborhood",
"metadata": {
"code_folding": []
},
"outputs": [],
"source": [
"# DFS algorithm\n",
"def DepthFirstSearch(visited, graph, node):\n",
" if node not in visited:\n",
" visited.add(node)\n",
" # Store the node\n",
" vertices.append(node)\n",
" \n",
" for idx in range(len(graph[node])):\n",
" neighbour = sorted(graph[node])[idx]\n",
" DepthFirstSearch(visited, graph, neighbour)"
]
},
{
"cell_type": "markdown",
"id": "mounted-russia",
"metadata": {},
"source": [
"### Implementation"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "intensive-bidding",
"metadata": {},
"outputs": [],
"source": [
"# Graph data\n",
"graph = {\n",
" 'A': set(['B', 'C']),\n",
" 'B': set(['D', 'E']),\n",
" 'D': set([]),\n",
" 'E': set([]),\n",
" 'C': set(['F', 'G', 'H']),\n",
" 'G': set([]),\n",
" 'H': set([]),\n",
" 'F': set(['I', 'J']),\n",
" 'I': set([]),\n",
" 'J': set([])\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "respiratory-blond",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A': {'B', 'C'},\n",
" 'B': {'D', 'E'},\n",
" 'D': set(),\n",
" 'E': set(),\n",
" 'C': {'F', 'G', 'H'},\n",
" 'G': set(),\n",
" 'H': set(),\n",
" 'F': {'I', 'J'},\n",
" 'I': set(),\n",
" 'J': set()}"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Look the data\n",
"graph"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "clear-migration",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Following is Depth-First Traversal\n"
]
},
{
"data": {
"text/plain": [
"['A', 'B', 'D', 'E', 'C', 'F', 'I', 'J', 'G', 'H']"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print('Following is Depth-First Traversal')\n",
"vertices = []\n",
"visited = set()\n",
"DepthFirstSearch(visited, graph, 'A')\n",
"vertices"
]
},
{
"cell_type": "markdown",
"id": "suitable-calgary",
"metadata": {},
"source": [
"## File system searching"
]
},
{
"cell_type": "markdown",
"id": "disciplinary-individual",
"metadata": {},
"source": [
"### **1 Load the data**"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "concrete-scheduling",
"metadata": {},
"outputs": [],
"source": [
"tree = {\n",
" 'A': ['A1', 'A2', 'A3', 'A4', 'A5'],\n",
" # Directory for A1\n",
" 'A1': ['A11', 'A12', 'A13'],\n",
" 'A11': ['A111', 'A112'],\n",
" 'A111': ['A111_file_1'],\n",
" 'A111_file_1': [],\n",
" 'A112': ['A112_file_1', 'A112_file_2'],\n",
" 'A112_file_1': [],\n",
" 'A112_file_2': [],\n",
" 'A12': ['A121', 'A122', 'A123'],\n",
" 'A121': ['A121_file_1'],\n",
" 'A121_file_1': [],\n",
" 'A122': ['A1221'],\n",
" 'A1221': ['A1221_file_1', 'A1221_file_2'],\n",
" 'A1221_file_1': [],\n",
" 'A1221_file_2': [],\n",
" 'A123': [],\n",
" 'A13': ['A13_file_1'],\n",
" 'A13_file_1': [],\n",
" # Directory for A2\n",
" 'A2': ['A21', 'A22'],\n",
" 'A21': ['A211', 'A212', 'A213'],\n",
" 'A211': ['A211_file_1', 'A211_file_2'],\n",
" 'A211_file_1': [],\n",
" 'A211_file_2': [],\n",
" 'A212': ['A2121'],\n",
" 'A2121': ['A21211', 'A2121_file_1', 'A2121_file_2'],\n",
" 'A2121_file_1': [],\n",
" 'A2121_file_2': [],\n",
" 'A21211': ['A21211_file_1', 'A21211_file_2'],\n",
" 'A21211_file_1': [],\n",
" 'A21211_file_2': [],\n",
" 'A213': ['A2131'],\n",
" 'A2131': ['A2131_file_1', 'A21311'],\n",
" 'A2131_file_1': [],\n",
" 'A21311': ['A21311_file_1', 'A21311_file_2'],\n",
" 'A21311_file_1': [],\n",
" 'A21311_file_2': [],\n",
" 'A22': ['A221'],\n",
" 'A221': ['A221_file_1', 'A2211', 'A2212'],\n",
" 'A221_file_1': [],\n",
" 'A2211': ['A2211_file_1', 'A2211_file_2'],\n",
" 'A2211_file_1': [],\n",
" 'A2211_file_2': [],\n",
" 'A2212': ['A2212_file_1'],\n",
" 'A2212_file_1': [],\n",
" # Directory for A3\n",
" 'A3': ['A31', 'A32'],\n",
" 'A31': ['A31_file_1'],\n",
" 'A31_file_1': [],\n",
" 'A32': ['A321'],\n",
" 'A321': ['A3211', 'A3212', 'A3213'],\n",
" 'A3211': ['A3211_file_1', 'A32111'],\n",
" 'A3211_file_1': [],\n",
" 'A32111': ['A32111_file_1', 'A32111_file_2'],\n",
" 'A32111_file_1': [],\n",
" 'A32111_file_2': [],\n",
" 'A3212': ['A3212_file_1', 'A32122', 'A3212_file_2'],\n",
" 'A3212_file_1': [],\n",
" 'A3212_file_2': [],\n",
" 'A32122': ['A32122_file_1', 'A32122_file_2'],\n",
" 'A32122_file_1': [],\n",
" 'A32122_file_2': [],\n",
" 'A3213': ['A32131'],\n",
" 'A32131': ['A321311'],\n",
" 'A321311': ['A321311_file_1', 'A321311_file_2'],\n",
" 'A321311_file_1': [],\n",
" 'A321311_file_2': [],\n",
" # Directory for A4\n",
" 'A4': ['A41'],\n",
" 'A41': ['A41_file_1', 'A411'],\n",
" 'A41_file_1': [],\n",
" 'A411': ['A4111', 'A4112', 'A4113', 'A4114'],\n",
" 'A4111': ['A4111_file_1', 'A41111'],\n",
" 'A4111_file_1': [],\n",
" 'A41111': ['A41111_file_1', 'A41111_file_2', 'A41111_file_3'],\n",
" 'A41111_file_1': [],\n",
" 'A41111_file_2': [],\n",
" 'A41111_file_3': [],\n",
" 'A4112': ['A41121'],\n",
" 'A41121': ['A41121_file_1', 'A41121_file_2'],\n",
" 'A41121_file_1': [],\n",
" 'A41121_file_2': [],\n",
" 'A4113': ['A4113_file_1', 'A41131', 'A4113_file_2'],\n",
" 'A4113_file_1': [],\n",
" 'A4113_file_2': [],\n",
" 'A41131': ['A41131_file_1'],\n",
" 'A41131_file_1': [],\n",
" 'A4114': ['A41141', 'A4114_file_1'],\n",
" 'A4114_file_1': [],\n",
" 'A41141': ['A41141_file_1', 'A411411'],\n",
" 'A41141_file_1': [],\n",
" 'A411411': ['A4114111', 'A411411_file_1'],\n",
" 'A411411_file_1': [],\n",
" 'A4114111': ['A4114111_file_1'],\n",
" 'A4114111_file_1': [],\n",
" # Directory for A5\n",
" 'A5': ['A51', 'A52', 'A53', 'A54'],\n",
" 'A51': ['A511', 'A512', 'A513'],\n",
" 'A511': ['A511_file_1', 'A511_file_2'],\n",
" 'A511_file_1': [],\n",
" 'A511_file_2': [],\n",
" 'A512': ['A512_file_1', 'A5121', 'A512_file_2'],\n",
" 'A512_file_1': [],\n",
" 'A512_file_2': [],\n",
" 'A5121': ['A5121_file_1', 'A5121_file_2'],\n",
" 'A5121_file_1': [],\n",
" 'A5121_file_2': [],\n",
" 'A513': [],\n",
" 'A52': ['A521'],\n",
" 'A521': ['A521_file_1', 'A5211'],\n",
" 'A521_file_1': [],\n",
" 'A5211': ['A5211_file_1', 'A5211_file_2', 'A5211_file_3'],\n",
" 'A5211_file_1': [],\n",
" 'A5211_file_2': [],\n",
" 'A5211_file_3': [],\n",
" 'A53': ['A53_file_1', 'A53_file_2', 'A53_file_3'],\n",
" 'A53_file_1': [],\n",
" 'A53_file_2': [],\n",
" 'A53_file_3': [],\n",
" 'A54': []\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "directed-nevada",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A': ['A1', 'A2', 'A3', 'A4', 'A5'],\n",
" 'A1': ['A11', 'A12', 'A13'],\n",
" 'A11': ['A111', 'A112'],\n",
" 'A111': ['A111_file_1'],\n",
" 'A111_file_1': [],\n",
" 'A112': ['A112_file_1', 'A112_file_2'],\n",
" 'A112_file_1': [],\n",
" 'A112_file_2': [],\n",
" 'A12': ['A121', 'A122', 'A123'],\n",
" 'A121': ['A121_file_1'],\n",
" 'A121_file_1': [],\n",
" 'A122': ['A1221'],\n",
" 'A1221': ['A1221_file_1', 'A1221_file_2'],\n",
" 'A1221_file_1': [],\n",
" 'A1221_file_2': [],\n",
" 'A123': [],\n",
" 'A13': ['A13_file_1'],\n",
" 'A13_file_1': [],\n",
" 'A2': ['A21', 'A22'],\n",
" 'A21': ['A211', 'A212', 'A213'],\n",
" 'A211': ['A211_file_1', 'A211_file_2'],\n",
" 'A211_file_1': [],\n",
" 'A211_file_2': [],\n",
" 'A212': ['A2121'],\n",
" 'A2121': ['A21211', 'A2121_file_1', 'A2121_file_2'],\n",
" 'A2121_file_1': [],\n",
" 'A2121_file_2': [],\n",
" 'A21211': ['A21211_file_1', 'A21211_file_2'],\n",
" 'A21211_file_1': [],\n",
" 'A21211_file_2': [],\n",
" 'A213': ['A2131'],\n",
" 'A2131': ['A2131_file_1', 'A21311'],\n",
" 'A2131_file_1': [],\n",
" 'A21311': ['A21311_file_1', 'A21311_file_2'],\n",
" 'A21311_file_1': [],\n",
" 'A21311_file_2': [],\n",
" 'A22': ['A221'],\n",
" 'A221': ['A221_file_1', 'A2211', 'A2212'],\n",
" 'A221_file_1': [],\n",
" 'A2211': ['A2211_file_1', 'A2211_file_2'],\n",
" 'A2211_file_1': [],\n",
" 'A2211_file_2': [],\n",
" 'A2212': ['A2212_file_1'],\n",
" 'A2212_file_1': [],\n",
" 'A3': ['A31', 'A32'],\n",
" 'A31': ['A31_file_1'],\n",
" 'A31_file_1': [],\n",
" 'A32': ['A321'],\n",
" 'A321': ['A3211', 'A3212', 'A3213'],\n",
" 'A3211': ['A3211_file_1', 'A32111'],\n",
" 'A3211_file_1': [],\n",
" 'A32111': ['A32111_file_1', 'A32111_file_2'],\n",
" 'A32111_file_1': [],\n",
" 'A32111_file_2': [],\n",
" 'A3212': ['A3212_file_1', 'A32122', 'A3212_file_2'],\n",
" 'A3212_file_1': [],\n",
" 'A3212_file_2': [],\n",
" 'A32122': ['A32122_file_1', 'A32122_file_2'],\n",
" 'A32122_file_1': [],\n",
" 'A32122_file_2': [],\n",
" 'A3213': ['A32131'],\n",
" 'A32131': ['A321311'],\n",
" 'A321311': ['A321311_file_1', 'A321311_file_2'],\n",
" 'A321311_file_1': [],\n",
" 'A321311_file_2': [],\n",
" 'A4': ['A41'],\n",
" 'A41': ['A41_file_1', 'A411'],\n",
" 'A41_file_1': [],\n",
" 'A411': ['A4111', 'A4112', 'A4113', 'A4114'],\n",
" 'A4111': ['A4111_file_1', 'A41111'],\n",
" 'A4111_file_1': [],\n",
" 'A41111': ['A41111_file_1', 'A41111_file_2', 'A41111_file_3'],\n",
" 'A41111_file_1': [],\n",
" 'A41111_file_2': [],\n",
" 'A41111_file_3': [],\n",
" 'A4112': ['A41121'],\n",
" 'A41121': ['A41121_file_1', 'A41121_file_2'],\n",
" 'A41121_file_1': [],\n",
" 'A41121_file_2': [],\n",
" 'A4113': ['A4113_file_1', 'A41131', 'A4113_file_2'],\n",
" 'A4113_file_1': [],\n",
" 'A4113_file_2': [],\n",
" 'A41131': ['A41131_file_1'],\n",
" 'A41131_file_1': [],\n",
" 'A4114': ['A41141', 'A4114_file_1'],\n",
" 'A4114_file_1': [],\n",
" 'A41141': ['A41141_file_1', 'A411411'],\n",
" 'A41141_file_1': [],\n",
" 'A411411': ['A4114111', 'A411411_file_1'],\n",
" 'A411411_file_1': [],\n",
" 'A4114111': ['A4114111_file_1'],\n",
" 'A4114111_file_1': [],\n",
" 'A5': ['A51', 'A52', 'A53', 'A54'],\n",
" 'A51': ['A511', 'A512', 'A513'],\n",
" 'A511': ['A511_file_1', 'A511_file_2'],\n",
" 'A511_file_1': [],\n",
" 'A511_file_2': [],\n",
" 'A512': ['A512_file_1', 'A5121', 'A512_file_2'],\n",
" 'A512_file_1': [],\n",
" 'A512_file_2': [],\n",
" 'A5121': ['A5121_file_1', 'A5121_file_2'],\n",
" 'A5121_file_1': [],\n",
" 'A5121_file_2': [],\n",
" 'A513': [],\n",
" 'A52': ['A521'],\n",
" 'A521': ['A521_file_1', 'A5211'],\n",
" 'A521_file_1': [],\n",
" 'A5211': ['A5211_file_1', 'A5211_file_2', 'A5211_file_3'],\n",
" 'A5211_file_1': [],\n",
" 'A5211_file_2': [],\n",
" 'A5211_file_3': [],\n",
" 'A53': ['A53_file_1', 'A53_file_2', 'A53_file_3'],\n",
" 'A53_file_1': [],\n",
" 'A53_file_2': [],\n",
" 'A53_file_3': [],\n",
" 'A54': []}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The directory data\n",
"tree"
]
},
{
"cell_type": "markdown",
"id": "classical-education",
"metadata": {},
"source": [
"### **2 Convert into sets**"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "finished-colors",
"metadata": {},
"outputs": [],
"source": [
"# Convert the previous tree data structure to the new one\n",
"tree_set = {}\n",
"for key in tree.keys():\n",
" tree_set.update({key: set(tree[key])})"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "industrial-buying",
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"{'A': {'A1', 'A2', 'A3', 'A4', 'A5'},\n",
" 'A1': {'A11', 'A12', 'A13'},\n",
" 'A11': {'A111', 'A112'},\n",
" 'A111': {'A111_file_1'},\n",
" 'A111_file_1': set(),\n",
" 'A112': {'A112_file_1', 'A112_file_2'},\n",
" 'A112_file_1': set(),\n",
" 'A112_file_2': set(),\n",
" 'A12': {'A121', 'A122', 'A123'},\n",
" 'A121': {'A121_file_1'},\n",
" 'A121_file_1': set(),\n",
" 'A122': {'A1221'},\n",
" 'A1221': {'A1221_file_1', 'A1221_file_2'},\n",
" 'A1221_file_1': set(),\n",
" 'A1221_file_2': set(),\n",
" 'A123': set(),\n",
" 'A13': {'A13_file_1'},\n",
" 'A13_file_1': set(),\n",
" 'A2': {'A21', 'A22'},\n",
" 'A21': {'A211', 'A212', 'A213'},\n",
" 'A211': {'A211_file_1', 'A211_file_2'},\n",
" 'A211_file_1': set(),\n",
" 'A211_file_2': set(),\n",
" 'A212': {'A2121'},\n",
" 'A2121': {'A21211', 'A2121_file_1', 'A2121_file_2'},\n",
" 'A2121_file_1': set(),\n",
" 'A2121_file_2': set(),\n",
" 'A21211': {'A21211_file_1', 'A21211_file_2'},\n",
" 'A21211_file_1': set(),\n",
" 'A21211_file_2': set(),\n",
" 'A213': {'A2131'},\n",
" 'A2131': {'A21311', 'A2131_file_1'},\n",
" 'A2131_file_1': set(),\n",
" 'A21311': {'A21311_file_1', 'A21311_file_2'},\n",
" 'A21311_file_1': set(),\n",
" 'A21311_file_2': set(),\n",
" 'A22': {'A221'},\n",
" 'A221': {'A2211', 'A2212', 'A221_file_1'},\n",
" 'A221_file_1': set(),\n",
" 'A2211': {'A2211_file_1', 'A2211_file_2'},\n",
" 'A2211_file_1': set(),\n",
" 'A2211_file_2': set(),\n",
" 'A2212': {'A2212_file_1'},\n",
" 'A2212_file_1': set(),\n",
" 'A3': {'A31', 'A32'},\n",
" 'A31': {'A31_file_1'},\n",
" 'A31_file_1': set(),\n",
" 'A32': {'A321'},\n",
" 'A321': {'A3211', 'A3212', 'A3213'},\n",
" 'A3211': {'A32111', 'A3211_file_1'},\n",
" 'A3211_file_1': set(),\n",
" 'A32111': {'A32111_file_1', 'A32111_file_2'},\n",
" 'A32111_file_1': set(),\n",
" 'A32111_file_2': set(),\n",
" 'A3212': {'A32122', 'A3212_file_1', 'A3212_file_2'},\n",
" 'A3212_file_1': set(),\n",
" 'A3212_file_2': set(),\n",
" 'A32122': {'A32122_file_1', 'A32122_file_2'},\n",
" 'A32122_file_1': set(),\n",
" 'A32122_file_2': set(),\n",
" 'A3213': {'A32131'},\n",
" 'A32131': {'A321311'},\n",
" 'A321311': {'A321311_file_1', 'A321311_file_2'},\n",
" 'A321311_file_1': set(),\n",
" 'A321311_file_2': set(),\n",
" 'A4': {'A41'},\n",
" 'A41': {'A411', 'A41_file_1'},\n",
" 'A41_file_1': set(),\n",
" 'A411': {'A4111', 'A4112', 'A4113', 'A4114'},\n",
" 'A4111': {'A41111', 'A4111_file_1'},\n",
" 'A4111_file_1': set(),\n",
" 'A41111': {'A41111_file_1', 'A41111_file_2', 'A41111_file_3'},\n",
" 'A41111_file_1': set(),\n",
" 'A41111_file_2': set(),\n",
" 'A41111_file_3': set(),\n",
" 'A4112': {'A41121'},\n",
" 'A41121': {'A41121_file_1', 'A41121_file_2'},\n",
" 'A41121_file_1': set(),\n",
" 'A41121_file_2': set(),\n",
" 'A4113': {'A41131', 'A4113_file_1', 'A4113_file_2'},\n",
" 'A4113_file_1': set(),\n",
" 'A4113_file_2': set(),\n",
" 'A41131': {'A41131_file_1'},\n",
" 'A41131_file_1': set(),\n",
" 'A4114': {'A41141', 'A4114_file_1'},\n",
" 'A4114_file_1': set(),\n",
" 'A41141': {'A411411', 'A41141_file_1'},\n",
" 'A41141_file_1': set(),\n",
" 'A411411': {'A4114111', 'A411411_file_1'},\n",
" 'A411411_file_1': set(),\n",
" 'A4114111': {'A4114111_file_1'},\n",
" 'A4114111_file_1': set(),\n",
" 'A5': {'A51', 'A52', 'A53', 'A54'},\n",
" 'A51': {'A511', 'A512', 'A513'},\n",
" 'A511': {'A511_file_1', 'A511_file_2'},\n",
" 'A511_file_1': set(),\n",
" 'A511_file_2': set(),\n",
" 'A512': {'A5121', 'A512_file_1', 'A512_file_2'},\n",
" 'A512_file_1': set(),\n",
" 'A512_file_2': set(),\n",
" 'A5121': {'A5121_file_1', 'A5121_file_2'},\n",
" 'A5121_file_1': set(),\n",
" 'A5121_file_2': set(),\n",
" 'A513': set(),\n",
" 'A52': {'A521'},\n",
" 'A521': {'A5211', 'A521_file_1'},\n",
" 'A521_file_1': set(),\n",
" 'A5211': {'A5211_file_1', 'A5211_file_2', 'A5211_file_3'},\n",
" 'A5211_file_1': set(),\n",
" 'A5211_file_2': set(),\n",
" 'A5211_file_3': set(),\n",
" 'A53': {'A53_file_1', 'A53_file_2', 'A53_file_3'},\n",
" 'A53_file_1': set(),\n",
" 'A53_file_2': set(),\n",
" 'A53_file_3': set(),\n",
" 'A54': set()}"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The directory data\n",
"tree_set"
]
},
{
"cell_type": "markdown",
"id": "dominant-guidance",
"metadata": {},
"source": [
"### 3 Convert into tree format (optional)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "cardiac-proposal",
"metadata": {},
"outputs": [],
"source": [
"# Create a nodelist\n",
"nodelists = dict((node, [node, []]) for node in tree.keys())"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "posted-rendering",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A': ['A', []],\n",
" 'A1': ['A1', []],\n",
" 'A11': ['A11', []],\n",
" 'A111': ['A111', []],\n",
" 'A111_file_1': ['A111_file_1', []],\n",
" 'A112': ['A112', []],\n",
" 'A112_file_1': ['A112_file_1', []],\n",
" 'A112_file_2': ['A112_file_2', []],\n",
" 'A12': ['A12', []],\n",
" 'A121': ['A121', []],\n",
" 'A121_file_1': ['A121_file_1', []],\n",
" 'A122': ['A122', []],\n",
" 'A1221': ['A1221', []],\n",
" 'A1221_file_1': ['A1221_file_1', []],\n",
" 'A1221_file_2': ['A1221_file_2', []],\n",
" 'A123': ['A123', []],\n",
" 'A13': ['A13', []],\n",
" 'A13_file_1': ['A13_file_1', []],\n",
" 'A2': ['A2', []],\n",
" 'A21': ['A21', []],\n",
" 'A211': ['A211', []],\n",
" 'A211_file_1': ['A211_file_1', []],\n",
" 'A211_file_2': ['A211_file_2', []],\n",
" 'A212': ['A212', []],\n",
" 'A2121': ['A2121', []],\n",
" 'A2121_file_1': ['A2121_file_1', []],\n",
" 'A2121_file_2': ['A2121_file_2', []],\n",
" 'A21211': ['A21211', []],\n",
" 'A21211_file_1': ['A21211_file_1', []],\n",
" 'A21211_file_2': ['A21211_file_2', []],\n",
" 'A213': ['A213', []],\n",
" 'A2131': ['A2131', []],\n",
" 'A2131_file_1': ['A2131_file_1', []],\n",
" 'A21311': ['A21311', []],\n",
" 'A21311_file_1': ['A21311_file_1', []],\n",
" 'A21311_file_2': ['A21311_file_2', []],\n",
" 'A22': ['A22', []],\n",
" 'A221': ['A221', []],\n",
" 'A221_file_1': ['A221_file_1', []],\n",
" 'A2211': ['A2211', []],\n",
" 'A2211_file_1': ['A2211_file_1', []],\n",
" 'A2211_file_2': ['A2211_file_2', []],\n",
" 'A2212': ['A2212', []],\n",
" 'A2212_file_1': ['A2212_file_1', []],\n",
" 'A3': ['A3', []],\n",
" 'A31': ['A31', []],\n",
" 'A31_file_1': ['A31_file_1', []],\n",
" 'A32': ['A32', []],\n",
" 'A321': ['A321', []],\n",
" 'A3211': ['A3211', []],\n",
" 'A3211_file_1': ['A3211_file_1', []],\n",
" 'A32111': ['A32111', []],\n",
" 'A32111_file_1': ['A32111_file_1', []],\n",
" 'A32111_file_2': ['A32111_file_2', []],\n",
" 'A3212': ['A3212', []],\n",
" 'A3212_file_1': ['A3212_file_1', []],\n",
" 'A3212_file_2': ['A3212_file_2', []],\n",
" 'A32122': ['A32122', []],\n",
" 'A32122_file_1': ['A32122_file_1', []],\n",
" 'A32122_file_2': ['A32122_file_2', []],\n",
" 'A3213': ['A3213', []],\n",
" 'A32131': ['A32131', []],\n",
" 'A321311': ['A321311', []],\n",
" 'A321311_file_1': ['A321311_file_1', []],\n",
" 'A321311_file_2': ['A321311_file_2', []],\n",
" 'A4': ['A4', []],\n",
" 'A41': ['A41', []],\n",
" 'A41_file_1': ['A41_file_1', []],\n",
" 'A411': ['A411', []],\n",
" 'A4111': ['A4111', []],\n",
" 'A4111_file_1': ['A4111_file_1', []],\n",
" 'A41111': ['A41111', []],\n",
" 'A41111_file_1': ['A41111_file_1', []],\n",
" 'A41111_file_2': ['A41111_file_2', []],\n",
" 'A41111_file_3': ['A41111_file_3', []],\n",
" 'A4112': ['A4112', []],\n",
" 'A41121': ['A41121', []],\n",
" 'A41121_file_1': ['A41121_file_1', []],\n",
" 'A41121_file_2': ['A41121_file_2', []],\n",
" 'A4113': ['A4113', []],\n",
" 'A4113_file_1': ['A4113_file_1', []],\n",
" 'A4113_file_2': ['A4113_file_2', []],\n",
" 'A41131': ['A41131', []],\n",
" 'A41131_file_1': ['A41131_file_1', []],\n",
" 'A4114': ['A4114', []],\n",
" 'A4114_file_1': ['A4114_file_1', []],\n",
" 'A41141': ['A41141', []],\n",
" 'A41141_file_1': ['A41141_file_1', []],\n",
" 'A411411': ['A411411', []],\n",
" 'A411411_file_1': ['A411411_file_1', []],\n",
" 'A4114111': ['A4114111', []],\n",
" 'A4114111_file_1': ['A4114111_file_1', []],\n",
" 'A5': ['A5', []],\n",
" 'A51': ['A51', []],\n",
" 'A511': ['A511', []],\n",
" 'A511_file_1': ['A511_file_1', []],\n",
" 'A511_file_2': ['A511_file_2', []],\n",
" 'A512': ['A512', []],\n",
" 'A512_file_1': ['A512_file_1', []],\n",
" 'A512_file_2': ['A512_file_2', []],\n",
" 'A5121': ['A5121', []],\n",
" 'A5121_file_1': ['A5121_file_1', []],\n",
" 'A5121_file_2': ['A5121_file_2', []],\n",
" 'A513': ['A513', []],\n",
" 'A52': ['A52', []],\n",
" 'A521': ['A521', []],\n",
" 'A521_file_1': ['A521_file_1', []],\n",
" 'A5211': ['A5211', []],\n",
" 'A5211_file_1': ['A5211_file_1', []],\n",
" 'A5211_file_2': ['A5211_file_2', []],\n",
" 'A5211_file_3': ['A5211_file_3', []],\n",
" 'A53': ['A53', []],\n",
" 'A53_file_1': ['A53_file_1', []],\n",
" 'A53_file_2': ['A53_file_2', []],\n",
" 'A53_file_3': ['A53_file_3', []],\n",
" 'A54': ['A54', []]}"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Nodelist data\n",
"nodelists"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "liable-diversity",
"metadata": {},
"outputs": [],
"source": [
"# Convert childs into nodelist data\n",
"for node, children in tree.items():\n",
" for child in children:\n",
" nodelists[node][1].extend(nodelists.setdefault(child, [child]))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "south-registrar",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A': ['A',\n",
" ['A1',\n",
" ['A11',\n",
" ['A111',\n",
" ['A111_file_1', []],\n",
" 'A112',\n",
" ['A112_file_1', [], 'A112_file_2', []]],\n",
" 'A12',\n",
" ['A121',\n",
" ['A121_file_1', []],\n",
" 'A122',\n",
" ['A1221', ['A1221_file_1', [], 'A1221_file_2', []]],\n",
" 'A123',\n",
" []],\n",
" 'A13',\n",
" ['A13_file_1', []]],\n",
" 'A2',\n",
" ['A21',\n",
" ['A211',\n",
" ['A211_file_1', [], 'A211_file_2', []],\n",
" 'A212',\n",
" ['A2121',\n",
" ['A21211',\n",
" ['A21211_file_1', [], 'A21211_file_2', []],\n",
" 'A2121_file_1',\n",
" [],\n",
" 'A2121_file_2',\n",
" []]],\n",
" 'A213',\n",
" ['A2131',\n",
" ['A2131_file_1',\n",
" [],\n",
" 'A21311',\n",
" ['A21311_file_1', [], 'A21311_file_2', []]]]],\n",
" 'A22',\n",
" ['A221',\n",
" ['A221_file_1',\n",
" [],\n",
" 'A2211',\n",
" ['A2211_file_1', [], 'A2211_file_2', []],\n",
" 'A2212',\n",
" ['A2212_file_1', []]]]],\n",
" 'A3',\n",
" ['A31',\n",
" ['A31_file_1', []],\n",
" 'A32',\n",
" ['A321',\n",
" ['A3211',\n",
" ['A3211_file_1',\n",
" [],\n",
" 'A32111',\n",
" ['A32111_file_1', [], 'A32111_file_2', []]],\n",
" 'A3212',\n",
" ['A3212_file_1',\n",
" [],\n",
" 'A32122',\n",
" ['A32122_file_1', [], 'A32122_file_2', []],\n",
" 'A3212_file_2',\n",
" []],\n",
" 'A3213',\n",
" ['A32131', ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]]]]],\n",
" 'A4',\n",
" ['A41',\n",
" ['A41_file_1',\n",
" [],\n",
" 'A411',\n",
" ['A4111',\n",
" ['A4111_file_1',\n",
" [],\n",
" 'A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]],\n",
" 'A4112',\n",
" ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]],\n",
" 'A4113',\n",
" ['A4113_file_1',\n",
" [],\n",
" 'A41131',\n",
" ['A41131_file_1', []],\n",
" 'A4113_file_2',\n",
" []],\n",
" 'A4114',\n",
" ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A4114_file_1',\n",
" []]]]],\n",
" 'A5',\n",
" ['A51',\n",
" ['A511',\n",
" ['A511_file_1', [], 'A511_file_2', []],\n",
" 'A512',\n",
" ['A512_file_1',\n",
" [],\n",
" 'A5121',\n",
" ['A5121_file_1', [], 'A5121_file_2', []],\n",
" 'A512_file_2',\n",
" []],\n",
" 'A513',\n",
" []],\n",
" 'A52',\n",
" ['A521',\n",
" ['A521_file_1',\n",
" [],\n",
" 'A5211',\n",
" ['A5211_file_1', [], 'A5211_file_2', [], 'A5211_file_3', []]]],\n",
" 'A53',\n",
" ['A53_file_1', [], 'A53_file_2', [], 'A53_file_3', []],\n",
" 'A54',\n",
" []]]],\n",
" 'A1': ['A1',\n",
" ['A11',\n",
" ['A111',\n",
" ['A111_file_1', []],\n",
" 'A112',\n",
" ['A112_file_1', [], 'A112_file_2', []]],\n",
" 'A12',\n",
" ['A121',\n",
" ['A121_file_1', []],\n",
" 'A122',\n",
" ['A1221', ['A1221_file_1', [], 'A1221_file_2', []]],\n",
" 'A123',\n",
" []],\n",
" 'A13',\n",
" ['A13_file_1', []]]],\n",
" 'A11': ['A11',\n",
" ['A111',\n",
" ['A111_file_1', []],\n",
" 'A112',\n",
" ['A112_file_1', [], 'A112_file_2', []]]],\n",
" 'A111': ['A111', ['A111_file_1', []]],\n",
" 'A111_file_1': ['A111_file_1', []],\n",
" 'A112': ['A112', ['A112_file_1', [], 'A112_file_2', []]],\n",
" 'A112_file_1': ['A112_file_1', []],\n",
" 'A112_file_2': ['A112_file_2', []],\n",
" 'A12': ['A12',\n",
" ['A121',\n",
" ['A121_file_1', []],\n",
" 'A122',\n",
" ['A1221', ['A1221_file_1', [], 'A1221_file_2', []]],\n",
" 'A123',\n",
" []]],\n",
" 'A121': ['A121', ['A121_file_1', []]],\n",
" 'A121_file_1': ['A121_file_1', []],\n",
" 'A122': ['A122', ['A1221', ['A1221_file_1', [], 'A1221_file_2', []]]],\n",
" 'A1221': ['A1221', ['A1221_file_1', [], 'A1221_file_2', []]],\n",
" 'A1221_file_1': ['A1221_file_1', []],\n",
" 'A1221_file_2': ['A1221_file_2', []],\n",
" 'A123': ['A123', []],\n",
" 'A13': ['A13', ['A13_file_1', []]],\n",
" 'A13_file_1': ['A13_file_1', []],\n",
" 'A2': ['A2',\n",
" ['A21',\n",
" ['A211',\n",
" ['A211_file_1', [], 'A211_file_2', []],\n",
" 'A212',\n",
" ['A2121',\n",
" ['A21211',\n",
" ['A21211_file_1', [], 'A21211_file_2', []],\n",
" 'A2121_file_1',\n",
" [],\n",
" 'A2121_file_2',\n",
" []]],\n",
" 'A213',\n",
" ['A2131',\n",
" ['A2131_file_1',\n",
" [],\n",
" 'A21311',\n",
" ['A21311_file_1', [], 'A21311_file_2', []]]]],\n",
" 'A22',\n",
" ['A221',\n",
" ['A221_file_1',\n",
" [],\n",
" 'A2211',\n",
" ['A2211_file_1', [], 'A2211_file_2', []],\n",
" 'A2212',\n",
" ['A2212_file_1', []]]]]],\n",
" 'A21': ['A21',\n",
" ['A211',\n",
" ['A211_file_1', [], 'A211_file_2', []],\n",
" 'A212',\n",
" ['A2121',\n",
" ['A21211',\n",
" ['A21211_file_1', [], 'A21211_file_2', []],\n",
" 'A2121_file_1',\n",
" [],\n",
" 'A2121_file_2',\n",
" []]],\n",
" 'A213',\n",
" ['A2131',\n",
" ['A2131_file_1',\n",
" [],\n",
" 'A21311',\n",
" ['A21311_file_1', [], 'A21311_file_2', []]]]]],\n",
" 'A211': ['A211', ['A211_file_1', [], 'A211_file_2', []]],\n",
" 'A211_file_1': ['A211_file_1', []],\n",
" 'A211_file_2': ['A211_file_2', []],\n",
" 'A212': ['A212',\n",
" ['A2121',\n",
" ['A21211',\n",
" ['A21211_file_1', [], 'A21211_file_2', []],\n",
" 'A2121_file_1',\n",
" [],\n",
" 'A2121_file_2',\n",
" []]]],\n",
" 'A2121': ['A2121',\n",
" ['A21211',\n",
" ['A21211_file_1', [], 'A21211_file_2', []],\n",
" 'A2121_file_1',\n",
" [],\n",
" 'A2121_file_2',\n",
" []]],\n",
" 'A2121_file_1': ['A2121_file_1', []],\n",
" 'A2121_file_2': ['A2121_file_2', []],\n",
" 'A21211': ['A21211', ['A21211_file_1', [], 'A21211_file_2', []]],\n",
" 'A21211_file_1': ['A21211_file_1', []],\n",
" 'A21211_file_2': ['A21211_file_2', []],\n",
" 'A213': ['A213',\n",
" ['A2131',\n",
" ['A2131_file_1',\n",
" [],\n",
" 'A21311',\n",
" ['A21311_file_1', [], 'A21311_file_2', []]]]],\n",
" 'A2131': ['A2131',\n",
" ['A2131_file_1', [], 'A21311', ['A21311_file_1', [], 'A21311_file_2', []]]],\n",
" 'A2131_file_1': ['A2131_file_1', []],\n",
" 'A21311': ['A21311', ['A21311_file_1', [], 'A21311_file_2', []]],\n",
" 'A21311_file_1': ['A21311_file_1', []],\n",
" 'A21311_file_2': ['A21311_file_2', []],\n",
" 'A22': ['A22',\n",
" ['A221',\n",
" ['A221_file_1',\n",
" [],\n",
" 'A2211',\n",
" ['A2211_file_1', [], 'A2211_file_2', []],\n",
" 'A2212',\n",
" ['A2212_file_1', []]]]],\n",
" 'A221': ['A221',\n",
" ['A221_file_1',\n",
" [],\n",
" 'A2211',\n",
" ['A2211_file_1', [], 'A2211_file_2', []],\n",
" 'A2212',\n",
" ['A2212_file_1', []]]],\n",
" 'A221_file_1': ['A221_file_1', []],\n",
" 'A2211': ['A2211', ['A2211_file_1', [], 'A2211_file_2', []]],\n",
" 'A2211_file_1': ['A2211_file_1', []],\n",
" 'A2211_file_2': ['A2211_file_2', []],\n",
" 'A2212': ['A2212', ['A2212_file_1', []]],\n",
" 'A2212_file_1': ['A2212_file_1', []],\n",
" 'A3': ['A3',\n",
" ['A31',\n",
" ['A31_file_1', []],\n",
" 'A32',\n",
" ['A321',\n",
" ['A3211',\n",
" ['A3211_file_1',\n",
" [],\n",
" 'A32111',\n",
" ['A32111_file_1', [], 'A32111_file_2', []]],\n",
" 'A3212',\n",
" ['A3212_file_1',\n",
" [],\n",
" 'A32122',\n",
" ['A32122_file_1', [], 'A32122_file_2', []],\n",
" 'A3212_file_2',\n",
" []],\n",
" 'A3213',\n",
" ['A32131', ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]]]]]],\n",
" 'A31': ['A31', ['A31_file_1', []]],\n",
" 'A31_file_1': ['A31_file_1', []],\n",
" 'A32': ['A32',\n",
" ['A321',\n",
" ['A3211',\n",
" ['A3211_file_1', [], 'A32111', ['A32111_file_1', [], 'A32111_file_2', []]],\n",
" 'A3212',\n",
" ['A3212_file_1',\n",
" [],\n",
" 'A32122',\n",
" ['A32122_file_1', [], 'A32122_file_2', []],\n",
" 'A3212_file_2',\n",
" []],\n",
" 'A3213',\n",
" ['A32131', ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]]]]],\n",
" 'A321': ['A321',\n",
" ['A3211',\n",
" ['A3211_file_1', [], 'A32111', ['A32111_file_1', [], 'A32111_file_2', []]],\n",
" 'A3212',\n",
" ['A3212_file_1',\n",
" [],\n",
" 'A32122',\n",
" ['A32122_file_1', [], 'A32122_file_2', []],\n",
" 'A3212_file_2',\n",
" []],\n",
" 'A3213',\n",
" ['A32131', ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]]]],\n",
" 'A3211': ['A3211',\n",
" ['A3211_file_1', [], 'A32111', ['A32111_file_1', [], 'A32111_file_2', []]]],\n",
" 'A3211_file_1': ['A3211_file_1', []],\n",
" 'A32111': ['A32111', ['A32111_file_1', [], 'A32111_file_2', []]],\n",
" 'A32111_file_1': ['A32111_file_1', []],\n",
" 'A32111_file_2': ['A32111_file_2', []],\n",
" 'A3212': ['A3212',\n",
" ['A3212_file_1',\n",
" [],\n",
" 'A32122',\n",
" ['A32122_file_1', [], 'A32122_file_2', []],\n",
" 'A3212_file_2',\n",
" []]],\n",
" 'A3212_file_1': ['A3212_file_1', []],\n",
" 'A3212_file_2': ['A3212_file_2', []],\n",
" 'A32122': ['A32122', ['A32122_file_1', [], 'A32122_file_2', []]],\n",
" 'A32122_file_1': ['A32122_file_1', []],\n",
" 'A32122_file_2': ['A32122_file_2', []],\n",
" 'A3213': ['A3213',\n",
" ['A32131', ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]]],\n",
" 'A32131': ['A32131',\n",
" ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]]],\n",
" 'A321311': ['A321311', ['A321311_file_1', [], 'A321311_file_2', []]],\n",
" 'A321311_file_1': ['A321311_file_1', []],\n",
" 'A321311_file_2': ['A321311_file_2', []],\n",
" 'A4': ['A4',\n",
" ['A41',\n",
" ['A41_file_1',\n",
" [],\n",
" 'A411',\n",
" ['A4111',\n",
" ['A4111_file_1',\n",
" [],\n",
" 'A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]],\n",
" 'A4112',\n",
" ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]],\n",
" 'A4113',\n",
" ['A4113_file_1', [], 'A41131', ['A41131_file_1', []], 'A4113_file_2', []],\n",
" 'A4114',\n",
" ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A4114_file_1',\n",
" []]]]]],\n",
" 'A41': ['A41',\n",
" ['A41_file_1',\n",
" [],\n",
" 'A411',\n",
" ['A4111',\n",
" ['A4111_file_1',\n",
" [],\n",
" 'A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]],\n",
" 'A4112',\n",
" ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]],\n",
" 'A4113',\n",
" ['A4113_file_1', [], 'A41131', ['A41131_file_1', []], 'A4113_file_2', []],\n",
" 'A4114',\n",
" ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A4114_file_1',\n",
" []]]]],\n",
" 'A41_file_1': ['A41_file_1', []],\n",
" 'A411': ['A411',\n",
" ['A4111',\n",
" ['A4111_file_1',\n",
" [],\n",
" 'A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]],\n",
" 'A4112',\n",
" ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]],\n",
" 'A4113',\n",
" ['A4113_file_1', [], 'A41131', ['A41131_file_1', []], 'A4113_file_2', []],\n",
" 'A4114',\n",
" ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A4114_file_1',\n",
" []]]],\n",
" 'A4111': ['A4111',\n",
" ['A4111_file_1',\n",
" [],\n",
" 'A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]]],\n",
" 'A4111_file_1': ['A4111_file_1', []],\n",
" 'A41111': ['A41111',\n",
" ['A41111_file_1', [], 'A41111_file_2', [], 'A41111_file_3', []]],\n",
" 'A41111_file_1': ['A41111_file_1', []],\n",
" 'A41111_file_2': ['A41111_file_2', []],\n",
" 'A41111_file_3': ['A41111_file_3', []],\n",
" 'A4112': ['A4112', ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]]],\n",
" 'A41121': ['A41121', ['A41121_file_1', [], 'A41121_file_2', []]],\n",
" 'A41121_file_1': ['A41121_file_1', []],\n",
" 'A41121_file_2': ['A41121_file_2', []],\n",
" 'A4113': ['A4113',\n",
" ['A4113_file_1', [], 'A41131', ['A41131_file_1', []], 'A4113_file_2', []]],\n",
" 'A4113_file_1': ['A4113_file_1', []],\n",
" 'A4113_file_2': ['A4113_file_2', []],\n",
" 'A41131': ['A41131', ['A41131_file_1', []]],\n",
" 'A41131_file_1': ['A41131_file_1', []],\n",
" 'A4114': ['A4114',\n",
" ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A4114_file_1',\n",
" []]],\n",
" 'A4114_file_1': ['A4114_file_1', []],\n",
" 'A41141': ['A41141',\n",
" ['A41141_file_1',\n",
" [],\n",
" 'A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]]],\n",
" 'A41141_file_1': ['A41141_file_1', []],\n",
" 'A411411': ['A411411',\n",
" ['A4114111', ['A4114111_file_1', []], 'A411411_file_1', []]],\n",
" 'A411411_file_1': ['A411411_file_1', []],\n",
" 'A4114111': ['A4114111', ['A4114111_file_1', []]],\n",
" 'A4114111_file_1': ['A4114111_file_1', []],\n",
" 'A5': ['A5',\n",
" ['A51',\n",
" ['A511',\n",
" ['A511_file_1', [], 'A511_file_2', []],\n",
" 'A512',\n",
" ['A512_file_1',\n",
" [],\n",
" 'A5121',\n",
" ['A5121_file_1', [], 'A5121_file_2', []],\n",
" 'A512_file_2',\n",
" []],\n",
" 'A513',\n",
" []],\n",
" 'A52',\n",
" ['A521',\n",
" ['A521_file_1',\n",
" [],\n",
" 'A5211',\n",
" ['A5211_file_1', [], 'A5211_file_2', [], 'A5211_file_3', []]]],\n",
" 'A53',\n",
" ['A53_file_1', [], 'A53_file_2', [], 'A53_file_3', []],\n",
" 'A54',\n",
" []]],\n",
" 'A51': ['A51',\n",
" ['A511',\n",
" ['A511_file_1', [], 'A511_file_2', []],\n",
" 'A512',\n",
" ['A512_file_1',\n",
" [],\n",
" 'A5121',\n",
" ['A5121_file_1', [], 'A5121_file_2', []],\n",
" 'A512_file_2',\n",
" []],\n",
" 'A513',\n",
" []]],\n",
" 'A511': ['A511', ['A511_file_1', [], 'A511_file_2', []]],\n",
" 'A511_file_1': ['A511_file_1', []],\n",
" 'A511_file_2': ['A511_file_2', []],\n",
" 'A512': ['A512',\n",
" ['A512_file_1',\n",
" [],\n",
" 'A5121',\n",
" ['A5121_file_1', [], 'A5121_file_2', []],\n",
" 'A512_file_2',\n",
" []]],\n",
" 'A512_file_1': ['A512_file_1', []],\n",
" 'A512_file_2': ['A512_file_2', []],\n",
" 'A5121': ['A5121', ['A5121_file_1', [], 'A5121_file_2', []]],\n",
" 'A5121_file_1': ['A5121_file_1', []],\n",
" 'A5121_file_2': ['A5121_file_2', []],\n",
" 'A513': ['A513', []],\n",
" 'A52': ['A52',\n",
" ['A521',\n",
" ['A521_file_1',\n",
" [],\n",
" 'A5211',\n",
" ['A5211_file_1', [], 'A5211_file_2', [], 'A5211_file_3', []]]]],\n",
" 'A521': ['A521',\n",
" ['A521_file_1',\n",
" [],\n",
" 'A5211',\n",
" ['A5211_file_1', [], 'A5211_file_2', [], 'A5211_file_3', []]]],\n",
" 'A521_file_1': ['A521_file_1', []],\n",
" 'A5211': ['A5211',\n",
" ['A5211_file_1', [], 'A5211_file_2', [], 'A5211_file_3', []]],\n",
" 'A5211_file_1': ['A5211_file_1', []],\n",
" 'A5211_file_2': ['A5211_file_2', []],\n",
" 'A5211_file_3': ['A5211_file_3', []],\n",
" 'A53': ['A53', ['A53_file_1', [], 'A53_file_2', [], 'A53_file_3', []]],\n",
" 'A53_file_1': ['A53_file_1', []],\n",
" 'A53_file_2': ['A53_file_2', []],\n",
" 'A53_file_3': ['A53_file_3', []],\n",
" 'A54': ['A54', []]}"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Nodelist data\n",
"nodelists"
]
},
{
"cell_type": "markdown",
"id": "hydraulic-potter",
"metadata": {},
"source": [
"## Implementation"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "received-eclipse",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Following is Bread-First Traversal\n"
]
},
{
"data": {
"text/plain": [
"['A',\n",
" 'A1',\n",
" 'A2',\n",
" 'A3',\n",
" 'A4',\n",
" 'A5',\n",
" 'A11',\n",
" 'A12',\n",
" 'A13',\n",
" 'A21',\n",
" 'A22',\n",
" 'A31',\n",
" 'A32',\n",
" 'A41',\n",
" 'A51',\n",
" 'A52',\n",
" 'A53',\n",
" 'A54',\n",
" 'A111',\n",
" 'A112',\n",
" 'A121',\n",
" 'A122',\n",
" 'A123',\n",
" 'A13_file_1',\n",
" 'A211',\n",
" 'A212',\n",
" 'A213',\n",
" 'A221',\n",
" 'A31_file_1',\n",
" 'A321',\n",
" 'A411',\n",
" 'A41_file_1',\n",
" 'A511',\n",
" 'A512',\n",
" 'A513',\n",
" 'A521',\n",
" 'A53_file_1',\n",
" 'A53_file_2',\n",
" 'A53_file_3',\n",
" 'A111_file_1',\n",
" 'A112_file_1',\n",
" 'A112_file_2',\n",
" 'A121_file_1',\n",
" 'A1221',\n",
" 'A211_file_1',\n",
" 'A211_file_2',\n",
" 'A2121',\n",
" 'A2131',\n",
" 'A2211',\n",
" 'A2212',\n",
" 'A221_file_1',\n",
" 'A3211',\n",
" 'A3212',\n",
" 'A3213',\n",
" 'A4111',\n",
" 'A4112',\n",
" 'A4113',\n",
" 'A4114',\n",
" 'A511_file_1',\n",
" 'A511_file_2',\n",
" 'A5121',\n",
" 'A512_file_1',\n",
" 'A512_file_2',\n",
" 'A5211',\n",
" 'A521_file_1',\n",
" 'A1221_file_1',\n",
" 'A1221_file_2',\n",
" 'A21211',\n",
" 'A2121_file_1',\n",
" 'A2121_file_2',\n",
" 'A21311',\n",
" 'A2131_file_1',\n",
" 'A2211_file_1',\n",
" 'A2211_file_2',\n",
" 'A2212_file_1',\n",
" 'A32111',\n",
" 'A3211_file_1',\n",
" 'A32122',\n",
" 'A3212_file_1',\n",
" 'A3212_file_2',\n",
" 'A32131',\n",
" 'A41111',\n",
" 'A4111_file_1',\n",
" 'A41121',\n",
" 'A41131',\n",
" 'A4113_file_1',\n",
" 'A4113_file_2',\n",
" 'A41141',\n",
" 'A4114_file_1',\n",
" 'A5121_file_1',\n",
" 'A5121_file_2',\n",
" 'A5211_file_1',\n",
" 'A5211_file_2',\n",
" 'A5211_file_3',\n",
" 'A21211_file_1',\n",
" 'A21211_file_2',\n",
" 'A21311_file_1',\n",
" 'A21311_file_2',\n",
" 'A32111_file_1',\n",
" 'A32111_file_2',\n",
" 'A32122_file_1',\n",
" 'A32122_file_2',\n",
" 'A321311',\n",
" 'A41111_file_1',\n",
" 'A41111_file_2',\n",
" 'A41111_file_3',\n",
" 'A41121_file_1',\n",
" 'A41121_file_2',\n",
" 'A41131_file_1',\n",
" 'A411411',\n",
" 'A41141_file_1',\n",
" 'A321311_file_1',\n",
" 'A321311_file_2',\n",
" 'A4114111',\n",
" 'A411411_file_1',\n",
" 'A4114111_file_1']"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Breadth-First Search\n",
"result_bfs = BreadthFirstSearch(tree_set, 'A')\n",
"print('Following is Bread-First Traversal')\n",
"result_bfs"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "embedded-contractor",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Following is Depth-First Traversal\n"
]
},
{
"data": {
"text/plain": [
"['A',\n",
" 'A1',\n",
" 'A11',\n",
" 'A111',\n",
" 'A111_file_1',\n",
" 'A112',\n",
" 'A112_file_1',\n",
" 'A112_file_2',\n",
" 'A12',\n",
" 'A121',\n",
" 'A121_file_1',\n",
" 'A122',\n",
" 'A1221',\n",
" 'A1221_file_1',\n",
" 'A1221_file_2',\n",
" 'A123',\n",
" 'A13',\n",
" 'A13_file_1',\n",
" 'A2',\n",
" 'A21',\n",
" 'A211',\n",
" 'A211_file_1',\n",
" 'A211_file_2',\n",
" 'A212',\n",
" 'A2121',\n",
" 'A21211',\n",
" 'A21211_file_1',\n",
" 'A21211_file_2',\n",
" 'A2121_file_1',\n",
" 'A2121_file_2',\n",
" 'A213',\n",
" 'A2131',\n",
" 'A21311',\n",
" 'A21311_file_1',\n",
" 'A21311_file_2',\n",
" 'A2131_file_1',\n",
" 'A22',\n",
" 'A221',\n",
" 'A2211',\n",
" 'A2211_file_1',\n",
" 'A2211_file_2',\n",
" 'A2212',\n",
" 'A2212_file_1',\n",
" 'A221_file_1',\n",
" 'A3',\n",
" 'A31',\n",
" 'A31_file_1',\n",
" 'A32',\n",
" 'A321',\n",
" 'A3211',\n",
" 'A32111',\n",
" 'A32111_file_1',\n",
" 'A32111_file_2',\n",
" 'A3211_file_1',\n",
" 'A3212',\n",
" 'A32122',\n",
" 'A32122_file_1',\n",
" 'A32122_file_2',\n",
" 'A3212_file_1',\n",
" 'A3212_file_2',\n",
" 'A3213',\n",
" 'A32131',\n",
" 'A321311',\n",
" 'A321311_file_1',\n",
" 'A321311_file_2',\n",
" 'A4',\n",
" 'A41',\n",
" 'A411',\n",
" 'A4111',\n",
" 'A41111',\n",
" 'A41111_file_1',\n",
" 'A41111_file_2',\n",
" 'A41111_file_3',\n",
" 'A4111_file_1',\n",
" 'A4112',\n",
" 'A41121',\n",
" 'A41121_file_1',\n",
" 'A41121_file_2',\n",
" 'A4113',\n",
" 'A41131',\n",
" 'A41131_file_1',\n",
" 'A4113_file_1',\n",
" 'A4113_file_2',\n",
" 'A4114',\n",
" 'A41141',\n",
" 'A411411',\n",
" 'A4114111',\n",
" 'A4114111_file_1',\n",
" 'A411411_file_1',\n",
" 'A41141_file_1',\n",
" 'A4114_file_1',\n",
" 'A41_file_1',\n",
" 'A5',\n",
" 'A51',\n",
" 'A511',\n",
" 'A511_file_1',\n",
" 'A511_file_2',\n",
" 'A512',\n",
" 'A5121',\n",
" 'A5121_file_1',\n",
" 'A5121_file_2',\n",
" 'A512_file_1',\n",
" 'A512_file_2',\n",
" 'A513',\n",
" 'A52',\n",
" 'A521',\n",
" 'A5211',\n",
" 'A5211_file_1',\n",
" 'A5211_file_2',\n",
" 'A5211_file_3',\n",
" 'A521_file_1',\n",
" 'A53',\n",
" 'A53_file_1',\n",
" 'A53_file_2',\n",
" 'A53_file_3',\n",
" 'A54']"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Depth-First Search\n",
"vertices = []\n",
"visited = set()\n",
"DepthFirstSearch(visited, tree_set, 'A')\n",
"print('Following is Depth-First Traversal')\n",
"vertices"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment