Connected Graph using Adjacency Matrix

[s ravi chandran]

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.

public class AdjacencyMatrixConnectedGraph {

	public static void main(String[] args) {

		int adjacency_matrix[][] = {
				{0 ,1 ,0 ,1 ,0},
				{0 ,0 ,1 ,0 ,0},
				{0 ,0 ,0 ,0 ,0},
				{0 ,1 ,0 ,0 ,0},
				{0 ,0 ,0 ,0 ,0}

		};

		/* Connected Graph
		 * 
		 *  {0 ,1 ,1 ,1 ,1},
			{1 ,0 ,1 ,1 ,1},
			{1 ,1 ,0 ,1 ,1},
			{1 ,1 ,1 ,0 ,1},
			{1 ,1 ,1 ,1 ,0}*/

	boolean result = isConnected(adjacency_matrix, 5);

		if (result)
		{
			System.out.println("The graph is connected");
		}else
		{
			System.out.println("The graph is disconnected");
		}
	}

	private static boolean isConnected(int[][] adjacency_matrix, int number_of_nodes) {
		int visited[] = new int[number_of_nodes ];

		for(int row=0; row< number_of_nodes; row++)
		{
			for(int col=0; col < number_of_nodes; col++){

				if(adjacency_matrix[row][col]==1 && visited[row]==0)
				{
					visited[row] = 1;
					System.out.println("new visit");
				}

			}
		}

		boolean connected = false;

		System.out.println(Arrays.toString(visited));

		for (int vertex = 1; vertex < number_of_nodes; vertex++)
		{
			if (visited[vertex] == 1) 
			{
				connected = true;
			} else
			{
				connected = false;
				break;
			}
		}

		return connected;

	}

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]

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]

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]

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]

Carey pointed out about different braces, so apologies for my recent post Carey and OP.

[s ravi chandran]

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.

public class AdjacencyMatrixConnectedGraph 
{
	 
    public static void main(String[] args) 
    {
 
        int adjacencyMatrix[][] = {
                {0 ,1 ,0 ,1 ,0},
                {0 ,0 ,1 ,0 ,0},
                {0 ,0 ,0 ,0 ,0},
                {0 ,1 ,0 ,0 ,0},
                {0 ,0 ,0 ,0 ,0}
        };
 
    boolean result = isConnected(adjacencyMatrix);
 
        if (result)
        {
            System.out.println("The graph is connected");
        }else
        {
            System.out.println("The graph is disconnected");
        }
    }
 
    private static boolean isConnected(int[][] adjacencyMatrix) 
    {
        int visited[] = new int[adjacencyMatrix.length ];
 
        for(int row=0; row< adjacencyMatrix.length; row++)
        {
            for(int col=0; col < adjacencyMatrix.length; col++)
            {
 
                if(adjacencyMatrix[row][col]==1 && visited[row]==0)
                {
                    visited[row] = 1;
                }
 
            }
        }
 
        boolean connected = false;
 
        for (int vertex = 0; vertex < adjacencyMatrix.length; vertex++)
        {
            if (visited[vertex] == 1) 
            {
                connected = true;
            } else
            {
                connected = false;
                break;
            }
        }
 
        return connected;
 
    }
    
}

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]

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]

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]

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]

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:

public class Vertex<E >
{

	private E element;
	private Vertex<E> next;
	private List<Vertex<E>> neighbors;

	public Vertex()
	{
		neighbors = new ArrayList<>();
	}

	public E getElement()
	{
		return element;
	}
	
	public void setElement(E element) 
	{
		this.element = element;
	}

	public Vertex<E> getNext()
	{
		return next;
	}

	public void setNext(Vertex<E> next) 
	{
		this.next = next;
	}

	public void addNeighbor(Vertex<E> e)
	{
		if(!neighbors.contains(e))
			neighbors.add(e);
	}
	
	public List<Vertex<E>> getNeighbors()
	{
		return neighbors;
	}
	
	public void removeNeighbor(Vertex<E> e)
	{
		neighbors.remove(e);
	}

	@Override
	public int hashCode() 
	{
		return element.hashCode();
	}

	@Override
	public boolean equals(Object obj)
	{
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Vertex other = (Vertex) obj;
		if (element == null) {
			if (other.element != null)
				return false;
		} else if (!element.equals(other.element))
			return false;
		return true;
	}
}

Edge:

public class Edge<E> {

	private Vertex<E> vertex1;
	private Vertex<E> vertex2;

	public Vertex<E> getVertex1()
        {
		return vertex1;
	}
	public void setVertex1(Vertex<E> vertex1) 
       {
		this.vertex1 = vertex1;
	}
	public Vertex<E> getVertex2() 
{
		return vertex2;
	}
	public void setVertex2(Vertex<E> vertex2) 
       {
		this.vertex2 = vertex2;
	}
    	
@Override
	public int hashCode()
	{
		final int prime = 31;
		int result = 1;
		result = prime * result + ((vertex1 == null) ? 0 : vertex1.hashCode());
		result = prime * result + ((vertex2 == null) ? 0 : vertex2.hashCode());
		return result;
	}
	
	@Override
	public boolean equals(Object obj)
	{
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Edge<E> other = (Edge) obj;
		if (vertex1 == null) {
			if (other.vertex1 != null)
				return false;
		} else if (!vertex1.equals(other.vertex1))
			return false;
		if (vertex2 == null) {
			if (other.vertex2 != null)
				return false;
		} else if (!vertex2.equals(other.vertex2))
			return false;
		return true;
	}
}

Graph:

public class Graph {

	private List<Edge<Integer>> listOfEdges;
	
	public Graph()
	{
		listOfEdges = new ArrayList<>();
	}
	
	public void addEdge(Edge<Integer> e)
	{
		listOfEdges.add(e);
	}
	
	public void removeEdge(Edge<Integer> e)
	{
		listOfEdges.remove(e);
	}
}

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]

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]

Updated Graph class:

public class Graph {

	private List<Edge<Integer>> listOfEdges;
	private final boolean isUndirected;

	public Graph(boolean isUndirected)
	{
		listOfEdges = new ArrayList<>();
		this.isUndirected = isUndirected;
	}

	public void addEdge(Edge<Integer> e)
	{

		if(!listOfEdges.contains(e))
		{

			listOfEdges.add(e);

			e.getVertex1().addNeighbor(e.getVertex2());

			if(isUndirected)
			{
				e.getVertex2().addNeighbor(e.getVertex1());
			}

		}

	}

	public void removeEdge(Edge<Integer> e)
	{
		listOfEdges.remove(e);
	}
	
	public List<Edge<Integer>> getEdgeList()
	{
		return listOfEdges;
	}
}

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]

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]

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:

public class Graph {

	private List<Edge<Integer>> listOfEdges;

	private final boolean isUndirected;

	private List<Vertex<Integer>> listOfVertices;

