Repository: roedoejet/g2p

Issue:
RAM usage: replace networkx elements used by the web API server
g2p is used on the ReadAlong Studio back-end server, and causes a fairly high amount of RAM to get used.

 - importing `networkx` (any subpart of it, even just the top-level import) costs about 30MB
 - importing the languages database costs about 60MB, 40 or 50 of which is likely the English lexicon (see #395)

If we can rewrite the tiny part of `networkx` we use ourselves, or maybe use `networkx` in general except for the parts `readalongs/web_api.py` needs, that would be nice -- basically `g2p update` would use `networkx` but `make_g2p` and loading the langs database would not. The algorithms we use from networkx are quite simple, after all:
 - [ ] has path
 - [ ] shortest path
 - [ ] ancestors
 - [ ] descendants

Given the simplicity of the g2p language DAG, we don't need full Dijkstra, implementing `has_path(src, tgt)` as `tgt in descendants(src)` would not likely have any performance cost, and there are so few cases where the is more than one path between two nodes, implementing `shortest_path(src,tgt)` with a simple BFS from src would be unlikely to be more expensive than a real Dijkstra implementation.


Discussion:
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/roedoejet/g2p/pull/397?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine) Report
Attention: Patch coverage is `93.65079%` with `8 lines` in your changes missing coverage. Please review.
> Project coverage is 93.15%. Comparing base [(`d48a7a9`)](https://app.codecov.io/gh/roedoejet/g2p/commit/d48a7a9a920cf9466be374248fa9b24dc911e0e3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine) to head [(`b10f22e`)](https://app.codecov.io/gh/roedoejet/g2p/commit/b10f22ec0921fa647d3eac29c66949a590e619b1?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine).

| [Files with missing lines](https://app.codecov.io/gh/roedoejet/g2p/pull/397?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine) | Patch % | Lines |
|---|---|---|
| [g2p/mappings/langs/network\_lite.py](https://app.codecov.io/gh/roedoejet/g2p/pull/397?src=pr&el=tree&filepath=g2p%2Fmappings%2Flangs%2Fnetwork_lite.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine#diff-ZzJwL21hcHBpbmdzL2xhbmdzL25ldHdvcmtfbGl0ZS5weQ==) | 92.15% | [4 Missing and 4 partials :warning: ](https://app.codecov.io/gh/roedoejet/g2p/pull/397?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main     #397      +/-   ##
==========================================
- Coverage   93.22%   93.15%   -0.08%     
==========================================
  Files          17       18       +1     
  Lines        2450     2541      +91     
  Branches      547      576      +29     
==========================================
+ Hits         2284     2367      +83     
- Misses         95       99       +4     
- Partials       71       75       +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/roedoejet/g2p/pull/397?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Aidan+Pine).

joanise: > Great! I have various small changes mostly related to type annotations... should I just add them in a commit?

I'll do them as a learning exercise, you're suggesting things I was not familiar with.
joanise: > I'll do them as a learning exercise, you're suggesting things I was not familiar with.

Never mind, you said in another channel you've started doing the changes, so go for it.

Thanks for the review, it's very helpful!
dhdaines: > > I'll do them as a learning exercise, you're suggesting things I was not familiar with.
> 
> Never mind, you said in another channel you've started doing the changes, so go for it.
> 
> Thanks for the review, it's very helpful!

Okay! It's done here, with generics, etc:   #398 

Patch:
diff --git a/g2p/__init__.py b/g2p/__init__.py
index 38cfdcd..d4513d5 100644
--- a/g2p/__init__.py
+++ b/g2p/__init__.py
@@ -70,9 +70,6 @@ def make_g2p(  # noqa: C901
         NoPath: if there is path between in_lang and out_lang
     """
     # Defer expensive imports
-    from networkx import shortest_path  # type: ignore
-    from networkx.exception import NetworkXNoPath  # type: ignore
-
     from g2p.log import LOGGER
     from g2p.mappings import Mapping
     from g2p.mappings.langs import LANGS_NETWORK
@@ -100,13 +97,13 @@ def make_g2p(  # noqa: C901
 
     # Try to find the shortest path between the nodes
     try:
-        path = shortest_path(LANGS_NETWORK, in_lang, out_lang)
-    except NetworkXNoPath as e:
+        path = LANGS_NETWORK.shortest_path(in_lang, out_lang)
+    except ValueError:
         LOGGER.error(
             f"Sorry, we couldn't find a way to convert {in_lang} to {out_lang}. "
             "Please update your langs by running `g2p update` and try again."
         )
-        raise NoPath(in_lang, out_lang) from e
+        raise NoPath(in_lang, out_lang)
 
     # Find all mappings needed
     mappings_needed = []
@@ -162,8 +159,6 @@ def get_arpabet_langs():
             LANG_NAMES maps each code to its full language name and is ordered by codes
     """
     # Defer expensive imports
-    from networkx import has_path
-
     from g2p.mappings import LANGS
     from g2p.mappings.langs import LANGS_NETWORK
 
@@ -203,8 +198,8 @@ def get_arpabet_langs():
             and not x.endswith("-equiv")
             and not x.endswith("-no-symbols")
             and x not in ["und-ascii", "moh-festival"]
-            and LANGS_NETWORK.has_node(x)
-            and has_path(LANGS_NETWORK, x, "eng-arpabet")
+            and x in LANGS_NETWORK
+            and LANGS_NETWORK.has_path(x, "eng-arpabet")
         ]
 
         # Sort LANGS so the -h messages list them alphabetically
diff --git a/g2p/api.py b/g2p/api.py
index 3a4c43d..4f35589 100644
--- a/g2p/api.py
+++ b/g2p/api.py
@@ -6,7 +6,6 @@ from typing import List
 from fastapi import FastAPI, HTTPException, Path, Query
 from fastapi.exceptions import RequestValidationError
 from fastapi.responses import JSONResponse, PlainTextResponse
-from networkx.algorithms.dag import ancestors, descendants  # type: ignore
 
 from g2p import make_g2p
 from g2p.exceptions import NoPath
@@ -71,7 +70,7 @@ def get_all_ancestors_of_node(
     """Get the valid ancestors in the network's path to a given node. These
     are all the mappings that you can convert from in order to get the
     given node."""
-    return sorted(ancestors(LANGS_NETWORK, node.name))
+    return sorted(LANGS_NETWORK.ancestors(node.name))
 
 
 @api.get(
@@ -84,7 +83,7 @@ def get_all_ancestors_of_node(
 def get_all_descendants_of_node(
     node: Lang = Path(description="language node name"),
 ) -> List[str]:
-    return sorted(descendants(LANGS_NETWORK, node.name))
+    return sorted(LANGS_NETWORK.descendants(node.name))
 
 
 @api.get(
diff --git a/g2p/api_v2.py b/g2p/api_v2.py
index 9b2e339..5e7165e 100644
--- a/g2p/api_v2.py
+++ b/g2p/api_v2.py
@@ -32,9 +32,6 @@ from typing import Dict, List, Tuple, Union
 
 from fastapi import Body, FastAPI, HTTPException, Path
 from fastapi.middleware.cors import CORSMiddleware
-from networkx import shortest_path  # type: ignore
-from networkx.algorithms.dag import ancestors, descendants  # type: ignore
-from networkx.exception import NetworkXNoPath  # type: ignore
 from pydantic import BaseModel, Field
 
 import g2p
@@ -385,7 +382,7 @@ def get_possible_output_conversions_for_a_writing_system(
     are all the phonetic or orthographic systems into which you can convert
     this input.
     """
-    return sorted(descendants(g2p_langs.LANGS_NETWORK, lang.name))
+    return sorted(g2p_langs.LANGS_NETWORK.descendants(lang.name))
 
 
 @api.get(
@@ -399,7 +396,7 @@ def get_writing_systems_that_can_be_converted_to_an_output(
     are all the phonetic or orthographic systems that you can convert
     into this output.
     """
-    return sorted(ancestors(g2p_langs.LANGS_NETWORK, lang.name))
+    return sorted(g2p_langs.LANGS_NETWORK.ancestors(lang.name))
 
 
 @api.get(
@@ -412,8 +409,8 @@ def get_path_from_one_language_to_another(
 ) -> List[str]:
     """Get the sequence of intermediate forms used to convert from {in_lang} to {out_lang}."""
     try:
-        return shortest_path(g2p_langs.LANGS_NETWORK, in_lang.name, out_lang.name)
-    except NetworkXNoPath:
+        return g2p_langs.LANGS_NETWORK.shortest_path(in_lang.name, out_lang.name)
+    except ValueError:
         raise HTTPException(
             status_code=400, detail=f"No path from {in_lang} to {out_lang}"
         )
diff --git a/g2p/app.py b/g2p/app.py
index 3baaac8..7c75d39 100644
--- a/g2p/app.py
+++ b/g2p/app.py
@@ -20,7 +20,6 @@ from pathlib import Path
 from typing import Dict, List, Union
 
 import socketio  # type: ignore
-from networkx import shortest_path  # type: ignore
 from starlette.applications import Starlette
 from starlette.requests import Request
 from starlette.responses import HTMLResponse, RedirectResponse
@@ -282,7 +281,7 @@ async def change_table(sid, message):
             namespace="/table",
         )
     else:
-        path = shortest_path(LANGS_NETWORK, message["in_lang"], message["out_lang"])
+        path = LANGS_NETWORK.shortest_path(message["in_lang"], message["out_lang"])
         mappings: List[Mapping] = []
         for lang1, lang2 in zip(path[:-1], path[1:]):
             transducer = make_g2p(lang1, lang2, tokenize=False)
diff --git a/g2p/cli.py b/g2p/cli.py
index da84129..0d222f5 100644
--- a/g2p/cli.py
+++ b/g2p/cli.py
@@ -501,8 +501,6 @@ def convert(  # noqa: C901
     fra->fra-ipa, fra-ipa->eng-ipa and eng-ipa->eng-arpabet.
     """
     # Defer expensive imports
-    from networkx import has_path  # type: ignore
-
     from g2p.log import LOGGER
     from g2p.mappings import MAPPINGS_AVAILABLE, Mapping, MappingConfig
     from g2p.mappings.langs import LANGS_NETWORK
@@ -535,7 +533,7 @@ def convert(  # noqa: C901
     if out_lang not in LANGS_NETWORK.nodes:
         raise click.UsageError(f"'{out_lang}' is not a valid value for 'OUT_LANG'")
     # Check if path exists
-    if not has_path(LANGS_NETWORK, in_lang, out_lang):
+    if not LANGS_NETWORK.has_path(in_lang, out_lang):
         raise click.UsageError(
             f"Path between '{in_lang}' and '{out_lang}' does not exist"
         )
@@ -689,7 +687,7 @@ def update(in_dir, out_dir):
         reload_db()
         network_to_echart(
             outfile=os.path.join(os.path.dirname(static_file), "languages-network.json")
-        )  # updates g2p/status/languages-network.json
+        )  # updates g2p/static/languages-network.json
 
 
 @click.option(
@@ -851,4 +849,4 @@ def show_mappings(lang1, lang2, verbose, csv):
             print()
     else:
         for i, m in enumerate(mappings):
-            print(f"{i+1}: {m.in_lang} → {m.out_lang}")
+            print(f"{i+1}: {m.in_lang} → {m.out_lang}  ({m.display_name})")
diff --git a/g2p/mappings/langs/__init__.py b/g2p/mappings/langs/__init__.py
index a2473c9..c2bdf48 100644
--- a/g2p/mappings/langs/__init__.py
+++ b/g2p/mappings/langs/__init__.py
@@ -6,11 +6,11 @@ import gzip
 import json
 import os
 
-import networkx  # type: ignore
-
 from g2p.constants import LANGS_DIR, LANGS_FILE_NAME, NETWORK_FILE_NAME
 from g2p.log import LOGGER
 
+from .network_lite import DiGraph, node_link_graph
+
 assert LANGS_DIR == os.path.dirname(__file__)
 LANGS_PKL = os.path.join(LANGS_DIR, LANGS_FILE_NAME)
 LANGS_NWORK_PATH = os.path.join(LANGS_DIR, NETWORK_FILE_NAME)
@@ -25,14 +25,14 @@ def load_langs(path: str = LANGS_PKL):
         return {}
 
 
-def load_network(path: str = LANGS_NWORK_PATH):
+def load_network(path: str = LANGS_NWORK_PATH) -> DiGraph[str]:
     try:
         with gzip.open(path, "rt", encoding="utf8") as f:
             data = json.load(f)
-            return networkx.node_link_graph(data)
+            return node_link_graph(data)
     except Exception as e:
         LOGGER.warning(f"Failed to read language network from {path}: {e}")
-        return networkx.DiGraph()
+        return DiGraph()
 
 
 def get_available_languages(langs: dict) -> list:
diff --git a/g2p/mappings/langs/network_lite.py b/g2p/mappings/langs/network_lite.py
new file mode 100644
index 0000000..39df236
--- /dev/null
+++ b/g2p/mappings/langs/network_lite.py
@@ -0,0 +1,198 @@
+from collections import deque
+from typing import (
+    Any,
+    Dict,
+    Generic,
+    Hashable,
+    Iterable,
+    Iterator,
+    List,
+    Set,
+    Tuple,
+    TypeVar,
+    Union,
+)
+
+from typing_extensions import TypedDict
+
+T = TypeVar("T", bound=Hashable)
+
+
+class DiGraph(Generic[T]):
+    """A simple directed graph class
+
+    Most functions raise KeyError if called with a node u or v not in the graph.
+    """
+
+    def __init__(self) -> None:
+        """Contructor, empty if no data, else load from data"""
+        self._edges: Dict[T, List[T]] = {}
+
+    def clear(self):
+        """Clear the graph"""
+        self._edges.clear()
+
+    def update(self, edges: Iterable[Tuple[T, T]], nodes: Iterable[T]):
+        """Update the graph with new edges and nodes"""
+        for node in nodes:
+            self.add_node(node)
+        for u, v in edges:
+            self.add_edge(u, v)
+
+    def add_node(self, u: T):
+        """Add a node to the graph"""
+        if u not in self._edges:
+            self._edges[u] = []
+
+    def add_edge(self, u: T, v: T):
+        """Add a directed edge from u to v"""
+        self.add_node(u)
+        self.add_node(v)
+        if v not in self._edges[u]:
+            self._edges[u].append(v)
+
+    def add_edges_from(self, edges: Iterable[Tuple[T, T]]):
+        """Add edges from a list of tuples"""
+        for u, v in edges:
+            self.add_edge(u, v)
+
+    @property  # read-only
+    def nodes(self):
+        """Return the nodes"""
+        return self._edges.keys()
+
+    @property  # read-only
+    def edges(self) -> Iterator[Tuple[T, T]]:
+        """Iterate over all edges"""
+        for u, neighbours in self._edges.items():
+            for v in neighbours:
+                yield u, v
+
+    def __contains__(self, u: T) -> bool:
+        """Check if a node is in the graph"""
+        return u in self._edges
+
+    def has_path(self, u: T, v: T) -> bool:
+        """Check if there is a path from u to v"""
+        if v not in self._edges:
+            raise KeyError(f"Node {v} not in graph")
+        visited: Set[T] = set()
+        return self._has_path(u, v, visited)
+
+    def _has_path(self, u: T, v: T, visited: Set[T]) -> bool:
+        """Helper function for has_path"""
+        visited.add(u)
+        if u == v:
+            return True
+        for neighbour in self._edges[u]:
+            if neighbour not in visited:
+                if self._has_path(neighbour, v, visited):
+                    return True
+        return False
+
+    def successors(self, u: T) -> Iterator[T]:
+        """Return the successors of u"""
+        return iter(self._edges[u])
+
+    def descendants(self, u: T) -> Set[T]:
+        """Return the descendants of u"""
+        visited: Set[T] = set()
+        self._descendants(u, visited)
+        visited.remove(u)
+        return visited
+
+    def _descendants(self, u: T, visited: Set[T]):
+        """Helper function for descendants"""
+        visited.add(u)
+        for neighbour in self._edges[u]:
+            if neighbour not in visited:
+                self._descendants(neighbour, visited)
+
+    def ancestors(self, u: T) -> Set[T]:
+        """Return the ancestors of u"""
+        reversed_graph: DiGraph[T] = DiGraph()
+        reversed_graph.add_edges_from((v, u) for u, v in self.edges)
+        for node in self.nodes:
+            reversed_graph.add_node(node)
+        return reversed_graph.descendants(u)
+
+    def shortest_path(self, u: T, v: T) -> List[T]:
+        """Return the shortest path from u to v
+
+        Algorithm: Dijsktra's algorithm for unweighted graphs, which is just BFS
+
+        Returns:
+            list: the shortest path from u to v
+        Raises:
+            KeyError: if u or v is not in the graph
+            ValueError: if there is no path from u to v
+        """
+
+        if v not in self._edges:
+            raise KeyError(f"Node {v} not in graph")
+        visited: Dict[T, Union[T, None]] = {
+            u: None
+        }  # dict of {node: predecessor on shortest path from u}
+        queue: deque[T] = deque([u])
+        while queue:
+            u = queue.popleft()
+            if u == v:
+                rev_path: List[T] = []
+                nextu: Union[T, None] = u
+                while nextu is not None:
+                    rev_path.append(nextu)
+                    nextu = visited[nextu]
+                return list(reversed(rev_path))
+            for neighbour in self._edges[u]:
+                if neighbour not in visited:
+                    visited[neighbour] = u
+                    queue.append(neighbour)
+        raise ValueError(f"No path from {u} to {v}")
+
+
+NodeDict = TypedDict("NodeDict", {"id": Any})
+
+
+class NodeLinkDict(TypedDict, Generic[T]):
+    source: T
+    target: T
+
+
+class NodeLinkDataDict(TypedDict, Generic[T]):
+    directed: bool
+    graph: Dict
+    links: List[NodeLinkDict[T]]
+    multigraph: bool
+    nodes: List[NodeDict]
+
+
+def node_link_graph(data: NodeLinkDataDict[T]) -> DiGraph[T]:
+    """Replacement for networkx.node_link_graph"""
+    if not data.get("directed", False):
+        raise ValueError("Graph must be directed")
+    if data.get("multigraph", True):
+        raise ValueError("Graph must not be a multigraph")
+    if not isinstance(data.get("nodes", None), list):
+        raise ValueError('data["nodes"] must be a list')
+    if not isinstance(data.get("links", None), list):
+        raise ValueError('data["links"] must be a list')
+
+    graph: DiGraph[T] = DiGraph()
+    for node in data["nodes"]:
+        graph.add_node(node["id"])
+    for edge in data["links"]:
+        graph.add_edge(edge["source"], edge["target"])
+    return graph
+
+
+def node_link_data(graph: DiGraph[T]) -> NodeLinkDataDict[T]:
+    """Replacement for networkx.node_link_data"""
+    nodes: List[NodeDict] = [{"id": node} for node in graph.nodes]
+    links: List[NodeLinkDict[T]] = [{"source": u, "target": v} for u, v in graph.edges]
+    return {
+        "directed": True,
+        "graph": {},
+        "links": links,
+        "multigraph": False,
+        "nodes": nodes,
+    }
diff --git a/g2p/mappings/langs/utils.py b/g2p/mappings/langs/utils.py
index 9c495aa..7f23571 100644
--- a/g2p/mappings/langs/utils.py
+++ b/g2p/mappings/langs/utils.py
@@ -9,14 +9,13 @@ import json
 from pathlib import Path
 from typing import Any, Optional
 
-import networkx  # type: ignore
-from networkx.algorithms.dag import ancestors, descendants  # type: ignore
-
 from g2p.log import LOGGER
 from g2p.mappings import MAPPINGS_AVAILABLE, Mapping, MappingConfig
 from g2p.mappings.langs import LANGS_DIR, LANGS_NETWORK, LANGS_NWORK_PATH, LANGS_PKL
 from g2p.mappings.utils import MAPPING_TYPE, is_ipa
 
+from .network_lite import DiGraph, node_link_data
+
 # panphon.distance.Distance() takes a long time to initialize, so...
 # a) we don't want to load it if we don't need it, i.e., don't use a constant
 # b) we don't want to load it more than once, i.e., don't use a local variable.
@@ -170,9 +169,9 @@ def cache_langs(
         langs[code] = mapping_config.export_to_dict()
 
     # Save as a Directional Graph
-    lang_network = networkx.DiGraph()
+    lang_network: DiGraph[str] = DiGraph()
     lang_network.add_edges_from(mappings_legal_pairs)
-    write_json_gz(network_path, networkx.node_link_data(lang_network))
+    write_json_gz(network_path, node_link_data(lang_network))
     write_json_gz(langs_path, langs)
     return langs
 
@@ -194,8 +193,8 @@ def network_to_echart(outfile: Optional[str] = None, layout: bool = False):
     no_nodes = len(LANGS_NETWORK.nodes)
     for node in LANGS_NETWORK.nodes:
         lang_name = node.split("-")[0]
-        no_ancestors = len(ancestors(LANGS_NETWORK, node))
-        no_descendants = len(descendants(LANGS_NETWORK, node))
+        no_ancestors = len(LANGS_NETWORK.ancestors(node))
+        no_descendants = len(LANGS_NETWORK.descendants(node))
         size = min(
             20,
             max(
diff --git a/g2p/mappings/tokenizer.py b/g2p/mappings/tokenizer.py
index edaa1b2..d799241 100644
--- a/g2p/mappings/tokenizer.py
+++ b/g2p/mappings/tokenizer.py
@@ -9,8 +9,6 @@ language's input mapping or that are unicode letters, numbers and diacritics.
 import re
 from typing import List
 
-from networkx.exception import NetworkXError  # type: ignore
-
 from g2p.exceptions import MappingMissing
 from g2p.log import LOGGER
 from g2p.mappings import Mapping
@@ -154,8 +152,8 @@ class TokenizerLibrary:
                     out_lang = tok_path[1:3]
             if not out_lang:
                 try:
-                    successors = [x for x in LANGS_NETWORK.successors(in_lang)]
-                except NetworkXError:
+                    successors = list(LANGS_NETWORK.successors(in_lang))
+                except KeyError:
                     successors = []
                 ipa_successors = [x for x in successors if is_ipa(x)]
                 # LOGGER.warning(pprint.pformat([in_lang, "->", successors, ipa_successors]))
diff --git a/pyproject.toml b/pyproject.toml
index dde03ef..0b3c763 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -20,7 +20,6 @@ classifiers = [
 dependencies = [
     "click>=8.0.4",
     "coloredlogs>=15.0.1",
-    "networkx>=2.6",
     "openpyxl",
     "panphon>=0.19",
     "panphon<0.21; python_version<'3.9'",
@@ -30,6 +29,7 @@ dependencies = [
     "regex",
     "text_unidecode",
     "tqdm",
+    "typing_extensions",
 ]
 
 [project.optional-dependencies]
diff --git a/requirements.txt b/requirements.txt
index ecf1bd6..d1c70d5 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -3,7 +3,6 @@
 #
 # - click>=8.0.4
 # - coloredlogs>=15.0.1
-# - networkx>=2.6
 # - openpyxl
 # - panphon>=0.19
 # - pydantic>=2.3
@@ -55,8 +54,6 @@ markupsafe==2.1.5
     # via jinja2
 munkres==1.1.4
     # via panphon
-networkx==3.2.1
-    # via hatch.envs.prod
 numpy==1.26.4
     # via panphon
 openpyxl==3.1.2


Test patch:
diff --git a/g2p/tests/run.py b/g2p/tests/run.py
index 6fd37e0..8db3f64 100755
--- a/g2p/tests/run.py
+++ b/g2p/tests/run.py
@@ -25,7 +25,7 @@ from g2p.tests.test_indices import IndicesTest
 from g2p.tests.test_langs import LangTest
 from g2p.tests.test_lexicon_transducer import LexiconTransducerTest
 from g2p.tests.test_mappings import MappingTest
-from g2p.tests.test_network import NetworkTest
+from g2p.tests.test_network import NetworkLiteTest, NetworkTest
 from g2p.tests.test_tokenize_and_map import TokenizeAndMapTest
 from g2p.tests.test_tokenizer import TokenizerTest
 from g2p.tests.test_transducer import TransducerTest
@@ -60,6 +60,7 @@ MAPPINGS_TESTS = [
         MappingCreationTest,
         MappingTest,
         NetworkTest,
+        NetworkLiteTest,
         UtilsTest,
         TokenizerTest,
         TokenizeAndMapTest,
diff --git a/g2p/tests/test_network.py b/g2p/tests/test_network.py
index 80d4a56..da7136b 100755
--- a/g2p/tests/test_network.py
+++ b/g2p/tests/test_network.py
@@ -1,10 +1,14 @@
 #!/usr/bin/env python
 
+import gzip
+import json
 from unittest import TestCase, main
 
 from g2p import make_g2p
 from g2p.exceptions import InvalidLanguageCode, NoPath
 from g2p.log import LOGGER
+from g2p.mappings.langs import LANGS_NWORK_PATH
+from g2p.mappings.langs.network_lite import DiGraph, node_link_data, node_link_graph
 from g2p.transducer import CompositeTransducer, Transducer
 
 
@@ -37,5 +41,162 @@ class NetworkTest(TestCase):
         self.assertEqual("niɡiɡw", transducer("nikikw").output_string)
 
 
+class NetworkLiteTest(TestCase):
+    @classmethod
+    def setUpClass(cls):
+        with gzip.open(LANGS_NWORK_PATH, "rt", encoding="utf8") as f:
+            cls.data = json.load(f)
+
+    def test_has_path(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        graph.add_edge("b", "a")  # cycle
+        graph.add_edge("a", "c")
+        graph.add_edge("c", "d")
+        graph.add_edge("e", "f")
+        self.assertTrue(graph.has_path("a", "c"))
+        self.assertTrue(graph.has_path("a", "d"))
+        self.assertTrue(graph.has_path("b", "a"))
+        self.assertFalse(graph.has_path("a", "e"))
+        self.assertFalse(graph.has_path("a", "f"))
+        self.assertFalse(graph.has_path("c", "a"))
+        with self.assertRaises(KeyError):
+            graph.has_path("a", "y")
+        with self.assertRaises(KeyError):
+            graph.has_path("x", "b")
+
+    def test_g2p_path(self):
+        graph = node_link_graph(self.data)
+        self.assertTrue(graph.has_path("atj", "eng-ipa"))
+        self.assertTrue(graph.has_path("atj", "atj-ipa"))
+        self.assertFalse(graph.has_path("hei", "git"))
+
+    def test_successors(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        graph.add_edge("b", "a")
+        graph.add_edge("a", "c")
+        self.assertEqual(set(graph.successors("a")), {"b", "c"})
+        self.assertEqual(set(graph.successors("b")), {"a"})
+        self.assertEqual(set(graph.successors("c")), set())
+
+    def test_descendants(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        graph.add_edge("b", "a")  # cycle
+        graph.add_edge("a", "c")
+        graph.add_edge("c", "d")
+        graph.add_edge("e", "f")
+        self.assertEqual(graph.descendants("a"), {"b", "c", "d"})
+        self.assertEqual(graph.descendants("b"), {"a", "c", "d"})
+        self.assertEqual(graph.descendants("c"), {"d"})
+        self.assertEqual(graph.descendants("d"), set())
+        self.assertEqual(graph.descendants("e"), {"f"})
+        self.assertEqual(graph.descendants("f"), set())
+        with self.assertRaises(KeyError):
+            graph.descendants("x")
+
+    def test_g2p_descendants(self):
+        graph = node_link_graph(self.data)
+        self.assertEqual(
+            graph.descendants("atj"), {"eng-ipa", "atj-ipa", "eng-arpabet"}
+        )
+        self.assertEqual(graph.descendants("eng-ipa"), {"eng-arpabet"})
+        self.assertEqual(graph.descendants("atj-ipa"), {"eng-ipa", "eng-arpabet"})
+        self.assertEqual(graph.descendants("eng-arpabet"), set())
+
+    def test_ancestors(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        graph.add_edge("a", "c")
+        graph.add_edge("d", "a")  # cycle
+        graph.add_edge("c", "d")
+        graph.add_edge("e", "f")
+        self.assertEqual(graph.ancestors("a"), {"c", "d"})
+        self.assertEqual(graph.ancestors("b"), {"a", "d", "c"})
+        self.assertEqual(graph.ancestors("c"), {"a", "d"})
+        self.assertEqual(graph.ancestors("d"), {"a", "c"})
+        self.assertEqual(graph.ancestors("e"), set())
+        self.assertEqual(graph.ancestors("f"), {"e"})
+        with self.assertRaises(KeyError):
+            graph.ancestors("x")
+
+    def test_g2p_ancestors(self):
+        graph = node_link_graph(self.data)
+        self.assertEqual(graph.ancestors("atj"), set())
+        self.assertGreater(len(graph.ancestors("eng-ipa")), 50)
+
+    def test_shortest_path(self):
+        graph = DiGraph()
+        graph.add_edge("a", "e")
+        graph.add_edge("e", "f")
+        graph.add_edge("f", "g")
+        graph.add_edge("g", "d")
+        graph.add_edge("f", "d")
+        graph.add_edge("a", "b")
+        graph.add_edge("b", "a")  # Cycle
+        graph.add_edge("a", "c")
+        graph.add_edge("c", "d")
+        graph.add_edge("a", "d")
+        graph.add_edge("b", "d")
+        self.assertEqual(graph.shortest_path("a", "d"), ["a", "d"])
+        self.assertEqual(graph.shortest_path("c", "d"), ["c", "d"])
+        self.assertEqual(graph.shortest_path("a", "a"), ["a"])
+        with self.assertRaises(ValueError):
+            graph.shortest_path("c", "a")
+        with self.assertRaises(KeyError):
+            graph.shortest_path("a", "y")
+        with self.assertRaises(KeyError):
+            graph.shortest_path("x", "b")
+
+    def test_g2p_shortest_path(self):
+        graph = node_link_graph(self.data)
+        self.assertEqual(
+            graph.shortest_path("atj", "eng-arpabet"),
+            ["atj", "atj-ipa", "eng-ipa", "eng-arpabet"],
+        )
+
+    def test_contains(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        self.assertTrue("a" in graph)
+        self.assertTrue("b" in graph)
+        self.assertFalse("c" in graph)
+
+    def test_node_link_data(self):
+        graph = node_link_graph(self.data)
+        self.assertEqual(node_link_data(graph), self.data)
+
+    def test_node_link_graph_errors(self):
+        with self.assertRaises(ValueError):
+            node_link_graph({**self.data, "directed": False})
+        with self.assertRaises(ValueError):
+            node_link_graph({**self.data, "multigraph": True})
+        with self.assertRaises(ValueError):
+            node_link_graph({**self.data, "nodes": "not a list"})
+        with self.assertRaises(ValueError):
+            node_link_graph({**self.data, "links": "not a list"})
+        with self.assertRaises(ValueError):
+            data = self.data.copy()
+            del data["nodes"]
+            node_link_graph(data)
+        with self.assertRaises(ValueError):
+            data = self.data.copy()
+            del data["links"]
+            node_link_graph(data)
+
+    def test_no_duplicates(self):
+        graph = DiGraph()
+        graph.add_edge("a", "b")
+        graph.add_edge("b", "c")
+        graph.add_edge("a", "c")
+        graph.add_edge("a", "b")
+        self.assertEqual(len(list(graph.edges)), 3)
+        self.assertEqual(len(graph.nodes), 3)
+        self.assertEqual(len(list(graph.successors("a"))), 2)
+        self.assertEqual(len(list(graph.successors("b"))), 1)
+        self.assertEqual(len(list(graph.successors("c"))), 0)
+
+
 if __name__ == "__main__":
     main()