Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/fun/FindPath.java @ 68:5028fdace37b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 16:23:26 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 68:5028fdace37b
1 package fun;
2
3 import java.util.ArrayList;
4 import java.util.HashMap;
5 import java.util.LinkedHashSet;
6
7 import fileIO.TextFile;
8 import shared.Timer;
9
10 public class FindPath {
11
12 public static void main(String[] args){
13 Timer t=new Timer();
14 String start=args[0];
15 String stop=args[1];
16 String fname=args[2];
17
18 makeGraph(fname);
19 Path path;
20 if(!start.equals(stop)){
21 path=findPath(map.get(start), map.get(stop));
22 }else{
23 path=new Path(new Node(start));
24 }
25 printPath(path);
26 t.stop();
27 System.out.println("Time: \t"+t);
28 }
29
30 private static Path findPath(Node start, Node stop) {
31 HashMap<Node, Path> pmap=new HashMap<Node, Path>();
32 pmap.put(start, new Path(start));
33 LinkedHashSet<Node> seen=new LinkedHashSet<Node>();
34 seen.add(start);
35
36 while(seen.size()>0){
37 LinkedHashSet<Node> seen2=new LinkedHashSet<Node>();
38 for(Node n : seen){
39 Path current=pmap.get(n);
40 for(Edge e : n.edges){
41 Path p=pmap.get(e.b);
42 if(p==null || p.dist>current.dist+e.dist){
43 p=current.copy();
44 p.add(e);
45 pmap.put(e.b, p);
46 seen2.add(e.b);
47 }
48 }
49 }
50 seen=seen2;
51 }
52 return pmap.get(stop);
53 }
54
55 private static void printPath(Path path) {
56 if(path==null){
57 System.out.println("Unreachable.");
58 return;
59 }
60 String comma="";
61 for(Node n : path.list){
62 System.out.print(comma+n.name);
63 comma=",";
64 }
65 System.out.println(" \t"+path.dist);
66 }
67
68 static void makeGraph(String fname){
69 map=new HashMap<String, Node>();
70 TextFile tf=new TextFile(fname);
71 String line=tf.nextLine();
72 while(line!=null){
73 String[] split=line.split("\t");
74 Node a=fetch(split[0]), b=fetch(split[1]);
75 int dist=Integer.parseInt(split[2]);
76 a.edges.add(new Edge(a, b, dist));
77 b.edges.add(new Edge(b, a, dist));
78 line=tf.nextLine();
79 }
80 }
81
82 static Node fetch(String s){
83 Node n=map.get(s);
84 if(n==null){
85 n=new Node(s);
86 map.put(s, n);
87 }
88 return n;
89 }
90
91 static HashMap<String, Node> map;
92
93 static class Node{
94
95 Node(String s){
96 name=s;
97 }
98 String name;
99 ArrayList<Edge> edges=new ArrayList<Edge>();
100
101 }
102
103 static class Edge{
104 Edge(Node a_, Node b_, int dist_){
105 a=a_;
106 b=b_;
107 dist=dist_;
108 }
109 Node a, b;
110 int dist;
111 }
112
113 static class Path{
114 Path(Node start){
115 list.add(start);
116 }
117 private Path() {
118 // TODO Auto-generated constructor stub
119 }
120 public void add(Edge e){
121 list.add(e.b);
122 dist+=e.dist;
123 }
124 public Path copy(){
125 Path p=new Path();
126 p.list.addAll(list);
127 p.dist=dist;
128 return p;
129 }
130 public ArrayList<Node> list=new ArrayList<Node>();
131 public int dist=0;
132 }
133
134 }