	public Graph(boolean isUndirected)
	{
		listOfEdges = new ArrayList<>();
		listOfVertices = new ArrayList<>();
		this.isUndirected = isUndirected;
	}

	public void addEdge(Edge<Integer> e)
	{

		if(!listOfEdges.contains(e))
		{

			listOfEdges.add(e);

			e.getVertex1().addNeighbor(e.getVertex2());

			if(isUndirected)
			{
				e.getVertex2().addNeighbor(e.getVertex1());
			}

		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(listOfEdges.contains(e))
		{
			listOfEdges.remove(e);

			e.getVertex1().removeNeighbor(e.getVertex2());

			if(isUndirected)
			{
				e.getVertex2().removeNeighbor(e.getVertex1());
			}

		}

	}

	public void addVertex(Vertex<Integer> v)
	{
		if(!listOfVertices.contains(v))
		{
			listOfVertices.add(v) ;
		}
	}

	public void removeVertex(Vertex<Integer> v)
	{
		if(listOfVertices.contains(v))
		{
			listOfVertices.remove(v) ;
		}
	}


	public List<Edge<Integer>> getEdgeList()
	{
		return listOfEdges;
	}

	public static void main(String[] args)
	{

		Vertex<Integer> v1 = new Vertex<>();
		v1.setElement(100001);

		Vertex<Integer> v2 = new Vertex<>();
		v2.setElement(100002);

		Vertex<Integer> v4 = new Vertex<>();
		v4.setElement(100004);

		Vertex<Integer> v3 = new Vertex<>();
		v3.setElement(100003);

		Vertex<Integer> v5 = new Vertex<>();
		v5.setElement(100001);

		Vertex<Integer> v6 = new Vertex<>();
		v6.setElement(100002);


		Edge<Integer> e1 = new Edge<>();
		e1.setVertex1(v1);
		e1.setVertex2(v2);

		Edge<Integer> e2 = new Edge<>();
		e2.setVertex1(v4);
		e2.setVertex2(v3);

		Edge<Integer> e3 = new Edge<>();
		e3.setVertex1(v5);
		e3.setVertex2(v6);


		System.out.println("Edge1 and Edge2 not equal: "+(e1.equals(e2)));

		System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

	}
}

[Piet Souris]

Morning!

Okay.

Some remarks and questions:

1) you have this code::

 

 Edge<Integer> e1 = new Edge<>();
    e1.setVertex1(v1);
    e1.setVertex2(v2);

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:
   

Graph graph = new Graph(true);   // graph is undirected
    Edge<Integer> edge = new Edge<>(1,3);
    graph.addEdge(edge);
    System.out.println(graph.getEdgeList());
    graph.removeEdge(edge);
    System.out.println(graph.getEdgeList());

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]

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:

public class Vertex<E extends Comparable<E>>
{

	private E element;
	private Vertex<E> next;
	private List<Vertex<E>> neighbors;

	public Vertex()
	{
		neighbors = new ArrayList<>();
	}

	public E getElement()
	{
		return element;
	}
	
	public void setElement(E element) 
	{
		this.element = element;
	}

	public Vertex<E> getNext()
	{
		return next;
	}

	public void setNext(Vertex<E> next) 
	{
		this.next = next;
	}

	public void addNeighbor(Vertex<E> e)
	{
		if(!neighbors.contains(e))
			neighbors.add(e);
	}
	
	public List<Vertex<E>> getNeighbors()
	{
		return neighbors;
	}
	
	public void removeNeighbor(Vertex<E> e)
	{
		neighbors.remove(e);
	}

	@Override
	public int hashCode() 
	{
		return element.hashCode();
	}

	@Override
	public boolean equals(Object obj)
	{
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Vertex other = (Vertex) obj;
		if (element == null) {
			if (other.element != null)
				return false;
		} else if (!element.equals(other.element))
			return false;
		return true;
	}

	@Override
	public String toString()
	{
		return "element=" + element ;
	}

Edge:

public class Edge<E extends Comparable<E>>
{

	private Vertex<E> vertex1;
	private Vertex<E> vertex2;

	public Edge(E vertex1, E vertex2)
	{
		if(vertex1!=null)
		{
			this.vertex1 = new Vertex<E>();
			this.vertex1.setElement(vertex1);
		}

		if(vertex2!=null)
		{
			this.vertex2 = new Vertex<E>();
			this.vertex2.setElement(vertex2);
		}

	}

	public Vertex<E> getVertex1()
	{
		return vertex1;
	}
	public Vertex<E> getVertex2()
	{
		return vertex2;
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		Edge<?> edge = (Edge<?>) o;

		if (!vertex1.equals(edge.vertex1)) return false;
		return vertex2.equals(edge.vertex2);

	}

	@Override
	public int hashCode() {
		int result = vertex1.hashCode();
		result = 31 * result + vertex2.hashCode();
		return result;
	}

	@Override
	public String toString() {
		return "Edge{" + vertex1 +", " + vertex2 +	'}';
	}
}

Graph:

public class Graph {

	private List<Edge<Integer>> listOfEdges;

	private final boolean isUndirected;

	private List<Vertex<Integer>> listOfVertices;

	public Graph(boolean isUndirected)
	{
		listOfEdges = new ArrayList<>();

		listOfVertices = new ArrayList<>();
		this.isUndirected = isUndirected;
	}

	public void addEdge(Edge<Integer> e)
	{

		if(!listOfEdges.contains(e))
		{

			listOfEdges.add(e);

			e.getVertex1().addNeighbor(e.getVertex2());

			if(isUndirected)
			{
				e.getVertex2().addNeighbor(e.getVertex1());
			}

		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(listOfEdges.contains(e))
		{
			listOfEdges.remove(e);

			e.getVertex1().removeNeighbor(e.getVertex2());

			if(isUndirected)
			{
				e.getVertex2().removeNeighbor(e.getVertex1());
			}

		}

	}

	public void addVertex(Vertex<Integer> v)
	{
		if(!listOfVertices.contains(v))
		{
			listOfVertices.add(v) ;
		}
	}

	public void removeVertex(Vertex<Integer> v)
	{
		if(listOfVertices.contains(v))
		{
			listOfVertices.remove(v) ;
		}
	}


	public List<Edge<Integer>> getEdgeList()
	{
		return listOfEdges;
	}

	public static void main(String[] args)
	{

		Edge<Integer> e1 = new Edge<>(100001, 100002);

		Edge<Integer> e2 = new Edge<>(100004, 100003);

		Edge<Integer> e3 = new Edge<>(100001, 100002);

		System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));

		System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

		Graph graph = new Graph(true);
		graph.addEdge(e1);

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

		graph.removeEdge(e1);
		System.out.println("Graph Edge List:  "+graph.getEdgeList());
	}
}

I will work on adding Adjacency List and Adjacency Matrix.

[s ravi chandran]

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]

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]

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:

