API Reference#

This section contains a detailed description of the functions, modules, and objects included in pygraphs.

Graphs#

The three main graph representations in the package are :

  • AdjacencyList: List[List[Integral]]]: A list of lists, where the outer list has a length equal to the number of vertices in the graph, and each inner list contains the neighbors (i.e., [v1, v2, ...]) of the corresponding vertex (from outer vertex to inner vertex). For a weighted graph, the form List[List[Tuple[Integral, Real]]] is used where the inner lists contain tuples of the form \((v, w)\), where \(v\) is a neighbor vertex and \(w\) is the weight of the edge connecting the vertex to its neighbor. To store more than weight, the form List[List[Tuple[Integral, Dict[str, Any]]]] is used.

  • Edges: List[Tuple[Integral, Integral]]: A list of tuples, where each tuple represents an edge \((u, v)\) in the graph (from vertex \(u\) to vertex \(v\)). For a undirected graph consider converting in pygraphs.Graph class and use the to_undirected method to duplicate \((u, v)\) into \((u, v)\) and \((v, u)\). For a weighted graph, the form List[Tuple[Integral, Integral, Real]] containing \((u, v, w)\) is used, where \(u\) and \(v\) are the vertices connected by the edge and \(w\) is the weight of the edge. To store more than weight, the form List[Tuple[Integral, Integral, Dict[str, Any]]] is used.

  • GraphRepresentation: Dict[int, Dict[int, Dict[str, Any]]]: A dictionary where the keys are vertex identifiers and the values are dictionaries mapping neighboring vertex identifiers to edge attributes (e.g., weight). This is the internal representation used by the pygraphs.Graph class.

Graph Class#

  • pygraphs.Graph: The main class representing a graph and validating the graph structure.

  • Conversion Functions - Functions to convert between different graph representations (e.g., adjacency list, edge list, graph dictionary format).

A graph is :

  • weighted/unweighted if it has edges with weights (i.e., numerical values representing the strength or cost of the connection between vertices). In the pygraphs.Graph class, all graphs are stored in a weighted format but the weights can be set to a default value (e.g., 1) for unweighted graphs.

  • directed/undirected if the edges have a direction (i.e., they go from one vertex to another) or not. In the pygraphs.Graph class, all graphs are stored in a directed format but undirected graphs can be represented by adding edges in both directions. The weights must be the same for both directions in the case of undirected graphs otherwise the graph will be considered as directed.

  • weight symmetric (for directed graphs) if for both two-way edges between vertices \(u\) and \(v\), the weights are the same (i.e., \(w(u, v) = w(v, u)\) if \((u, v)\) and \((v, u)\) are both present).

Algorithms#

  • Breadth-First Search (BFS) - A graph traversal algorithm that explores the graph level by level starting from a source vertex. It is used to find the shortest path in an unweighted graph and to explore all reachable nodes efficiently.

  • Depth-First Search (DFS) - A graph traversal algorithm that explores as far as possible along each branch before backtracking. It is useful for connectivity checks, cycle detection, and structural analysis of graphs.

  • Strongly Connected Components (SCC) - A decomposition of a directed graph into maximal subsets of vertices where every vertex is reachable from every other vertex in the same subset. It is used to analyze dependency structures and directed graph topology (e.g., via Tarjan’s or Kosaraju’s algorithm).

  • Dijkstra - An algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It is widely used in routing, GPS navigation, and network optimization.