stop at node in BFS

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

stop at node in BFS

Matthias Kricke
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: stop at node in BFS

Joris Kinable
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 <[hidden email]> 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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: stop at node in BFS

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



On Wed, Apr 3, 2013 at 6:47 PM, Joris Kinable <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...