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

[Joris K. <de...@gm...>]

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
>
>