• Post Reply Bookmark Topic Watch Topic
  • New Topic

Connected Graph using Adjacency Matrix  RSS feed

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

I am learning graph structures, trying to understand adjacency matrix for starters.

I have created this program to check if a graph is connected or not.




Does this look correct? Though it is very basic problem, I just wanted to know if I have missed something here.

Also, what other use cases can be solved using this matrix?
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know what a "connected graph" means. It would help if you described what this is supposed to do. In the mean time I'll mention some of the stylistic improvements you could make.
  • Names in Java should be in camel-case and not use underscores, constants are an exception to this rule.
  • Instead of passing in the "number of nodes" use the length of the arrays. Note that a 2D matrix in Java is an array of arrays. So, instead of numberOfNodes use adjacencyMatrix.length.
  • Your indentation is good and consistent.
  • You are using two different styles of braces, use one or the other.
    for(;;) {
    }
    vs
    for(;;)
    {
    }

  • Did you mean to write: for (int vertex = 1; vertex < number_of_nodes; vertex++)? Why aren't you starting the vertex at zero?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    No, it is not correct.

    For instance, try this matrix:

    0, 1, 0, 0
    1, 0, 0, 0
    0, 0, 0, 1
    0, 0, 1, 0

    (follow Carey's advice, remove the parameter "number_of_nodes").

    As you see, this graph contains two undirected edges (a, b) and (c, d). Your method will now find that all rows are visited and concludes that the graph is connected.
    The standard way is to use a Queue. Start with a node that has an outgoing edge, put in on the Queue and mark it as visited. Then look at all the connected neighbors, et cetera.

    Two prechecks are useful: if there is a vertex with no incoming or outgoing edges, and there are more than one vertices, then the graph is disconnected.
    If there are two or more vertices that only have outgoing edges, then the graph is also disconnected.
     
    Liutauras Vilda
    Sheriff
    Posts: 4928
    334
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Carey Brown wrote:Your indentation is good and consistent.
    Not really consistent. Uses different braces placing style (i.e.: Line 33, Line 37). But in general way better than what we see usually.
     
    Liutauras Vilda
    Sheriff
    Posts: 4928
    334
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Carey pointed out about different braces, so apologies for my recent post Carey and OP.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for all the replies.

    I am solving the problem for undirected graph.

    Here is the code after the corrections. I will work on adding queue logic in this program.



    Okay, I see the logic fails with the input given here.

    If I use queue, how should it work?

    1. Take an element , mark it visited.
    2. Find it's neighbors, move to each neighbor and mark it visited.
    3.  Go to Step 1.

    Will this logic work?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    s ravi chandran wrote:Thanks for all the replies.

    You're welcome!
    s ravi chandran wrote:(...)
    If I use queue, how should it work?

    1. Take an element , mark it visited.
    2. Find it's neighbors, move to each neighbor and mark it visited.
    3.  Go to Step 1.

    Will this logic work?


    Yes, but don't forget the 'Queue' part.

    So, create a Queue first (a LinkedList is fine), and a List (or Set) that will contain all visited vertices.

    1. Take an element , mark it visited (i.e. add it to the list or set).
    1.5 add it to the Queue
    1.6 while the Queue still is not empty
    1.7 get and remove the first element
    2. Find it's neighbors
    3 remove all neighbors that are in the 'visited' list
    4 mark all of the remaining neighbors as visited
    5 add them either to the fromt (DFS) or to the back (BFS) of the Queue
    6.  Go to Step 1.6

    If the graphh is connected, all the vertices should also be in the visited list. If not, then the graph is not connected.
    You can repeat this procedure for all non visited vertices, you will find all components in this way, but that is not necessary to determine the connectedness.

    I use this technique in my KillerSudoku and calcudoku program. If the user selects a couple of cells, and wants to make a group out of them, I check, in exactly this way, if the selected cells are connected.
     
    Carey Brown
    Saloon Keeper
    Posts: 3329
    46
    Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It seems like this problem should also have a test to see if a matrix is valid or not. It would be valid if for all rows and columns matrix[row][col] == matrix[col][row]. The test matrix you've shown is not valid.
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Given that we're dealing with undirected Graphs, the matrix should be symmetrical.

    A likely scenario is that we have a Graph<T> class, with a boolean field 'undirected'. In my graph library, I have also an Edge class, and if the edge is undirected, then the 'equals' method considers (a,b) equal to (b,a). The derived adjacency matrix of the graph is then always symmetrical.

    If we extend this a little and have this directed Graph: a -> b -> c -> a, this Graph is also connected (in the sense that from any vertex we can reach any other vertex), yet the adjacency matrix is not symmetrical.

    But making a Matrix library, with the method '<T> boolean isSymmetrical(T[][] matrix)' is of course a good and useful idea.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Okay. I am a bit slow in understanding the steps here.

    Will work on it one step at a time.

    First question I have is, will this algorithm work with adjacency matrix?

    I somehow think this would work with an actual node graph.

    Here is my initial code to start in that direction:

    Vertex:


    Edge:


    Graph:




    Will update this program as I get some more insight.

    So far here is what I know, for a graph I need 3 components:
    1) Vertex - connecting point for all edges. This will have a list of neighbor vertices.
    2) Edge - two vertex join to form an edge. I do not remember if this needs some other list.
    3) Graph - will contain group of edges.

    I am missing quite a few important operations here.
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well, there are quite some remarks to be made.

    But for now, my main problem is: how do you see whether a Graph is undirected or not?
    If you add an Edge(a,b), then you should also add the Edge(b,a), if the Graph is undirected.

    Think about how you are going to handle this.

    The other problem is that to apply your method 'isConnected', you need the adjacency matrix. So, the second thing I like you to handle is to get this adjacency matrix from your list of Edges.

    If these two points are solved, we can see what to do next: getting this Queue method up and running, or working further on your three classes.

    But nevertheless: having these three classes is certainly a big step in the right direction!
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Updated Graph class:



    1) Handle undirected/ directed graph: added a boolean to add neighbors to the vertex.
    2) Handle adjacency matrix: returning list of edges, we can get the vertices from the Edge and iterate neighbors for each vertex.

    Does this looks reasonable?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, that looks very reasonable!

    I have three remarks/questions:

    1) have a look at the 'removeEdge' method, and compare it to the 'addEdge' method. Do you notice an important difference?

    2) you make use of the 'remove' and 'contains' methods of List. That is perfect, but it relies heavily on the 'equals' method of the Edge class. Have you tested the Edge.equals method thoroughly?

    3) in the Graph theory, you see that a Graph G is usually denoted as: G = (V, E), where V is a set of so called vertices and E is a set of relations between pais of vertices. In your Graph class, you have E, but not V. The disadvantage of this: if the Graph contains an isolated vertex (i.e. with an indegree and an outdegree of 0), how would you handle that?

    And a minor point, but that'll be for later: why limit the Graph to Edge<Integer>? You could easily make the Graph class generic as well, like: Graph<E>. But as said: not important for now.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Okay, will work on making Graph generic once I add all functionalities.

    I have added list of vertices, but not sure how I will be using it.

    I have added main method to check the equality of edges.

    The logic is based on equality of vertices. I only used the element for this test.

    Added E extends Comparable hoping that this would make the element data type to override comparable attributes and hopefully override equals and hashcode.

    Updated Graph:

     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Morning!

    Okay.

    Some remarks and questions:

    1) you have this code::

      

    First of all, it looks a bit clumsy. Don't you think that new Edge<>(1, 3) is more convenient? And also, by having a constructor: Edge(), leaves the possibility for one or both of the vertices to be null. My advice: remove the constructor 'Edge()', replace it with 'Edge(Vertex<E> v1, Vertex<E> v2)' and test both parameters for being not null.

    2) are two equality tests for edges enough to convince yourself that this method is correct?

    3) Test this:
       

    are you okay with the results?

    Note: for testing convenience, override the method 'toString' in both Vertex and Edge class.

    With this separate list of Vertices, you can now add a Vertex without it being in one of the edges of the graph.

    Well, there is quite some work to be done still. I have some remarks about your classes, we must add methods to create both the AdjacencyList and the Adjacency matrix, and we are to discuss the test for connectedness. I hope you are not in a big hurry?

       
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks. I am fine with whatever time it takes to understand this concept the properly.

    I have updated my classes based on your suggestions.

    Vertex:



    Edge:



    Graph:



    I will work on adding Adjacency List and Adjacency Matrix.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I was looking for definition of Adjacency List, found this: definition.

    I have a list of vertex: which covers [v1, v2 ....... vn]

    Each vertex has a list of adjacent vertices. Would it not be functionally a Adjacency List?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi ravi (if I may call you so),

    the article that your link points to tells quite a lot, but be warned: it is not so easy to understand.
    Tht is partly because of the names used. For instance, an important part is what is called 'adjNode'.
    This name is not very clear. Did you understand what this 'adjNode' represents?
    If you now look at your Vertex class, you see that you also have the field 'next'. Do you think your Vertex class is the same as this 'adjNode'? If not, what is the meaning of the field 'next' in your Vertex class?

    Let us concentrate on edges and how we can represent them, as I have done sofar in my graph programs. It is equivalent to your linked article, but I hope it is a bit more clear.

    Four ways to administer edges. For simplicity, let us assume that our vertices are the ints 0 ... N-1,
    so N in total. You can create a Graph constructor with parameter this N. That way, we have defined our vertices in one go. Now, we can simply have a field called size, equal to this N, and we know all we need to know about vertices. This is simple, but there is one disadvantage: it is hard to remove a vertex, but if we do not allow this possibility then we're okay. The alternative is to have a Set<Integer>, initially containg the integers 0 ... N-1. Now we can delete or add easily a new vertex. I always use a Set<E>, but usually this E is simply an Integer.

    Now, how do we store the edge information?

    1) In the graph, we will have a List<Edge> or Set<Edge> that contains the edges. For this we need a dedicated Edge class. This is what you have now. Given this List or Set, do you think we need, in our Vertex class, a List of neighbors? From this List or Set the Adjecency list and - matrix can be easily derived. More on this later.

    2) By having an Adjacency matrix in the Graph class. If we have N vertices, then this matrix is simply the int[N][N] 2D array. In the 'addEdge(a, b)' we simply update this matrix by putting matrix[a][b] to 1, and if the Graph is undirected, by also putting matrix[b][a] to 1.
    This is also simple, but removing a vertex is again not so simple. Removing an edge boils down to setting the correcponding matrix element to 0. (don't forget to consider the undirectedness of the graph!)

    3) By having an Adjacency List, mentioned in your linked to-GitHub article. I will not discuss how that article handles this (I asked you to explain that in the beginnig of my reply), but what I always do is to have a Map<Integer, Set<Integer>>, where the first Integer is the vertex, and the Set is the set of adjacent integers. This is very flexible, and takes less space than an adjacency matrix if the number of edges is small.

    4) have the graph a Set<Vertex> (Vertex being Integer), and let each Vertex have a list (or Set) of adjacent vertices.

    You now have a combination of 1) and 4). This makes it complicated and adds redundency. The information in the List<Edge> is sufficient to derive the neighbors of each vertex, or vice versa.
    The problem can be seen in both the 'addEdge' and the 'removeEdge' method. In the 'addEdge' you neatly add the edge to your Edge list, but if the graph is undirected, you only update the neighbor list of the vertex. So you then get a discrepancy between the Edge list and the neighbor-information in the vertices.

    Well, nearly enough for now. The question I want to conclude this reply: if we use Integers as our vertices, and we have either an Adjacency List or Adjacency matrix, do we need the Vertex and the Edge class?
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the feedback.

    I had not seen the code before. What I read was the description that was given along with the figure.

    Seeing my Vertex class now, I do not seem to remember why I added next() method for. Also with all the information gathered so far, Vertex seem to be redundant.

    I will keep the Edge class for the time being. In my work, what we do is first make a business requirement work functionally. Then we do constant cleanup to optimize the code while keeping the functionality intact. I will clean up Edge class, list of edges and other redundancies later.

    As I already have done a bit of work over AdjacencyList, so will continue in that direction first. Will take up Adjacency Matrix after that.


    Here is my updated code.

    Edge:



    Graph:



    Does the adjacency list functionality look correct?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    s ravi chandran wrote:Does the adjacency list functionality look correct?

    Yes it does, but of course, only testing can answer this. We will come to talk about JUnit testing in a while.

    But it is getting better and better!

    A couple of remarks/questions again.

    1) There is still no Vertex list in the Graph class. So we can still not handle a vertex that has no edges. And remember, if we only have vertices that have edges, then we might erroneously think we have a connected graph, just because we did not record isolated vertices.

    What about a Graph constructor like: public Graph(int nrOfVertices, boolean isUndirected)? How to deal with this 'nrOfVertices'?

    2) maintaining both a map of edges and an Edge list is double work and thus double chance of making some mistake. If you have a Map<Integer, Set<Integer>>, can you think of a way to get all the edges? Or vice versa? So, is it wise to store two things that are equivalent? (Performance is not an issue, currently).

    3) About the Edge class: what do you think of: new Edge(a, b) where at least one of a and b is null? Will you allow for such a possibility?

    4) What to do if in 'addEdge(Edge e)' one of the vertices of e is not in our 'list of Vertices'? For instance, if nrOfVertices = 10, meaning we have the vertices 0, 1, 2, ..., 9, and we get this: addEdge(11, 15)?
    Do we add these vertices to our (implicit) vertices list, or do we throw an Exception?

    5) If you run the 'main' method of the Graph class, you see that after new Graph(true) and after adding the Edge e(100001, 100002), you see that the list of Eges contains only one element. Since the Graph is undirected, I would have expected two Edges.

    As you see, I'm trying to get the details clear about the Edge and the Graph class. If you are on some Graph course, then expect to get some questions about the degree distribution of edges, and, very interesting, how 'resilient' a graph is (that is, if the graph is connected, is it still connected if we remove an edge, two edges, et cetera). So we better make that our Graph is capable of answering such questions.

    But as said: this is looking more and more promising! Slowly but steadily getting near the end.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have updated the Graph class. They handle point 1, 2, 4.

    Regarding point 3: I am thinking I can allow null vertex. If I keep this, I can even have an isolated vertex added to graph.
    It would be like this:

    Now this vertex 4 is not connected to any other vertex, I will have an entry in the adjacency list and it can be traversed(with possible null check). This might work as an alternative to listOfVertices, is my logic correct?

    Regarding point 1: One possible concern with listOfVertices can be limitation of scope. Say I put String in place of Integer, then the current logic will not work. I can even have 10 vertices and the label will start from 1000001, this requires additional logic like start index.

    Regarding Point 5: Graph class contains list of vertices, adjacency list. Should I override the toString() to just print all the edges after iterating all entries in adjacency list?

    Here is my updated Graph:


    Added a main class GraphDemo:
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Updated Graph toString() to print just the Edges:


    Here is how the output looks like:
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    We're almost there.

    Again some remarks:

    1) if graph = new Graph(10, true), test if we can do:
    Did you expect the outcome? Is the outcome acceptable?

    2) in your separate testprogram (very good idea, that keeps the Graph class uncluttered), if you follow what happens after removing Edge(2, 4), we now get that vertex 4 has an empty HashSet as value. Yet in the output I do not see vertex 4 anymore. That can be deliberately, but it is possible that the method 'printEdges' has a flaw. Can you investigate this? And more general: do you want to have, in the adjacencyList, a key that has an empty HashSet as value?

    3) since your adjacencyList is a Map, why not call it 'adjacncyMap'?

    4) test what happens if we do:
    on beforehand: what do you expect?

    5) a start with using java 8.
    Look at this code: (in the method: 'addEdge')

    with a novelty in java 8 we can reduce this to just one line of code:

    So, the last touches, next time (or now if you can't wait), we will add the method 'public int[][] getAdjacencyMatrix()', and we will discuss the current method 'getVertices'.

    Well done!
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the feedback.

    Here is the updated code.

    Graph:


    GraphDemo:


    Regarding point 1, I did the correction. My condition was wrong before. Now it will throw exception. Unless I wish to handle isolated vertex using addEdge(), this logic should work. Issue found at line number 32 of Graph.

    Regarding point 2, Fixed the toString() method of Graph. There too the logic was wrong. Issue found at line number 83 of Graph.

    Regarding point 3, done the changes.

    Regarding point 4, this will give compilation error as Graph is not generic type, it is restricted to Integer. If I change Graph to support generics, I will have to handle  initializeVertices().

    I have added the java 8 enhancement. I do use java 8 in my work, but forgot to use it in this program.

    Will work on adding AdjacencyMatrix.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Updated the code with initial adjacency matrix logic.

    VertexIndexer:



    Graph:



    Sample Output:



    Let me know if this logic needs some enhancement.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Some correction to VertexIndexer class. The index where assigned based on insert order.

    Added logic to re-shuffle the index in a sorted manner and assign proper indexes to each vertex.



    Updated Graph class to include viewing index of each vertex:



    This change gives the following output:


    The index will update everytime an element is inserted.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Last changes to VertexIndexer messed up the adjacency matrix.

    Here is what I am trying to do:

    1) Whatever data type that is used as vertex, VertexIndexer will assign an index to each vertex.
    2) All operations for AdjacencyMatrix will depend on index retrieved from VertexIndexer. This will allow us to even assign String type as vertex.

    Here is the issue I am facing:
    1) After each index addition/updation, the matrix doesnt reflect the correct indexes for vertices.


    There is a need to refill the matrix with latest index. But this is increasing complexity. How should I solve this?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    well, interesting! But I need a little time to oversee the current situation, so bear with me.

    My first impressions:

    1) I certainly like the idea behind the VertexIndexer class. Whether it is usefull or can be improved is another matter, though. We will discuss that later. As you will have noticed, I ask you many questions about your code. The goal is to let you make your design choices, whether I like these choices or not. If a choice of yours is not optimal, then you will be the first to find out. And if a choice is perfect, then you can be proud of yourself!

    2) My idea is to only have a list of Vertices and and adjacencyMap in the graph class. A adjacency matrix and a list of edges are to be made in dedicated methods, like 'getListOfEdges' and 'getAdjacencyMatrix'. The advantage is that, whenever we add or remove an edge, we only need logic to update our adjacency map. That makes life easier. The possible drawback may be one of speed: maybe creating an Edgelist or an adjacency matrix will be too time consuming. But first of all, I doubt this very much, and secondly only time will tell.

    3) Why do you want the vertices, of generic type E, be sorted? What is wrong with just a HashMap<E, Integer>? (note: a TreeMap is certainly not wrong, I just want to know your reasoning).

    4) can you post all of your classes when you make an update? That will make it easier for me to run your code, since the copying is then so much easier for me.

    That's it for now, I will have a look at your matrix generator!
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well, after some testing I see no problems concerning the matrix!
    But it is getting a bit complex. And the reason for this complexity is that you only update the VertexIndexer afrter adding an Edge.

    First of all: I made the method 'printAdjacencyMatrix' public, instead of private, for testing purposes.

    Now, I ran this test:
    Graph graph = new Graph(5, true);
            Edge<Integer> e1 = new Edge<>(2, 4);
            Edge<Integer> e2 = new Edge<>(1, 3);
            Edge<Integer> e3 = new Edge<>(0, 1);
            Edge<Integer> e4 = new Edge<>(0, 2);
            Edge<Integer> e5 = new Edge<>(3, 4);

            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");
            graph.addEdge(e1);
            System.out.println("adjM after adding edge " + e1);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");
            graph.addEdge(e2);
            System.out.println("adjM after adding edge " + e2);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");
            graph.addEdge(e3);
            System.out.println("adjM after adding edge " + e3);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");
            graph.addEdge(e4);
            System.out.println("adjM after adding edge " + e4);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");
            graph.addEdge(e5);
            System.out.println("adjM after adding edge " + e5);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("**********************************");

            System.out.println("Graph Edge List:  " + graph);
            System.out.println("**********************************");

            graph.removeEdge(e1);
            System.out.println("adjM after removing edge " + e1);
            System.out.println(graph.getVertexIndexer());
            System.out.println(graph.getAdjacencyList());
            System.out.println(graph.printAdjacencyMatrix());
            System.out.println("Graph Edge List:  " + graph);
            System.out.println("**********************************");


    Now, after the creation of the graph, we see this:
    AdjacencyIndex [noOfVertices=0, indexMap={}]
    {}
    AdjacencyMatrix{
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]}

    **********************************
    adjM after adding edge Edge{2, 4}
    AdjacencyIndex [noOfVertices=2, indexMap={2=0, 4=1}]
    {2=[4], 4=[2]}
    AdjacencyMatrix{
    [0, 1, 0, 0, 0]
    [1, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]}


    As you see, after adding the edge (2, 4), we see that integer 2 gets index 0, and integer 4 gets index 1. Therefore, we should expect, in the matrix, that matrix[0, 1] becomes 1, and dito matrix[1,0].
    And that is precisely what we see! You would probably have thought that matrix[2, 4] would become 1, as well as matrix[4,2]. As I said, that is the confusing part.

    To make this less confusing, my advice would be to create the VertexIndexer in the constructor of the Graph. But then you will see that you map Integer 0 to Integer 0, Integer 1 to Integer 1, et cetera. That's why I wondered, in my previous reply, if this VertexIndexer was useful. But for now, this VertexIndexer confuses things, and maybe it is wiser to postpone the idea until we have answered the question about completeness.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Okay, I think the best course of action here would be to backtrack to the state before adjacency matrix.

    Before that, here are my reply to your queries:

    2) If I understand it correctly, we should have ListOfVertices and AdjacencyMap associated with addEdge() and removeEdge().  ListOfEdges and AdjacencyMatrix would be generated whenever we are calling their respective getter methods. Am I correct ?

    3) I actually replaced HashMap with TreeMap later. The reason was what I was seeing with the indexer sequences. Let me recreate what was happening. Here is the output with HashMap indexing:



    Well, when I am running it now, the vertex are coming in sequence, but while I was running in before, they were out of sorts. The objective was to make the sequence easier to track.

    What I will do is remove the vertex indexer and keep everything else intact. Will work from that state.

    Here are the classes.

    Edge:

    Graph:

    GraphDemo:


    Here are the items that are pending:
    1) Complete AdjacencyMatrix and figure out how to use it in this program.
    2) Utilizing listOfVertices in the program.

     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    s ravi chandran wrote:
    Here are the items that are pending:
    1) Complete AdjacencyMatrix and figure out how to use it in this program.
    2) Utilizing listOfVertices in the program.


    Right, it is time to write the methods 'public int[][] getAdjacencyMatrix()' and 'public List<Edge<Integer>> getListOfEdges()'.
    You already have these methods, albeit that they return a String. So the logic is already there.

    Since EdgeList, AdjacencyMap and AdjacencyMatrix are equivalent (anyone can be derived from any other one), there is no direct use for the matrix and the list. But suppose you want to find the isolated vertices: List<Integer> isolates = new ArrayList<>(ListOfVertices); isolates.removeAll(adjacencyMap.getKeys());
    And there are some very nice lemma's concerning adjacency matrices. For instance: there is a path between vertices i and j if there is an integer k such that matrix^k has a 1 at position[i][j]
    And with the method 'getAdjacencyMatrix', there is no need for the equally-named member.

    A java 8 method for a list of edges could be:

     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the listOfEdge method.

    I am still getting used to the functional programming style. It's concise manner is very hard to get by.

    I have updated the graph class with a crude way of AdjacencyMatrix, I have also created  AdjacencyMatrix using VertexIndexer. I like the normal method though, not much fuss and easy to understand.

    Here are the classes.

    Graph:



    GraphDemo:



    I will keep working on making it more efficient.
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You are right. Sometimes Java <= 7 is much easier. What about:

    Now, I have not much to remark, but here goes:

    1) Your method 'generateAdjacencyMatrix' returns a String. That is fine for printing purposes, but sometimes we will need the actual matrix. So, why not return the matrix in that method? You can then have a separate method that makes a nice String for this matrix.

    2) concerning the method: public Map<Integer, Set<Integer>> getAdjacencyList().
    You return the adjacencyMap, which is dangerous! What if some external method calls this method, and then clears the map? The Graph would then suddenly be left with an empty Map! So, ideally we should return a copy of that Map. Can you see, in the HashMap api, if there is an easy way to get a copy of a HashMap?

    Unfortunately, the story doesn't end here. By returning a reference of (a copy of) our Map we also supply references to the Sets that act as our values. So, even though we supply a copy of the Map, we can still clear the Sets in it! Here is a simple demo:

    But let's leave that for later. So, can you make the getListOfEdges and getAdjacencyMatrix so that these return a real list and a real matrix? Again, you already have the logic and it looks correct to me.

    And then it is time to read the API of a LinkedList. Next time we will discuss the method from much earlier in this topic, how to determine if the graph is connected.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Okay, I am returning unmodifiable collection now. Though it doesn't protect against modifying the referenced value. Will work on that.

    Here are the updated classes.

    Graph:

    GraphDemo:


    I am familiar with LinkedList operations. By definition, a graph is connected when all its vertices are connected to each other.

    So from LinkedList point of view, we should have a vertex having adjacency list containing all other vertices or adjacency matrix having 1 for all other vertices.

    This logic should work right?
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hmm...

    Let us make three different graphs, all undirected:

    1) graph = new Graph(6, true).
    Make edges between the vertices 0, 1 and 2, and between the vertices 3, 4, 5. The graph is clearly not connected. Look at the adjacency matrix and adjacencyMap. Are they what you would expect for an unconnected graph?

    2) same question for the graph(6, true), where we have this scheme (vertices): 0 - 1 - 2 - 3 - 4 - 5.
    Now this graph is connected, but are the matrix and the map anything like you would expect?

    3) create a graph(25, true), such that for any pair(i, j) with i not equal to j, there is a 50% chance of there being an edge between vertices i and j.
    You can either put all the edges in by hand, or, more interesting, create a method that creates such a graph, with parameters the number of vertices and the chance p.
    Then have a look again at the matrix and map. Can you tell (or get an impression) from these if the graph is connected?

    Having looked at the matrices and maps, think about how to determine if an undirected graph is connected or not. Then have a look at your original algorithm in your opening post, and reread my reply in which I described a solution using a Queue. See if both methods are more clear now.

    Last remark: about the immutability: indeed, an unmodifiableMap also unveils references to the mutable values (the Set<Integer>s of our map), that can be changed just as well. Coincidently, today a topic on immutability has been started. You might give it a read. We will address this point later.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Will work on point 3 and adding immutability.

    Here are the results after working on point 1 and point 2.

    Adjacency Matrix for unconnected graph:

    Adjacency Matrix for connected graph:


    Cell No:  AdjacencyMatrix[3][2] and AdjacencyMatrix[2][3] looks like the only difference between these two graphs.

    The pattern I see is that the connected graph are symmetrical along the diagonal axis. This should be the reflexive property.

     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    For an directed graph, the output would not be symmetrical.

    But the matrix should have 1's along the diagonal.

    This should work right?
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Here is a crude logic for connected graph.

    Graph:


    GraphDemo:

    Here is the method I am working on now which iterates all vertices in matrix:

    This logic is flawed. I am working on it.
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I've changed your latest version of 'public boolean isConnected()', to make the output slightly more clear:

    Now, I ran this testprogram:

    and this was the output:

    As you see, the adjacencyList, the ListOfEdges and the adjacencyMatrix are fine.

    Next it shows that 0-->1 is connected, okay. But then it shows that 1-->0 is connected as well. Although that is true, given the nested for-next loop that you issue I would have expected to see the line '0-->2 is connected' first. Can you find out why we do not see that line? Also interesting is that 3-->4 and 4-->3 areboth displayed. Why?
    And finally, although we see that there are only 4 edges, your method nevertheless says there are 5. And since 5 > nrOfVertices - 1 (i.e. 4) it concludes that the graph is not connected.

    The first question therefore is: why is the edgecount wrong?
    And, unfortunately, the conclusion that a graph is connected if and only if the number of Edges found == nrOfVertices - 1, is incorrect.

    As they say in mathmatics: the nrOfEdges >= nrOfVertices - 1 is a necessary condition, but it is not a sufficient condition. Meaning that if the nrOfEdges < nrOfVertices - 1, then the graph is not connected. But that does not mean that when nrOfEdges >= nrOfVertices - 1, that the graph is connected. Compare it with these statements:
    necessary for the integer p to be positive is thet p > -10. However, that alone is not sufficient.
    Sufficient for p to be positive is that p > 10, but that is not necessary.

    As another example: say that we have a complete graph, i.e. an undirected graph in which every two vertices have an edge. Suppose we have 6 vertices, how many edges do we have? (and edge(0.1) == edge(1,0) so beware of double counting). Clearly, the graph is connected, but do we have that nrOfEdges == nrOfVertices - 1?

    And coming back to the graph that I tested: we have 4 edges, with 5 vertices. Yet the graph is not connected.

    It is clear: counting the edges does not tell us much about the graph being connected. That is why I asked you to create three different graphs and to inspect th adjacency matrices, to get an idea if these matrices could answer the connectedness question without further ado. If only life were that simple...

    I'll await your working on the logic. But my next reply will be describing in more detail the Queue method, and I will use another interesting structure that can help answering the connectedness-question, named UnionFind. I heard about that a couple of weeks ago, but it is an interesting structure.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the feedback.

    Here is my current Graph:


    Here are my views on the points you raised.


    Next it shows that 0-->1 is connected, okay. But then it shows that 1-->0 is connected as well. Although that is true, given the nested for-next loop that you issue I would have expected to see the line '0-->2 is connected' first.

         The reason for 0-->2 not showing and 2-->0 showing is  statement at line 145.
         Once the vertex is marked visited. It is skipped next time. The idea was to mark each unique vertex and increment the vertex count. I can move this marking outside inner for loop, but that would visit each vertex
          multiple times.


       Also interesting is that 3-->4 and 4-->3 areboth displayed. Why?

          3-->4 and 4-->3 are both printed because when we visit vertex 3, we mark it visited, and next time we visit vertex 4 which is still unmarked. Should I mark both vertices as visited when I come to line number: 145?


       And finally, although we see that there are only 4 edges, your method nevertheless says there are 5. And since 5 > nrOfVertices - 1 (i.e. 4) it concludes that the graph is not connected.

           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?



    Suppose we have 6 vertices, how many edges do we have? (and edge(0.1) == edge(1,0) so beware of double counting).

           The condition at line number:145  handles undirected edge cases, we are testing both the connections together and incrementing the vertexCount once.


    And coming back to the graph that I tested: we have 4 edges, with 5 vertices. Yet the graph is not connected.

          Graph is not connected due to point mentioned above. Unless I am not seeing something.


    It is clear: counting the edges does not tell us much about the graph being connected. That is why I asked you to create three different graphs and to inspect th adjacency matrices, to get an idea if these matrices could answer the connectedness question without further ado.

           I will run all the three scenarios few times and revert back. Definitely relying on vertex and edge count is not correct. Will search for optimal criteria.

     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!