In this project we were asked to display the graph visually,
we chose to represent the graph using Java Swing with a panel that allows uploading a graph using a JSON file.
Saving a graph to a JSON file, adding and deleting a vertex, adding and deleting an Edge,
Access to see the whole process of the algorithms in real time (Shorted path, isConnected, Travelling Salesman Problem (TSP), Center).
In addition, we added a help button that links directly to Git.
Content
Object-Oriented Programming Exercise 2 - Directed Weighted Graph:
This Exercise is dedicated to the design and implementation of data structures and algorithms on graphs (directed and weighted). As usual, it is recommended to start planning the Exercise (without a code) and only after you have a basic plan you should move on to the implementation phase of the code.
The Exercise are defined as interfaces in the epic package, you need to plan and implement two really key ones: Interface of a weighted directed graph Interface of algorithms on graphs (weighted tuners).
When the Exercise is checked through three public static functions, place fences in the Ex2.java class - note that you must complete the three steps below - through which your Exercise will be checked. Directed Graph Class - should support uploading json files, please note: We have attached some json files of graphs for you.
"The origins of graph theory are humble, even frivolous 📍"
Unified Modeling Language (UML) :
Click the image for zoom in.
As you can see in UML we implement the main Directed Weighted Graph interfaces that with the help of other interfaces and class we can build the whole project. The interface is implemented DirectedWeightedGraphAlgorithm the EdgeData, NodeData, GeoLocation.
We have built a JSON Operation class which receives a JSON file and initializes the entire graph using the interfaces mentioned above. Sends all data to DirectedWeightedGraph, so we can build a graph. In the same class there are options for saving a given graph as a JSON file.
The DirectedWeightedGraphAlgorithms class contains all the algorithms that can be run on the given graph such as DijkstraAlgorithm and BFS, in addition you can find other functions related to solving various problems in directed graphs.
In addition to all the departments and interfaces mentioned above, we have prepared a test folder that checks all the functions that are in the project, from the simplest function to the most complex function and algorithms that appear in the project.
We have prepared a folder for the graphical interface which contains all the departments of the interface we need from the visual graph presentation to the structure and execution of the algorithms within it, the option to delete and add edges and vertices.
In this project we used a number of algorithms, we will present the algorithms that were implemented in this project.
Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Graph Center A graph with central points colored red. These are the three vertices A such that d(A, B) ≤ 3 for all vertices B. Each black vertex is a distance of at least 4 from some other vertex.
Connected Graph A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on n >= 2 nodes are disconnected.
Traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
These analyze were tested on a computer with an Intel i7 processor and 16 GB of RAM WIN10
-
Graph size: 1000, Shortest path Run time ~0.027 seconds, Center ~2.158 seconds, isConnected ~0.007 seconds
-
Graph size: 10000, Shortest path Run time ~0.14 seconds, Center ~314.63 seconds, isConnected ~0.153 seconds
-
Graph size: 100000, Shortest path ~1.345 seconds, Center timeout, isConnected ~0.946 seconds
-
Graph size: 1000000. Shortest path x seconds, Center x seconds, isConnected x seconds.
We were unable to generate a JSON file under the IDE (ERROR: HEAP MEMORY jumped at the time of writing) of a million-sized graph where each vertex has an average of 20 edges.
Despite this, we were able to generate a maximum JSON file without error with 150,000 vertices where the rank of each vertex is 20 on average.
Here are the results on 150,000 vertices:
Graph size: 150000. Shortest path 1.03 seconds, Center timeout, isConnected 1.275 seconds.
- Note: (The Graphs is with an average edge rank of 20 edges per vertex: incoming + outgoing - total 20)
Jar file:
-
THE JAR MUST BE IN THE PROJECT FOLDER!!
-
Jar file name: Ex2.jar
Run Jar file in commend line:
java -jar Ex2.jar G1.json
In this project we used some external libraries in the JAVA language, in order to make life easier these libraries are located within the project called external libraries.
First, it's important to make sure you clone this project in IntelliJ through Terminal. To be sure:
git clone https://github.com/GalKoaz/OOP-Ex2.git
Second, in this project we used some external libraries in the JAVA language, in order to make life easier these libraries are located within the project called external libraries. In order to update these libraries in this project, we will do the following:
File -> Project Structure -> Libraries and select the folder with all external libraries.
Java SDK Verison: 15
Project language level: 15 - Text blocks
External libraries:
- gson-2.8.2
- javax.json-1.1.4
- javax.ws.rs-api-2.1.1
- json-simple-1.1.1
Contact Top▲
Gal - here
Amir - here
Project Link: here
Copyright © This Project was created on Dec 08, 2021, by Gal & Amir.