public class Edge<E extends Comparable<E>>
{
 
    private E vertex1;
    private E vertex2;
 
    public Edge(E vertex1, E vertex2)
    {
        if(vertex1!=null)
        {
            this.vertex1 = vertex1;
        }
 
        if(vertex2!=null)
        {
            this.vertex2 = vertex2;
        }
 
    }
 
    public E getVertex1()
    {
        return vertex1;
    }
    public E getVertex2()
    {
        return vertex2;
    }
 
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
 
        Edge<?> edge = (Edge<?>) o;
 
        if (!vertex1.equals(edge.vertex1)) return false;
        return vertex2.equals(edge.vertex2);
 
    }
 
    @Override
    public int hashCode() {
        int result = vertex1.hashCode();
        result = 31 * result + vertex2.hashCode();
        return result;
    }
 
    @Override
    public String toString() {
        return "Edge{" + vertex1 +", " + vertex2 +  '}';
    }
}

Graph:

public class Graph {

//redundant field
	private List<Edge<Integer>> listOfEdges;

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyList;

	public Graph(boolean isUndirected)
	{
		listOfEdges = new ArrayList<>();

		this.isUndirected = isUndirected;

		adjacencyList = new HashMap<>();
	}

	public void addEdge(Edge<Integer> e)
	{

		if(!listOfEdges.contains(e))
		{

			listOfEdges.add(e);

			if(adjacencyList.containsKey(e.getVertex1()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
				adjacentNodes.add(e.getVertex2());
			}
			else
			{
				Set<Integer> adjacentNodes = new HashSet<>();
				adjacencyList.put(e.getVertex1(), adjacentNodes);
				adjacentNodes.add(e.getVertex2());
			}

			if(isUndirected)
			{

				if(adjacencyList.containsKey(e.getVertex2()))
				{
					Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
					adjacentNodes.add(e.getVertex1());
				}
				else
				{
					Set<Integer> adjacentNodes = new HashSet<>();
					adjacencyList.put(e.getVertex2(), adjacentNodes);
					adjacentNodes.add(e.getVertex1());
				}
			}

		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(listOfEdges.contains(e))
		{
			listOfEdges.remove(e);

			if(adjacencyList.containsKey(e.getVertex1()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
				adjacentNodes.remove(e.getVertex2());
			}

			if(isUndirected)
			{

				if(adjacencyList.containsKey(e.getVertex2()))
				{
					Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
					adjacentNodes.remove(e.getVertex1());
				}

			}

		}

	}

	public List<Edge<Integer>> getEdgeList()
	{
		return listOfEdges;
	}

	public static void main(String[] args)
	{

		Edge<Integer> e1 = new Edge<>(100001, 100002);

		Edge<Integer> e2 = new Edge<>(100004, 100003);

		Edge<Integer> e3 = new Edge<>(100001, 100002);

		System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));

		System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

		Graph graph = new Graph(true);
		graph.addEdge(e1);

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

		graph.removeEdge(e1);
		System.out.println("Graph Edge List:  "+graph.getEdgeList());
	}
}

Does the adjacency list functionality look correct?

[Piet Souris]

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]

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:

Edge e = new Edge(4, null);

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:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyList;

	private List<Integer> listOfVertices;

	public Graph(int nrOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyList = new HashMap<>();

		listOfVertices = new ArrayList<>();

		initializeVertices(nrOfVertices);
	}

	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) || listOfVertices.contains(e.getVertex1()))  )
		{
			System.out.println("The edge has vertex out of range");
			throw new IllegalArgumentException("One or both the vertex are out of range");
		}
		
		if(adjacencyList.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
			adjacentNodes.add(e.getVertex2());
		}
		else
		{
			Set<Integer> adjacentNodes = new HashSet<>();
			adjacencyList.put(e.getVertex1(), adjacentNodes);
			adjacentNodes.add(e.getVertex2());
		}

		if(isUndirected)
		{

			if(adjacencyList.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
				adjacentNodes.add(e.getVertex1());
			}
			else
			{
				Set<Integer> adjacentNodes = new HashSet<>();
				adjacencyList.put(e.getVertex2(), adjacentNodes);
				adjacentNodes.add(e.getVertex1());
			}
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyList.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected)
		{

			if(adjacencyList.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
			}

		}

	}
	
	@Override
	public String toString() {
		return "Graph [isUndirected=" + isUndirected + ", adjacencyList="
				+ adjacencyList + "]";
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyList;
	}
	
	public List<Integer> getVertices()
	{
		return listOfVertices;
	}
}

Added a main class GraphDemo:

public class GraphDemo {

	public static void main(String[] args) {
		Graph graph = new Graph(10, true);
		Edge<Integer> e1 = new Edge<>(2, 4);
		 
        Edge<Integer> e2 = new Edge<>(5, 6);
 
        Edge<Integer> e3 = new Edge<>(2, 4);
 
        System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));
 
        System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));
 
        graph.addEdge(e1);
 
        System.out.println("Graph Edge List:  "+graph);
 
        graph.removeEdge(e1);
        System.out.println("Graph Edge List:  "+graph);
	}
}

[s ravi chandran]

Updated Graph toString() to print just the Edges:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyList;

	private List<Integer> listOfVertices;

	public Graph(int nrOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyList = new HashMap<>();

		listOfVertices = new ArrayList<>();

		initializeVertices(nrOfVertices);
	}

	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) || listOfVertices.contains(e.getVertex1()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range");
		}
		
		if(adjacencyList.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
			adjacentNodes.add(e.getVertex2());
		}
		else
		{
			Set<Integer> adjacentNodes = new HashSet<>();
			adjacencyList.put(e.getVertex1(), adjacentNodes);
			adjacentNodes.add(e.getVertex2());
		}

		if(isUndirected)
		{

			if(adjacencyList.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
				adjacentNodes.add(e.getVertex1());
			}
			else
			{
				Set<Integer> adjacentNodes = new HashSet<>();
				adjacencyList.put(e.getVertex2(), adjacentNodes);
				adjacentNodes.add(e.getVertex1());
			}
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyList.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected)
		{

			if(adjacencyList.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
			}

		}

	}
	
	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}";
	}

	private String printEdges() {

		Set< Integer> vertexNode = adjacencyList.keySet();
		StringBuilder sb = new StringBuilder();
		
		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyList.get(vertex);
			if(connectedNodes!=null)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append(vertex+"-->[]");
			}
			
		}
		
		return sb.toString();
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyList;
	}
	
	public List<Integer> getVertices()
	{
		return listOfVertices;
	}
}

Here is how the output looks like:

Edge1 and Edge2 not equal: true
Edge1 and Edge3 equal: true
Graph Edge List:  Edges={
[2-->3]
[2-->4]
[3-->2]
[4-->2]
[5-->6]
[6-->5]
}
Graph Edge List:  Edges={
[2-->3]
[3-->2]
[5-->6]
[6-->5]
}

