# Issue Building Graph in Adjacency Matrix

• October 22nd, 2010, 09:54 AM
mike.s
Issue Building Graph in Adjacency Matrix
Hey guys and girls,

Somewhat stuck on this program. Im building an Adjacency Matrix and I cant seem to figure out how to create my buildGraph method. The whole program won't fit here so I have attached the netbeans project folder.

Here is essentially what needs work:

Code Java:

``` public void buildGraph() { // v.getIncidentEdges(); // w.getIncidentEdges(); for (int x = 1; x <10; x++){ for (int y = 1; y<10; y++){ /* * This needs help for sure. Im trying to check the Vertex to the * left, and the vertex above, and if they arent null, then create * and edge with them. * Moving through a 10x10 grid of Vertices creating edges between * them. * * if (Vertices != null && Vertices != null){ */ try {g.addEdge(v, w);}catch (NullPointerException npe) {} } } }```

Code Java:

``` public Edge addEdge(Vertex v,Vertex w) { Edge e = new Edge(v, w); v.addIncidentEdge(e); w.addIncidentEdge(e); e.getDestVertex(); e.getOriginVertex(); Edges.add(e); return e;   }```

Code Java:

``` public Vertex addVertex(Cell c){ Coordinate z = c.getCoordinate(); int x = z.getX(); int y = z.getY(); Vertex v = new Vertex(c); try {Vertices.add(v);}catch (NullPointerException npe) {} System.out.println("("+ x + "," + y + ")" ); return v; }```

Here is how I'm adding the vertices, essentially everytime it creates a new cell, it adds a vertex there, except when we add an Agent cell, for later when moving through the Matrix it wont be possible to walk into the agents:
Code Java:

```if ((coordinate).equals(generator.getNeo())){ cell = new Cell(CellType.Neo,coordinate); System.out.println(CellType.Neo + " Vertex"); g.addVertex(cell);   } else if(coordinate.equals(generator.getMorpheus())){ cell = new Cell(CellType.Morpheus,coordinate); System.out.println(CellType.Morpheus + " Vertex"); g.addVertex(cell);   }   else if(coordinate.equals(generator.getPhoneBooth())){ cell = new Cell(CellType.PhoneBooth,coordinate); System.out.println(CellType.PhoneBooth + " Vertex"); g.addVertex(cell);   } else if (generator.getAgents().contains(coordinate)){ cell = new Cell(CellType.Agent,coordinate); System.out.println(CellType.Agent); System.out.println(coordinate); } else { cell = new Cell(CellType.Blank,coordinate); System.out.println(CellType.Blank + " Vertex"); g.addVertex(cell); }```

Again, the code in its entirety is attached. There are multiple classes and didnt exactly want to post every last peice of code here.

