Re: [jgrapht-users] stop at node in BFS

[John S. <js...@gm...>]

Another approach would be to first mask the original graph and then run the
BFS on the masked graph.

http://jgrapht.org/javadoc/org/jgrapht/graph/MaskSubgraph.html


On Wed, Apr 3, 2013 at 6:47 PM, Joris Kinable <de...@gm...> wrote:

> Dear Matthias,
>
> This functionality is not included in the JgraphT package, so you'll have
> to program it yourself. What kind of graph do you have? Implementing a BFS
> isn't very difficult. You probably want to maintain a set of 'special
> nodes'.
> So BFS works something like (copied from wiki):
>
> 1  *procedure* BFS(*G*,*v*):
> 2      create a queue *Q*
> 3      enqueue *v* onto *Q*
> 4      mark *v*
> 5      *while* *Q* is not empty:
> 6          *t* ← Q.dequeue()
> 7          *if* *t* is what we are looking for:
> 8              return *t*
> 9          *for all* edges e in G.adjacentEdges(t) *do*
> 12             *u* ← G.adjacentVertex(*t*,*e*)
> 13             *if* *u* is not marked:
> 14                  mark *u*
> 15                  enqueue *u* onto *Q*
> 16     return *none*
>
> So at step 15, you would NOT enqueue a node if it is special. You would
> simply mark it as visited.
>
> br,
>
> Joris
>
>
>
>
> On Wed, Apr 3, 2013 at 11:24 AM, Matthias Kricke <
> mat...@gm...> wrote:
>
>> Hi,
>>
>> I want to do a BFS where some nodes are excluded. To clarify, If BFS
>> accesses such a specified node I want BFS to stop at this node and don't
>> insert it to the results nor giving me the neighbors of the node but I want
>> BFS to go on other nodes.
>>
>> In other words, I want to exclude the subgraphs beneath specified nodes.
>> If another unspecified node is also able to access the subgraph I need the
>> subgraph and it shoudlnt be excluded.
>>
>> is it possible to do so with JGraphT? If yes, how?
>>
>> Hope you understand my desire =)
>>
>> Regards,
>> MK
>>
>>
>> ------------------------------------------------------------------------------
>> Minimize network downtime and maximize team effectiveness.
>> Reduce network management and security costs.Learn how to hire
>> the most talented Cisco Certified professionals. Visit the
>> Employer Resources Portal
>> http://www.cisco.com/web/learning/employer_resources/index.html
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>