Question about the immutable (di)graph construction GSoC idea
吳述宇
Hello SageMath GSoC mentors and developers,
My name is David Wu, and I am an undergraduate student interested in the GSoC 2026 idea “Speed up the construction of immutable (di)graphs.”
I have already built Sage locally from source and started reading the relevant issues and source files related to immutable graphs and construction paths.
After reading the code and running a few local benchmarks, my current understanding is the following:
immutable=True is essentially mapped to data_structure='static_sparse'.
GenericGraph.copy(..., immutable=True) appears to translate this into data_structure='static_sparse' and then rebuild via the constructor.
In Graph / DiGraph construction, it seems that the current path first builds using the sparse data structure and then re-encodes to static_sparse, rather than directly constructing a StaticSparseBackend.
I also ran some small local benchmarks. For example, on one of my larger test cases:
For Graph with n=10000, m=50000:
Graph(..., sparse default): about 0.023s
Graph(..., immutable=True): about 0.127s
Graph(...).copy(immutable=True): about 0.141s
Graph(..., data_structure='static_sparse'): about 0.128s
For DiGraph with n=10000, m=50000:
DiGraph(..., sparse default): about 0.027s
DiGraph(..., immutable=True): about 0.114s
DiGraph(...).copy(immutable=True): about 0.120s
DiGraph(..., data_structure='static_sparse'): about 0.112s
I also observed that for an already constructed graph object G0, the timings for
G0.copy(immutable=True)
G0.copy(data_structure='static_sparse')
Graph(G0, immutable=True)
are all very close, which seems consistent with the idea that a large part of the overhead comes from the conversion/re-encoding path.
My question is that is this two-stage construction path the main intended optimization target of the GSoC idea? If so, would you recommend starting from a smaller contribution around the constructor/copy path, or is there another part of the immutable graph stack that would be a better first place to investigate?
If there is some misunderstandings, please also tell me.
Best regards,
David Wu