Thanks in advance for the help :)
• October 22nd, 2010, 12:40 PM
copeg
Re: Issue Building Graph in Adjacency Matrix
Not fully sure how you are storing your vertices (don't have time to look at the attachment), but I'd presume your graph has a method to retrieve a vertex at a particular position? Something like

Code java:

```Vertext me = g.getVertex(x,y);//current position Vertex left = g.getVertex(x-1, y);//left if ( left != null ){ g.addEdge(me, v);//add the edge if the left isn't null } //do the same for vertical position```
• October 22nd, 2010, 01:31 PM
mike.s
Re: Issue Building Graph in Adjacency Matrix
I am storing the Vertices and the Edges in ArrayLists
here is my graph class:
Code java:

```package matrix;   import java.util.ArrayList;   public class Graph {   public ArrayList<Vertex> Vertices; public ArrayList<Edge> Edges;     public Graph() {   ArrayList<Vertex> Vertices = new ArrayList<Vertex>(); ArrayList<Edge> Edges = new ArrayList<Edge>();   }   public Vertex addVertex(Cell c){ Coordinate z = c.getCoordinate(); int x = z.getX(); int y = z.getY(); Vertex v = new Vertex(c); try {Vertices.add(v);}catch (NullPointerException npe) {} System.out.println("("+ x + "," + y + ")" ); return v; }   public Edge addEdge(Vertex v,Vertex w) { Edge e = new Edge(v, w); v.addIncidentEdge(e); w.addIncidentEdge(e); e.getDestVertex(); e.getOriginVertex(); Edges.add(e); return e;   }     }```

because its an ArrayList this is what ive tryed to do for buildGraph:
Code Java:

``` public void buildGraph() {   if (g.Vertices -1 != null && g.Vertices -10 != null){ g.addEdge(v,w); }   }```

Im not really comfortable with array lists, so im a little confused how to move through-out them. That above method is giving me an error, cant use int with Vertex. Also for the g.addEdge(v,w); line im a little confused about where to pull my v and w from at this point.
• October 22nd, 2010, 02:19 PM
DavidFongs
Re: Issue Building Graph in Adjacency Matrix
Why are you catching NullPointerExceptions, and then ignoring them. You should fix the code that is generating the NPEs, instead of catching them and ignoring them.
• October 22nd, 2010, 02:21 PM
copeg
Re: Issue Building Graph in Adjacency Matrix
First, the methods of Graph will throw a NullPointerException (caught in the addVertex method) - take a look at the scope of the variables in the constructor. Second, based upon what you have posted there are 'unidirectional pointers': seems you can get the Celll/ocation from the vertex but not vice versa. So make some method (as I mentioned in my previous post) so you can look up a vertex based upon the cell values. Some sort of lookup table would work, be it an array or HashMap, where you can retrieve the Vertex based upon position, or null if the vertex hasn't been set
• October 22nd, 2010, 02:26 PM
mike.s
Re: Issue Building Graph in Adjacency Matrix
so I would essentially use this new method to check the vertex before and above? is there no way to move around the ArrayList without creating a new method?

With the new method, I would loop through to check all the Vertices and add edges as I go through them, no?

Just for reference, here is my Edge class and my Vertex class:

Edge:
Code Java:

```package matrix;   /** * * @author Sunny */ public class Edge {   private Vertex originVertex; private Vertex destVertex;   public Edge(Vertex origin, Vertex destination) { originVertex = origin; destVertex = destination; }   public Vertex getOriginVertex() { return originVertex; } public Vertex getDestVertex() { return destVertex; }   @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Edge other = (Edge) obj; if (this.originVertex != other.originVertex && (this.originVertex == null || !this.originVertex.equals(other.originVertex))) { return false; } if (this.destVertex != other.destVertex && (this.destVertex == null || !this.destVertex.equals(other.destVertex))) { return false; } return true; }   @Override public int hashCode() { int hash = 5; hash = 97 * hash + (this.originVertex != null ? this.originVertex.hashCode() : 0); hash = 97 * hash + (this.destVertex != null ? this.destVertex.hashCode() : 0); return hash; }   public String toString() { String s = ""; s = "Origin: " + originVertex.toString(); s += "\n"; s += "Destination: " + destVertex.toString();   return s; } }```

Vertex:
Code Java:

```package matrix;   import java.util.ArrayList;   /** * * @author Sunny */ public class Vertex {   private Cell _element; private ArrayList<Edge> incidentEdges;   public Vertex() { _element = null; incidentEdges = new ArrayList<Edge>(); } public Vertex(Cell element) { _element = element; incidentEdges = new ArrayList<Edge>(); } public Vertex(Cell element, ArrayList<Edge> edges) { incidentEdges = new ArrayList<Edge>(); for (Edge e : edges) incidentEdges.add(e); }   //Get or Set Element public void setElement(Cell element) {_element = element;} public Cell getElement() { return _element; }   //Get Incident Edges public ArrayList<Edge> getIncidentEdges() { return incidentEdges; } //Add an incident Edge public void addIncidentEdge(Edge e) { if (!incidentEdges.contains(e)) incidentEdges.add(e); }   public void removeEdge(Vertex v) { for (int i=incidentEdges.size()-1; i>=0; i--) { Edge e = incidentEdges.get(i); if (e.getDestVertex().equals(v) && e.getOriginVertex().equals(this)) { incidentEdges.remove(i); break; } else if (e.getDestVertex().equals(this) && e.getOriginVertex().equals(v)) { incidentEdges.remove(i); break; } } }   @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Vertex other = (Vertex) obj; if (this._element != other._element && (this._element == null || !this._element.equals(other._element))) { return false; } return true; }   @Override public int hashCode() { int hash = 7; hash = 31 * hash + (this._element != null ? this._element.hashCode() : 0); return hash; }     }```
• October 22nd, 2010, 02:36 PM
copeg
Re: Issue Building Graph in Adjacency Matrix
Quote:

Originally Posted by mike.s
so I would essentially use this new method to check the vertex before and above?

Yes
Quote:

Originally Posted by mike.s
is there no way to move around the ArrayList without creating a new method?

Yes...you can create an Array or ArrayList of size with*height, initializing all its values to null. Then instead of 'adding' the Vertex to the array, you set the Vertex value in the array when creating a new vertex.
Quote:

With the new method, I would loop through to check all the Vertices and add edges as I go through them, no?
No. You use a lookup to retrieve the value at the position.
• October 22nd, 2010, 02:44 PM
mike.s
Re: Issue Building Graph in Adjacency Matrix
cant wait till I have to translate this into 68HC11... Havent even gotten to the search algorithms yet :|