[Piet Souris]

We're almost there.

Again some remarks:

1) if graph = new Graph(10, true), test if we can do:

graph.addEdge(new Edge<Integer>(9, 25));

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:

graph.addEdge(new Edge<String>("a", "b"));

on beforehand: what do you expect?

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

if (adjacencyList.containsKey(e.getVertex1())) {
    Set<Integer> adjacentNodes = adjacencyList.get(e.getVertex1());
    adjacentNodes.add(e.getVertex2());
} 
else {
    Set<Integer> adjacentNodes = new HashSet<>();
    adjacencyList.put(e.getVertex1(), adjacentNodes);
    adjacentNodes.add(e.getVertex2());
}

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

adjacencyList.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2();

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]

Thanks for the feedback.

Here is the updated code.

Graph:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;

	public Graph(int nrOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		initializeVertices(nrOfVertices);
	}

	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}
		
		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());
		
		if(isUndirected)
		{
			
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected)
		{

			if(adjacencyMap.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
			}

		}

	}
	
	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}";
	}

	private String printEdges() {

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();
		
		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}
			
		}
		
		return sb.toString();
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyMap;
	}
	
	public List<Integer> getVertices()
	{
		return listOfVertices;
	}
}

GraphDemo:

public class GraphDemo {

	public static void main(String[] args) {
		Graph graph = new Graph(10, true);
		Edge<Integer> e1 = new Edge<>(2, 4);
		 
        Edge<Integer> e2 = new Edge<>(5, 6);
 
        Edge<Integer> e3 = new Edge<>(2, 4);
        
        Edge<Integer> e4 = new Edge<>(2, 3);
 
        System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));
 
        System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));
 
        graph.addEdge(e1);
        graph.addEdge(e2);
        graph.addEdge(e4);
 
        System.out.println("Graph Edge List:  "+graph);
 
        graph.removeEdge(e1);
        System.out.println("Graph Edge List:  "+graph);
        
        graph.addEdge(new Edge<Integer>(9, 25));
        System.out.println("should fail Graph Edge List:  "+graph);
        
        //Compile time error
        //graph.addEdge(new Edge<String>("a", "b"));
	}
}

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]

Updated the code with initial adjacency matrix logic.

VertexIndexer:

public class VertexIndexer<E> {

	private int noOfVertices;
	private Map<E, Integer> indexMap;

	public VertexIndexer(){
		indexMap = new HashMap<>();
	}

	public void addVertex(E vertex)
	{
		if(!indexMap.containsKey(vertex))
			indexMap.put(vertex, noOfVertices++)   	;
	}

	public void removeVertex(E vertex)
	{
		if(indexMap.containsKey(vertex))
		{
			indexMap.remove(vertex)   	;
			noOfVertices--;
		}
	}

	public int getVertexIndex(E vertex)
	{
		if(!indexMap.containsKey(vertex))
			return -1;

		return indexMap.get(vertex);
	}

	@Override
	public String toString() {
		return "AdjacencyIndex [noOfVertices=" + noOfVertices + ", indexMap="
				+ indexMap + "]";
	}

}

Graph:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;
	
	private VertexIndexer<Integer> indexer;
	
	private int[][] adjacencyMatrix;

	public Graph(int noOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		initializeVertices(noOfVertices);
		
		//Adjacency Matrix
		indexer = new VertexIndexer<Integer>();
		
		adjacencyMatrix = new int[noOfVertices][noOfVertices];
	}

	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}
		
		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());
		
		indexer.addVertex(e.getVertex1());
		indexer.addVertex(e.getVertex2());
		adjacencyMatrix[indexer.getVertexIndex(e.getVertex1())][indexer.getVertexIndex(e.getVertex2())] = 1;
		
		if(isUndirected)
		{
			
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
			
			adjacencyMatrix[indexer.getVertexIndex(e.getVertex2())][indexer.getVertexIndex(e.getVertex1())] = 1;
		}
		
		
	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
			
		}
		
		adjacencyMatrix[indexer.getVertexIndex(e.getVertex1())][indexer.getVertexIndex(e.getVertex2())] = 0;

		if(isUndirected)
		{

			if(adjacencyMap.containsKey(e.getVertex2()))
			{
				Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
				
			}
			
			adjacencyMatrix[indexer.getVertexIndex(e.getVertex2())][indexer.getVertexIndex(e.getVertex1())] = 0;

		}

	}
	
	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n"+
				  printAdjacencyMatrix();
	}

	private String printAdjacencyMatrix() {
		StringBuilder sb = new StringBuilder();
		
		sb.append("AdjacencyMatrix{");
		
		for(int[] vertexNodes: adjacencyMatrix)
		{
			sb.append("\n");
			sb.append(Arrays.toString(vertexNodes));
		}
		
		sb.append("}");
		sb.append("\n");
		
		return sb.toString();
	}

	private String printEdges() {

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();
		
		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}
			
		}
		
		return sb.toString();
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyMap;
	}
	
	public List<Integer> getVertices()
	{
		return listOfVertices;
	}
}

Sample Output:

Edge1 and Edge2 not equal: true
Edge1 and Edge3 equal: true
Graph Edge List:  Edges={
[2-->4]
[2-->3]
[3-->2]
[4-->2]
[5-->6]
[6-->5]
}
AdjacencyMatrix{
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0]}

Graph Edge List:  Edges={
[2-->3]
[3-->2]
[4-->EMPTY]
[5-->6]
[6-->5]
}
AdjacencyMatrix{
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0]}

Let me know if this logic needs some enhancement.

[s ravi chandran]

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.

public class VertexIndexer<E extends Comparable<E>> {

	private int noOfVertices;
	private SortedMap<E, Integer> indexMap;

	public VertexIndexer(){
		indexMap = new TreeMap<>();
	}

	public void addVertex(E vertex)
	{
		if(!indexMap.containsKey(vertex))
		{
			indexMap.put(vertex, noOfVertices++)   	;
			
			reshuffle();
		}
			
	}

	private void reshuffle() {
     int initialVertexIndex = 0;
     
     for(E key: indexMap.keySet())
     {
    	 indexMap.put(key, initialVertexIndex++);
     }
		
	}

	public void removeVertex(E vertex)
	{
		if(indexMap.containsKey(vertex))
		{
			indexMap.remove(vertex)   	;
			noOfVertices--;
			reshuffle();
		}
	}

	public int getVertexIndex(E vertex)
	{
		if(!indexMap.containsKey(vertex))
			return -1;

		return indexMap.get(vertex);
	}

	@Override
	public String toString() {
		return "AdjacencyIndex [noOfVertices=" + noOfVertices + ", indexMap="
				+ indexMap + "]";
	}

}

Updated Graph class to include viewing index of each vertex:

@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n"+
				indexer+"\n"+
				  printAdjacencyMatrix();
	}

