7 Replies - 1598 Views - Last Post: 15 April 2010 - 09:32 PM Rate Topic: -----

#1 Crunch   User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Is my graph correct

Posted 15 April 2010 - 10:41 AM

This is my graph

class edge{

    vertex from;
    edge next;
    int cost;

   edge(vertex from, int cost){
       this.cost = cost;
       this.from = from;       
   }

}

class vertex{

   vertex down;
   edge next;
   String name;

    vertex(String s){
       name=s;

    }
}


class Graph{

    vertex V;

    void addedge(vertex to, vertex from, int cost){

        if(to.next == null) to.next = new edge(from,cost);
        else{

            edge tmp= to.next;

            for(; tmp.next!=null; tmp=tmp.next);
            tmp.next = new edge(from,cost);

        }
    }
    void addvertex(String s){

        if(V==null){
         V = new vertex(s);

        }
        else{

            vertex tmp=V;

            for( ; tmp.down != null ; tmp=tmp.down);
            tmp.down = new vertex(s);

        }

    }

}



Is my implementation correct?

Is This A Good Question/Topic? 0
  • +

Replies To: Is my graph correct

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Is my graph correct

Posted 15 April 2010 - 11:07 AM

That looks good. I implemented a Graph structure a little bit differently to allow for additional functionality. Feel free to take a look at my Graphs tutorial for ideas.
Was This Post Helpful? 1
  • +
  • -

#3 Crunch   User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Is my graph correct

Posted 15 April 2010 - 06:53 PM

View Postmacosxnerd101, on 15 April 2010 - 05:07 PM, said:

That looks good. I implemented a Graph structure a little bit differently to allow for additional functionality. Feel free to take a look at my Graphs tutorial for ideas.



In your graph implementation i didn't see a vertex class why is that?
And whats does the connector class do here?

This post has been edited by Au-Z-C: 15 April 2010 - 06:53 PM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Is my graph correct

Posted 15 April 2010 - 06:56 PM

I believe I explained in the tutorial that An Edge is a synonym for Vertex. I also believe that I discussed in the tutorial that the Connectors are used to connect two Edges, allowing for distance to be representing through weighting the Graphs at the Edges or along the Connectors. When using this structure to represent a Map in a Game, it makes it easier to represent significance of certain places, along with the distance required to get there.

Edit: Scratch that one part. I did not mention that in my tutorial, though I will add a comment to clarify. Anyways, an Edge is a Vertex, so there is no need to have two separate classes for Edge and Vertex.

This post has been edited by macosxnerd101: 15 April 2010 - 07:02 PM

Was This Post Helpful? 1
  • +
  • -

#5 Crunch   User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Is my graph correct

Posted 15 April 2010 - 07:19 PM

macosxnerd101: now in your tutorial you have this connector class that acts like edges in the normal graph. So to connect two vertices you have to create a new connector object. So how do we perform a BFS or DFS using your graph since the connector objects have no link with the array-list vertices?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Is my graph correct

Posted 15 April 2010 - 07:37 PM

I'm not sure I understand what you mean. I use an ArrayList<Edge<E>> in the Graph class for efficient random access to an Edge. Once you find your starting Edge, you can use Connectors to go between Edges. Both Breadth-first and depth-first searches are still possible with my Graph. Really, the whole function of the Graph class is to encapsulate the Edges. All the work is done via Edges and Connectors.
Was This Post Helpful? 0
  • +
  • -

#7 Galois   User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Is my graph correct

Posted 15 April 2010 - 08:32 PM

macosxnerd101, in graph theory vertices and edges are 2 different things. When drawing a graph, vertices are the nodes, whereas edges are the lines that connect those vertices. The names are rather self-descriptive.

Edit: It looks like you call vertices as edges, and edges as connectors. Don't know where you got this terminology, but it's not right.

http://en.wikipedia....ki/Graph_theory

This post has been edited by Galois: 15 April 2010 - 08:42 PM

Was This Post Helpful? 1
  • +
  • -

#8 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Is my graph correct

Posted 15 April 2010 - 09:32 PM

Thanks for correcting my terminology. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1