package com.kartik.dj;
public class ProgramSolver {
public static void main(String[] args) {
String input1 = "{1-2-30#2-3-25#3-4-30#4-5-45#5-6-30#6-7-15#7-8-60#8-9-40,10-11-45#11-4-60#4-12-60#12-13-45#13-14-30#14-15-35,1-3-40#3-4-25#4-16-30#16-17-15#17-18-20#18-19-30#19-20-25,21-12-30#12-17-180#17-22-45}";
String input2 = "12#18";
CandidateCode dj = new CandidateCode();
dj.quickstroute(input1, input2);
}
}
public class ProgramSolver {
public static void main(String[] args) {
String input1 = "{1-2-30#2-3-25#3-4-30#4-5-45#5-6-30#6-7-15#7-8-60#8-9-40,10-11-45#11-4-60#4-12-60#12-13-45#13-14-30#14-15-35,1-3-40#3-4-25#4-16-30#16-17-15#17-18-20#18-19-30#19-20-25,21-12-30#12-17-180#17-22-45}";
String input2 = "12#18";
CandidateCode dj = new CandidateCode();
dj.quickstroute(input1, input2);
}
}
Step 2
package com.kartik.dj;
/**
* Created by Kartik Chandra Mandal on 26/01/2016.
*/
import java.io.IOException;
import java.util.*;
public class CandidateCode {
private int size;
private HashMap<Integer, Double> weight; // store weights for each vertex
private HashMap<Integer, Integer> previousNode; // store previous vertex
private PriorityQueue<Integer> pq; // store vertices that need to be visited
private WeighedDigraph graph; // graph object
CandidateCode() {
}
/**
* @return string representation of digraph
*/
public String getWeight(int from, int to) {
ArrayList<WeighedDigraphEdge> currentEdges = graph.edgesOf(from);
String out = "";
out += from + "-";
for (WeighedDigraphEdge edge : currentEdges) {
if (to == edge.to())
out += edge.to() + "-" + edge.weight() + ",";
}
return out;
}
public String getWeightSecond(int from, int to) {
ArrayList<WeighedDigraphEdge> currentEdges = graph.edgesOf(from);
String out = "";
out += from + "-";
for (WeighedDigraphEdge edge : currentEdges) {
if (to == edge.to())
out += edge.to() + "-" + edge.weight() + "#";
}
return out;
}
public String convertData(ArrayList<Integer> nodePath) {
Integer[] stockArr = new Integer[nodePath.size()];
for (int j = 0; j < nodePath.size(); j++) {
stockArr[j] = nodePath.get(j);
}
StringBuffer sb = new StringBuffer();
sb.append("{ NC,");
for (int i = 0; i < stockArr.length; i++) {
if (i == 0) {
int first = stockArr[i];
int second = stockArr[i + 1];
sb.append(getWeight(first, second));
} else if (i > 0 && i < stockArr.length - 1) {
int first = stockArr[i];
int second = stockArr[i + 1];
if (i == stockArr.length - 2) {
sb.append(getWeight(first, second));
} else {
sb.append(getWeightSecond(first, second));
}
}
}
sb.append(" NC }");
System.out.println(sb.toString());
return sb.toString();
}
/**
* Instantiate algorithm providing graph
*
* @param graph
* WeighedDigraph graph
*/
public CandidateCode(WeighedDigraph graph) {
this.graph = graph;
size = graph.size();
}
/**
* Calculate shortest path from A to B
*
* @param vertexA
* source vertex
* @param vertexB
* destination vertex
* @return list of vertices composing shortest path between A and B
*/
public ArrayList<Integer> shortestPath(int vertexA, int vertexB) {
previousNode = new HashMap<Integer, Integer>();
weight = new HashMap<Integer, Double>();
pq = new PriorityQueue<Integer>(size, PQComparator);
/* Set all distances to Infinity */
for (int vertex : graph.vertices())
weight.put(vertex, Double.POSITIVE_INFINITY);
previousNode.put(vertexA, -1); // negative means no previous vertex
weight.put(vertexA, 0.0); // weight to has to be 0
pq.add(vertexA); // enqueue first vertex
while (pq.size() > 0) {
int currentNode = pq.poll();
ArrayList<WeighedDigraphEdge> neighbors = graph
.edgesOf(currentNode);
if (neighbors == null)
continue;
for (WeighedDigraphEdge neighbor : neighbors) {
int nextVertex = neighbor.to();
double newDistance = weight.get(currentNode)
+ neighbor.weight();
if (weight.get(nextVertex) == Double.POSITIVE_INFINITY) {
previousNode.put(nextVertex, currentNode);
weight.put(nextVertex, newDistance);
pq.add(nextVertex);
} else {
if (weight.get(nextVertex) > newDistance) {
previousNode.put(nextVertex, currentNode);
weight.put(nextVertex, newDistance);
}
}
}
}
/* Path from A to B will be stored here */
ArrayList<Integer> nodePath = new ArrayList<Integer>();
/*
* We are reverse walking points to get to the beginning of the path.
* Using temporary stack to reverse the order of node keys stored in
* nodePath.
*/
Stack<Integer> nodePathTemp = new Stack<Integer>();
nodePathTemp.push(vertexB);
int v = vertexB;
while (previousNode.containsKey(v) && previousNode.get(v) >= 0 && v > 0) {
v = previousNode.get(v);
nodePathTemp.push(v);
}
// Put node in ArrayList in reversed order
while (nodePathTemp.size() > 0)
nodePath.add(nodePathTemp.pop());
convertData(nodePath);
return nodePath;
}
/**
* Comparator for priority queue
*/
public Comparator<Integer> PQComparator = new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
if (weight.get(a) > weight.get(b)) {
return 1;
} else if (weight.get(a) < weight.get(b)) {
return -1;
}
return 0;
}
};
private static String[] dataSplit(String colData) {
String[] cols = colData.split(Constant.constantD);
return cols;
}
public String[] quickstroute(String first, String second) {
WeighedDigraph graph;
try {
String[] cols = dataSplit(second);
int source = Integer.parseInt(cols[0]);
int destination = Integer.parseInt(cols[1]);
graph = new WeighedDigraph(first);
CandidateCode finder = new CandidateCode(graph);
finder.shortestPath(source, destination);
} catch (IOException e) {
System.out.println();
}
return null;
}
}
Step 3>
package com.kartik.dj;
public interface Constant {
public final String constantA = "#|\\,";
public final String constantB = "-";
public final String constantC = "[#,]";
public final String constantD = "#";
}
Step 4>
package com.kartik.dj;
/**
* Created by Kartik Chandra Mandal on 26/01/2016.
*/
public class WeighedDigraphEdge {
private int from, to;
private int weight;
/**
* Construct graph edge
* @param from
* @param to
* @param weight
*/
public WeighedDigraphEdge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
/**
* @return from vertex
*/
public int from() { return from; }
/**
* @return to vertex
*/
public int to() { return to; }
/**
* @return weight of edge between from() and to()
*/
public int weight() { return weight; }
}
Step 5>
package com.kartik.dj;
/**
* Created by Kartik Chandra Mandal on 26/01/2016.
*/
import java.util.HashMap;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.io.IOException;
public class WeighedDigraph {
private HashMap<Integer, ArrayList<WeighedDigraphEdge>> adj = new HashMap(); // adjacency-list
public WeighedDigraph() {
}
/**
*
* @param colData
* @return
*/
private static String[] colmnSplit(String colData) {
String[] cols = colData.split(Constant.constantA);
return cols;
}
private static String[] rowSplit(String colData) {
String[] cols = colData.split(Constant.constantB);
return cols;
}
public WeighedDigraph(String input) throws IOException {
String substring = input.substring(1, input.length() - 1);
try {
Pattern regex = Pattern.compile(Constant.constantC);
Matcher matcher = regex.matcher(substring);
if (matcher.find()) {
for (String col : colmnSplit(substring)) {
String[] row = rowSplit(col);
int from = Integer.parseInt(row[0]);
int to = Integer.parseInt(row[1]);
int weight = Integer.parseInt(row[2]);
addEdge(new WeighedDigraphEdge(from, to, weight));
addEdge(new WeighedDigraphEdge(to, from, weight));// if
// directed
// comment
// that
// line
}
}
} catch (Exception e) {
}
}
/**
* @param vertex
* @return list of edges vertex is connected to.
*/
public ArrayList<WeighedDigraphEdge> edgesOf(int vertex) {
return adj.get(vertex);
}
/**
* @return list of all edges in the graph.
*/
public ArrayList<WeighedDigraphEdge> edges() {
ArrayList list = new ArrayList<WeighedDigraphEdge>();
for (int from : adj.keySet()) {
ArrayList<WeighedDigraphEdge> currentEdges = adj.get(from);
for (WeighedDigraphEdge e : currentEdges) {
list.add(e);
}
}
return list;
}
/**
* @return iterable of all vertices in the graph.
*/
public Iterable<Integer> vertices() {
HashSet set = new HashSet();
for (WeighedDigraphEdge edge : edges()) {
set.add(edge.from());
set.add(edge.to());
}
return set;
}
/**
* @return size of adjacency list
*/
public int size() {
return adj.size();
}
/**
* @return string representation of digraph
*/
public String toString() {
String out = "";
for (int from : adj.keySet()) {
ArrayList<WeighedDigraphEdge> currentEdges = adj.get(from);
out += from + " -> ";
if (currentEdges.size() == 0)
out += "-,";
for (WeighedDigraphEdge edge : currentEdges)
out += edge.to() + " @ " + edge.weight() + ", ";
out += "\n";
}
return out;
}
/**
* Add new edge to the system.
*
* @param newEdge
*/
public void addEdge(WeighedDigraphEdge newEdge) {
// create empty connection set
if (!adj.containsKey(newEdge.from()))
adj.put(newEdge.from(), new ArrayList<WeighedDigraphEdge>());
ArrayList<WeighedDigraphEdge> currentEdges = adj.get(newEdge.from());
/*
* Check if edge already exists, if it is, replace it with new one
* assuming it needs to be updated
*/
boolean edgeExists = false;
for (int i = 0; i < currentEdges.size(); i++) {
if (currentEdges.get(i).to() == newEdge.to()) {
currentEdges.set(i, newEdge);
edgeExists = true;
break;
}
}
if (!edgeExists)
currentEdges.add(newEdge);
adj.put(newEdge.from(), currentEdges);
}
}
Step 6> Out Put
{ NC,12-4-60,4-16-30#16-17-15#17-18-20, NC }
I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.
1 comments:
Click here for commentsGood work.