文件列表:

.gradle (0, 2022-07-04)
.gradle\6.7 (0, 2022-07-04)
.gradle\6.7\executionHistory (0, 2022-07-04)
.gradle\6.7\executionHistory\executionHistory.lock (17, 2022-07-04)
.gradle\6.7\fileChanges (0, 2022-07-04)
.gradle\6.7\fileChanges\last-build.bin (1, 2022-07-04)
.gradle\6.7\fileHashes (0, 2022-07-04)
.gradle\6.7\fileHashes\fileHashes.lock (17, 2022-07-04)
.gradle\6.7\gc.properties (0, 2022-07-04)
.gradle\buildOutputCleanup (0, 2022-07-04)
.gradle\buildOutputCleanup\buildOutputCleanup.lock (17, 2022-07-04)
.gradle\buildOutputCleanup\cache.properties (49, 2022-07-04)
.gradle\checksums (0, 2022-07-04)
.gradle\checksums\checksums.lock (17, 2022-07-04)
.gradle\configuration-cache (0, 2022-07-04)
.gradle\configuration-cache\gc.properties (0, 2022-07-04)
.gradle\vcs-1 (0, 2022-07-04)
.gradle\vcs-1\gc.properties (0, 2022-07-04)
.idea (0, 2022-07-04)
.idea\artifacts (0, 2022-07-04)
.idea\artifacts\Ex2_jar.xml (1799, 2022-07-04)
.idea\misc.xml (256, 2022-07-04)
.idea\modules.xml (246, 2022-07-04)
.idea\runConfigurations.xml (337, 2022-07-04)
.idea\uiDesigner.xml (8792, 2022-07-04)
.idea\vcs.xml (180, 2022-07-04)
Ex2.iml (4504, 2022-07-04)
Ex2.jar (25376074, 2022-07-04)
Ex2.java (1362, 2022-07-04)
Ex2.txt (463, 2022-07-04)
GUI.java (28689, 2022-07-04)
META-INF (0, 2022-07-04)
META-INF\MANIFEST.MF (39, 2022-07-04)
api (0, 2022-07-04)
api\DirectedWeightedGraph.java (3244, 2022-07-04)
api\DirectedWeightedGraphAlgorithms.java (3655, 2022-07-04)
api\EdgeData.java (1059, 2022-07-04)
... ...

Project review

Graph calculator is a simple GUI app capable of creating, loading, and editing weighted directed graphs. After receiving/loading a graph from a JSON file it can be used as the basis for many graph operations, such as finding the shortest path between two nodes, finding the center, etc...
The manipulated graph can be saved to json file.

How to run the calculator

To run the calculator you should first create a JSON file that holds a graph. You can check the "data" directory in the main repository to see some examples of graphs files.
Download the jar file found in the top level of the repository, and run it from a terminal using the following command:
java -jar Ex2.jar graph.json , replacing, of course, graph.json with your file name.
Now you should be looking at a visual representation of your graph.

from now on, all the interactions with the app will be done through the GUI.

Editing the graph

You can change the graph components (Nodes and edges) via the "Edit" tab, all changes will be shown immediatly at the screen. changes can be save via the "File" tab

Graph Algorithms

 The calculator provides several operations(algorithms) to run on the graph.

• Is connected: check if the graph is strongly connected
• Shortest path dist: get a source and destination nodes from the user and return the distance of the shortest path between them
• Shortest path: get a source and destination nodes from the user and color all the edges of the path with Black (default is red)
• Center: Mark the Center node of the graph
• Tsp-Traveling salesmen problem: The calculator receives a list of nodes and returns the shortest path it can find that traverse them all. The user should insert the nodes id separated by comma.

The algorithms behind the scenes

• Is connected: Using BFS, we "color" the graph vertices with white, black, and gray starting from an arbitrary node. after The BFS is done we look for white nodes, if no white node is found it means that there is a path from the source node to any other node in the graph. However, this does not guarantee connectivity since we deal we directed graph, so we recolor the nodes with white, reverse all the edges and perform another BFS. if again we can't find white nodes then the graph is Strongly connected


• Shortest path - distance: We use our implementation of Dijkstra's algorithm on the source node, get the resulting distances' array, and simply return the distance to the required vertex
• Shortest path: We call Dijkstra's algorithm on the source node, fetch the parents array it returns, and use it to calculate the path to the destination vertex
• Center: The implementation is rather simple, we first compute the eccentricity of each node (eccentricity:wikipedia) using Dijkstra's algorithm on each vertex and taking the max distance. then, we pick the vertex with the smallest eccentricy as the center
• Tsp-Traveling salesmen problem: We start from some random node from the list, perform the Dijkstra algorithm, and travel to the closest Unvisited node from the list, we keep doing that until we reached all the nodes from the list. following this method will yield us a valid path, albeit not necessarily the shortest. we repeat this process for each node in the list, each time picking another vertex as a starting point. in the end we return the shortest path we've found

Dijkstra's algorithms

Dijkstra's algorithm played a major part in our work, being part of almost every algorithm. After our first implementation of the algorithm (using regular priority queue) proved to be too slow for our purposes, we implemented it again using a Fibonacci heap. The implementation for Fibonacci is an open-source code that can be found here.
Using the new implementation, we managed to greatly improve our complexity cutting between 70 to 80 percent of the running time.

UML diagram


Running time analysis

We tested the algorithms on graphs with rising number of nodes to see how efficient they are.  
nodes to visit = we look for a path containing all these nodes.
In graphs bigger than 100,000 nodes some of the heavier algorithms run out of memory. The code was executed on a 5-year-old laptop, on a newer machine the results would be way better

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：