Created
June 14, 2013 22:02
-
-
Save mmonaco/5785635 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| static Map<Long,RouteTable> calc_all_routes(Logger log, Graph graph) | |
| { | |
| // Initialize a new routing tables | |
| Map<Long,RouteTable> new_tbl = new Hashtable<>(); | |
| Map<String, PathFinder> paths = new Hashtable<>(); | |
| for (String s : graph.vertices()) { | |
| paths.put(s, new PathFinder(graph, s)); | |
| } | |
| for (String s : graph.vertices()) { // to iterate through the whole graph vertex we want to calculate shortest paths for | |
| //System.out.println("Route Table for: " + s); | |
| RouteTable rt = new RouteTable(); // create RouteTable for this node | |
| for (String r : graph.vertices()){ // to iterate through all reachable vertex to s | |
| if ((!r.equals(s)) && (paths.get(s).isReachable(r))){ | |
| RouteEntry highRouteEntry = null; | |
| RouteEntry lowRouteEntry = null; | |
| ST<String, Integer> st = graph.adjacentTo(s); | |
| for (String neighbor : st.keys()){ // to iterate through all neighbors of s | |
| // skip single hop | |
| if (neighbor.equals(r)) | |
| continue; | |
| // skip loop of size 2 | |
| if (paths.get(neighbor).firstHop(r).equals(s)) | |
| continue; | |
| // skip nodes not reachable by neighbor | |
| if (paths.get(neighbor).isReachable(r)) | |
| continue; | |
| // Is this 1? | |
| int hops = (paths.get(s).distanceTo(neighbor) + paths.get(neighbor).distanceTo(r)); | |
| if (highRouteEntry == null){ | |
| // What is this? I guess the /incorrect primary route/ | |
| highRouteEntry = new RouteEntry((byte)2, Util.str_to_long(r), Util.str_to_long(neighbor), hops); | |
| } else if ((hops <= highRouteEntry.hops) || (lowRouteEntry == null)){ | |
| // minimize hops for secondary route | |
| lowRouteEntry = new RouteEntry((byte)3, Util.str_to_long(r), Util.str_to_long(neighbor), hops); | |
| } else if(hops < lowRouteEntry.hops){ | |
| // minimize hops for secondary route | |
| lowRouteEntry = new RouteEntry((byte)3, Util.str_to_long(r), Util.str_to_long(neighbor), hops); | |
| } | |
| } | |
| if(highRouteEntry != null){ | |
| rt.add_route(highRouteEntry); | |
| if (lowRouteEntry != null){ | |
| rt.add_route(lowRouteEntry); | |
| } | |
| } | |
| } | |
| } | |
| if (rt != null){ | |
| new_tbl.put(Util.str_to_long(s), rt); | |
| } | |
| } | |
| return new_tbl; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment