This project is a SageMath library for manipulating maps. Maps are embeddings of graphs on surfaces, commonly used in graph theory, combinatorics, and topology.
This library provides tools for creating, visualizing, and manipulating planar maps within the SageMath environment.
The implementation of maps is primarily based on the following references:
-
[1] Handbook on Enumerative Combinatorics, Gilles Schaeffer, 2015 Website
-
[2] An Introduction to Map Enumeration, Guillaume Chapuy, 2014 Website
-
[3] Enumeration and Random Generation of Planar Maps, Ivan Geffner, Master’s Final Thesis, Universitat Politècnica de Catalunya, 2014 Website
-
[4] Optimal Coding and Sampling of Triangulations, Dominique Poulalhon and Gilles Schaeffer, LIX – CNRS Ecole Polytechnique Website
This library requires a working SageMath installation.
Before using it, we highly recommend reading the official SageMath documentation:
We recommend using Conda Forge:
After completing the installation, check the file example.py for usage examples or run it by : python example.py to see them in action.
We also recommend using the latest networkx version, on some old versions problems on the visualization of map may happen.
Below is a more detailled installation process for linux system , first we need to create a working sage virtual environement.
Run the following commands in order:
curl -L -O "https://github.com/conda-forge/miniforge/releases/latest/download/Miniforge3-$(uname)-$(uname -m).sh"
bash Miniforge3-$(uname)-$(uname -m).sh (say yes to all the questions asked)Once they finished running, close your terminal and open a new one , now choose your python version for sage denoted by X, here we will choose X=3.12, then run the following:
conda create -n sage sage python=3.12
It will take some time, when it is done you can activate the sage environment by running:
conda activate sageNow it is time to get the library and run the example file, enter the following commands in order:
git clone https://github.com/vicllo/PlanarMaps
cd PlanarMaps
conda activate sage
python example.pyThe library contains 6 main classes:
- LabelledMap
- RootedMap
- MutableLabelledMap
- PrimitiveMutableLabelledMap
- MapGenerator
- DynamicPlanarMapShow
Each class provides specific functionalities for working with maps.
A Labelled Map is a graph representation equipped with a rotation system and an arbitrary labeling of its (2n) half-edges(also called demi-edges) with numbers in [1 ... 2n].
This class provides two constructors:
- From permutations (
σandα), following the notation in [2]. - From an adjacency list.
- Compute:
- Face count, number of nodes, edges, genus, diameter, etc.
- Construct various derived maps:
- Spanning Tree, Dual Graph, Derived Map, Incidence Map, etc.
- Visualization:
show()method for plotting the map.
It also provides a more user-friendly way to interact with demi-edges other than raw indices, by allowing the use of TopologicalDemiEdge.
A Rooted Map is an equivalence class of labelled maps under relabeling of [1 ... 2n], preserving the root half-edge (labelled as 1).
The half-edge labelled 1 serves as the root of the map. All methods that return a map will return a RootedMap.
This class inherits from LabelledMap.
This class inherits from LabelledMap and provides methods for modifying the map, such as:
- Adding or removing edges
- Deleting vertices
- Contracting edges
- Contracting faces
- etc.
Some notes:
- All methods that return a map will return a
LabelledMap, not aMutableLabelledMap. - Most methods that modify the map will alter its labels. To keep track of demi-edges even when labels change, please use
MutableTopologicalDemiEdge, which guarantees that the label associated with it is updated accordingly.
This class inherits from LabelledMap and provides methods for modifying the map, it is much more primitive than MutableLabelledMap and place more responsability on the user and if you aren't careful the map may become not stable , some methods of LabelledMap are not implemented for this class and will raise an error.Only useful compared to MutableLabelledMap because on some operations it is O(1) instead of O(log(m)), if it isn't critical for your work we advised you to use MutableLabelledMap instead.
Some notes:
- All methods that return a map will return a
LabelledMap, not aPrimitiveMutableLabelledMap. - Most methods that modify the map will alter its labels. To keep track of demi-edges even when labels change, please use
PrimitiveMutableTopologicalDemiEdge, which guarantees that the label associated with it is updated accordingly.
Provides methods for generating maps or map-related objects, including:
- A method for generating uniformly random rooted map with a fixed number of edges.
- A method for generating uniformly random rooted tree of fixed size.
- A method for generating uniformly random Triangulations of fixed size
- etc.
This class provides a more advanced and customizable way for users to display maps than the default show method.
-
TopologicalDemiEdge: A more user-friendly way to interact with demi-edges than using raw indices. -
MutableTopologicalDemiEdge: Inherits fromTopologicalDemiEdge; adds methods only possible with mutable maps. -
MapPermutation: A custom implementation of permutations used internally by the library. -
RotatingPermutation: Inherits fromMapPermutation; a special kind of mutable permutation with performant query time (O(\log n)) operations (e.g., checking if two indices are on the same cycle) and efficient operations like deleting or adding indices in a cycle. -
PrimitiveRotatingPermutation: Inherits fromMapPermutation; a more primitive version of RotatingPermutation it support modification operations in O(1). -
CustomSwap: Inherits fromMapPermutation; a special class for transpositions, more efficient in some cases than usingMapPermutationdirectly. -
PermutationUtilsAbstractor: An internal class used to abstract some methods related to map permutations. -
RotatingPermutationUtilsAbstractor: Inherits fromPermutationUtilsAbstractor, adapted forRotatingPermutation. -
PrimitiveRotatingPermutationUtilsAbstractor: Inherits fromPermutationUtilsAbstractor, adapted forPrimitiveRotatingPermutation. -
CyclicChainedList: An implementation of a mutable cyclic list used inRotatingPermutation. -
CyclicUtilsProvider: A class that abstracts operations (e.g., querying whether two indices are on the same cycle), used inRotatingPermutation. -
SplayTree: An implementation of a modified splay tree data structure with some tweaks useful inCyclicUtilsProvider.
For questions, issues, or feature requests, please open an issue on the GitHub repository.