11 Replies - 11477 Views - Last Post: 07 April 2010 - 08:45 AM Rate Topic: -----

#1 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

help me implement addEdge method

Posted 04 April 2010 - 06:34 AM

package javaapplication1;

class Vertex{

    Vertex next;
    
    char name;

Vertex(char chr){

    name= chr;
    next=NULL;
        
}

}

class Graph{

    int nVerts=0;

int MAX_VERTS = 20;
    Vertex vertexList[];

    Graph(){

        vertexList = new Vertex[MAX_VERTS];

    }

    public void addVertex(char lab) // argument is label
{
vertexList[nVerts++] = new Vertex(lab);
}

    public void addEdge(int startnode , int nextnode){

Vertex tmp = vertexList[startnode] ;
        
for( ; tmp.next != NULL; tmp=tmp.next); // finding the spot to place the new Vertex
// Line A

    }


}
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        Graph  g1= new Graph();
        g1.addVertex('A');
        g1.addVertex('B');
        g1.addVertex('C');
        g1.addVertex('D');

    }

}




At line A

What do i have to do

Create a new Vertex or attach an already created vertex?

Is This A Good Question/Topic? 0
  • +

Replies To: help me implement addEdge method

#2 m-e-g-a-z   User is offline

  • Winning
  • member icon


Reputation: 497
  • View blog
  • Posts: 1,457
  • Joined: 19-October 09

Re: help me implement addEdge method

Posted 04 April 2010 - 07:03 AM

Well you need to have a method that takes both Verticies you want to add an edge to.

This is just an example below,

 public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException { 


In your case, you would have the two char signatures within the parameters of the method.

You may want to check out this -Graph Data Structure

Also Wikipedia explains things in detail when it comes to a Graph Data Structure.

Wiki - Graph

adjacent(G, x,y): tests whether there is an edge from node x to node y.
neighbors(G, x): lists all nodes y such that there is an edge from x to y.
add(G, x,y): adds to G the edge from x to y, if it is not there.
delete(G, x,y): removes the edge from x to y, if it is there.
get_node_value(G, x): returns the value associated with the node x.
set_node_value(G, x, a): sets the value associated with the node x to a.

Edit - bit of colour :)

This post has been edited by m-e-g-a-z: 04 April 2010 - 07:04 AM

Was This Post Helpful? 1
  • +
  • -

#3 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

Re: help me implement addEdge method

Posted 04 April 2010 - 07:13 AM

View Postm-e-g-a-z, on 04 April 2010 - 06:03 AM, said:

Well you need to have a method that takes both Verticies you want to add an edge to.

 public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException { 



what does to and from mean? What function do they do here?

This post has been edited by cissee: 04 April 2010 - 07:14 AM

Was This Post Helpful? 0
  • +
  • -

#4 m-e-g-a-z   User is offline

  • Winning
  • member icon


Reputation: 497
  • View blog
  • Posts: 1,457
  • Joined: 19-October 09

Re: help me implement addEdge method

Posted 04 April 2010 - 07:49 AM

Lets say we have two Verticies , lets call them '3' and '7'.

What this To and From simply means how the edge is connected.

From (3) ---> To (7)

So the edge is starting from Vertex 3 connecting to Vertex 7.
Was This Post Helpful? 1
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




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

Re: help me implement addEdge method

Posted 04 April 2010 - 08:50 AM

I've actually written a tutorial on designing a Graph Structure. You may want to check it out.

Link: http://www.dreaminco...raphs-tutorial/
Was This Post Helpful? 1
  • +
  • -

#6 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

Re: help me implement addEdge method

Posted 05 April 2010 - 07:29 PM

Now in the method addEdge do i have to create a new vertex or else connect it to already created vertex in the vertex list?
Was This Post Helpful? 0
  • +
  • -

#7 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

Re: help me implement addEdge method

Posted 05 April 2010 - 09:29 PM

Can i store just the index of the vertex as a edge to save space?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




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

Re: help me implement addEdge method

Posted 06 April 2010 - 05:26 AM

Did you take a look at my Graphs tutorial? I cover all that there.
Was This Post Helpful? 0
  • +
  • -

#9 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

Re: help me implement addEdge method

Posted 06 April 2010 - 09:23 AM

View Postmacosxnerd101, on 06 April 2010 - 04:26 AM, said:

Did you take a look at my Graphs tutorial? I cover all that there.



I cannot understand what you have done there. Come on its just an yes or no please answer.
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




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

Re: help me implement addEdge method

Posted 06 April 2010 - 06:46 PM

A vertex is an edge. What specifically do you not understand about my Graphs tutorial?
Was This Post Helpful? 0
  • +
  • -

#11 cissee   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 66
  • Joined: 20-November 09

Re: help me implement addEdge method

Posted 07 April 2010 - 07:23 AM

View Postmacosxnerd101, on 06 April 2010 - 05:46 PM, said:

A vertex is an edge. What specifically do you not understand about my Graphs tutorial?



Can't you do like this

Write an Edge class

then create an Edge object and attach it to Vertex Object?

So then you get Vertices in one linked list and edge's as linked list's that start from vertices.

Like this

class Edge{


}

class Vertice{

Vertice down;  Vertice linkedlist
Edge Next; // Edge linkedlist

}



Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




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

Re: help me implement addEdge method

Posted 07 April 2010 - 08:45 AM

If you look up the definition of a vertex, it will come up the same as an Edge.

As for your class structure, I used 3 classes:
-Edge: Contained weights, contained List<Connector> which described other Edges it was connected to

-Connector: Linked two Edges, possibly included a distance
-Graph: Contains a List<Edge>, which represents all the Edges in the Graph
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1