algorithm - The Widest Path Challenge - the most efficient way for finding path in Maximal Spanning Tree -


this question continuation of similar earlier asked question: find path between 2 nodes in graph, according given criteria - optimization task .

problem summary: need find best path in graph vertex vertex b, assumption, path quality calculated min value of edge weight on path , next best path that, has max min value. it's called "widest path problem".

previously needed solve problem in small graph (up 15 vertices), didn't need sophisticated algorithm , of kind peoples, have designed working algorithm. unfortunately i need redefine necessities in such way, graph can large (even 50 thousands of edges). i'm aware need find maximal spanning tree graph , obtain simple path start stop vertex in obtained mst. have decided use jgrapht library. has implemented kruskal minimum spanning tree algorithm. can obtain maximal spanning tree multiplying each edge weight (-1) , using kruskal minimal spanning tree, algorithm in library has been designed retrieving hash set of mst edges.

my question following: have obtained maximal spanning tree of graph java hashset of edges. how can find path vertex vertex b in such structure in efficient way , data structure efficient purpose? recommend me?

additionally, i'm worried such situation, graph not consistent (it may contain isolated vertices or isolated subgraphs), main condition kruskal algorithm correctness. way bypass problem?

thank or tips.

use set construct subgraph object. subclass depthfirstiterator encountervertex puts entry key v , value (whatever other endpoint of e is) map p. search depth-first sink. recover path initializing v source , looking v, p[v], p[p[v]], etc., until there no entry. pain, library authors baked fibonacciheap closestfirstiterator, otherwise class want. (heck, if don't care n log n time operation, run dijkstra on subgraph.)

kruskal's algorithm functions fine disconnected graphs. returns minimum-weight spanning forest, i.e., each connected component, minimum-weight spanning tree. can't vouch particular implementation.


Comments

Post a Comment

Popular posts from this blog

How to remove text and logo OR add Overflow on Android ActionBar using AppCompat on API 8? -

have researched death , cannot find answer. i have actionbar using appcompat. supporting api v7 (api v8 do). actionbar works api v11. api < v11 has problem of removing icon (and feature) actionbar without supplying overflow. big picture have app logo, app title, , 3 icons squidging same actionbar on low end phone. trying make room! i happy 1 of 2 solutions. either: a method of getting overflow functionality can retrieved pull down. (preferred) method of removing icon , text actionbar below current xml api 11+: <resources> <!-- base application theme api 11+. theme replaces appbasetheme res/values/styles.xml on api 11+ devices. --> <style name="appbasetheme" parent="theme.appcompat.light.darkactionbar"> <item name="android:actionbarstyle">@style/liteactionbarstyle</item> <item name="actionbarstyle">@style/liteactionbarstyle</item> </st...
Read more

html - How to style widget with post count different than without post count -

i have border below li elements in wordpress widget types appropriate. element inside set block gives them nice easy click full width. the problem, when choose option "show post count" when adding widget such categories or archives displays post count plain text after tag , because tag block pushes post number text line below. whether choose show post count or not show post count still gives exact same element identifyer example "widget_categories". how style post count not on next line still keep links non post count list items full width? here's example on sidebar www.bbmthemes.com/themes/modular/blog-standard/ in order solve problem need remove display:block; for ul.widgets ul a , add in it's place line-height: 33px; what going achieve have same visual effect. what going lose doing links going work on text , not on "box". the other way out of find post count coming , make changes this. example change text count i...
Read more

url rewriting - How to redirect a http POST with urlrewritefilter -

i have question urlrewritefilter , until not find in net. i want redirect http post in tomcat7. here example... the call http post ulr http://localhost:8080/oldapplication/example?a=123&b=2 this call contains content either xml or json. filter configured works , urlrewrite.xml contains: <?xml version="1.0" encoding="utf-8"?> <!doctype urlrewrite public "-//tuckey.org//dtd urlrewrite 4.0//en" "http://www.tuckey.org/res/dtds/urlrewrite4.0.dtd"> <urlrewrite use-query-string="true"> <rule> <condition type="method">post</condition> <from>^(.*)$</from> <to type="redirect">/newapplication$1</to> </rule> </urlrewrite> in access log can see call http://localhost:8080/oldapplication/example?a=123&b=2 gets redirected http://localhost:8080/newapplication/example?a=123&b=2 fine until now. pr...
Read more