Home - HelenYunes/OOP_Ex3 GitHub Wiki

Welcome to the wiki of our project!

Our project consists of three parts. In the first and second parts of this project we built the data structure of weighted directed graph and implemented algorithms on this graph. In the third part of this project we will be comparing runtimes for our graph related libraries. We will be comparing what we coded with Python and previously with Java to the Python library Networkx. The methods we're about to compare in this project are all ran on the same six Directed Weighted Graphs and these methods are:

  • shortest_path() - Finds the shortest path between two nodes(src & dest) taking into account the weight of the edges between them.
  • connected_component() - Finds the Strongly Connected Component(SCC) that some node id1 is a part of.
  • connected_components() - Finds all the Strongly Connected Component(SCC) in the graph.
Tested on:
  • Operating System: Windows 10 pro 64-bit
  • System Model: HP EliteBook 840 G3
  • Processor: Intel(R) Core(TM) i5-6300U @ 2.40GHz, (4 CPUs), ~2.5GHz
  • Memory: 16384MB RAM

Each test is performed and ran with JetBrains ide's(Integrated development environment), PyCharm for python and IntelliJ for Java.
The sizes of the graphs we're testing are(V - Veracities, E - Edges):

  • 10V | 80E
  • 100V | 800E
  • 1,000V | 8,000E
  • 10,000V | 80,000E
  • 20,000V | 160,000E
  • 30,000V | 240,000E

About Networkx

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

Open Source software for complex networks

  • Data structures for graphs, digraphs, and multigraphs
  • Many standard graph algorithms
  • Network structure and analysis measures
  • Generators for classic graphs, random graphs, and synthetic networks
  • Nodes can be "anything" (e.g., text, images, XML records)
  • Edges can hold arbitrary data (e.g., weights, time-series)
  • Open source 3-clause BSD license
  • Well tested with over 90% code coverage
  • Additional benefits from Python include fast prototyping, easy to teach, and multi-platform

source | website

netwrokx