This change gives the following output:

Graph Edge List:  Edges={
[2-->3]
[3-->2]
[4-->EMPTY]
[5-->6]
[6-->5]
}
AdjacencyIndex [noOfVertices=5, indexMap={2=0, 3=1, 4=2, 5=3, 6=4}]
AdjacencyMatrix{
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 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, 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, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]}

The index will update everytime an element is inserted.

[s ravi chandran]

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]

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]

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]

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:

Graph Edge List:  Edges={
[2-->3]
[3-->2]
[4-->EMPTY]
[5-->6]
[6-->5]
}
AdjacencyIndex [noOfVertices=5, indexMap={2=0, 3=4, 4=1, 5=2, 6=3}]
AdjacencyMatrix{
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0]}

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:

public class Edge<E extends Comparable<E>>
{

	private E vertex1;
	private E vertex2;

	public Edge(E vertex1, E vertex2)
	{
		if(vertex1!=null)
		{
			this.vertex1 = vertex1;
		}

		if(vertex2!=null)
		{
			this.vertex2 = vertex2;
		}

	}

	public E getVertex1()
	{
		return vertex1;
	}
	public E getVertex2()
	{
		return vertex2;
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		Edge<?> edge = (Edge<?>) o;

		if (!vertex1.equals(edge.vertex1)) return false;
		return vertex2.equals(edge.vertex2);

	}

	@Override
	public int hashCode() {
		int result = vertex1.hashCode();
		result = 31 * result + vertex2.hashCode();
		return result;
	}

	@Override
	public String toString() {
		return "Edge{" + vertex1 +", " + vertex2 +  '}';
	}
}

Graph:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;

	private int[][] adjacencyMatrix;

	public Graph(int noOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		initializeVertices(noOfVertices);
		//Adjacency Matrix
		adjacencyMatrix = new int[noOfVertices][noOfVertices];
	}

	//todo: this needs to be rectified.
	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}

		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());

		if(isUndirected)
		{
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected && adjacencyMap.containsKey(e.getVertex2()))
		{
				Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
		}

	}

	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n"+
				printAdjacencyMatrix();
	}

	private String printAdjacencyMatrix() {
		StringBuilder sb = new StringBuilder();

		sb.append("AdjacencyMatrix{");

		for(int[] vertexNodes: adjacencyMatrix)
		{
			sb.append("\n");
			sb.append(Arrays.toString(vertexNodes));
		}

		sb.append("}");
		sb.append("\n");

		return sb.toString();
	}

	private String printEdges() {

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();

		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}

		}

		return sb.toString();
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyMap;
	}

	public List<Integer> getVertices()
	{
		return listOfVertices;
	}
}

GraphDemo:

public class GraphDemo {

    public static void main(String[] args) {
        Graph graph = new Graph(10, true);
        Edge<Integer> e1 = new Edge<>(2, 4);

        Edge<Integer> e2 = new Edge<>(5, 6);

        Edge<Integer> e3 = new Edge<>(2, 4);

        Edge<Integer> e4 = new Edge<>(2, 3);

        System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));

        System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

        graph.addEdge(e1);
        graph.addEdge(e2);
        graph.addEdge(e4);

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

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

        graph.addEdge(new Edge<Integer>(9, 25));
        System.out.println("should fail Graph Edge List:  "+graph);

        //Compile time error
        //graph.addEdge(new Edge<String>("a", "b"));
    }
}

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]

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:

public List<Edge<Integer>> getListOfEdges() {
    return adjacencyMap.keySet().stream()
        .flatMap(v -> adjacencyMap.get(v).stream().map(w -> new Edge<>(v, w)))
        .collect(Collectors.toList())
    ;
}

[s ravi chandran]

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:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;

	private int noOfVertices;

	public Graph(int noOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		this.noOfVertices = noOfVertices;

		initializeVertices(noOfVertices);
	}

	//todo: this needs to be rectified.
	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}

		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());

		if(isUndirected)
		{
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected && adjacencyMap.containsKey(e.getVertex2()))
		{
				Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
				adjacentNodes.remove(e.getVertex1());
		}

	}

	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n" +
				generateAdjacencyMatrix();
	}

/* Adjacency Matrix using Vertex Indexer
private String generateAdjacencyMatrix()
	{

		int[][] adjacencyMatrix = new int[noOfVertices][noOfVertices];

		VertexIndexer<Integer> indexer = new VertexIndexer<>();
		for( Integer vertex1: adjacencyMap.keySet())
		{
			indexer.addVertex(vertex1);

			Set<Integer> connectedVertices = adjacencyMap.get(vertex1);

			if(connectedVertices!=null)
			{
               for(Integer vertex2: connectedVertices)
			   {
                indexer.addVertex(vertex2);
				   adjacencyMatrix[indexer.getVertexIndex(vertex1)][indexer.getVertexIndex(vertex2)] = 1;

				   if(isUndirected)
					   adjacencyMatrix[indexer.getVertexIndex(vertex2)][indexer.getVertexIndex(vertex1)] = 1;
			   }
			}

		}

		return printAdjacencyMatrix(adjacencyMatrix);
	}*/

	private String printAdjacencyMatrix(int[][] adjacencyMatrix)
	{
		StringBuilder sb = new StringBuilder();

		sb.append("AdjacencyMatrix{");

		for(int[] vertexNodes: adjacencyMatrix)
		{
			sb.append("\n");
			sb.append(Arrays.toString(vertexNodes));
		}

		sb.append("}");
		sb.append("\n");

		return sb.toString();
	}

	private String printEdges()
	{

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();

		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}

		}

		return sb.toString();
	}

	public String generateAdjacencyMatrix()
	{

		int[][] adjacencyMatrix = new int[noOfVertices][noOfVertices];

         Set<Integer> connectingVertexSet = adjacencyMap.keySet();

		// retrieve connected vertices
		connectingVertexSet.stream().filter(key -> adjacencyMap.get(key) != null).forEach(key -> {
			Set<Integer> connectedVertexSet = adjacencyMap.get(key);

			connectedVertexSet.forEach(vertex2 -> {

				adjacencyMatrix[key][vertex2] = 1;

				if (isUndirected)
					adjacencyMatrix[vertex2][key] = 1;

			});
		});

		return printAdjacencyMatrix(adjacencyMatrix);
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return adjacencyMap;
	}

	public List<Integer> getVertices()
	{
		return listOfVertices;
	}

        public List<Edge<Integer>> getListOfEdges() {
		return adjacencyMap.keySet().stream()
				.flatMap(v -> adjacencyMap.get(v).stream().map(w -> new Edge<>(v, w)))
				.collect(Collectors.toList());
	}
}

GraphDemo:

public class GraphDemo {

