Skip to content

Latest commit

 

History

History
201 lines (179 loc) · 10.8 KB

README.md

File metadata and controls

201 lines (179 loc) · 10.8 KB

Instructions

  • Clone the repository, or download the zip file and unzip it.
  • Run the command mvn package.
  • This will build the project, create a JAR file in the targets/ folder and run all tests.
  • Opening the project folder in IntelliJ as a project will also enable running the tests and inspecting the code.

API Functions

The API is contained in the GraphData.java file at src/main/java/ location. The various functions implemented are listed below:

  • boolean parseGraph(String filepath) : Import DOT file to create a JGrapht graph object. Returns true if successful else false.
  • String toString() : Display graph information such as node and edge number in string format. Returns a String.
  • boolean outputGraph(String filepath) : Writes graph details to a file at filepath. Returns true if successful else false.
  • boolean addNode(String label) : Adds a node to the graph. Returns true if successful else false.
  • boolean addNodes(String[] labels) : Adds a list of nodes to the graph. Returns true if successful else false.
  • boolean addEdge(String srcLabel, String dstLabel) : Adds an edge to the graph. Returns true if successful else false.
  • boolean outputDOTGraph(String path) : Outputs the JGraphT graph object to a DOT file at the specified path. Returns true if successful else false.
  • void outputGraphics(String path, String format) : Outputs the JGraphT graph object to a file with file format format at the specified path.

How to use (Example code)

  • GraphData object creation
GraphData graphApi = new GraphData();  
  • Parse a graph
graphApi.parseGraph("src/main/resources/example.dot");

Expected Output: ![[Pasted image 20231011191820.png]]

  • Display graph data
graphApi.toString();

Expected Output:

Number of nodes: 4  
Node labels: [A, B, C, D]  
Number of edges: 3  
Node and edge directions: (A -> B), (A -> C), (A -> D)
  • Output graph data to file
graphApi.outputGraph("src/main/resources/output.txt");

Expected Output (in output.txt):

Number of nodes: 4  
Node labels: [A, B, C, D]  
Number of edges: 3  
Node and edge directions: (A -> B), (A -> C), (A -> D)
  • Add nodes
graphApi.addNode("Y");
graphApi.addNodes(new String[]{"Z", "X"});
  • Add edge
graphApi.addEdge("Z", "C");
  • Output graph in DOT file format
graphApi.outputDOTGraph("src/main/resources/gen_graph.dot");

Expected Output (in gen_graph.dot):

strict digraph G {  
A;  
B;  
C;  
D;
Y;  
Z;
X;  
A -> B;  
A -> C;  
A -> D;  
Z -> C;  
}
  • Output graph as PNG file
graphApi.outputGraphics("src/main/resources/", "png");
  • GraphSearch API
Path path = graphApi.GraphSearch("C","D", Algorithm.BFS); 
// Algorithm.DFS can also be used.
path.printPath();

Expected Output

Using BFS
C->A->D

Project Part 3

Refactors

Template Pattern

The Template Pattern involves:

  • Creating an abstract class (GraphSearch) to define common graph search steps.
  • Extending this template with concrete subclasses (BFS and DFS) that implement specific traversal methods by overriding abstract template methods.
  • This structure provides a shared algorithm skeleton while allowing BFS and DFS to have their unique implementations.

Strategy Pattern

The Strategy Pattern involves:

  • Defining a strategy interface (SearchStrategy) that declares a method signature for the algorithm.
  • Creating concrete strategy classes (BFS and DFS) that implement the strategy interface with their specific algorithm implementations.
  • Implementing a context class (Context) that holds a reference to the strategy interface and utilizes it to execute the selected strategy.
  • Utilizing the Context class in the main code to dynamically switch between different strategies (BFS or DFS) based on input.

Random Walk Search

Exampe graph (from Canvas) ![[Pasted image 20231203183455.png]]

Running this code,

Path path = graphApi.GraphSearch("a","c", Algorithm.RWS);  
path.printPath();

gives the following outputs - ![[Pasted image 20231203183730.png]] ![[Pasted image 20231203183757.png]] ![[Pasted image 20231203183807.png]]

Commits

main

bfs

dfs

refactors

Template & Strategy patterns

Random Walk Search

PR Review commits