Re: [Wala-wala] DSFPathFinder

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Let g' be the graph g, with getPredNodes(A) == getPredNodes(B) == EmptySet 
[not null].

let s1 = DFS.getReachableNodes(g',A).
let s2 = DFS.getReachableNodes(GraphInverter.invert(g'),B).
then s1 intersect s2 == the set of nodes that lie on a path from A to B in 
g.

[anyone .. please speak up if I've messed this up somehow ...]

SJF
------------------------------------------------------------------------
Stephen Fink
IBM T.J. Watson Research Center
sj...@us...
(914)784-7776

dongyu sun <sun...@ya...> wrote on 10/21/2008 09:25:42 AM:

> thx, so if say A is the startNode, B is the ending node, if 
> grePredNode(A) returns NULL and getSuccNode(B) return NULL, will 
> this give a subgraph start with A end with B??
> 
> Or it is right to start from node A, use Graph.addEdge(src,dest) 
> recursively to build a graph from scrach until reaches node B??
> 
> 
> --- On Tue, 10/21/08, Stephen Fink <sj...@us...> wrote:
> From: Stephen Fink <sj...@us...>
> Subject: Re: [Wala-wala] DSFPathFinder
> To: "WALA discussion and Q&A" <wal...@li...>
> Date: Tuesday, October 21, 2008, 9:13 AM

> 
> No, we don't have such a class. 
> 
> I'd suggest just building one using delegation to the original 
> graph, overriding the getPredNodes() and getSuccNodes() functions. 
> 
> ------------------------------------------------------------------------
> Stephen Fink
> IBM T.J. Watson Research Center
> sj...@us...
> (914)784-7776
> 
> 

> 
> dongyu sun <sun...@ya...> 
> 10/21/2008 08:40 AM 
> 
> Please respond to
> WALA discussion and Q&A <wal...@li...>
> 
> To
> 
> WALA discussion and Q&A <wal...@li...> 
> 
> cc
> 
> Subject
> 
> Re: [Wala-wala] DSFPathFinder
> 
> 
> 

> 
> thx, in WALA, is there a class to build a view or subgraph of a 
> graph based on start and ending node?
> 
> --- On Sun, 10/19/08, Stephen Fink <sj...@us...> wrote: 
> From: Stephen Fink <sj...@us...>
> Subject: Re: [Wala-wala] DSFPathFinder
> To: "WALA discussion and Q&A" <wal...@li...>
> Date: Sunday, October 19, 2008, 6:44 PM
> 
> 
> > 
> > 1./ To construct a DSFPathFinder object, the constructor requires a 
> > "filter" obj, which only has one method of "accept". How this accept
> > is used? does it give indication of when the search should stop or 
> > which node should be included in the path? If it is to test whether 
> > a node should be included what the criteria should given? 
> 
> The filter defines the methods that are being searched for .. that 
> is, when the search should stop. 
> 
> > 2./   from the description of DSFPathFinder, it returns the first 
> > path found connnecting two node, is there any way to find all the 
> > path between two nodes? 
> 
> Here's one way to find all the paths between A and B: 
>   1.  Create a view of the graph which elides all outgoing edges 
> from B, and do a DFS to find all nodes reachable from A. 
>   2.  Create a view of the graph with edges inverted (see 
> GraphInverter) which deletes all outgoing edges from A, and do a DFS
> to find all nodes reachable from B. 
>   3.  Report nodes in the interesection of results from steps 1 and 2. 
> 
> SJF 
> 
> ------------------------------------------------------------------------
> Stephen Fink
> IBM T.J. Watson Research Center
> sj...@us...
> (914)784-7776
> 
> 
> dongyu sun <sun...@ya...> wrote on 10/17/2008 11:53:20 AM:
> 
> > Hi, 
> >     I got some question on the use of DSFPathFinder. 
> > 
> > 1./ To construct a DSFPathFinder object, the constructor requires a 
> > "filter" obj, which only has one method of "accept". How this accept
> > is used? does it give indication of when the search should stop or 
> > which node should be included in the path? If it is to test whether 
> > a node should be included what the criteria should given? 
> > 
> >       Currently, I used this class to search a interprocedure CFG, 
> > and I used the getNumber() of the 
> > BasicBlockInContext<ISSABasicBlock> and return true if this number 
> > equals. It is as following 
> > 
> >  Filter<BasicBlockInContext<ISSABasicBlock>> f = new 
> > Filter<BasicBlockInContext<ISSABasicBlock>>() {
> >    public boolean accepts(BasicBlockInContext<ISSABasicBlock> o) {
> >     return endNode.getNumber()==o.getNumber();
> >    }
> >   }; 
> > 
> >     Is this the right way to use? Becaues after I use this method, 
> > It seems does not work, I even can't get the start and end node inthe 
list.
> > 
> > 2./   from the description of DSFPathFinder, it returns the first 
> > path found connnecting two node, is there any way to find all the 
> > path between two nodes? 
> > 
> > thanks 
> > dongyu 
> > 
> > 
> > __________________________________________________
> > Do You Yahoo!?
> > Tired of spam? Yahoo! Mail has the best spam protection around 
> > http://mail.yahoo.com 
> > 
-------------------------------------------------------------------------
> > This SF.Net email is sponsored by the Moblin Your Move 
Developer'schallenge
> > Build the coolest Linux based applications with Moblin SDK & win 
> great prizes
> > Grand prize is a trip for two to an Open Source event anywhere in the 
world
> > http://moblin-contest.org/redirect.php?banner_id=100&url=/
> > _______________________________________________
> > Wala-wala mailing list
> > Wal...@li...
> > https://lists.sourceforge.net/lists/listinfo/wala-wala 
> 
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's
> challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the 
world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/ 
> _______________________________________________
> Wala-wala mailing list
> Wal...@li...
> https://lists.sourceforge.net/lists/listinfo/wala-wala
> 
> 
> 
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's 
challenge
> Build the coolest Linux based applications with Moblin SDK & win great 
prizes
> Grand prize is a trip for two to an Open Source event anywhere in the 
world
> http://moblin-contest.org/redirect.php?
> banner_id=100&url=/_______________________________________________
> Wala-wala mailing list
> Wal...@li...
> https://lists.sourceforge.net/lists/listinfo/wala-wala

> 
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's
> challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the 
world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Wala-wala mailing list
> Wal...@li...
> https://lists.sourceforge.net/lists/listinfo/wala-wala

> 
> 
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's 
challenge
> Build the coolest Linux based applications with Moblin SDK & win great 
prizes
> Grand prize is a trip for two to an Open Source event anywhere in the 
world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Wala-wala mailing list
> Wal...@li...
> https://lists.sourceforge.net/lists/listinfo/wala-wala