• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Connected Graph using Adjacency Matrix

 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

s ravi chandran wrote:Thanks for the feedback.


You're welcome!

s ravi chandran wrote:I am not sure where is the edge count, the line I see is this:

This is definitely the vertices found and not the edge. Graph is not connected, that might be correct as there is no edge between 2-->3. Am I getting it wrong?


Well, yes and no. First of all, I misread 'vertexFound' as 'EdgeFound'. My bad, I apologize. But look what happens here. If you find that the pair(v1, v2) is connected, you do 'vertexFound++', and thus for every isConnected(v1, v2) you count a vertex. But 'isConnected(v1, v2)' also means that there is an edge between v1 and v2, and thus 'vertexFound' is equal to 'EdgeFound'. Think about it.
And also, you have that 'vertexFound' == 5, while there are 5 vertrices. So, why not conclude that the graph is connected, since we 'found all the vertices'? Complicated, isn't it? But then again, great excersize!

Then, as promised, an new explanation of the Queue method.

We start with the graph(5, true), with the edges (0, 1), (0,2), (2, 3), (2, 4) and (4, 5). By the way: wouldn't it be handy to have a Graph-method 'addEdge(int i1, int i2), somewhat simpler to use than 'addEdge(new Edge<>(i1, i2)'.

Now, if we make a drawing of the graph, we get:      

Clearly connected.
Let's start with a random vertex, say 2. For the Queue we take a LinkedList<Integer>, and for Visited we take a Set<Integer>.
We start by putting 2 in the Queue and in the Visited.
Then the whole sv=cheme becomes:
Queueheadremaining QneighborsVisitedrem. neighborsnew Visitednew QueueQueue empty?
22empty0, 3, 420, 3, 40, 2, 3, 40, 3, 4No
0, 3, 403, 41, 20, 2, 3, 410, 1, 2, 3, 43, 4, 1No
3, 4, 134, 120, 1, 2, 3, 4-0, 1, 2, 3, 44, 1No
4, 1412, 50, 1, 2, 3, 450, 1, 2, 3, 4, 51, 5No
1, 51500, 1, 2, 3, 4, 5-0, 1, 2, 3, 4, 55No
55-40, 1, 2, 3, 4, 5-0, 1, 2, 3, 4, 5-Yes

Now, is Vuisited equal to the list Of Vertices? Yes. So, graph is connected. Now, remove edge (0, 2) and repeat the procedure. Do we now find that the graph is unconnected?
Remains to put this table into real code. Reread my early description of the Queue method.

And since I typed the whole table from the keyboard, there may be the odd mistakes...
 
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the queue solution.

I will take some time to understand this logic.

My initial idea was to use Adjacency Matrix to check for graph connectivity. Also, I was under the impression that we should have a connection like 0-->1-->2-->3-->4-->5, to conclude the graph is connected.

Know my understanding on the definition is corrected. Also, this code would best be solved using Adjacency List.

Will work on the coding it once I understand the logic.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The definition of connectedness for an undirected graph is that there is a path between any two vertices.
The Queue method showed that from a starting vertex S we can reach any other vertex. That involves that the graph is connected, since given two vertices v1 and v2 there is a path, from v1 to S and then to v2.

Where you would want to use the adjacency matrix is when finding the neighbors, like you did in your methid 'isConnected'. Well. we have three structures that we can use: the adjacency matrix, the adjacency map and the list of edges. Just use the one that is handiest for a given problem.

I will postpone talking about this 'UnionFind', until after you have understood the logic of, and succesfully coded, the queue method. If you use the collection framework, it should not be too difficult.
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is the crude logic I created using queue.

Graph:


Will try to optimize this further if I get a better solution.
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Adding GraphDemo:
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Updated the isConnected() method:

 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well done!

I gave it a couple of graphs, and the 'isConnected' worked flawlessly.

Now, we've come to the end of part 1. I hope you found it as interesting as I did, and that graphs will have no secrets for you anymore (mind you: there are many, many mean questions out there concerning grpahs).
Let us know if you encounter some difficulty in the future.

Greetings,
Piet
 
Marshal
Posts: 8853
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
s ravi chandran, have a cow, your topic has been chosen to publish in our April's journal
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic