{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "36912668-210d-419d-a568-af6dd4404869",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Libraries Loaded Successfully\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd\n",
    "\n",
    "print(\"Libraries Loaded Successfully\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "88cc41da-3afa-43c7-9fe5-8ac12f7dc918",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current Working Directory:\n",
      "C:\\Users\\Admin\\Desktop\\My_work\\haplodetox\\DeBruijn\n",
      "\n",
      "Searching for GraphML files...\n",
      "\n",
      "C:\\Users\\Admin\\Desktop\\My_work\\haplodetox\\DeBruijn\\graphs\\pao1_debruijn.graphml\n",
      "C:\\Users\\Admin\\Desktop\\My_work\\haplodetox\\DeBruijn\\graphs\\tb_debruijn.graphml\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "print(\"Current Working Directory:\")\n",
    "print(Path.cwd())\n",
    "\n",
    "print(\"\\nSearching for GraphML files...\\n\")\n",
    "\n",
    "for file in Path.cwd().rglob(\"*.graphml\"):\n",
    "    print(file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9ff91648-1f62-4bd3-9949-8c969d3f0a45",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "============================================================\n",
      "LOADING GRAPH: TB\n",
      "============================================================\n",
      "File: graphs\\tb_debruijn.graphml\n",
      "✓ Graph Loaded Successfully\n",
      "Nodes : 8183728\n",
      "Edges : 8152226\n",
      "\n",
      "============================================================\n",
      "LOADING GRAPH: PAO1\n",
      "============================================================\n",
      "File: graphs\\pao1_debruijn.graphml\n",
      "✓ Graph Loaded Successfully\n",
      "Nodes : 10136309\n",
      "Edges : 10086400\n",
      "\n",
      "ALL GRAPHS LOADED SUCCESSFULLY\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# LOAD DE BRUIJN GRAPHS\n",
    "# ============================================================\n",
    "\n",
    "from pathlib import Path\n",
    "import networkx as nx\n",
    "\n",
    "GRAPH_FILES = {\n",
    "    \"tb\": Path(\"graphs/tb_debruijn.graphml\"),\n",
    "    \"pao1\": Path(\"graphs/pao1_debruijn.graphml\")\n",
    "}\n",
    "\n",
    "graphs = {}\n",
    "\n",
    "for dataset, graph_file in GRAPH_FILES.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*60)\n",
    "    print(\"LOADING GRAPH:\", dataset.upper())\n",
    "    print(\"=\"*60)\n",
    "\n",
    "    print(\"File:\", graph_file)\n",
    "\n",
    "    if graph_file.exists():\n",
    "\n",
    "        G = nx.read_graphml(graph_file)\n",
    "\n",
    "        graphs[dataset] = G\n",
    "\n",
    "        print(\"✓ Graph Loaded Successfully\")\n",
    "        print(\"Nodes :\", G.number_of_nodes())\n",
    "        print(\"Edges :\", G.number_of_edges())\n",
    "\n",
    "    else:\n",
    "\n",
    "        print(\"✗ Graph file not found!\")\n",
    "\n",
    "print(\"\\nALL GRAPHS LOADED SUCCESSFULLY\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f5515f64-c03f-4e60-b629-5cef390ee0e4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "============================================================\n",
      "VERIFYING: TB\n",
      "============================================================\n",
      "Nodes : 8183728\n",
      "Edges : 8152226\n",
      "✓ Node coverage attribute found.\n",
      "Example Node : TTGAGCTTGGCACCAACATC\n",
      "Coverage : 3\n",
      "✓ Edge coverage attribute found.\n",
      "Example Edge : ('TTGAGCTTGGCACCAACATC', 'TGAGCTTGGCACCAACATCG')\n",
      "Coverage : 3\n",
      "Graph verification completed successfully.\n",
      "\n",
      "============================================================\n",
      "VERIFYING: PAO1\n",
      "============================================================\n",
      "Nodes : 10136309\n",
      "Edges : 10086400\n",
      "✓ Node coverage attribute found.\n",
      "Example Node : GTGCGTGACGCCCACCTGGG\n",
      "Coverage : 144\n",
      "✓ Edge coverage attribute found.\n",
      "Example Edge : ('GTGCGTGACGCCCACCTGGG', 'TGCGTGACGCCCACCTGGGG')\n",
      "Coverage : 84\n",
      "Graph verification completed successfully.\n",
      "\n",
      "ALL GRAPHS VERIFIED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# VERIFY LOADED GRAPHS\n",
    "# ============================================================\n",
    "\n",
    "for dataset, G in graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*60)\n",
    "    print(\"VERIFYING:\", dataset.upper())\n",
    "    print(\"=\"*60)\n",
    "\n",
    "    print(\"Nodes :\", G.number_of_nodes())\n",
    "    print(\"Edges :\", G.number_of_edges())\n",
    "\n",
    "    # Check graph is not empty\n",
    "    if G.number_of_nodes() == 0:\n",
    "        print(\"ERROR: Graph has no nodes.\")\n",
    "        continue\n",
    "\n",
    "    if G.number_of_edges() == 0:\n",
    "        print(\"ERROR: Graph has no edges.\")\n",
    "        continue\n",
    "\n",
    "    # Check node coverage\n",
    "    first_node = next(iter(G.nodes()))\n",
    "\n",
    "    if \"coverage\" in G.nodes[first_node]:\n",
    "        print(\"✓ Node coverage attribute found.\")\n",
    "        print(\"Example Node :\", first_node)\n",
    "        print(\"Coverage :\", G.nodes[first_node][\"coverage\"])\n",
    "    else:\n",
    "        print(\"✗ Node coverage attribute missing!\")\n",
    "\n",
    "    # Check edge coverage\n",
    "    first_edge = next(iter(G.edges()))\n",
    "\n",
    "    if \"coverage\" in G.edges[first_edge]:\n",
    "        print(\"✓ Edge coverage attribute found.\")\n",
    "        print(\"Example Edge :\", first_edge)\n",
    "        print(\"Coverage :\", G.edges[first_edge][\"coverage\"])\n",
    "    else:\n",
    "        print(\"✗ Edge coverage attribute missing!\")\n",
    "\n",
    "    print(\"Graph verification completed successfully.\")\n",
    "\n",
    "print(\"\\nALL GRAPHS VERIFIED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4d2c8e42-b6c2-4a03-9708-6ba6b79ee30a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "IDENTIFYING TIPS : TB\n",
      "======================================================================\n",
      "Total Tip Nodes : 80652\n",
      "First 5 Tip Nodes:\n",
      "TTGAGCTTGGCACCAACATC\n",
      "CGCCACCAGGTTGGGACGGA\n",
      "TCATCGGCAACCGCACGACA\n",
      "AACACCGTGCCTGGCAGCTT\n",
      "TGTCCGCGGCCGATACCGGG\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "IDENTIFYING TIPS : PAO1\n",
      "======================================================================\n",
      "Total Tip Nodes : 138883\n",
      "First 5 Tip Nodes:\n",
      "ATGCTCGGCAAGGTCTACGC\n",
      "CCGCTCGCCCAGCCACAGGG\n",
      "GCGACGATGCCCATCAGCGA\n",
      "GTCATCGGTGACATGGCCGG\n",
      "ACCGGTGCCGCCAGCATCCG\n",
      "SUCCESS\n",
      "\n",
      "TIP DETECTION COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# IDENTIFY TIP NODES\n",
    "# ============================================================\n",
    "\n",
    "tip_nodes = {}\n",
    "\n",
    "for dataset, G in graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"IDENTIFYING TIPS : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    tips = []\n",
    "\n",
    "    for node in G.nodes():\n",
    "\n",
    "        indeg = G.in_degree(node)\n",
    "        outdeg = G.out_degree(node)\n",
    "\n",
    "        # Start tip\n",
    "        if indeg == 0 and outdeg == 1:\n",
    "            tips.append(node)\n",
    "\n",
    "        # End tip\n",
    "        elif indeg == 1 and outdeg == 0:\n",
    "            tips.append(node)\n",
    "\n",
    "    tip_nodes[dataset] = tips\n",
    "\n",
    "    print(\"Total Tip Nodes :\", len(tips))\n",
    "\n",
    "    if len(tips) > 0:\n",
    "        print(\"First 5 Tip Nodes:\")\n",
    "        for tip in tips[:5]:\n",
    "            print(tip)\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nTIP DETECTION COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "efe56246-f665-4777-a6a7-c5711d8c9463",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "MEASURING TIP LENGTHS : TB\n",
      "======================================================================\n",
      "Total Tips: 80652\n",
      "Shortest Tip: 2\n",
      "Longest Tip : 2678\n",
      "Average Tip Length: 174.93\n",
      "\n",
      "======================================================================\n",
      "MEASURING TIP LENGTHS : PAO1\n",
      "======================================================================\n",
      "Total Tips: 138883\n",
      "Shortest Tip: 2\n",
      "Longest Tip : 314\n",
      "Average Tip Length: 116.27\n",
      "\n",
      "TIP LENGTH ANALYSIS COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# MEASURE TIP LENGTHS\n",
    "# ============================================================\n",
    "\n",
    "tip_paths = {}\n",
    "\n",
    "for dataset, G in graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"MEASURING TIP LENGTHS : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    paths = []\n",
    "\n",
    "    for tip in tip_nodes[dataset]:\n",
    "\n",
    "        path = [tip]\n",
    "        current = tip\n",
    "\n",
    "        # Forward tip\n",
    "        if G.out_degree(current) == 1:\n",
    "\n",
    "            while True:\n",
    "\n",
    "                nxt = list(G.successors(current))[0]\n",
    "\n",
    "                if G.in_degree(nxt) != 1 or G.out_degree(nxt) != 1:\n",
    "                    path.append(nxt)\n",
    "                    break\n",
    "\n",
    "                path.append(nxt)\n",
    "                current = nxt\n",
    "\n",
    "        # Backward tip\n",
    "        elif G.in_degree(current) == 1:\n",
    "\n",
    "            while True:\n",
    "\n",
    "                prev = list(G.predecessors(current))[0]\n",
    "\n",
    "                if G.in_degree(prev) != 1 or G.out_degree(prev) != 1:\n",
    "                    path.append(prev)\n",
    "                    break\n",
    "\n",
    "                path.append(prev)\n",
    "                current = prev\n",
    "\n",
    "        paths.append(path)\n",
    "\n",
    "    tip_paths[dataset] = paths\n",
    "\n",
    "    lengths = [len(p) for p in paths]\n",
    "\n",
    "    print(\"Total Tips:\", len(paths))\n",
    "    print(\"Shortest Tip:\", min(lengths))\n",
    "    print(\"Longest Tip :\", max(lengths))\n",
    "    print(\"Average Tip Length:\", round(sum(lengths) / len(lengths), 2))\n",
    "\n",
    "print(\"\\nTIP LENGTH ANALYSIS COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "652cc008-560b-45c5-946a-60825bd44e92",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "K-mer Size: 21\n",
      "Tip Length Threshold: 42\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# PARAMETERS\n",
    "# ============================================================\n",
    "\n",
    "K = 21\n",
    "TIP_THRESHOLD = 2 * K\n",
    "\n",
    "print(\"K-mer Size:\", K)\n",
    "print(\"Tip Length Threshold:\", TIP_THRESHOLD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ccbdca2f-fe7d-4b03-9489-bab473f88218",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "REMOVING SHORT TIPS : TB\n",
      "======================================================================\n",
      "Short Tips Removed : 15688\n",
      "Nodes To Remove    : 118072\n",
      "Remaining Nodes : 8065656\n",
      "Remaining Edges : 8040383\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "REMOVING SHORT TIPS : PAO1\n",
      "======================================================================\n",
      "Short Tips Removed : 23638\n",
      "Nodes To Remove    : 347719\n",
      "Remaining Nodes : 9788590\n",
      "Remaining Edges : 9741335\n",
      "SUCCESS\n",
      "\n",
      "SHORT TIP REMOVAL COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# REMOVE SHORT TIPS\n",
    "# ============================================================\n",
    "\n",
    "TIP_THRESHOLD = 2 * K\n",
    "\n",
    "clean_graphs = {}\n",
    "\n",
    "for dataset, G in graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"REMOVING SHORT TIPS : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    G_clean = G.copy()\n",
    "\n",
    "    nodes_to_remove = set()\n",
    "\n",
    "    removed_tips = 0\n",
    "\n",
    "    for path in tip_paths[dataset]:\n",
    "\n",
    "        if len(path) <= TIP_THRESHOLD:\n",
    "\n",
    "            removed_tips += 1\n",
    "\n",
    "            for node in path[:-1]:\n",
    "                nodes_to_remove.add(node)\n",
    "\n",
    "    print(\"Short Tips Removed :\", removed_tips)\n",
    "    print(\"Nodes To Remove    :\", len(nodes_to_remove))\n",
    "\n",
    "    G_clean.remove_nodes_from(nodes_to_remove)\n",
    "\n",
    "    clean_graphs[dataset] = G_clean\n",
    "\n",
    "    print(\"Remaining Nodes :\", G_clean.number_of_nodes())\n",
    "    print(\"Remaining Edges :\", G_clean.number_of_edges())\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nSHORT TIP REMOVAL COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "0521f23c-54f5-4ddd-8563-11851a506266",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "REMOVING ISOLATED NODES : TB\n",
      "======================================================================\n",
      "Isolated Nodes Found : 2\n",
      "Remaining Nodes : 8065654\n",
      "Remaining Edges : 8040383\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "REMOVING ISOLATED NODES : PAO1\n",
      "======================================================================\n",
      "Isolated Nodes Found : 0\n",
      "Remaining Nodes : 9788590\n",
      "Remaining Edges : 9741335\n",
      "SUCCESS\n",
      "\n",
      "ISOLATED NODE REMOVAL COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# REMOVE ISOLATED NODES\n",
    "# ============================================================\n",
    "\n",
    "for dataset, G in clean_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"REMOVING ISOLATED NODES : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    isolated_nodes = [\n",
    "        node for node in G.nodes()\n",
    "        if G.in_degree(node) == 0 and G.out_degree(node) == 0\n",
    "    ]\n",
    "\n",
    "    print(\"Isolated Nodes Found :\", len(isolated_nodes))\n",
    "\n",
    "    G.remove_nodes_from(isolated_nodes)\n",
    "\n",
    "    print(\"Remaining Nodes :\", G.number_of_nodes())\n",
    "    print(\"Remaining Edges :\", G.number_of_edges())\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nISOLATED NODE REMOVAL COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "5a16b7a2-7add-43c3-9017-62090fce4549",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "FINDING BRANCHING NODES : TB\n",
      "======================================================================\n",
      "Branch Nodes Found : 11272\n",
      "\n",
      "Example Branch Nodes:\n",
      "AGCCCGCCAGCGCCACCGGC\n",
      "GCCACCGGCTCCGAACAGCC\n",
      "CACCGGCTCCGAACAGCCCG\n",
      "CCGAACAGCCCGCCGGCCCC\n",
      "CGAACAGCCCGCCGGCCCCA\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "FINDING BRANCHING NODES : PAO1\n",
      "======================================================================\n",
      "Branch Nodes Found : 25561\n",
      "\n",
      "Example Branch Nodes:\n",
      "CAGGTCCAGGGCCTGGGCGG\n",
      "GATCGGCTTGCCGTAATAGA\n",
      "GATCCAGAAGCTGGTGGACA\n",
      "GGTCAGCCAGGTCTTCGTCC\n",
      "GACGGCCAGCCGCTGCTGGC\n",
      "SUCCESS\n",
      "\n",
      "BRANCH DETECTION COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# FIND BRANCHING NODES\n",
    "# ============================================================\n",
    "\n",
    "branch_nodes = {}\n",
    "\n",
    "for dataset, G in clean_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"FINDING BRANCHING NODES : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    branches = []\n",
    "\n",
    "    for node in G.nodes():\n",
    "\n",
    "        if G.out_degree(node) > 1 or G.in_degree(node) > 1:\n",
    "\n",
    "            branches.append(node)\n",
    "\n",
    "    branch_nodes[dataset] = branches\n",
    "\n",
    "    print(\"Branch Nodes Found :\", len(branches))\n",
    "\n",
    "    if len(branches) > 0:\n",
    "\n",
    "        print(\"\\nExample Branch Nodes:\")\n",
    "\n",
    "        for node in branches[:5]:\n",
    "\n",
    "            print(node)\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nBRANCH DETECTION COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "846f8d09-8879-408b-851e-54d2e9e98a5a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "IDENTIFYING WEAK BRANCHES : TB\n",
      "======================================================================\n",
      "Weak Branches Found : 152\n",
      "\n",
      "First 5 Weak Branches:\n",
      "('TGCCGCCGTTGCCGCCGTTG', 'GCCGCCGTTGCCGCCGTTGA', 15, 318)\n",
      "('CCGCCGTTGCCGCCGTTGCC', 'CGCCGTTGCCGCCGTTGCCA', 22, 464)\n",
      "('CCGCCGTTGCCGCCGTTGCC', 'CGCCGTTGCCGCCGTTGCCT', 24, 464)\n",
      "('CCGCCGGCCCCGCCGGCCCC', 'CGCCGGCCCCGCCGGCCCCC', 20, 245)\n",
      "('CCGCCGGCCCCGCCGGCCCC', 'CGCCGGCCCCGCCGGCCCCT', 5, 245)\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "IDENTIFYING WEAK BRANCHES : PAO1\n",
      "======================================================================\n",
      "Weak Branches Found : 8229\n",
      "\n",
      "First 5 Weak Branches:\n",
      "('GATCCAGAAGCTGGTGGACA', 'ATCCAGAAGCTGGTGGACAC', 3, 183)\n",
      "('GCCAGCGTTCATCGCCTGCT', 'CCAGCGTTCATCGCCTGCTG', 3, 168)\n",
      "('CCGTCGCGGTCGAGGTGGTC', 'CGTCGCGGTCGAGGTGGTCT', 4, 179)\n",
      "('GCCGCAGCAGGTCGGCCAGG', 'CCGCAGCAGGTCGGCCAGGG', 3, 218)\n",
      "('CTGCGGTCTCGACGAGGCCA', 'TGCGGTCTCGACGAGGCCAC', 3, 174)\n",
      "SUCCESS\n",
      "\n",
      "WEAK BRANCH DETECTION COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# IDENTIFY LOW-COVERAGE BRANCHES\n",
    "# ============================================================\n",
    "\n",
    "BRANCH_RATIO = 0.10      # 10% of the strongest branch\n",
    "\n",
    "weak_edges = {}\n",
    "\n",
    "for dataset, G in clean_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"IDENTIFYING WEAK BRANCHES : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    edges_to_remove = []\n",
    "\n",
    "    for node in branch_nodes[dataset]:\n",
    "\n",
    "        successors = list(G.successors(node))\n",
    "\n",
    "        if len(successors) < 2:\n",
    "            continue\n",
    "\n",
    "        edge_cov = []\n",
    "\n",
    "        for s in successors:\n",
    "\n",
    "            cov = int(G.edges[node, s][\"coverage\"])\n",
    "            edge_cov.append((s, cov))\n",
    "\n",
    "        max_cov = max(c for _, c in edge_cov)\n",
    "\n",
    "        for s, cov in edge_cov:\n",
    "\n",
    "            if cov < BRANCH_RATIO * max_cov:\n",
    "\n",
    "                edges_to_remove.append((node, s, cov, max_cov))\n",
    "\n",
    "    weak_edges[dataset] = edges_to_remove\n",
    "\n",
    "    print(\"Weak Branches Found :\", len(edges_to_remove))\n",
    "\n",
    "    if edges_to_remove:\n",
    "        print(\"\\nFirst 5 Weak Branches:\")\n",
    "        for e in edges_to_remove[:5]:\n",
    "            print(e)\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nWEAK BRANCH DETECTION COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e042313e-c92c-4b0f-b5bf-07c8b45dd9c6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "REMOVING WEAK BRANCHES : TB\n",
      "======================================================================\n",
      "Edges Removed : 152\n",
      "Remaining Nodes : 8065654\n",
      "Remaining Edges : 8040231\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "REMOVING WEAK BRANCHES : PAO1\n",
      "======================================================================\n",
      "Edges Removed : 8229\n",
      "Remaining Nodes : 9788590\n",
      "Remaining Edges : 9733106\n",
      "SUCCESS\n",
      "\n",
      "WEAK BRANCH REMOVAL COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# REMOVE WEAK BRANCHES\n",
    "# ============================================================\n",
    "\n",
    "pruned_graphs = {}\n",
    "\n",
    "for dataset, G in clean_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"REMOVING WEAK BRANCHES : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    G_pruned = G.copy()\n",
    "\n",
    "    removed = 0\n",
    "\n",
    "    for edge in weak_edges[dataset]:\n",
    "\n",
    "        u, v, _, _ = edge\n",
    "\n",
    "        if G_pruned.has_edge(u, v):\n",
    "\n",
    "            G_pruned.remove_edge(u, v)\n",
    "            removed += 1\n",
    "\n",
    "    pruned_graphs[dataset] = G_pruned\n",
    "\n",
    "    print(\"Edges Removed :\", removed)\n",
    "    print(\"Remaining Nodes :\", G_pruned.number_of_nodes())\n",
    "    print(\"Remaining Edges :\", G_pruned.number_of_edges())\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nWEAK BRANCH REMOVAL COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "17d0f751-e315-4c44-9911-0ab94b3c0dbf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "DETECTING BUBBLE STARTS : TB\n",
      "======================================================================\n",
      "Candidate Bubble Starts : 6557\n",
      "\n",
      "First 5 Bubble Starts:\n",
      "AGCCCGCCAGCGCCACCGGC\n",
      "CACCGGCTCCGAACAGCCCG\n",
      "CCGAACAGCCCGCCGGCCCC\n",
      "AACAGCCCGCCGGCCCCACC\n",
      "CGGCCCCACCCGTCCCACCA\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "DETECTING BUBBLE STARTS : PAO1\n",
      "======================================================================\n",
      "Candidate Bubble Starts : 5222\n",
      "\n",
      "First 5 Bubble Starts:\n",
      "GATCGGCTTGCCGTAATAGA\n",
      "GACGGCCAGCCGCTGCTGGC\n",
      "GCGCTGTTGGCGGCGCTGGC\n",
      "TCGACTATCACCTCGACGAC\n",
      "GCAGCACCACCAACGGCAAG\n",
      "SUCCESS\n",
      "\n",
      "BUBBLE START DETECTION COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# DETECT CANDIDATE BUBBLE START NODES\n",
    "# ============================================================\n",
    "\n",
    "bubble_starts = {}\n",
    "\n",
    "for dataset, G in pruned_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"DETECTING BUBBLE STARTS : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    starts = []\n",
    "\n",
    "    for node in G.nodes():\n",
    "\n",
    "        if G.out_degree(node) > 1:\n",
    "            starts.append(node)\n",
    "\n",
    "    bubble_starts[dataset] = starts\n",
    "\n",
    "    print(\"Candidate Bubble Starts :\", len(starts))\n",
    "\n",
    "    if len(starts) > 0:\n",
    "        print(\"\\nFirst 5 Bubble Starts:\")\n",
    "        for node in starts[:5]:\n",
    "            print(node)\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nBUBBLE START DETECTION COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "6456933b-b961-4d67-ae71-eca8683fa224",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum Bubble Length: 100\n",
      "Bubble detection function created successfully.\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# BUBBLE DETECTION FUNCTION\n",
    "# ============================================================\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "MAX_BUBBLE_LENGTH = 100\n",
    "\n",
    "print(\"Maximum Bubble Length:\", MAX_BUBBLE_LENGTH)\n",
    "\n",
    "\n",
    "def detect_bubbles(G, bubble_starts, max_length=100):\n",
    "\n",
    "    bubbles = []\n",
    "\n",
    "    for start in bubble_starts:\n",
    "\n",
    "        successors = list(G.successors(start))\n",
    "\n",
    "        # Only handle simple 2-way bubbles\n",
    "        if len(successors) != 2:\n",
    "            continue\n",
    "\n",
    "        s1, s2 = successors\n",
    "\n",
    "        visited1 = {s1: [start, s1]}\n",
    "        visited2 = {s2: [start, s2]}\n",
    "\n",
    "        q1 = deque([(s1, 1)])\n",
    "        q2 = deque([(s2, 1)])\n",
    "\n",
    "        bubble_found = False\n",
    "\n",
    "        while q1 and q2 and not bubble_found:\n",
    "\n",
    "            # -------- Expand branch 1 --------\n",
    "            node1, depth1 = q1.popleft()\n",
    "\n",
    "            if depth1 < max_length:\n",
    "\n",
    "                for nxt in G.successors(node1):\n",
    "\n",
    "                    if nxt not in visited1:\n",
    "\n",
    "                        visited1[nxt] = visited1[node1] + [nxt]\n",
    "                        q1.append((nxt, depth1 + 1))\n",
    "\n",
    "                        if nxt in visited2:\n",
    "\n",
    "                            bubbles.append({\n",
    "                                \"start\": start,\n",
    "                                \"end\": nxt,\n",
    "                                \"path1\": visited1[nxt],\n",
    "                                \"path2\": visited2[nxt]\n",
    "                            })\n",
    "\n",
    "                            bubble_found = True\n",
    "                            break\n",
    "\n",
    "            if bubble_found:\n",
    "                break\n",
    "\n",
    "            # -------- Expand branch 2 --------\n",
    "            node2, depth2 = q2.popleft()\n",
    "\n",
    "            if depth2 < max_length:\n",
    "\n",
    "                for nxt in G.successors(node2):\n",
    "\n",
    "                    if nxt not in visited2:\n",
    "\n",
    "                        visited2[nxt] = visited2[node2] + [nxt]\n",
    "                        q2.append((nxt, depth2 + 1))\n",
    "\n",
    "                        if nxt in visited1:\n",
    "\n",
    "                            bubbles.append({\n",
    "                                \"start\": start,\n",
    "                                \"end\": nxt,\n",
    "                                \"path1\": visited1[nxt],\n",
    "                                \"path2\": visited2[nxt]\n",
    "                            })\n",
    "\n",
    "                            bubble_found = True\n",
    "                            break\n",
    "\n",
    "    return bubbles\n",
    "\n",
    "\n",
    "print(\"Bubble detection function created successfully.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "d137e6e3-8edc-474b-b0af-15fd8861ac1b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "DETECTING BUBBLES : TB\n",
      "======================================================================\n",
      "Total Bubbles Found : 3260\n",
      "\n",
      "Example Bubble\n",
      "Start : AGCCCGCCAGCGCCACCGGC\n",
      "End   : CCGGCCCCACCGGCGCCGCC\n",
      "Path 1 Length : 34\n",
      "Path 2 Length : 16\n",
      "SUCCESS\n",
      "\n",
      "======================================================================\n",
      "DETECTING BUBBLES : PAO1\n",
      "======================================================================\n",
      "Total Bubbles Found : 915\n",
      "\n",
      "Example Bubble\n",
      "Start : CTTGCTCATCAGACACCTCT\n",
      "End   : TCGCCTAAATCGGTGTCCGG\n",
      "Path 1 Length : 37\n",
      "Path 2 Length : 37\n",
      "SUCCESS\n",
      "\n",
      "BUBBLE DETECTION COMPLETED\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# RUN BUBBLE DETECTION\n",
    "# ============================================================\n",
    "\n",
    "all_bubbles = {}\n",
    "\n",
    "for dataset, G in pruned_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"DETECTING BUBBLES : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    bubbles = detect_bubbles(\n",
    "        G,\n",
    "        bubble_starts[dataset],\n",
    "        max_length=MAX_BUBBLE_LENGTH\n",
    "    )\n",
    "\n",
    "    all_bubbles[dataset] = bubbles\n",
    "\n",
    "    print(\"Total Bubbles Found :\", len(bubbles))\n",
    "\n",
    "    if len(bubbles) > 0:\n",
    "\n",
    "        print(\"\\nExample Bubble\")\n",
    "\n",
    "        print(\"Start :\", bubbles[0][\"start\"])\n",
    "        print(\"End   :\", bubbles[0][\"end\"])\n",
    "\n",
    "        print(\"Path 1 Length :\", len(bubbles[0][\"path1\"]))\n",
    "        print(\"Path 2 Length :\", len(bubbles[0][\"path2\"]))\n",
    "\n",
    "    print(\"SUCCESS\")\n",
    "\n",
    "print(\"\\nBUBBLE DETECTION COMPLETED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "2781e965-aa38-48f8-b6b3-931a32169e76",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "======================================================================\n",
      "SAVING FINAL GRAPH : TB\n",
      "======================================================================\n",
      "Saved Successfully:\n",
      "final_graphs\\tb_final_cleaned.graphml\n",
      "Nodes : 8065654\n",
      "Edges : 8040231\n",
      "\n",
      "======================================================================\n",
      "SAVING FINAL GRAPH : PAO1\n",
      "======================================================================\n",
      "Saved Successfully:\n",
      "final_graphs\\pao1_final_cleaned.graphml\n",
      "Nodes : 9788590\n",
      "Edges : 9733106\n",
      "\n",
      "ALL FINAL GRAPHS SAVED SUCCESSFULLY\n"
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "# SAVE FINAL CLEANED GRAPH\n",
    "# ============================================================\n",
    "\n",
    "from pathlib import Path\n",
    "import networkx as nx\n",
    "\n",
    "SAVE_DIR = Path(\"final_graphs\")\n",
    "SAVE_DIR.mkdir(exist_ok=True)\n",
    "\n",
    "for dataset, G in pruned_graphs.items():\n",
    "\n",
    "    print(\"\\n\" + \"=\"*70)\n",
    "    print(f\"SAVING FINAL GRAPH : {dataset.upper()}\")\n",
    "    print(\"=\"*70)\n",
    "\n",
    "    output_file = SAVE_DIR / f\"{dataset}_final_cleaned.graphml\"\n",
    "\n",
    "    nx.write_graphml(G, output_file)\n",
    "\n",
    "    print(\"Saved Successfully:\")\n",
    "    print(output_file)\n",
    "\n",
    "    print(\"Nodes :\", G.number_of_nodes())\n",
    "    print(\"Edges :\", G.number_of_edges())\n",
    "\n",
    "print(\"\\nALL FINAL GRAPHS SAVED SUCCESSFULLY\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "223b2829-b613-4bcb-98d2-5c28ee3be7c1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (torch-gpu)",
   "language": "python",
   "name": "torch-gpu"
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}