423,834 Members | 1,336 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 423,834 IT Pros & Developers. It's quick & easy.

How would you fetch, delete, and update a vertex and edge in java?

P: 74
I have looked in several different data structures and algorithms books, but I have yet to find any of them useful when it comes to researching how to implement the operations of fetching, deleting, and updating an vertex and edge for a graph in java? Here is my starting program. Any help would be much appreciated or any suggestions to any books that would assist me in this matter?

Expand|Select|Wrap|Line Numbers
  1. public class SimpleGraph // a directed graph
  2. {   Listing vertex[ ];  //the reference to the vertex array
  3.     int edge[ ][ ];  // reference to the adjacency matrix array
  4.     int max, numberOfVertices;
  5.     public SimpleGraph(int n)
  6.    {  vertex = new Listing[n]; // allocation of the vertex array
  7.        edge = new int[n][n];   // adjacency matrix with all elements set to 0
  8.        max = n;   numberOfVertices = 0;
  9.    }
  10.    public boolean insertVertex(int vertexNumber, Listing newListing)
  11.    {   if (vertexNumber >= max)  //the graph is full
  12.            return false;
  13.        vertex[vertexNumber] = newListing.deepCopy();     numberOfVertices++;
  14.        return true;
  15.    }
  16.     public boolean insertEdge(int fromVertex, int toVertex)
  17.    {  if(vertex[fromVertex] == null || vertex[toVertex] == null) // non-existent vertex
  18.           return false;
  19.       edge[fromVertex][toVertex] = 1;
  20.       return true;
  21.    }
  22.     public Listing fetchVertex(int vertex) 
  23.     { 
  24.  
  25.     } 
  26.     public Listing fetchEdge(int vertex1, int vertex2)
  27.     { 
  28.  
  29.     } 
  30.    public boolean deleteVertex(int vertex)
  31.    { 
  32.  
  33.     } 
  34.     public boolean deleteEdge(int vertex1, int vertex2)
  35.     { 
  36.  
  37.     }
  38.  
  39.     public boolean updateVertex(int vertex1)
  40.     { 
  41.        // not really sure if this method would have a second parameter.
  42.        // My guess is yes it would be because you 
  43.        // need to know which other vertex you want to update the first one
  44.        // to
  45.       } 
  46.  
  47.     public boolean updateEdge(int vertex1, int vertex2)
  48.     {
  49.  
  50.     } 
  51.  
  52.    public void showVertex(int vertexNumber)
  53.    {  System.out.println(vertex[vertexNumber]);
  54.    }
  55.     public void showEdges(int vertexNumber) //edges emanating from vertexNumber
  56.    {   for(int column=0; column<numberOfVertices; column++)
  57.        {   if(edge[vertexNumber][column] == 1) // there is an edge
  58.               System.out.println(vertexNumber + "," + column);
  59.        }
  60.    }
  61. }// end of SimpleGraph class
  62.  
  63.  
  64.  
  65. // definition of a hub city (a vertex)
  66. public class Listing
  67. {  private String name;
  68.     public Listing(String n)
  69.    {  name=n;
  70.    }
  71.     public String toString()
  72.     {  return("Name is " + name);
  73.     }
  74.     public Listing deepCopy()
  75.    {  Listing clone = new Listing(name);
  76.        return clone;
  77.    }
  78. }
Dec 5 '17 #1

✓ answered by chaarmann

About fetchVertex:
In line 1 there is written "int". That means you cannot return "false" in line 4 and you cannot return a Vertex in line 6, you must return an int.
That's the reason your code didn't work.
But I think this method should not return an int but the vertex itself.
So the corrected method is:

Expand|Select|Wrap|Line Numbers
  1. public Vertex fetchVertex(int vertexNumber) 
  2.     {   
  3.        if(vertex.length >= vertexNumber) return null;
  4.        return vertex[vertexNumber];
  5.     }
About the delete-method that I gave you: it's just a code snipped. The whole method would be:
Expand|Select|Wrap|Line Numbers
  1.     public boolean deleteVertex(int vertexIndex) 
  2.    { 
  3.          int  numberOfVertices = vertex.length;
  4.          if (vertexIndex >= numberOfVertices) return false;
  5.          for (int i=vertexIndex; i<numberOfVertices-1 ; i++)
  6.          {
  7.              vertex[i] = vertex[i+1];
  8.          }
  9.          vertex[numberOfVertices] == null;
  10.          return true;     
  11.    } 
  12.  
  13.  

Share this Question
Share on Google+
12 Replies


