Home
Welcome to the OOP-Ex3 wiki!
- Develop a data structure type of a directed weighted graph in Python.
- Make comparison for the implementation of selected algorithms of the graph in Python versus 2 other implementations: of ex2 project which implemented in Java and of the Python library for graphs - NetworkX.
Our results for the runtime comparison of selected algorithms using given graphs loaded from given JSON files (Those JSON files can be found in data folder):
| Python implementation | Java implementation | NetworkX implementation | |
|---|---|---|---|
| shortest_path | |||
| G_10_80_0.json | 0.0s | 0.0s | 0.0s |
| G_100_800_0.json | 0.001009225845336914s | 0.003s | 0.0009763240814208984s |
| G_1000_8000_0.json | 0.008789539337158203s | 0.048s | 0.001991748809814453s |
| G_10000_80000_0.json | 0.251767635345459s | 0.2s | 0.20882296562194824s |
| G_20000_160000_0.json | 0.46164894104003906s | 0.334s | 0.21179485321044922s |
| G_30000_240000_0.json | 0.6002418994903564s | 0.707s | 0.1903536319732666s |
| connected_component | |||
| G_10_80_0.json | 0.0s | 0.005s | ------------------------------- |
| G_100_800_0.json | 0.0009291172027587891s | 0.01s | ------------------------------- |
| G_1000_8000_0.json | 0.005831241607666016s | 0.081s | ------------------------------- |
| G_10000_80000_0.json | 0.0800313949584961s | 0.481s | ------------------------------- |
| G_20000_160000_0.json | 0.20691275596618652s | 0.655s | ------------------------------- |
| G_30000_240000_0.json | 0.3171975612640381s | 0.582s | ------------------------------- |
| connected_components | |||
| G_10_80_0.json | 0.0s | 0.001s | 0.0s |
| G_100_800_0.json | 0.0s | 0.001s | 0.0009329319000244141s |
| G_1000_8000_0.json | 0.006830930709838867s | 0.051s | 0.01073765754699707s |
| G_10000_80000_0.json | 0.5397286415100098s | 20.217s | 0.11910343170166016s |
| G_20000_160000_0.json | 1.5870063304901123s | 44.01s | 0.2645070552825928s |
| G_30000_240000_0.json | 4.76577091217041s | 80.845s | 0.41577601432800293s |
For more information about those algorithms can be found here
Computer's specification on which we performed the runtime comparison of the algorithms mentioned above:
- Processor: i5-7200U dual core 2.50GHZ.
- Installed memory (RAM): 16.0 GB.
- Operating system: Microsoft Windows 10 pro 64 bit.