"""
TinyDiGraph
This code defines a custom graph data structure called TinyDiGraph, which is
designed to be a lightweight and efficient implementation of a directed graph.
The purpose of this code is to provide a simple way to create and manipulate
directed graphs, particularly for cases where performance and memory
efficiency are important.
The main input for this code is the number of nodes in the graph, which is set
when initializing the graph using the init_nodes method. The code doesn't
directly produce any output, but it provides methods to add edges, count nodes
and edges, and iterate through the graph's structure.
TinyDiGraph achieves its purpose by subclassing from DiGraphAdapter, which in
turn inherits from NetworkX's DiGraph class. This allows TinyDiGraph to
leverage existing graph functionality while customizing certain aspects for
efficiency. The key feature of TinyDiGraph is its use of a custom data
structure called MapAdapter (likely a list-based dictionary) to store node
and edge information.
The code implements several important methods:
1. cheat_node_dict and cheat_adjlist_outer_dict: These methods create
MapAdapter objects to store node and edge information efficiently.
2. init_nodes: This method initializes the graph with a specified number of
nodes, setting up the necessary data structures.
The main logic flow of the code is as follows:
1. Define the TinyDiGraph class with custom node and edge storage methods.
2. Provide a method to initialize the graph with a given number of nodes.
3. Set up the graph structure using MapAdapter objects for efficient storage
and access.
At the end of the file, there's a small example of how to use TinyDiGraph. It
creates a graph with 1000 nodes, adds an edge, and then demonstrates how to
iterate through the graph and access its properties.
The code also includes a brief demonstration of the MapAdapter data structure,
showing how it can be used as an efficient list-like dictionary.
Overall, this code provides a foundation for working with directed graphs in a
memory-efficient manner, which could be particularly useful for large graphs or
in situations where performance is critical.
"""
from typing import ItemsView, Iterator, MutableMapping
import networkx as nx
from mywheel.map_adapter import MapAdapter # type: ignore
[docs]
class DiGraphAdapter(nx.DiGraph, MutableMapping):
def __iter__(self) -> Iterator:
"""
Return an iterator over the nodes in the graph.
Returns:
iterator: An iterator over the nodes in the graph.
"""
return super().__iter__()
def __setitem__(self, key: object, value: object) -> None:
"""
Set the value for a given key.
Args:
key: The key to set.
value: The value to set.
"""
super().__setitem__(key, value)
def __delitem__(self, key: object) -> None:
"""
Delete a key from the graph.
Args:
key: The key to delete.
"""
super().__delitem__(key)
[docs]
def items(self) -> ItemsView:
"""Returns an iterator over (node, adjacency dict) pairs for all nodes.
This method overrides the default items() method to use adjacency() instead,
providing a consistent interface for iterating through the graph's nodes
and their connections.
Examples:
>>> graph = DiGraphAdapter()
>>> graph.add_edge(1, 2)
>>> graph.add_edge(2, 3)
>>> sorted(list(graph.items()))
[(1, {2: {}}), (2, {3: {}}), (3, {})]
"""
return self.adjacency()
[docs]
class TinyDiGraph(DiGraphAdapter):
"""A lightweight directed graph implementation optimized for performance and memory efficiency.
This class extends DiGraphAdapter to provide custom storage mechanisms using MapAdapter,
which is particularly efficient for graphs with a known, fixed number of nodes.
"""
num_nodes = 0 # Class variable to store the total number of nodes in the graph
[docs]
def cheat_node_dict(self) -> MapAdapter:
"""Creates a MapAdapter instance to store node attributes.
Returns:
MapAdapter: A list-based dictionary where each node's attributes are stored
in a separate dictionary at the node's index position.
Examples:
>>> graph = TinyDiGraph()
>>> graph.init_nodes(3)
>>> node_dict = graph.cheat_node_dict()
>>> list(node_dict.keys())
[0, 1, 2]
>>> node_dict[0]
{}
"""
return MapAdapter([dict() for _ in range(self.num_nodes)])
[docs]
def cheat_adjlist_outer_dict(self) -> MapAdapter:
"""Creates a MapAdapter instance to store adjacency lists.
Returns:
MapAdapter: A list-based dictionary where each node's outgoing edges are stored
in a separate dictionary at the node's index position.
Examples:
>>> graph = TinyDiGraph()
>>> graph.init_nodes(2)
>>> adj_list = graph.cheat_adjlist_outer_dict()
>>> list(adj_list.keys())
[0, 1]
>>> adj_list[0]
{}
"""
return MapAdapter([dict() for _ in range(self.num_nodes)])
[docs]
def node_dict_factory(self) -> MapAdapter: # type: ignore
"""Return `cheat_node_dict` function.
The `node_dict_factory` method is responsible for creating a factory
that produces the dictionary used to store node attributes in the
`TinyDiGraph`. In this specific implementation, it returns the
`cheat_node_dict` method, which is a custom function designed to create
a `MapAdapter` instance. This `MapAdapter` serves as a highly
efficient, list-based dictionary for storing node attributes.
The primary purpose of this method is to allow `TinyDiGraph` to
leverage a more memory-efficient data structure for its node storage
compared to a standard Python dictionary. By using a `MapAdapter`, the
graph can achieve better performance, especially when the number of
nodes is known in advance. This method is part of the internal factory
customization that allows `TinyDiGraph` to be optimized for specific use
cases.
Returns:
MapAdapter: a list-based dictionary for storing node attributes
Examples:
>>> graph = TinyDiGraph()
>>> graph.init_nodes(3)
>>> factory = graph.node_dict_factory()
>>> isinstance(factory, MapAdapter)
True
"""
return self.cheat_node_dict()
[docs]
def adjlist_outer_dict_factory(self) -> MapAdapter: # type: ignore
"""Return `cheat_adjlist_outer_dict` function.
The `adjlist_outer_dict_factory` method is responsible for creating a
factory that produces the outer dictionary for the adjacency list of the
`TinyDiGraph`. In this case, it returns the `cheat_adjlist_outer_dict`
method, which is a custom method designed to create a `MapAdapter`
instance. This `MapAdapter` serves as a highly efficient, list-based
dictionary for storing the adjacency lists of each node in the graph.
The primary purpose of this method is to allow `TinyDiGraph` to
leverage a more memory-efficient data structure for its adjacency list
compared to a standard Python dictionary. By using a `MapAdapter`, the
graph can achieve better performance, especially when the number of
nodes is known in advance. This method is part of the internal factory
customization that allows `TinyDiGraph` to be optimized for specific use
cases.
Returns:
MapAdapter: a list-based dictionary for storing node attributes
Examples:
>>> graph = TinyDiGraph()
>>> graph.init_nodes(2)
>>> factory = graph.adjlist_outer_dict_factory()
>>> isinstance(factory, MapAdapter)
True
"""
return self.cheat_adjlist_outer_dict()
[docs]
def init_nodes(self, num_nodes: int) -> None:
"""Initializes the graph with a specified number of nodes.
Sets up the internal data structures for node storage, adjacency lists (successors),
and predecessor lists. This method must be called before adding any edges.
Args:
num_nodes (int): The number of nodes to initialize in the graph. Nodes will be
indexed from 0 to num_nodes-1.
Examples:
>>> graph = TinyDiGraph()
>>> graph.init_nodes(5)
>>> graph.number_of_nodes()
5
>>> list(graph._node.keys())
[0, 1, 2, 3, 4]
>>> list(graph._adj.keys())
[0, 1, 2, 3, 4]
"""
self.num_nodes = num_nodes
self._node = self.cheat_node_dict() # Stores node attributes
self._adj = (
self.cheat_adjlist_outer_dict()
) # Stores outgoing edges (successors)
self._pred = (
self.cheat_adjlist_outer_dict()
) # Stores incoming edges (predecessors)
if __name__ == "__main__":
# Example usage of TinyDiGraph
graph = TinyDiGraph()
graph.init_nodes(1000) # Initialize graph with 1000 nodes
graph.add_edge(2, 1) # Add an edge from node 2 to node 1
# Print basic graph properties
print(graph.number_of_nodes()) # Expected output: 1000
print(graph.number_of_edges()) # Expected output: 1
# Iterate through all edges in the graph
for utx in graph:
for vtx in graph.neighbors(utx):
print(f"{utx}, {vtx}") # Will print "2, 1"
# Demonstration of MapAdapter functionality
a = MapAdapter([0] * 8) # Create a MapAdapter with 8 zero-initialized elements
for idx in a:
a[idx] = idx * idx # Square each element's index and store it
for idx, vtx in a.items():
print(f"{idx}: {vtx}") # Print index: value pairs
print(3 in a) # Check if index 3 exists (should return True)