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

[dseals22]

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?

public class SimpleGraph // a directed graph
{   Listing vertex[ ];  //the reference to the vertex array
    int edge[ ][ ];  // reference to the adjacency matrix array
    int max, numberOfVertices;
    public SimpleGraph(int n)
   {  vertex = new Listing[n]; // allocation of the vertex array
       edge = new int[n][n];   // adjacency matrix with all elements set to 0
       max = n;   numberOfVertices = 0;
   }
   public boolean insertVertex(int vertexNumber, Listing newListing)
   {   if (vertexNumber >= max)  //the graph is full
           return false;
       vertex[vertexNumber] = newListing.deepCopy();     numberOfVertices++;
       return true;
   }
    public boolean insertEdge(int fromVertex, int toVertex)
   {  if(vertex[fromVertex] == null || vertex[toVertex] == null) // non-existent vertex
          return false;
      edge[fromVertex][toVertex] = 1;
      return true;
   }
    public Listing fetchVertex(int vertex) 
    { 

    } 
    public Listing fetchEdge(int vertex1, int vertex2)
    { 

    } 
   public boolean deleteVertex(int vertex)
   { 

    } 
    public boolean deleteEdge(int vertex1, int vertex2)
    { 

    }

    public boolean updateVertex(int vertex1)
    { 
       // not really sure if this method would have a second parameter.
       // My guess is yes it would be because you 
       // need to know which other vertex you want to update the first one
       // to
      } 

    public boolean updateEdge(int vertex1, int vertex2)
    {

    } 

   public void showVertex(int vertexNumber)
   {  System.out.println(vertex[vertexNumber]);
   }
    public void showEdges(int vertexNumber) //edges emanating from vertexNumber
   {   for(int column=0; column<numberOfVertices; column++)
       {   if(edge[vertexNumber][column] == 1) // there is an edge
              System.out.println(vertexNumber + "," + column);
       }
   }
}// end of SimpleGraph class



// definition of a hub city (a vertex)
public class Listing
{  private String name;
    public Listing(String n)
   {  name=n;
   }
    public String toString()
    {  return("Name is " + name);
    }
    public Listing deepCopy()
   {  Listing clone = new Listing(name);
       return clone;
   }
}

[chaarmann]

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.)

class Listing {
    public Listing() {
     }
}

class Vertex {
   private final Listing listing;
   private final List<Integer> edges;
   public Vertex(Listing listing, List<Integer> edges) {
       this.listing = listing;
       this.edges = edges;
    }
   public String toString() {
       return "edges=" + edges;
   }
}

class SimpleGraph {
    private final List<Vertex> vertices;
    private final int max;
    public SimpleGraph(int n, List<Vertex> vertices) {
        max = n;
        this.vertices = vertices;
    }
    public String toString() {
        return "max=" +  max + ", vertices=" + vertices;
    }
}

if you run the code above with:

Listing listing = new Listing();
Vertex vertex1 = new Vertex(listing, Arrays.asList(1, 2, 3));
Vertex vertex2 = new Vertex(listing, Arrays.asList(3, 4, 5, 6));
SimpleGraph simpleGraph = new SimpleGraph(3, Arrays.asList(vertex1, vertex2));
System.out.println("graph: " + simpleGraph);

The output would be:

graph: max=3, vertices=[edges=[1, 2, 3], edges=[3, 4, 5, 6]]

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

Collections.sort(edges); // sorts the whole list of edges
int index = edges.indexOf(4); index of edge "4".
edges.remove(index); // removes this element;
edges.add(6); // adds an element to the list;

[dseals22]

@chaarmann How would I do it with just my implementation that I currently have?

[dseals22]

@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?

[chaarmann]

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.arraycop y() 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.

[dseals22]

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

  // public boolean fetchVertex(int vertex1) 
    // { 
         // if(vertex[vertex1] == null) 
         // return true;  
       } 
    public boolean fetchEdge(int vertex1, int vertex2) 
    { 
       if(vertex[vertex1] == null || vertex[vertex2] == null) // non-existent vertex
          return false;
       edge[vertex1][vertex2] = 1;
    }   
   public boolean deleteVertex(int vertex1) 
   { 
       if(vertex[vertex1] == null) 
        return true;
   } 
   public boolean deleteEdge(int vertex1, int vertex2)
   { 
      if(vertex[vertex1] == null || vertex[vertex2] == null) // non-existent vertex
      return false;
      edge[vertex1][vertex2] = 0;  // deletes the edge from one vertex to the next vertex 
      return true;
   }

[chaarmann]

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(Ver tex 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:

int  numberOfVertices = vertex.length;
for(int i=0; i<numberOfVertices-1 ; i++)
{
   vertex[i] = vertex[i+1];
}
vertex[numberOfVertices] == null;

Do the same algorithm with the edges.

[dseals22]

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

public int fetchVertex(int vertexNumber) 
    {   
       if(vertex[vertexNumber] == null)
        return false;

         return vertex[vertexNumber];
                 
    }

[dseals22]

@chaarmann Your delete vertex does not work at all

[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:

public Vertex fetchVertex(int vertexNumber) 
    {   
       if(vertex.length >= vertexNumber) return null;
       return vertex[vertexNumber];
    }

About the delete-method that I gave you: it's just a code snipped. The whole method would be:

    public boolean deleteVertex(int vertexIndex) 
   { 
         int  numberOfVertices = vertex.length;
         if (vertexIndex >= numberOfVertices) return false;
         for (int i=vertexIndex; i<numberOfVertices-1 ; i++)
         {
             vertex[i] = vertex[i+1];
         }
         vertex[numberOfVertices] == null;
         return true;     
   }

[dseals22]

@chaarmann What would be the purpose of the vertex[numberOfVertice s] == 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.

[chaarmann]

"vertex[numberOfVertice s] == null;" is a mistyping. It should be

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:

a[0] = e0
a[1] = e1
a[2] = e2
a[3] = e3
a[4] = e4

after running the for-loop:

a[0] = e0
a[1] = e1
a[2] = e3
a[3] = e4
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:

a[0] = e0
a[1] = e1
a[2] = e3
a[3] = e4
a[4] = null

[dseals22]

@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!