Skip to content

Latest commit

 

History

History
41 lines (29 loc) · 1.37 KB

README.md

File metadata and controls

41 lines (29 loc) · 1.37 KB
Raw

Graphs

The project aims to test the implementation of graphs in the implementation of algorithms for determining MST and shortest paths

Testing algorithms

Tasks performed by the program are saved in the config.ini file in the following syntax

<name of file which will contain results>
<name of file with graph> <graph structure> <type of graph> <algorithm> <number of repeats> <type of test>
...

In the first line specify name of file which will contain result (CSV file) In the next lines specify:

  • <name of file with graph> - name of file where you store graph as a list of edges (source_vertex destination_vertex weight)
  • <graph structure> - adjacency_matrix or adjacency_matrix or incident_matrix (not yet implemented)
  • <type of graph> - directed or undirected
  • <algorithm> - MST (Prim) or shortest_paths (Dijkstra)
  • <number of repeats> - number of repeats algorithm in test window
  • <type of test> - time or memory or print

Generating graphs

You can generate graph by setting afv-data-config.ini file and running Python script.

Graph will be generated as a Erdős–Rényi graph. Weights of edges will be randomly generated from specified range.

[graph]
graph_name = <name of file where graph will be saved>
vertices = <number of vertices>
density = <density of graph>
min_weight = <minimum weight of edge>
max_weight = <maximum weight of edge>