Expert 100+
P: 778
if you only have a hammer everything looks like a nail. Don't repeat the beginners mistake and put everything in arrays. Use the collection framework of Java instead.
I assume that vertex n corresponds to edge n, so keep this data together!
I have seen enough bad code where programmers put employee first names in one array and employee last names in a second array and then messing around with the indexes when inserting/finding/deleting, instead of defining a class employee and putting the first name and last name as member variables.

Looka at the code below that you can easisly extend (with getters/setters etc.)
Expand|Select|Wrap|Line Numbers
  1. class Listing {
  2.     public Listing() {
  3.      }
  4. }
  5.  
  6. class Vertex {
  7.    private final Listing listing;
  8.    private final List<Integer> edges;
  9.    public Vertex(Listing listing, List<Integer> edges) {
  10.        this.listing = listing;
  11.        this.edges = edges;
  12.     }
  13.    public String toString() {
  14.        return "edges=" + edges;
  15.    }
  16. }
  17.  
  18. class SimpleGraph {
  19.     private final List<Vertex> vertices;
  20.     private final int max;
  21.     public SimpleGraph(int n, List<Vertex> vertices) {
  22.         max = n;
  23.         this.vertices = vertices;
  24.     }
  25.     public String toString() {
  26.         return "max=" +  max + ", vertices=" + vertices;
  27.     }
  28. }
  29.  
if you run the code above with:
Expand|Select|Wrap|Line Numbers
  1. Listing listing = new Listing();
  2. Vertex vertex1 = new Vertex(listing, Arrays.asList(1, 2, 3));
  3. Vertex vertex2 = new Vertex(listing, Arrays.asList(3, 4, 5, 6));
  4. SimpleGraph simpleGraph = new SimpleGraph(3, Arrays.asList(vertex1, vertex2));
  5. System.out.println("graph: " + simpleGraph);
  6.  
The output would be:
Expand|Select|Wrap|Line Numbers
  1. graph: max=3, vertices=[edges=[1, 2, 3], edges=[3, 4, 5, 6]]
  2.  
Why are lists, maps and other collection objects better than one and two-dimensional arrays?
You don't need to write code to loop through the array to find an element, you don't need to shift indices if you want to delete an element in the middle of the array, you don't need to reinvent the sorting algorithm etc.
You can simply use one-liners for these tasks like
Expand|Select|Wrap|Line Numbers
  1. Collections.sort(edges); // sorts the whole list of edges
  2. int index = edges.indexOf(4); index of edge "4".
  3. edges.remove(index); // removes this element;
  4. edges.add(6); // adds an element to the list;
Dec 5 '17 #2

P: 74
@chaarmann How would I do it with just my implementation that I currently have?
Dec 5 '17 #3

P: 74
@chaarmann You know every programmer is always going to have a differrent way to solve a problem. I rather just stick with how I have mines first. I just need help thinking through these methods. Can you please help?
Dec 5 '17 #4

Expert 100+
P: 778
Why don't you take the code that I wrote as a template and I help you to extend it to your needs if you run in further problems?

Why still using arrays and not using collections and generics for this problem?
Why using a hammer to drill in screws?

Maybe your main intention is not to solve the problem. Your main intention is to learn how to deal with arrays and you just see the problem as an exercise example. Then I will not give you spoon-feeded code, else you don't learn, but will describe what to do.

1.) fetching a vertex
Use the classical for-loop or the newer forEach-loop to go through all elements of the vertex-array. Inside the loop, compare with your target and if equal, assign a variable "foundIndex" to the current index and break the loop. Return the currentIndex.

2.) updating a vertex
First find the index as described above. Then assign new data to vertex[found] = newVertex and edge[found]=newEdges.

3.) deleting a vertex
First find the index as described above.
Now you have to shift all elements one index down, starting from the element found until the end of the array, in a for-loop. Let's say you have 5 elements and the element to be deleted is the second (that means index =1). Then you must shift:
vertex[1] = vertex[2];
vertex[2] = vertex[3];
vertex[3] = vertex[4];
Do the same with the edges.

4.) adding a vertex at the end:
first define a new vertex-array that is one bigger than the current one. Copy all vertex from the old to the new array. You can use System.arraycopy() to do that efficiently, no need for a loop. Then set the new element at the end of the new array. Ah, yes, and don't forget to do this with the edges. You always have to remember this if you don't want to keep the data together in a object orientated way but still use separate arrays.
Dec 6 '17 #5

P: 74
@chaarmann, Okay I went and made a lot of changes but I am still having trouble fetchVertex and update edge and update vertex



