🕸️ Geodesic Subpath Number Analysis 🕸️

Project was developed as part of course 'Financial lab' at the University of Ljubljana, Faculty of Mathematics and Physics, during the academic year 2025/2026. The aim was to analyze structural properties in various classes of connected simple graphs through the lens of the geodesic subpath number.

📚 Essentials

Let $G = (V, E)$ be connected, simple, undirected graph. For any two vertices (nodes) $u, v \in V$ the length of shortest path between them is called graph distance, denoted as $d_G(u, v)$.

• Path in $G$ is a sequence of distinct vertices $(v_i)_{i=1}^{\ell}$ such that each consecutive pair $(v_{i-1}, v_i) \in E$
• Trivial path is a path of length $0$ consisting of a single vertex
• Geodesic path between vertices $u$ and $v$ is any simple path of length exactly $d_G(u, v)$

Let $P \mspace{2mu} (G \mspace{2mu})$ denote the set of all geodesic paths (including trivial paths).
The geodesic subpath number of $G$ is defined as:

$$ gpn \mspace{2mu}( G \mspace{3mu}) \mspace{2mu} = | P \mspace{5mu} ( G \mspace{3mu}) \mspace{6mu}| $$

Simply, $gpn(G \mspace{2mu} )$ counts all shortest paths between vertex pairs and includes all trivial paths.

📝 Findings

Report of our analysis in Slovene can be accessed here: full report

🛠️ Setup Guide

• 📋Pre-requisites:

  • Docker 20.10+
  • Docker Compose 2.0+

• 🔧 Environment Configuration:

  1. 🐳 Deploy Docker Compose Service

  docker compose up -d

  2. 🖥️ Shell Access to SageMath Container

  docker compose exec sagemath bash

Note

The current configuration (docker-compose.yml) defines a service which deploys a container with a volume that acts as a sync between the container directory and the host directory. Any changes made on the host are immediately reflected inside the container, and vice versa.

Tip

Before proceeding with any operations, ensure the Docker service is running and verify its status.

docker ps --filter "name=sagemath-dev"

Tip

Jupyter notebook cells can be executed directly from an IDE such as Visual Studio Code:

• Install the Jupyter Notebook extension
• Select Dev Containers: Attach to Running Container from option menu
• Choose /sagemath-dev container as the execution environment

• 🚀 Running Python Modules from Docker Container:

  sage -python <path-to-file>

💡 Advisors

Project was developed under the guidance of:

• Riste Škrekovski
• Timotej Hrga