GRAPHS AND ALGORITHMS

Versions

• v1.0-beta
• v1.0
• v1.1
• v1.2
• v2.0 - Latest stable release • What's new?

Goal

The project was focused on:

• implementation of unweighted undirected graphs that cannot have multiple edges nor loops.
• implementation of chosen algorithms involved with graphs.

Initially, the project was created to the needs of my diploma thesis 'Algorithmic aspects of domination problem in graphs', where I included implementation of an approximation algorithm for computing maximum connected dominating set in given graph. The implementation of the algorithm required defining specific data structure. Despite possibility to use already accessible data structures in Java, I decided to implement the structure myself in case of possible improvements and changes I could be willing to deploy - hence I defined Graph class. The next case was to decide about vertex implementation. And simply because of an idea:

what if there is a need for each or some vertex to store multiple values?

...I decided to create a Vertex class as well. However, it was important to me to keep it simple for a user. Thus, I decided that Vertex should be an inner non-static class of Graph, so the user do not have to worry about having an object instance and use only a number as a reference. To make it possible, I implemented methods that map numbers to vertex objects and the other way.

After a graduation, I decided to improve the quality of written code and add new features. However, my goal was to keep the assumption about the implementation I determined in v1.0-beta. Therefore, I didn't implement palpable representation of edges, since the implementation of vertex neighbourhood was satisfactory in such a case. The outcome of my work has been committed on this repository.

Features

• Create an empty graph (order-zero graph / null graph)
• Create a graph from a given file
• Create a complete graph (including an empty)
• Display a graph structure (all vertices and for each their [open] neighbourhood list and stored data)
• Get all vertices of the graph
• Get neighbours of a given vertex
• Get data stored in a given vertex
• Set data stored in a given vertex
• Add a vertex to the graph (with or without stored data)
• Add vertices to the graph
• Remove a vertex from the graph
• Remove vertices from the graph
• Connect vertices
• Disconnect vertices
• Check if a graph contains given vertex/vertices
• Check if a subgraph or a graph is connected
• Check if a subgraph or a graph is bipartite
• Check if a subgraph or a graph is complete
• Check if a given subset of vertices is a connected dominating set of the graph
• Check if a given subset of vertices is an independent set of the graph
• Modified implementation of breadth-first search algorithm
• Modified implementation of depth-first search algorithm
• Compute a minimal dominating set in the graph
• Compute a minimal connected dominating set in the graph
• Compute a maximal independent set in the graph
• Map a graph to a complete graph of the same size

Run Configuration

To run this project, it is recommended to add an environment variable to the run configuration:

ALLOW and set its value to true or false - depending on wanted behaviour.

if(ALLOW) -> runs basic and exceptions test of the Graph implementation
else -> runs only basic test of Graph implementation

Note that if you do not add an environment variable to the run configuration of a project, you can expect to run the basic test only.

Dependencies

Lombok (1.18.30)

JetBrains Annotations (24.1.0)

JUnit Jupiter API (5.10.1)

JUnit Jupiter Params (5.10.1)