Welcome to Graph Diameter Identifier’s documentation!¶

Overview¶

How do I install it?¶

You should have a python 3 interpreter installed on your machine.
- PyPy 3 is recommended (substitute <your_python_interpreter> with pypy3 for now on)
- CPython 3 is supported (substitute <your_python_interpreter> with python3 for now on)
Then you may choose between three alternatives:
1. User-specific installation (Recommended for end-users)
  
  run $ <your_python_interpreter> setup.py install --user
2. System-wide installation
  
  run # <your_python_interpreter> setup.py install as administrator
3. Virtual environment installation (Recommended for development)
  
  Create the virtual environment (you must create it at the first time you’re installing it): $ virtualenv -p `which <your_python_interpreter>` venv
  
  Activate the environment: $ source venv/bin/activate
  
  Run: $ <your_python_interpreter> setup.py install
  
  Are you done? Do you want to deactivate the environment? So do it through the command $ deactivate

How do I run it?¶

After installing it, you should have “diameter” installed as module.
You can see the available commands running $ <your_python_interpreter> -m diameter -h
There are two IO options available:
- Standard Input/Output;
- File.
The graph is undirected by default, but you can specify it as directed through the optional parameter --directed-graph (write it after $ <your_python_interpreter> -m diameter and before the IO option choice).
Both methods require you to describe a graph (following an specific structure).
For “Standard Input/Output”:
- run the following command: $ <your_python_interpreter> -m diameter stdio;
- the command prompt will be locked and you must type whatever input you want;
- the output will be printed out on the command prompt after the algorithm execution.
For “File”:
- you must specify an input file path and an output file path (Existing files on output path will be overwritten!);
- run the following command: $ <your_python_interpreter> -m diameter file <your_input_file_path> <your_output_file_path>.

Input structure:¶

First line: <Number of vertices> <Number of edges>
Following “Number of edges” lines: <Origin vertex> <Target vertex> <Edge weight>

Input example:¶

Understanding the output file¶

First line: Distance between the diameter vertices
Second line: <origin_diameter_vertex_id> <target_diameter_vertex_id>
Third line: Number of vertices on the Shortest Path between the diameter vertices
Fourth line: The id of each vertex on the Shortest Path between the diameter vertices

How do I contribute to it?¶

This is a design and analysis of algorithms work. No maintenance is planned and you shouldn’t run it in production.

But it’s open source! If you’re still interested on submitting contributions, then you should open an Issue, create a Pull Request, or contact me by e-mail.

Reference¶

Algorithms¶

Shortest Path (FloydWarshall)¶

class diameter.algorithms.shortest_path.FloydWarshall(w: diameter.model.graph.AdjacencyMatrix)¶

An implementation of the FloydWarshall Algorithm

apply()¶: FloydWarshall’s main method. It can be used only once, otherwise it’ll raise RuntimeError.

classmethod from_str(input_path: str, directed: bool = True)¶

An static factory method that reads input graph from a file

Parâmetros

input_path – Path to input graph description file
directed – A flag indicating whether the graph is directed or not

Retorna

A configured object of FloydWarshall ready to be applied

init_structures()¶: Output structures (shortest-path matrices and predecessors matrices) initialization.

class diameter.algorithms.shortest_path.Matrices(n, default_value=None)¶

A base class for Shortest Path output structures (both contain N square matrices of size N).

It’s optimized for space and time complexity (using two unidimensional lists instead of N bidimensional ones).

get(i, j, k) → Union[int, float]¶

Getter for a cell whose position and matrix-index are specified

Parâmetros

i – cell’s row number
j – cell’s column number
k – matrix-index where cell is located

Retorna

cell or default_value (value representing empty cell)

get_last(i, j) → Union[int, float]¶

Getter for a cell from the nth matrix whose position is specified

Parâmetros

i – cell’s row number
j – cell’s column number

Retorna

cell or default_value (value representing empty cell)

set(i, j, k, w)¶

Setter for a given cell on a given matrix

Parâmetros

i – cell’s row number
j – cell’s column number
k – matrix-index where cell is located
w – new weight cell should be set

class diameter.algorithms.shortest_path.PredecessorsMatrices(n)¶: A specialization of Matrices for predecessors matrix representation

class diameter.algorithms.shortest_path.ShortestPathMatrices(n)¶: A specialization of Matrices for shortest-path matrix representation

Diameter (FloydWarshall modification)¶

class diameter.algorithms.diameter.DiameterAlgorithm(w: diameter.model.graph.AdjacencyMatrix)¶

Implementation of the “Graph Diameter Identifier” algorithm.

Based on the FloydWarshall

apply()¶

Execute method from Command Pattern. Run diameter algorithm.

Run FloydWarshall, an O(n^3) time complexity algorithm;
Then find max value on shortest-path matrix;
Finally generate output’s information

It can be used only once, otherwise it’ll raise RuntimeError.

diameter_value() → int¶

Retorna: Diameter’s shortest-path total weight

diameter_vertices() → Tuple[int, int]¶

Retorna: Both origin and target diameter vertices

formatted_result() → str¶

Retorna: A formatted text to be outputted

minimum_path_size() → int¶

Retorna: Number of vertices on the shortest-path between diameter vertices

minimum_path_vertices() → List[int]¶

Retorna: Each vertex on the shortest-path between diameter vertices

store_shortest_path_to_output(i, j)¶

Read each vertex on the shortest-path between diameter vertices

Parâmetros

i – origin diameter vertex
j – target diameter vertex

update_max(i, j)¶

Check value on cell (i,j) and compare it to the current maximum value.

Parâmetros

i – cell’s row
j – cell’s column

Model (Data structure)¶

Adjacency Matrix¶

class diameter.model.graph.AdjacencyMatrix(n_vertices=0, m_edges=0, directed=True)¶

The main graph Data Structure.

__init__(n_vertices=0, m_edges=0, directed=True)¶

The AdjacencyMatrix’s main constructor.

The created graph doesn’t contain any edges yet, those should be added using place_edge()

Parâmetros

n_vertices – Number of vertices
m_edges – Number of edges
directed – A flag indicating whether the graph is directed or not

classmethod from_str(input_path: str, directed=True)¶

An static factory method that reads graph info from a file

Parâmetros

input_path – Path to input graph description file
directed – A flag indicating whether the graph is directed or not

Retorna

AdjacencyMatrix object populated with data extracted from file

place_edge(from_vertex, to_vertex, weight)¶

Place an expected edge with a given weight.

If edge placing exceeds “Number of Edges” specified on construction, the an ValueError is raised

Parâmetros

from_vertex – Origin vertex
to_vertex – Target vertex
weight – Edge’s weight