GSoC 2026 Proposal Feedback – Immutable Graph Construction

[Parry]

Dear Dr. Coudert,

I hope you are doing well.

My name is Parry Nall, and I am preparing a GSoC 2026 proposal for the project “Speed up the construction of immutable (di)graphs.”

I have started contributing to SageMath and working in the graph subsystem. In a recent pull request (#41923), I worked on shared backend initialization logic between Graph and DiGraph, which helped me better understand how immutable graph construction flows through the static sparse backend.

For my proposal, I am focusing on removing the current two-stage construction process (mutable → immutable) by enabling direct construction of immutable graphs from edge-list and adjacency-style inputs, along with benchmarking improvements in runtime and memory usage.

I had a couple of quick questions to make sure my proposal is well-scoped:

1. Would you consider edge lists the best starting point for direct construction, or is there another input format that would be more impactful?
2. How much emphasis would you recommend placing on backend-level optimizations versus focusing on clean direct construction paths?

I would be happy to share a draft of my proposal if that would be helpful.

Thank you for your time.

Best regards,
Parry Nall

[David Coudert]

Hello,

I think the easiest format to consider is vertices_and_edges.

The first step is clearly to avoid useless copies in the construction, in copy and in relabel.

Then, any optimization on the backends is welcome.

For instance we can certainly avoid some translations from one labeling to another that occur in Graph, in StatisSparseGraph and in short_digraph.

There is room for improvements in the backends. However, we must ensure compatibility with current use.

Sincerely,

David.

--
You received this message because you are subscribed to the Google Groups "sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-gsoc+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/sage-gsoc/482845b4-ae9a-4bec-a9cf-830ea6ca1d39n%40googlegroups.com.

——
David Coudert
Equipe-Projet COATI
Centre Inria d’Université Côte d'Azur
Université Côte d’Azur, Inria, CNRS, I3S, France
http://www-sop.inria.fr/members/David.Coudert/