Algorithms 2 Project: "Erdos Renyl Model (for generating Random Graphs)"

Random graphs help in analyzing complex networks.
In a random graph, the quantities of nodes and arcs are random variables defined according to a given probabilistic model.
In this project we will explore properties of undirected random graphs in the Erdos Renyl model.
In this model, the number of nodes in a graph (we will mark it with V) is fixed and given in advance.
However, every edge between a pair of nodes will appear in the graph with probability P independently of the other edges, where P - is a parameter of the model.

Table of Contents

1. About The Project
2. Build Requirements
3. Getting Started
   • Installation
4. Usage
5. License
6. Contributors
7. Contact

About The Project

In the 1st part of this project, 4 main tasks are answered:

1. Write a "build_random_graph" function that accepts V and P and returns a random graph with V nodes where each edge will appear in the graph with probability P (you must explain which representation you chose for graphs and why).
2. Write a function called "diameter" that accepts a graph and returns its diameter (the implementation rationale must be explained).
3. Write a function called "Is_Isolated" that receives a graph and returns 1 if the graph has at least one node without neighbors, otherwise the function returns 0.
4. Write a function called "connectivity" that receives a graph and returns 1 if the graph is connected, otherwise the function returns 0.

In the 2nd part of the project we would like to test properties of random graphs with the help of simulation.
For each of the features listed above:
A list of 10 possible values ​​for P must be selected - so that half of the P values ​​are greater than the threshold and half of the values ​​are smaller.
For each of the features, 500 random graphs should be generated for V=1000 and for each of the P's (Total 5000 for each property). You must count how many graphs satisfy the property and how many do not.

In this project you may find several subjects such as:

1. Graph bindings.
2. Graph diameter.
3. An isolated node in a graph.
4. Random graphs.
5. Probability.
6. Simulation.
7. Threshold values.
8. CSV files.
9. Calculation algorithms on graphs.

(back to top)

Build Requirements

Visual Studio 2017

• Community, Professional or Enterprise Edition
• VC++ 2017 latest v141 tools
• Visual C++ compilers and libraries for (ARM, ARM64)
• Windows XP support for C++
• Visual C++ ATL for (x86 and x64, ARM, ARM64)
• Windows 10 SDK

Visual Studio 2019

• Community, Professional or Enterprise Edition
• MSVC v142 - VS 2019 C++ (x64/x86, ARM, ARM64) build tools (Latest)
• C++ ATL for latest v142 build tools (x86 & x64, ARM, ARM64)
• Windows 10 SDK

Visual Studio 2022

• Community, Professional or Enterprise Edition
• MSVC v143 Buildtools (x64/x86, ARM, ARM64)
• C++ ATL for latest v143 build tools (x64/x86, ARM, ARM64)
• Windows 10 SDK

(back to top)

Getting Started

Follow these simple steps:

Installation

1. Clone the repo

   git clone https://github.com/RamMichaeli17/Erdos-Renyl-Model-for-generating-Random-Graphs.git

2. Run the program

   change the configuration to "Release" (x86 or x64) and press "Local Windows Debugger"

   
3. Watch the results on the opened cmd window:

(back to top)

Usage

Click here for a detailed explanation of all the functions in the program and the analysis of the results in the Hebrew language (it is recommended to use some translation software such as Google Translate in order to translate into another language).

For more examples, please refer to the Documentation

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Contributors

We thank the following people who contributed to this project:

Ram Michaeli

Gal Israeli

(back to top)

Contact

Ram Michaeli - [email protected]

Project Link: https://github.com/RamMichaeli17/Erdos-Renyl-Model-for-generating-Random-Graphs

(back to top)