Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: Issue Building Graph in Adjacency Matrix

  1. #1
    Junior Member
    Join Date
    Oct 2010
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

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

        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) {}
                     }
                }
            }

    Here is the addEdge method:
          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;
     
        }

    Here is the addVertex method:
          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:
    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
    Attached Files Attached Files
    Last edited by mike.s; October 22nd, 2010 at 09:57 AM.


  2. #2
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default 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

    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

  3. #3
    Junior Member
    Join Date
    Oct 2010
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Issue Building Graph in Adjacency Matrix

    I am storing the Vertices and the Edges in ArrayLists
    here is my graph class:
    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:
        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.
    Last edited by mike.s; October 22nd, 2010 at 02:15 PM.

  4. #4
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

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

  5. #5
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default 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

  6. #6
    Junior Member
    Join Date
    Oct 2010
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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:
    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:
    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;
        }
     
     
    }
    Last edited by mike.s; October 22nd, 2010 at 02:31 PM.

  7. #7
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default Re: Issue Building Graph in Adjacency Matrix

    Quote Originally Posted by mike.s View Post
    so I would essentially use this new method to check the vertex before and above?
    Yes
    Quote Originally Posted by mike.s View Post
    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.
    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.

  8. #8
    Junior Member
    Join Date
    Oct 2010
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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

Similar Threads

  1. How to make a graph like this
    By sugarhigh in forum AWT / Java Swing
    Replies: 1
    Last Post: August 27th, 2010, 09:05 AM
  2. Building Table of Specified Rows and Columns
    By wale89 in forum Java Servlet
    Replies: 1
    Last Post: August 3rd, 2010, 08:57 AM
  3. Building a Menu List
    By websey in forum AWT / Java Swing
    Replies: 1
    Last Post: November 15th, 2009, 09:34 AM
  4. Retrieving BFS code's adjacency list
    By moose4204l in forum Collections and Generics
    Replies: 0
    Last Post: October 20th, 2008, 06:30 PM
  5. Replies: 1
    Last Post: October 7th, 2008, 07:35 AM