# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="view-in-github" colab_type="text"
# <a href="https://colab.research.google.com/github/lmcanavals/algorithmic_complexity/blob/main/notebooks/al_dfs.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>

# + [markdown] id="95rZbZREmRvE"
# # Depth First Search (DFS)

# + id="SicRUvhEiaes"
# !git clone https://github.com/lmcanavals/algorithmic_complexity.git 2>/dev/null

# + id="ILQdP2LYif2y"
from algorithmic_complexity.aclib import graphstuff as gs
import numpy as np
import networkx as nx

# + colab={"base_uri": "https://localhost:8080/"} id="0Vn6ZpZNhniI" outputId="e4b62845-b6c1-402a-de33-28146a3cb56d"
# %%file 1.adjlist
0 3 4
1 3 5 6
2 4 5 6
3 0 1 7
4 0 2 6
5 1 2 6 7
6 1 2 4 5
7 3 5

# + colab={"base_uri": "https://localhost:8080/", "height": 559} id="cXmVKr8QiVwU" outputId="0a75ba3b-46eb-40e8-a141-faf130e98268"
G = nx.read_adjlist('1.adjlist')
gs.as_gv(G)


# + [markdown] id="RWwrN8jUmZxy"
# ## Recursive implementation with networkx graph

# + id="HynmAreFhoJC"
def _dfs(G, u):
  if not G.nodes[u]['visited']:
    G.nodes[u]['visited'] = True
    for v in G.neighbors(u):
      if not G.nodes[v]['visited']:
        G.nodes[v]['π'] = u
        _dfs(G, v)


def dfs(G, s):
  for u in G.nodes:
    G.nodes[u]['visited'] = False
    G.nodes[u]['π'] = -1
  _dfs(G, s)


# + colab={"base_uri": "https://localhost:8080/", "height": 673} id="j1apoUxqhrqZ" outputId="42748adc-fbe6-490b-f4f2-71cdcc261667"
dfs(G, '5')
path = [0]*G.number_of_nodes()
for v, info in G.nodes.data():
  path[int(v)] = int(info['π'])

print(path)
gs.path2gv(path)


# + [markdown] id="RvkHAhzJmfvh"
# ## Non recursive implementation with networkx graph

# + id="IFM3ooOFiljJ"
def dfsWithStack(G, s):
  for u in G.nodes:
    G.nodes[u]['visited'] = False
    G.nodes[u]['π'] = -1

  stack = [s]
  while stack:
    u = stack.pop()
    if not G.nodes[u]['visited']:
      G.nodes[u]['visited'] = True
      for v in reversed(list(G.neighbors(u))):
        if not G.nodes[v]['visited']:
          G.nodes[v]['π'] = u
          stack.append(v)

  path = [0]*G.number_of_nodes()
  for v, info in G.nodes.data():
    path[int(v)] = int(info['π'])

  return path


# + colab={"base_uri": "https://localhost:8080/", "height": 673} id="sq1Wtmqrj2-k" outputId="c7ed288b-d716-4585-90c4-800fd4351204"
path = dfsWithStack(G, '5')
print(path)
gs.path2gv(path)

StarcoderdataJupyterScriptsDedupFiltered