import pandas as pd
import networkx as nx

# -----------------------------
# Read graph from CSV
# -----------------------------
df = pd.read_csv("graph.csv")

G = nx.Graph()
for _, row in df.iterrows():
    G.add_edge(row["source"], row["target"], weight=row["weight"])



# -----------------------------
# BFS
# -----------------------------
print("BFS Path:", nx.shortest_path(G, "A", "D"))
print("BFS Traversal:", list(nx.bfs_tree(G, "A").nodes()))
print("-" * 40)

# -----------------------------
# DFS
# -----------------------------
print("DFS Traversal:", list(nx.dfs_preorder_nodes(G, "A")))

dfs_path = []

def dfs_path_finder(graph, current, target, visited):
    visited.add(current)
    dfs_path.append(current)

    if current == target:
        return True

    for neighbor in graph.neighbors(current):
        if neighbor not in visited:
            if dfs_path_finder(graph, neighbor, target, visited):
                return True

    dfs_path.pop()
    return False

visited = set()
dfs_path_finder(G, "A", "D", visited)

print("DFS Path:", dfs_path)
print("-" * 40)

# -----------------------------
# Best-First Search (Greedy)
# -----------------------------
heuristic = {"A": 3, "B": 2, "C": 1, "D": 0}

best_first = nx.astar_path(
    G, "A", "D",
    heuristic=lambda u, v: heuristic[u],
    weight=None
)

print("Best-First Path:", best_first)
print("-" * 40)

# -----------------------------
# A* Search
# -----------------------------
astar = nx.astar_path(
    G, "A", "D",
    heuristic=lambda u, v: heuristic[u],
    weight="weight"
)

print("A* Path:", astar)
print("-" * 40)


source,target,weight
A,B,1
A,C,4
B,C,2
B,D,5
C,D,1
