igraphGraspi 1.0.0

Graspi igraph

graspi_igraph

Python-Igraph is a graph-based library contender for the library that works with the GraSPI package.

This repository contains the implementation to test basic algorithm requirements that need to be met for this package to work similarly to GraSPI. The basic algorithm requirements include:

• Construction of graphs
• Graph Filtering
• Determine the number of connected components
• Determine the shortest path from the bottom boundary to all black vertices until the white vertices are met
• Graph visualization

Installation

Downloads needed can be found in requirements.txt

pip install igraph 
pip install matplotlib

If there are any issues with installation, please visit: https://python.igraph.org/en/stable/

To Generate Test Files

Test-input-files can be generated via the testFileMaker.py by calling the function testFileMaker(num,depth,textFileName)

• the function takes in a number of rows for the test graph, the depth of the graph, and the output file name
• to generate 2D graphs, set the depth to 1

There are existing test files that can be accessed in the 2D-testFile and 3D-testFile folders

2D Testfile Example

# generates a 10x10 2D graph input-file
testFileMaker(10,1,"output.txt")

3D Testfile Example

# generates a 10x10x5 3D graph input-file
testFileMaker(10,5,"output.txt")

To Test Algorithms

Import the igraph_testing.py file to access the functionalities

To generate graphs, call the generateGraph(file) function which takes in a input-file name

• returns a graph

generateGraph("2D-testFile/testFile-10-2D.txt")   # utilizing the test file found in 2D-testFiles folder

To filter graphs, call filterGraph(graph) function which takes in a graph object

• can pass a graph generated by generateGraph(file)
• returns a filtered graph

g = generateGraph("2D-testFile/testFile-10-2D.txt")     # utilizing the test file found in 2D-testFiles folder
fg = filterGraph(g)

To determine the connected components of the filtered graph, call connected_components() function

print(fg.connected_components())

The number of connected components can be found by taking the length of the result produced by the connected_components function

print(len(fg.connected_components())) 

The shortest path between the bottom boundary to all the black vertices until the white vertices are reached can be found by calling the function shortest_path(fiteredGraph)

• returns a dictionary of vertices and their corresponding path

shortest_path(fg)    #fg is a filtered graph object

To visualize graphs

• for 2d graphs, call visual2D(graph)

g = generateGraph("2D-testFile/testFile-10-2D.txt")     # utilizing the test file found in 2D-testFiles folder
visual2D(g)

• for 3d graphs, call visual3D(graph)

g = generateGraph("3D-testFile/testFile-10-3D.txt")     # utilizing the test file found in 2D-testFiles folder
visual3D(g)

Both take in a graph object