    public static void main(String[] args) {
        Graph graph = new Graph(10, true);
        Edge<Integer> e1 = new Edge<>(2, 4);

        Edge<Integer> e2 = new Edge<>(5, 6);

        Edge<Integer> e3 = new Edge<>(2, 4);

        Edge<Integer> e4 = new Edge<>(2, 3);

        //     System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));

        // System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

        graph.addEdge(e1);
        graph.addEdge(e2);
        graph.addEdge(e4);

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

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

        graph.addEdge(new Edge<Integer>(9, 25));
        System.out.println("should fail Graph Edge List:  "+graph);

        //Compile time error
        //graph.addEdge(new Edge<String>("a", "b"));

    }
}

I will keep working on making it more efficient.

[Piet Souris]

You are right. Sometimes Java <= 7 is much easier. What about:

public List<Edge<Integer>> getListOfEdge() {
    List<Edge<Integer>> result = new ArrayList<>();
    for (int k: adjacencyMap.keySet()) {
        for (int m: adjacencyMap.get(k)) {
            result.add(new Edge<>(k, m));
        }
    }
    return result;
}

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:

public class HahsmapTester {
    public static void main(String... args) {
        Map<Integer, Set<Integer>> piet = new HashMap<>();
        Set<Integer> p = new HashSet<>();
        p.add(1);p.add(2);p.add(3);
        piet.put(0, p);
        System.out.println(piet);
        System.out.println("***********************");
        Map<Integer, Set<Integer>> copij = new HashMap<>(piet);
        copij.get(0).clear();
        System.out.println(piet);
    }
}

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]

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:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;

	private int noOfVertices;

	public Graph(int noOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		this.noOfVertices = noOfVertices;

		initializeVertices(noOfVertices);
	}

	//todo: this needs to be rectified.
	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}

		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());

		if(isUndirected)
		{
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected && adjacencyMap.containsKey(e.getVertex2()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
			adjacentNodes.remove(e.getVertex1());
		}

	}

	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n" +
				printAdjacencyMatrix(generateAdjacencyMatrix());
	}

	private String printAdjacencyMatrix(int[][] adjacencyMatrix)
	{
		StringBuilder sb = new StringBuilder();

		sb.append("AdjacencyMatrix{");

		for(int[] vertexNodes: adjacencyMatrix)
		{
			sb.append("\n");
			sb.append(Arrays.toString(vertexNodes));
		}

		sb.append("}");
		sb.append("\n");

		return sb.toString();
	}

	private String printEdges()
	{

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();

		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}

		}

		return sb.toString();
	}

	public int[][] generateAdjacencyMatrix()
	{

		int[][] adjacencyMatrix = new int[noOfVertices][noOfVertices];
		// retrieve  connecting  vertices
		adjacencyMap.keySet().stream().filter(key -> adjacencyMap.get(key) != null).forEach(vertex1 -> {

			//retrieve connected vertices
			adjacencyMap.get(vertex1).forEach(vertex2 -> {
				adjacencyMatrix[vertex1][vertex2] = 1;
				if (isUndirected)
					adjacencyMatrix[vertex2][vertex1] = 1;
			});
		});

		return adjacencyMatrix;
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return Collections.unmodifiableMap(adjacencyMap);
	}

	public List<Integer> getVertices()
	{
		return Collections.unmodifiableList(listOfVertices);
	}

	public List<Edge<Integer>> getListOfEdges() {
		return adjacencyMap.keySet().stream()
				.flatMap(v -> adjacencyMap.get(v).stream().map(w -> new Edge<>(v, w)))
				.collect(Collectors.toList());
	}
}

GraphDemo:

public class GraphDemo {

    public static void main(String[] args) {
        Graph graph = new Graph(10, true);
        Edge<Integer> e1 = new Edge<>(2, 4);

        Edge<Integer> e2 = new Edge<>(5, 6);

        Edge<Integer> e3 = new Edge<>(2, 4);

        Edge<Integer> e4 = new Edge<>(2, 3);

        //     System.out.println("Edge1 and Edge2 not equal: "+(!e1.equals(e2)));

        // System.out.println("Edge1 and Edge3 equal: "+(e1.equals(e3)));

        graph.addEdge(e1);
        graph.addEdge(e2);
        graph.addEdge(e4);

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

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

        graph.addEdge(new Edge<Integer>(9, 25));
        System.out.println("should fail Graph Edge List:  "+graph);

        //Compile time error
        //graph.addEdge(new Edge<String>("a", "b"));

    }
}

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]

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]

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:

AdjacencyMatrix{
[0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 0]}

Adjacency Matrix for connected graph:

AdjacencyMatrix{
[0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 0]}

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]

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]

Here is a crude logic for connected graph.

Graph:

public class Graph {
	 
    private final boolean isUndirected;
 
    private Map<Integer, Set<Integer>> adjacencyMap;
 
    private List<Integer> listOfVertices;
 
    private int noOfVertices;
 
    public Graph(int noOfVertices, boolean isUndirected)
    {
        this.isUndirected = isUndirected;
 
        adjacencyMap = new HashMap<>();
 
        listOfVertices = new ArrayList<>();
 
        this.noOfVertices = noOfVertices;
 
        initializeVertices(noOfVertices);
    }
 
    //todo: this needs to be rectified.
    private void initializeVertices(int vertexIndexLimit)
    {
 
        for(int index=0; index< vertexIndexLimit; index++ )
        {
            listOfVertices.add(index);
        }
    }
 
    public void addEdge(Edge<Integer> e)
    {
 
        if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
        {
            throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
        }
 
        adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());
 