Expand|Select|Wrap|Line Numbers
  1.   // public boolean fetchVertex(int vertex1) 
  2.     // { 
  3.          // if(vertex[vertex1] == null) 
  4.          // return true;  
  5.        } 
  6.     public boolean fetchEdge(int vertex1, int vertex2) 
  7.     { 
  8.        if(vertex[vertex1] == null || vertex[vertex2] == null) // non-existent vertex
  9.           return false;
  10.        edge[vertex1][vertex2] = 1;
  11.     }   
  12.    public boolean deleteVertex(int vertex1) 
  13.    { 
  14.        if(vertex[vertex1] == null) 
  15.         return true;
  16.    } 
  17.    public boolean deleteEdge(int vertex1, int vertex2)
  18.    { 
  19.       if(vertex[vertex1] == null || vertex[vertex2] == null) // non-existent vertex
  20.       return false;
  21.       edge[vertex1][vertex2] = 0;  // deletes the edge from one vertex to the next vertex 
  22.       return true;
  23.    }
Dec 7 '17 #6

Expert 100+
P: 778
You have a function fetchVertex(int n).
That's easy, just return vertex[n]. (change your return type from boolean to int)
I thought you need a function fetchVertex(Vertex target), which finds the index of a vertex inside the array. For that you would have used a for-loop as I wrote.

Deleting a vertex:
add following code before line 16:

Expand|Select|Wrap|Line Numbers
  1. int  numberOfVertices = vertex.length;
  2. for(int i=0; i<numberOfVertices-1 ; i++)
  3. {
  4.    vertex[i] = vertex[i+1];
  5. }
  6. vertex[numberOfVertices] == null;     
  7.  
Do the same algorithm with the edges.
Dec 7 '17 #7

P: 74
@chaarmann I went back and tried to implement the fetchVertex and what you said didn't work. Here my snippet code.

Expand|Select|Wrap|Line Numbers
  1. public int fetchVertex(int vertexNumber) 
  2.     {   
  3.        if(vertex[vertexNumber] == null)
  4.         return false;
  5.  
  6.          return vertex[vertexNumber];
  7.  
  8.     } 
Dec 7 '17 #8

P: 74
@chaarmann Your delete vertex does not work at all
Dec 13 '17 #9

Expert 100+
P: 778
About fetchVertex:
In line 1 there is written "int". That means you cannot return "false" in line 4 and you cannot return a Vertex in line 6, you must return an int.
That's the reason your code didn't work.
But I think this method should not return an int but the vertex itself.
So the corrected method is:

Expand|Select|Wrap|Line Numbers
  1. public Vertex fetchVertex(int vertexNumber) 
  2.     {   
  3.        if(vertex.length >= vertexNumber) return null;
  4.        return vertex[vertexNumber];
  5.     }
About the delete-method that I gave you: it's just a code snipped. The whole method would be:
Expand|Select|Wrap|Line Numbers
  1.     public boolean deleteVertex(int vertexIndex) 
  2.    { 
  3.          int  numberOfVertices = vertex.length;
  4.          if (vertexIndex >= numberOfVertices) return false;
  5.          for (int i=vertexIndex; i<numberOfVertices-1 ; i++)
  6.          {
  7.              vertex[i] = vertex[i+1];
  8.          }
  9.          vertex[numberOfVertices] == null;
  10.          return true;     
  11.    } 
  12.  
  13.  
Dec 14 '17 #10

P: 74
@chaarmann What would be the purpose of the vertex[numberOfVertices] == null; statement? Will it return no vertices at all if the method does delete one vertex? As it stands, this line does not complle at all.
Dec 14 '17 #11

Expert 100+
P: 778
"vertex[numberOfVertices] == null;" is a mistyping. It should be
Expand|Select|Wrap|Line Numbers
  1. vertex[numberOfVertices - 1] = null;
A single equal sign is an assignment, whereas a double equal sign is a comparison.

the purpose:
When you shift all elements one index up in your array, the last element should not be duplicated.
let's say you have 5 elements. And you want to delete the third one.
before the for-loop:
Expand|Select|Wrap|Line Numbers
  1. a[0] = e0
  2. a[1] = e1
  3. a[2] = e2
  4. a[3] = e3
  5. a[4] = e4
after running the for-loop:
Expand|Select|Wrap|Line Numbers
  1. a[0] = e0
  2. a[1] = e1
  3. a[2] = e3
  4. a[3] = e4
  5. a[4] = e4
See? The a[4] was copied to a[3], but is still there. we need to delete it with a[4] = null;
Then you have:
Expand|Select|Wrap|Line Numbers
  1. a[0] = e0
  2. a[1] = e1
  3. a[2] = e3
  4. a[3] = e4
  5. a[4] = null
Dec 15 '17 #12

P: 74
@chaarmann Thanks for all of your help on this. As of right I don't have anymore questions. So I will accept all of feedback that you gave me!
Dec 15 '17 #13

Post your reply

Sign in to post your reply or Sign up for a free account.