Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to determine if two nodes are connected?

Tags:

I'm concerned that this might be working on an NP-Complete problem. I'm hoping someone can give me an answer as to whether it is or not. And I'm looking for more of an answer than just yes or no. I'd like to know why. If you can say,"This is basically this problem 'x' which is/is not NP-Complete. (wikipedia link)"

(No this is not homework)

Is there a way to determine if two points are connected on an arbitrary non-directed graph. e.g., the following

Well   |   |   A   |   +--B--+--C--+--D--+   |     |     |     |   |     |     |     |   E     F     G     H   |     |     |     |   |     |     |     |   +--J--+--K--+--L--+                     |                     |                     M                     |                     |                   House 

Points A though M (no 'I') are control points (like a valve in a natural gas pipe) that can be either open or closed. The '+'s are nodes (like pipe T's), and I guess the Well and the House are also nodes as well.

I'd like to know if I shut an arbitrary control point (e.g., C) whether the Well and House are still connected (other control points may also be closed). E.g., if B, K and D are closed, we still have a path through A-E-J-F-C-G-L-M, and closing C will disconnect the Well and the House. Of course; if just D was closed, closing only C does not disconnect the House.

Another way of putting this, is C a bridge/cut edge/isthmus?

I could treat each control point as a weight on the graph (either 0 for open or 1 for closed); and then find the shortest path between Well and House (a result >= 1 would indicate that they were disconnected. There's various ways I can short circuit the algorithm for finding the shortest path too (e.g., discard a path once it reaches 1, stop searching once we have ANY path that connects the Well and the House, etc.). And of course, I can also put in some artificial limit on how many hops to check before giving up.

Someone must have classified this kind of problem before, I'm just missing the name.

like image 752
BIBD Avatar asked Dec 09 '08 21:12

BIBD


People also ask

How do you know if two vertices are connected?

Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.

How do you check if all nodes in a graph are connected?

To check connectivity of a graph, we will try to traverse all nodes using any traversal algorithm. After completing the traversal, if there is any node, which is not visited, then the graph is not connected. For the directed graph, we will start traversing from all nodes to check connectivity.

How do you check if a graph is 2 connected?

A graph is connected if for any two vertices x, y ∈ V (G), there is a path whose endpoints are x and y. A connected graph G is called 2-connected, if for every vertex x ∈ V (G), G − x is connected. A separating set or vertex cut of a connected graph G is a set S ⊂ V (G) such that G − S is disconnected.


2 Answers

Your description seems to indicate that you are just interested in whether two nodes are connected, not finding the shortest path.

Finding if two nodes are connected is relatively easy:

Create two sets of nodes:  toDoSet and doneSet Add the source node to the toDoSet  while (toDoSet is not empty) {   Remove the first element from toDoSet   Add it to doneSet   foreach (node reachable from the removed node) {     if (the node equals the destination node) {        return success     }     if (the node is not in doneSet) {        add it to toDoSet      }   } }  return failure. 

If you use a hash table or something similar for toDoSet and doneSet, I believe this is a linear algorithm.

Note that this algorithm is basically the mark portion of mark-and-sweep garbage collection.

like image 52
David Norman Avatar answered Oct 11 '22 08:10

David Norman


See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , your one stop shop for all graph related problems. I believe your problem is in fact solvable in quadratic time.

like image 22
Nick Gebbie Avatar answered Oct 11 '22 08:10

Nick Gebbie