        if(isUndirected)
        {
            adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
        }
 
    }
 
    public void removeEdge(Edge<Integer> e)
    {
 
        if(adjacencyMap.containsKey(e.getVertex1()))
        {
            Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
            adjacentNodes.remove(e.getVertex2());
        }
 
        if(isUndirected && adjacencyMap.containsKey(e.getVertex2()))
        {
            Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
            adjacentNodes.remove(e.getVertex1());
        }
 
    }
 
    @Override
    public String toString() {
        return "Edges={\n"
                + printEdges()+"}\n" +
                printAdjacencyMatrix(generateAdjacencyMatrix());
    }
 
    private String printAdjacencyMatrix(int[][] adjacencyMatrix)
    {
        StringBuilder sb = new StringBuilder();
 
        sb.append("AdjacencyMatrix{");
 
        for(int[] vertexNodes: adjacencyMatrix)
        {
            sb.append("\n");
            sb.append(Arrays.toString(vertexNodes));
        }
 
        sb.append("}");
        sb.append("\n");
 
        return sb.toString();
    }
 
    private String printEdges()
    {
 
        Set< Integer> vertexNode = adjacencyMap.keySet();
        StringBuilder sb = new StringBuilder();
 
        for(int vertex: vertexNode)
        {
            Set<Integer> connectedNodes = adjacencyMap.get(vertex);
            if(connectedNodes!=null && connectedNodes.size()>0)
            {
                for(int connectedVertex: connectedNodes)
                {
                    sb.append("[");
                    sb.append(vertex+"-->"+connectedVertex);
                    sb.append("]");
                    sb.append("\n");
                }
            }
            else
            {
                sb.append("[");
                sb.append(vertex+"-->EMPTY");
                sb.append("]");
                sb.append("\n");
            }
 
        }
 
        return sb.toString();
    }
 
    public int[][] generateAdjacencyMatrix()
    {
 
        int[][] adjacencyMatrix = new int[noOfVertices][noOfVertices];
        // retrieve  connecting  vertices
        adjacencyMap.keySet().stream().filter(key -> adjacencyMap.get(key) != null).forEach(vertex1 -> {
 
            //retrieve connected vertices
            adjacencyMap.get(vertex1).forEach(vertex2 -> {
                adjacencyMatrix[vertex1][vertex2] = 1;
                if (isUndirected)
                    adjacencyMatrix[vertex2][vertex1] = 1;
            });
        });
 
        return adjacencyMatrix;
    }
 
    public Map<Integer, Set<Integer>> getAdjacencyList()
    {
        return Collections.unmodifiableMap(adjacencyMap);
    }
 
    public List<Integer> getVertices()
    {
        return Collections.unmodifiableList(listOfVertices);
    }
 
    public List<Object> getListOfEdges() {
        return adjacencyMap.keySet().stream()
                .flatMap(v -> adjacencyMap.get(v).stream().map(w -> new Edge<>(v, w)))
                .collect(Collectors.toList());
    }
    
    public boolean isConnected() {
        
		int[][] adjMatrix = generateAdjacencyMatrix();
		int vertexFound = 0;
		int iterations = 0;
		int v1 = 0;
		int v2 = 0;
		
		while(iterations< adjMatrix.length-1  && v2< adjMatrix.length-1 )
		{
			v2=v1+1;			
			
			if(isConnectedComponent(v1, v2, adjMatrix))
			{
				vertexFound++;
				System.out.println(v1+"-->"+v2+" is connected");
				
				if(isConnectedComponent(v2, v1, adjMatrix))
				{
					vertexFound++;
					System.out.println(v2+"-->"+v1+" is connected");
				}
			}
			
			v1++;
			iterations++;
		}
	
		if(isUndirected)
		{
			return vertexFound == (adjMatrix.length-1 )* 2;
		}
		else
		{
			return vertexFound == adjMatrix.length-1 ;			
		}
		
	}

	private boolean isConnectedComponent(int v1, int v2, int[][] adjMatrix)
	{
		
		return adjMatrix[v1][v2] == 1;		
	}
}

GraphDemo:

public class GraphDemo {
	 
    public static void main(String[] args) {
        Graph graph = new Graph(6, true);
        Edge<Integer> e1 = new Edge<>(0, 1);
 
        Edge<Integer> e3 = new Edge<>(1, 2);
 
        Edge<Integer> e4 = new Edge<>(3, 4);
        
        Edge<Integer> e2 = new Edge<>(4, 5);
        
        graph.addEdge(e1);
        graph.addEdge(e3);
        
        graph.addEdge(e4);
        graph.addEdge(e2);
        
        System.out.println(graph);
        
        System.out.println("Is Connected: "+graph.isConnected());
        
        Graph connectedGraph = new Graph(6, true);
        Edge<Integer> ce1 = new Edge<>(0, 1);
        
        Edge<Integer> ce3 = new Edge<>(1, 2);
 
        Edge<Integer> ce4 = new Edge<>(2, 3);
        
        Edge<Integer> ce2 = new Edge<>(3, 4);
        
        Edge<Integer> ce5 = new Edge<>(4, 5);
        
        connectedGraph.addEdge(ce1);
        connectedGraph.addEdge(ce3);
        connectedGraph.addEdge(ce4);
        connectedGraph.addEdge(ce2);
        connectedGraph.addEdge(ce5);
        
        System.out.println(connectedGraph);
        
        System.out.println("Is Connected: "+connectedGraph.isConnected());
    }
}

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

public boolean isConnected() {
       
		int[][] adjMatrix = generateAdjacencyMatrix();
		int vertexFound = 0;
        boolean[] visitedNodes = new boolean[adjMatrix.length];  		

		for(int vertex1 = 0; vertex1 < adjMatrix.length; vertex1++)
		{
			for(int vertex2 = 0; vertex2 < adjMatrix.length; vertex2++)
			{
                                if(vertex1==vertex2)
					continue;				

				if(isUndirected)
				{
					if(!visitedNodes[vertex1] &&  isConnectedComponent(vertex1, vertex2, adjMatrix) && isConnectedComponent(vertex2, vertex1, adjMatrix) )
					{
						vertexFound++;
						System.out.println(vertex1+"-->"+vertex2+" is connected");
						System.out.println(vertex2+"-->"+vertex1+" is connected");
						
						visitedNodes[vertex1] = true;
					}
				}
				else
				{
					if(!visitedNodes[vertex1] && isConnectedComponent(vertex1, vertex2, adjMatrix) )
					{
						vertexFound++;
						System.out.println(vertex1+"-->"+vertex2+" is connected");
						visitedNodes[vertex1] = true;
					}
				}
				
			}
		}
	
	
			return vertexFound == adjMatrix.length-1 ;			
	}

This logic is flawed. I am working on it.

[Piet Souris]

I've changed your latest version of 'public boolean isConnected()', to make the output slightly more clear:

public boolean isConnectedLatestVersion() {

    int[][] adjMatrix = generateAdjacencyMatrix();
    System.out.println("adjMat:");
    for (int[] row: adjMatrix) System.out.println(Arrays.toString(row));
    System.out.println("***");
    int vertexFound = 0;
    boolean[] visitedNodes = new boolean[adjMatrix.length];

    for (int vertex1 = 0; vertex1 < adjMatrix.length; vertex1++) {
        for (int vertex2 = 0; vertex2 < adjMatrix.length; vertex2++) {
            if (vertex1 == vertex2) {
                continue;
            }

            if (isUndirected) {
                if (!visitedNodes[vertex1] && isConnectedComponent(vertex1, vertex2, adjMatrix) && isConnectedComponent(vertex2, vertex1, adjMatrix)) {
                    vertexFound++;
                    System.out.println(vertex1 + "-->" + vertex2 + " is connected");
                    System.out.println("**********");

                    visitedNodes[vertex1] = true;
                }
            } else if (!visitedNodes[vertex1] && isConnectedComponent(vertex1, vertex2, adjMatrix)) {
                vertexFound++;
                System.out.println(vertex1 + "-->" + vertex2 + " is connected");
                visitedNodes[vertex1] = true;
            }

        }
    }

    System.out.println("In isConnectedLatestVersion; vertices found = " + vertexFound);
    return vertexFound == adjMatrix.length - 1;
}

