In this part, you will implement the algorithm to find the shortest path in a gr
ID: 3902126 • Letter: I
Question
In this part, you will implement the algorithm to find the shortest path in a graph.
ShorestPath.java: This class must only have a single method that expects a Graph object, a starting node, and an end node as arguments. The function returns the total weight of the shortest path found between these two nodes. The following data structures must be used:
• A HashMap to keep track of computed distances between starting node and every other node.
• A PriorityQueue to track edges.
• A HashSet to keep track of visited nodes.
Here are my Graph.java and Edge.java classes:
import java.util.ArrayList;
import java.util.List;
class Edge implements Comparable<Edge>{
private Integer from;
private Integer to;
private int weight;
public Edge(Integer from, Integer to, int weight)
{
this.from=from;
this.to=to;
this.weight=weight;
}
public Integer getFrom()
{
return from;
}
public Integer getTo()
{
return to;
}
public int getWeight()
{
return weight;
}
public int hashCode()
{
return this.hashCode();
}
public boolean equals(Object o)
{
if(o instanceof Edge)
{
if(((Edge)o).getWeight()==weight)
return true;
else
return false;
}
return false;
}
public String toString()
{
return "From: "+from+" To: "+to+" Weight: "+weight;
}
@Override
public int compareTo(Edge edge) {
// TODO Auto-generated method stub
if(this.weight<edge.weight)
return -1;
else if(this.weight==edge.weight)
return 0;
else
return 1;
}
}
class Graph{
private int[][] matrix;
public Graph()
{
matrix=null;
}
public Graph(int[][] matrix)
{
this.matrix=matrix;
}
public boolean hasEdge(Integer from, Integer to)
{
return matrix[from][to]!=0;
}
public int weight(Integer from, Integer to)
{
return matrix[from][to];
}
public List<Edge> getOutgoingEdges(Integer from)
{
List<Edge> list=new ArrayList<Edge>();
for(int i=0; i<matrix[0].length; i++)
{
if(matrix[from][i]!=0)
{
Edge edge=new Edge(from, i, matrix[from][i]);
list.add(edge);
}
}
return list;
}
public List<Integer> getNodes()
{
List<Integer> list=new ArrayList<Integer>();
for(int i=0; i<matrix.length; i++)
list.add(i);
return list;
}
public String toString()
{
String result="";
for(int i=0; i<matrix.length;i++)
{
for(int j=0; j<matrix.length; j++)
{
result=result+matrix[i][j]+" ";
}
result+=" ";
}
return result;
}
}
Explanation / Answer
ShortestPath.java
import java.awt.Color;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JPanel;
import org.gephi.algorithms.shortestpath.AbstractShortestPathAlgorithm;
import org.gephi.algorithms.shortestpath.BellmanFordShortestPathAlgorithm;
import org.gephi.algorithms.shortestpath.DijkstraShortestPathAlgorithm;
import org.gephi.graph.api.Edge;
import org.gephi.graph.api.GraphController;
import org.gephi.graph.api.GraphModel;
import org.gephi.graph.api.Node;
import org.gephi.tools.spi.MouseClickEventListener;
import org.gephi.tools.spi.NodeClickEventListener;
import org.gephi.tools.spi.Tool;
import org.gephi.tools.spi.ToolEventListener;
import org.gephi.tools.spi.ToolSelectionType;
import org.gephi.tools.spi.ToolUI;
import org.gephi.ui.tools.plugin.ShortestPathPanel;
import org.gephi.visualization.VizController;
import org.openide.util.Lookup;
import org.openide.util.NbBundle;
import org.openide.util.lookup.ServiceProvider;
@ServiceProvider(service = Tool.class)
public class ShortestPath implements Tool {
//Architecture
private ToolEventListener[] listeners;
private ShortestPathPanel shortestPathPanel;
//Settings
private Color color;
private boolean settingEdgeSourceColor;
//State
private Node sourceNode;
public ShortestPath() {
//Default settings
color = Color.RED;
}
@Override
public void select() {
settingEdgeSourceColor = !VizController.getInstance().getVizModel().isEdgeHasUniColor();
VizController.getInstance().getVizModel().setEdgeHasUniColor(true);
VizController.getInstance().getVizConfig().setEnableAutoSelect(false);
}
@Override
public void unselect() {
listeners = null;
sourceNode = null;
shortestPathPanel = null;
VizController.getInstance().getVizModel().setEdgeHasUniColor(settingEdgeSourceColor);
VizController.getInstance().getVizConfig().setEnableAutoSelect(true);
}
@Override
public ToolEventListener[] getListeners() {
listeners = new ToolEventListener[2];
listeners[0] = new NodeClickEventListener() {
@Override
public void clickNodes(Node[] nodes) {
Node n = nodes[0];
if (sourceNode == null) {
sourceNode = n;
shortestPathPanel.setResult("");
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status2"));
} else if (n != sourceNode) {
color = shortestPathPanel.getColor();
Node targetNode = n;
GraphController gc = Lookup.getDefault().lookup(GraphController.class);
GraphModel gm = gc.getGraphModel();
AbstractShortestPathAlgorithm algorithm;
if (gm.isDirected()) {
algorithm = new BellmanFordShortestPathAlgorithm(gm.getDirectedGraphVisible(), sourceNode);
} else {
algorithm = new DijkstraShortestPathAlgorithm(gm.getGraphVisible(), sourceNode);
}
algorithm.compute();
double distance;
if ((distance = algorithm.getDistances().get(targetNode)) != Double.POSITIVE_INFINITY) {
targetNode.setColor(color);
VizController.getInstance().selectNode(targetNode);
Edge predecessorEdge = algorithm.getPredecessorIncoming(targetNode);
Node predecessor = algorithm.getPredecessor(targetNode);
while (predecessorEdge != null && predecessor != sourceNode) {
predecessorEdge.setColor(color);
VizController.getInstance().selectEdge(predecessorEdge);
predecessor.setColor(color);
VizController.getInstance().selectNode(predecessor);
predecessorEdge = algorithm.getPredecessorIncoming(predecessor);
predecessor = algorithm.getPredecessor(predecessor);
}
predecessorEdge.setColor(color);
VizController.getInstance().selectEdge(predecessorEdge);
sourceNode.setColor(color);
VizController.getInstance().selectNode(sourceNode);
shortestPathPanel.setResult(NbBundle.getMessage(ShortestPath.class, "ShortestPath.result", distance));
} else {
//No path
shortestPathPanel.setResult(NbBundle.getMessage(ShortestPath.class, "ShortestPath.noresult"));
}
sourceNode = null;
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
}
}
};
listeners[1] = new MouseClickEventListener() {
@Override
public void mouseClick(int[] positionViewport, float[] position3d) {
if (sourceNode != null) {
//Cancel
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
sourceNode = null;
} else {
VizController.getInstance().resetSelection();
}
}
};
return listeners;
}
@Override
public ToolUI getUI() {
return new ToolUI() {
@Override
public JPanel getPropertiesBar(Tool tool) {
shortestPathPanel = new ShortestPathPanel();
shortestPathPanel.setColor(color);
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
return shortestPathPanel;
}
@Override
public String getName() {
return NbBundle.getMessage(ShortestPath.class, "ShortestPath.name");
}
@Override
public Icon getIcon() {
return new ImageIcon(getClass().getResource("/org/gephi/tools/plugin/resources/shortestpath.png"));
}
@Override
public String getDescription() {
return NbBundle.getMessage(ShortestPath.class, "ShortestPath.description");
}
@Override
public int getPosition() {
return 140;
}
};
}
@Override
public ToolSelectionType getSelectionType() {
return ToolSelectionType.SELECTION;
}
}import java.awt.Color;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JPanel;
import org.gephi.algorithms.shortestpath.AbstractShortestPathAlgorithm;
import org.gephi.algorithms.shortestpath.BellmanFordShortestPathAlgorithm;
import org.gephi.algorithms.shortestpath.DijkstraShortestPathAlgorithm;
import org.gephi.graph.api.Edge;
import org.gephi.graph.api.GraphController;
import org.gephi.graph.api.GraphModel;
import org.gephi.graph.api.Node;
import org.gephi.tools.spi.MouseClickEventListener;
import org.gephi.tools.spi.NodeClickEventListener;
import org.gephi.tools.spi.Tool;
import org.gephi.tools.spi.ToolEventListener;
import org.gephi.tools.spi.ToolSelectionType;
import org.gephi.tools.spi.ToolUI;
import org.gephi.ui.tools.plugin.ShortestPathPanel;
import org.gephi.visualization.VizController;
import org.openide.util.Lookup;
import org.openide.util.NbBundle;
import org.openide.util.lookup.ServiceProvider;
@ServiceProvider(service = Tool.class)
public class ShortestPath implements Tool {
//Architecture
private ToolEventListener[] listeners;
private ShortestPathPanel shortestPathPanel;
//Settings
private Color color;
private boolean settingEdgeSourceColor;
//State
private Node sourceNode;
public ShortestPath() {
//Default settings
color = Color.RED;
}
@Override
public void select() {
settingEdgeSourceColor = !VizController.getInstance().getVizModel().isEdgeHasUniColor();
VizController.getInstance().getVizModel().setEdgeHasUniColor(true);
VizController.getInstance().getVizConfig().setEnableAutoSelect(false);
}
@Override
public void unselect() {
listeners = null;
sourceNode = null;
shortestPathPanel = null;
VizController.getInstance().getVizModel().setEdgeHasUniColor(settingEdgeSourceColor);
VizController.getInstance().getVizConfig().setEnableAutoSelect(true);
}
@Override
public ToolEventListener[] getListeners() {
listeners = new ToolEventListener[2];
listeners[0] = new NodeClickEventListener() {
@Override
public void clickNodes(Node[] nodes) {
Node n = nodes[0];
if (sourceNode == null) {
sourceNode = n;
shortestPathPanel.setResult("");
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status2"));
} else if (n != sourceNode) {
color = shortestPathPanel.getColor();
Node targetNode = n;
GraphController gc = Lookup.getDefault().lookup(GraphController.class);
GraphModel gm = gc.getGraphModel();
AbstractShortestPathAlgorithm algorithm;
if (gm.isDirected()) {
algorithm = new BellmanFordShortestPathAlgorithm(gm.getDirectedGraphVisible(), sourceNode);
} else {
algorithm = new DijkstraShortestPathAlgorithm(gm.getGraphVisible(), sourceNode);
}
algorithm.compute();
double distance;
if ((distance = algorithm.getDistances().get(targetNode)) != Double.POSITIVE_INFINITY) {
targetNode.setColor(color);
VizController.getInstance().selectNode(targetNode);
Edge predecessorEdge = algorithm.getPredecessorIncoming(targetNode);
Node predecessor = algorithm.getPredecessor(targetNode);
while (predecessorEdge != null && predecessor != sourceNode) {
predecessorEdge.setColor(color);
VizController.getInstance().selectEdge(predecessorEdge);
predecessor.setColor(color);
VizController.getInstance().selectNode(predecessor);
predecessorEdge = algorithm.getPredecessorIncoming(predecessor);
predecessor = algorithm.getPredecessor(predecessor);
}
predecessorEdge.setColor(color);
VizController.getInstance().selectEdge(predecessorEdge);
sourceNode.setColor(color);
VizController.getInstance().selectNode(sourceNode);
shortestPathPanel.setResult(NbBundle.getMessage(ShortestPath.class, "ShortestPath.result", distance));
} else {
//No path
shortestPathPanel.setResult(NbBundle.getMessage(ShortestPath.class, "ShortestPath.noresult"));
}
sourceNode = null;
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
}
}
};
listeners[1] = new MouseClickEventListener() {
@Override
public void mouseClick(int[] positionViewport, float[] position3d) {
if (sourceNode != null) {
//Cancel
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
sourceNode = null;
} else {
VizController.getInstance().resetSelection();
}
}
};
return listeners;
}
@Override
public ToolUI getUI() {
return new ToolUI() {
@Override
public JPanel getPropertiesBar(Tool tool) {
shortestPathPanel = new ShortestPathPanel();
shortestPathPanel.setColor(color);
shortestPathPanel.setStatus(NbBundle.getMessage(ShortestPath.class, "ShortestPath.status1"));
return shortestPathPanel;
}
@Override
public String getName() {
return NbBundle.getMessage(ShortestPath.class, "ShortestPath.name");
}
@Override
public Icon getIcon() {
return new ImageIcon(getClass().getResource("/org/gephi/tools/plugin/resources/shortestpath.png"));
}
@Override
public String getDescription() {
return NbBundle.getMessage(ShortestPath.class, "ShortestPath.description");
}
@Override
public int getPosition() {
return 140;
}
};
}
@Override
public ToolSelectionType getSelectionType() {
return ToolSelectionType.SELECTION;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.