Now, I ran this testprogram:

Graph g = new Graph(5, true);
g.addEdge(new Edge<>(0,1));
g.addEdge(new Edge<>(1,2));
g.addEdge(new Edge<>(0,2));
g.addEdge(new Edge<>(3,4));
System.out.println(g.getAdjacencyList());
System.out.println(g.getListOfEdges());
System.out.println("Is Connected: " + g.isConnectedLatestVersion());

and this was the output:

{0=[1, 2], 1=[0, 2], 2=[0, 1], 3=[4], 4=[3]}
[Edge{0, 1}, Edge{0, 2}, Edge{1, 0}, Edge{1, 2}, Edge{2, 0}, Edge{2, 1}, Edge{3, 4}, Edge{4, 3}]
adjMat:
[0, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 0]
***
0-->1 is connected
**********
1-->0 is connected
**********
2-->0 is connected
**********
3-->4 is connected
**********
4-->3 is connected
**********
In isConnectedLatestVersion; vertices found = 5
Is Connected: false

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]

Thanks for the feedback.

Here is my current Graph:

public class Graph {

	private final boolean isUndirected;

	private Map<Integer, Set<Integer>> adjacencyMap;

	private List<Integer> listOfVertices;

	private int noOfVertices;

	public Graph(int noOfVertices, boolean isUndirected)
	{
		this.isUndirected = isUndirected;

		adjacencyMap = new HashMap<>();

		listOfVertices = new ArrayList<>();

		this.noOfVertices = noOfVertices;

		initializeVertices(noOfVertices);
	}

	//todo: this needs to be rectified.
	private void initializeVertices(int vertexIndexLimit)
	{

		for(int index=0; index< vertexIndexLimit; index++ )
		{
			listOfVertices.add(index);
		}
	}

	public void addEdge(Edge<Integer> e)
	{

		if(  !(listOfVertices.contains(e.getVertex1()) && listOfVertices.contains(e.getVertex2()))  )
		{
			throw new IllegalArgumentException("One or both the vertex are out of range for this Edge: "+e);
		}

		adjacencyMap.computeIfAbsent(e.getVertex1(), HashSet::new).add(e.getVertex2());

		if(isUndirected)
		{
			adjacencyMap.computeIfAbsent(e.getVertex2(), HashSet::new).add(e.getVertex1());
		}

	}

	public void removeEdge(Edge<Integer> e)
	{

		if(adjacencyMap.containsKey(e.getVertex1()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex1());
			adjacentNodes.remove(e.getVertex2());
		}

		if(isUndirected && adjacencyMap.containsKey(e.getVertex2()))
		{
			Set<Integer> adjacentNodes = adjacencyMap.get(e.getVertex2());
			adjacentNodes.remove(e.getVertex1());
		}

	}

	@Override
	public String toString() {
		return "Edges={\n"
				+ printEdges()+"}\n" +
				printAdjacencyMatrix(generateAdjacencyMatrix());
	}

	private String printAdjacencyMatrix(int[][] adjacencyMatrix)
	{
		StringBuilder sb = new StringBuilder();

		sb.append("AdjacencyMatrix{");

		for(int[] vertexNodes: adjacencyMatrix)
		{
			sb.append("\n");
			sb.append(Arrays.toString(vertexNodes));
		}

		sb.append("}");
		sb.append("\n");

		return sb.toString();
	}

	private String printEdges()
	{

		Set< Integer> vertexNode = adjacencyMap.keySet();
		StringBuilder sb = new StringBuilder();

		for(int vertex: vertexNode)
		{
			Set<Integer> connectedNodes = adjacencyMap.get(vertex);
			if(connectedNodes!=null && connectedNodes.size()>0)
			{
				for(int connectedVertex: connectedNodes)
				{
					sb.append("[");
					sb.append(vertex+"-->"+connectedVertex);
					sb.append("]");
					sb.append("\n");
				}
			}
			else
			{
				sb.append("[");
				sb.append(vertex+"-->EMPTY");
				sb.append("]");
				sb.append("\n");
			}

		}

		return sb.toString();
	}

	public boolean isConnected() {

		int[][] adjMatrix = generateAdjacencyMatrix();

		System.out.println("adjMat:");
		for (int[] row: adjMatrix) System.out.println(Arrays.toString(row));
		System.out.println("***");

		int vertexFound = 0;
		boolean[] visitedNodes = new boolean[adjMatrix.length];

		for(int vertex1 = 0; vertex1 < adjMatrix.length; vertex1++)
		{
			for(int vertex2 = 0; vertex2 < adjMatrix.length; vertex2++)
			{
				if(vertex1==vertex2)
					continue;

				if(isUndirected)
				{
					if(!visitedNodes[vertex1] &&  isConnectedComponent(vertex1, vertex2, adjMatrix) && isConnectedComponent(vertex2, vertex1, adjMatrix) )
					{
						vertexFound++;
						System.out.println(vertex1+"-->"+vertex2+" is connected");
						System.out.println("*****************");
						visitedNodes[vertex1] = true;
					}
				}
				else
				{
					if(!visitedNodes[vertex1] && isConnectedComponent(vertex1, vertex2, adjMatrix) )
					{
						vertexFound++;
						System.out.println(vertex1+"-->"+vertex2+" is connected *");
						visitedNodes[vertex1] = true;
					}
				}

			}
		}

		System.out.println("In isConnectedLatestVersion; vertices found = " + vertexFound);
		return vertexFound == adjMatrix.length-1 ;
	}

	public int[][] generateAdjacencyMatrix()
	{

		int[][] adjacencyMatrix = new int[noOfVertices][noOfVertices];
		// retrieve  connecting  vertices
		adjacencyMap.keySet().stream().filter(key -> adjacencyMap.get(key) != null).forEach(vertex1 -> {

			//retrieve connected vertices
			adjacencyMap.get(vertex1).forEach(vertex2 -> {
				adjacencyMatrix[vertex1][vertex2] = 1;
				if (isUndirected)
					adjacencyMatrix[vertex2][vertex1] = 1;
			});
		});

		return adjacencyMatrix;
	}

	private boolean isConnectedComponent(int v1, int v2, int[][] adjMatrix)
	{

		return adjMatrix[v1][v2] == 1;
	}

	public Map<Integer, Set<Integer>> getAdjacencyList()
	{
		return Collections.unmodifiableMap(adjacencyMap);
	}

	public List<Integer> getVertices()
	{
		return Collections.unmodifiableList(listOfVertices);
	}

	public List<Edge<Integer>> getListOfEdges() {
		return adjacencyMap.keySet().stream()
				.flatMap(v -> adjacencyMap.get(v).stream().map(w -> new Edge<>(v, w)))
				.collect(Collectors.toList());
	}
}

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:

 System.out.println("In isConnectedLatestVersion; vertices found = " + vertexFound);

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.