Dario Romani

Greenhorn

Posts: 13

posted 13 years ago

I am trying to understand the concept of "position", as it relates to data structures and as it is defined in the book "Data Structures and Algorithms in Java", 2nd. Ed., by Goodrich & Tomassia. For those who don't have access to this textbook, the concept is also explained in an article by same authors at the following link:

http://www.cs.brown.edu/cgc/jdsl/papers/access.pdf

I am a little confused and I was wondering if someone could help me out.

Sorry for the long post but I wanted to provide background for those who don't have the textbook.

Reference 1

--------------

According to the textbook, "A position is itself an abstract data type that supports the following simple method:

element():Return the element stored at this position

Input: NoneOutput: Object

Reference 2

---------------

Code fragment 5.3 (p.199) in the textbook shows a class called DNode that realizes a node of a doubly-linked list and implements Position.

class DNode implements Position {

private DNode prev, next;// References to the nodes before and after

private Object element;// Element stored in this position

// Constructor

public DNode(DNode newPrev, DNode newNext, Object elem) {

prev = newPrev;

next = newNext;

element = elem;

}

// Method from interface Position

public Object element() throws InvalidPositionException {

if ((prev == null) && (next == null))

throw new InvalidPositionException("Position is not in a list!");

return element;

}

// get and set methods.....

}

Reference 3

---------------

In Section 5.3.3 (p.209), in section entitled "Implementing a Sequence with an Array", the book defines a soultion where "..we store a new kind of position object in each cell of A, and we store elements in positions. The new position object p holds the index i, and the element e associated with p."

Reference 4

---------------

In section 6.4.1, a section entitled "A Vector-Based Structure for Binary Trees", on page 264, states:

"The level numbering function p suggests a representation of a binary tree T by means of a vector S such that node v of T is associated with the element of S at rank p(v). ........

Such an implementation is simple and efficient, for we can use it to easily perform the methods root, parent, leftChild, ......... by using simple arithmetic operations on the numbers p(v) associated with each node v involved in the operation. That is, each position object v is simply a wrapper for the index p(v) into the vector S."

Reference 5

---------------

In Section 12.2 entitled "Data Structures for Graphs", subsection 12.2.1 entitled "The Edge List Structure", on page 547, it states:

"In this representation, a vertex v of G storing an element o is explicitly represented as a vertex object. All such vertex objects ares tored in a container V, which would typically be a list, vector, or dictionary. If we represent V as a vector, for example, we would automatically think of the vertices as being numbered. ..... Note that the elements of container V are the vertex positions of graph G.

Vertex Objects

The vertex object for a vertex v storing element o has instance variables for:

- A reference to o

- Counters for the numbers of incident undirected edges, incoming directed edges, and outgoing edges

- A reference to the position of the vertex object in container V.

End of references

-----------------

I am tryng to set up Java classes to implement a graph using a vector implementation of an edge-list data structure.

My first step is to set up a class representing a Vertex. I will ignore the instance variables for edge counters mentioned above to keep it simple. I also want to add an instance variable to give the Vertex a name (e.g., vA, vB, etc.).

So following fromt he textbook (see Ref.5 above) I have set up the following class:

public class Vertex implements Position{

private String vName;

private Object vCargo;

private Position vPos;

//constructor

public Vertex(String n, Object o, Position p) {

vName = n;

vCargo = o;

vPos = p;

}

//get and set methods go here

//implementation of element() method of Position interface goes here

}

At some point I am going to have to use the constructor to create new vertex objects.

Question 1: What I will be passing to the constructor to represent parameter p ?

Question 2: What exactly should the element() method return? Just vCargo? or an object that includes vName and vCargo? Or an object that includes vname, vCargo and vPos?

I think I understand the concept of Position as it is used in the doubly-linked-list context, where you have to define nodes in relation to previous and next position. But when it comes to a vector context, where you can make direct reference to cells, I feel like I just don't have a full grip of the Position concept.

I would really appreciate if someone could help me, both conceptually and practically as it is applied above.

http://www.cs.brown.edu/cgc/jdsl/papers/access.pdf

I am a little confused and I was wondering if someone could help me out.

Sorry for the long post but I wanted to provide background for those who don't have the textbook.

Reference 1

--------------

According to the textbook, "A position is itself an abstract data type that supports the following simple method:

element():Return the element stored at this position

Input: NoneOutput: Object

Reference 2

---------------

Code fragment 5.3 (p.199) in the textbook shows a class called DNode that realizes a node of a doubly-linked list and implements Position.

class DNode implements Position {

private DNode prev, next;// References to the nodes before and after

private Object element;// Element stored in this position

// Constructor

public DNode(DNode newPrev, DNode newNext, Object elem) {

prev = newPrev;

next = newNext;

element = elem;

}

// Method from interface Position

public Object element() throws InvalidPositionException {

if ((prev == null) && (next == null))

throw new InvalidPositionException("Position is not in a list!");

return element;

}

// get and set methods.....

}

Reference 3

---------------

In Section 5.3.3 (p.209), in section entitled "Implementing a Sequence with an Array", the book defines a soultion where "..we store a new kind of position object in each cell of A, and we store elements in positions. The new position object p holds the index i, and the element e associated with p."

Reference 4

---------------

In section 6.4.1, a section entitled "A Vector-Based Structure for Binary Trees", on page 264, states:

"The level numbering function p suggests a representation of a binary tree T by means of a vector S such that node v of T is associated with the element of S at rank p(v). ........

Such an implementation is simple and efficient, for we can use it to easily perform the methods root, parent, leftChild, ......... by using simple arithmetic operations on the numbers p(v) associated with each node v involved in the operation. That is, each position object v is simply a wrapper for the index p(v) into the vector S."

Reference 5

---------------

In Section 12.2 entitled "Data Structures for Graphs", subsection 12.2.1 entitled "The Edge List Structure", on page 547, it states:

"In this representation, a vertex v of G storing an element o is explicitly represented as a vertex object. All such vertex objects ares tored in a container V, which would typically be a list, vector, or dictionary. If we represent V as a vector, for example, we would automatically think of the vertices as being numbered. ..... Note that the elements of container V are the vertex positions of graph G.

Vertex Objects

The vertex object for a vertex v storing element o has instance variables for:

- A reference to o

- Counters for the numbers of incident undirected edges, incoming directed edges, and outgoing edges

- A reference to the position of the vertex object in container V.

End of references

-----------------

I am tryng to set up Java classes to implement a graph using a vector implementation of an edge-list data structure.

My first step is to set up a class representing a Vertex. I will ignore the instance variables for edge counters mentioned above to keep it simple. I also want to add an instance variable to give the Vertex a name (e.g., vA, vB, etc.).

So following fromt he textbook (see Ref.5 above) I have set up the following class:

public class Vertex implements Position{

private String vName;

private Object vCargo;

private Position vPos;

//constructor

public Vertex(String n, Object o, Position p) {

vName = n;

vCargo = o;

vPos = p;

}

//get and set methods go here

//implementation of element() method of Position interface goes here

}

At some point I am going to have to use the constructor to create new vertex objects.

Question 1: What I will be passing to the constructor to represent parameter p ?

Question 2: What exactly should the element() method return? Just vCargo? or an object that includes vName and vCargo? Or an object that includes vname, vCargo and vPos?

I think I understand the concept of Position as it is used in the doubly-linked-list context, where you have to define nodes in relation to previous and next position. But when it comes to a vector context, where you can make direct reference to cells, I feel like I just don't have a full grip of the Position concept.

I would really appreciate if someone could help me, both conceptually and practically as it is applied above.

posted 13 years ago

Your "position" parameter in the class Vertex wouldn't be a "position" within a data structure.

Normally you create a class which represents something, anything. You than use a data structure to hold multiple of those.

So you create a class to represent a car, than have a data structure to represent a parking garage to hold one or more "cars".

So the first thing you need to do is figure what defines a vector and those things are a "vector" class. You than pick a data structure to hold one or more vectors.

Each data sturcture has different ways of holding and accessing the data members which it contains. This is the what you are refering to when you are talking about "postition", I think. Don't worry so much about all the different ways different data structures access their data. You need to pick the data structure which works best for you than start dropping in those "vectors".

Normally you create a class which represents something, anything. You than use a data structure to hold multiple of those.

So you create a class to represent a car, than have a data structure to represent a parking garage to hold one or more "cars".

So the first thing you need to do is figure what defines a vector and those things are a "vector" class. You than pick a data structure to hold one or more vectors.

Each data sturcture has different ways of holding and accessing the data members which it contains. This is the what you are refering to when you are talking about "postition", I think. Don't worry so much about all the different ways different data structures access their data. You need to pick the data structure which works best for you than start dropping in those "vectors".

Please ignore post, I have no idea what I am talking about.

posted 13 years ago

William,

You have to go read the article. The authors are presenting some specific concepts as alternatives to traditional iterators. They give a specific, subtle meaning to the term "position". Dario is just trying to understand this dry academic paper.

Dario,

I looked at the paper, didn't study it in detail, but I don't follow their arguments very well, either, and have a hard time understanding how you would extend what they're doing to vector-like containers. I

My personal, possibly misinformed opinion: if you're in a CompSci class and a professor told you to read this paper and implement a vector version, then OK, go ahead and do it. But otherwise, file this article in the "Interesting, but whatever" pile and go on with your life.

You have to go read the article. The authors are presenting some specific concepts as alternatives to traditional iterators. They give a specific, subtle meaning to the term "position". Dario is just trying to understand this dry academic paper.

Dario,

I looked at the paper, didn't study it in detail, but I don't follow their arguments very well, either, and have a hard time understanding how you would extend what they're doing to vector-like containers. I

*think*you could do it by introducing a layer of indirection -- the Position object could be (for example) a key into a hashtable that contained the index of the object in an vector container. But I have no idea why anybody would want to do this -- the time and space complexity are awful compared to a traditional vector.My personal, possibly misinformed opinion: if you're in a CompSci class and a professor told you to read this paper and implement a vector version, then OK, go ahead and do it. But otherwise, file this article in the "Interesting, but whatever" pile and go on with your life.

Dario Romani

Greenhorn

Posts: 13

posted 13 years ago

William,

I understand what you are saying, and the next step will be to build an EdgeListGraph class to represent the entire graph, and it will contain a vector of vertex objects (along with other things). But if you look at Reference 5 in my initial post, you will notice that the authors specifically identify as a Vertex instance variable "A reference to the position of the vertex object in container V."

However the position of a particular vertex object in the container will not be known until I create a Vertex object and use the insertVertex method in EdgeListGraph to add the vertex object to the Vector. So perhaps this is a field that stays "null" until it is populated by the insertVertex method. But my question is stil the same: what value or reference would I be placing into this field?

Ernest,

Thank you for your reply. It is gratifying that someone else at least understands what it is that I don't understand. There is some fundamental concept here that is eluding me, perhaps due to the subtlety of the concept (or not?). I would love to just "get on with my life", but this Position concept seems to come back with every assignment!

Follow-ups and additional opinions welcome!

I understand what you are saying, and the next step will be to build an EdgeListGraph class to represent the entire graph, and it will contain a vector of vertex objects (along with other things). But if you look at Reference 5 in my initial post, you will notice that the authors specifically identify as a Vertex instance variable "A reference to the position of the vertex object in container V."

However the position of a particular vertex object in the container will not be known until I create a Vertex object and use the insertVertex method in EdgeListGraph to add the vertex object to the Vector. So perhaps this is a field that stays "null" until it is populated by the insertVertex method. But my question is stil the same: what value or reference would I be placing into this field?

Ernest,

Thank you for your reply. It is gratifying that someone else at least understands what it is that I don't understand. There is some fundamental concept here that is eluding me, perhaps due to the subtlety of the concept (or not?). I would love to just "get on with my life", but this Position concept seems to come back with every assignment!

Follow-ups and additional opinions welcome!

posted 13 years ago

You have two objects a graph, and a vertex. The graph uses a vector data structure to hold the vertex(s). The vertex object wll contain (among other things) its location on/in the graph. Your problem is that you don't understand how to provide a value for the vertex location.

So we need to somehow map the location of the vertex on the graph to its location with in vector.

If we could change the problem a little it would be easyer to solve. (Is that allowed?) If the data structure to hold the vertex(s) was a 2d array than the mapping from the location in the data structure to its location on the graph would be the same. So if vertex Z was at graph location 3,4 (using x - y coridinates) that would also be its location within the 2d array. So you would have a 1 to 1 mapping between the location within the data stucture to the location on the graph.

Is it required that you use a vector to hold these vertex(s)?

So we need to somehow map the location of the vertex on the graph to its location with in vector.

If we could change the problem a little it would be easyer to solve. (Is that allowed?) If the data structure to hold the vertex(s) was a 2d array than the mapping from the location in the data structure to its location on the graph would be the same. So if vertex Z was at graph location 3,4 (using x - y coridinates) that would also be its location within the 2d array. So you would have a 1 to 1 mapping between the location within the data stucture to the location on the graph.

Is it required that you use a vector to hold these vertex(s)?

Please ignore post, I have no idea what I am talking about.

Dario Romani

Greenhorn

Posts: 13

posted 13 years ago

william,

Just to clarify, the type of graph I am talking about is defined as a collection of vertices and edges. In this context, it is not at all related to Cartesian co-ordinates or to other common uses of the word graph, such as "graphing a line" or "graphing data".

Here is a link that explains the kind of graph I am talking about:

http://www.cs.purdue.edu/homes/axa/cs251/transparencies/Ch12-Graphs-4x4.pdf

I am developing a java class to implement the Graph ADT mentioned in the link. I am following one of the approaches described in the textbook for doing this. The approach I am using is called using an edge list structure to represent a graph. It involves defining a Vertex class and an Edge class. The Graph class, which represents the entire graph, will include a container to hold the Vertex objects and a container to hold the Edge objects. There are several types of containers you can use. I have chosen to use a Vector implementation for the Vertices container and a Vector implementation for the Edges container.

I didn't mention edges in my earlier post because I wanted to keep it simple. But now that edges have come up, the concept of position applies to edges too: the textbook lists the following description fo one of the instance variables of an edge object:

"- a reference to the position of the edge-object in container E."

My questions relate specifically on how to implement the concept of "position" (in the sense that it is described in the textbook, which I have tried to convey above) in the context of the approach I have taken to implement the Graph ADT.

Have a look at the following link (from my initial post) if you want a better idea of the concept of "position" in this context.

http://www.cs.brown.edu/cgc/jdsl/papers/access.pdf

Are we still on the same wavelength?

Just to clarify, the type of graph I am talking about is defined as a collection of vertices and edges. In this context, it is not at all related to Cartesian co-ordinates or to other common uses of the word graph, such as "graphing a line" or "graphing data".

Here is a link that explains the kind of graph I am talking about:

http://www.cs.purdue.edu/homes/axa/cs251/transparencies/Ch12-Graphs-4x4.pdf

I am developing a java class to implement the Graph ADT mentioned in the link. I am following one of the approaches described in the textbook for doing this. The approach I am using is called using an edge list structure to represent a graph. It involves defining a Vertex class and an Edge class. The Graph class, which represents the entire graph, will include a container to hold the Vertex objects and a container to hold the Edge objects. There are several types of containers you can use. I have chosen to use a Vector implementation for the Vertices container and a Vector implementation for the Edges container.

I didn't mention edges in my earlier post because I wanted to keep it simple. But now that edges have come up, the concept of position applies to edges too: the textbook lists the following description fo one of the instance variables of an edge object:

"- a reference to the position of the edge-object in container E."

My questions relate specifically on how to implement the concept of "position" (in the sense that it is described in the textbook, which I have tried to convey above) in the context of the approach I have taken to implement the Graph ADT.

Have a look at the following link (from my initial post) if you want a better idea of the concept of "position" in this context.

http://www.cs.brown.edu/cgc/jdsl/papers/access.pdf

Are we still on the same wavelength?

Dario Romani

Greenhorn

Posts: 13

posted 13 years ago

Thanks for trying to help me out William. I think you were headed down the right path - what you described is a type of abstration, which is the stated purpose of the Position ADT - to allow client to use Position when referring to Verices and Edges, instead of using references that require the client to know the underlying implementation(e.g., indexed reference to a vector cell).

My problem is that I don't know how to accomplish this abstraction in the context of my implementation.

Regarding your last comment - I'll settle for someone who knows Data Structures and Algorithms in Java

My problem is that I don't know how to accomplish this abstraction in the context of my implementation.

Regarding your last comment - I'll settle for someone who knows Data Structures and Algorithms in Java

posted 13 years ago

Well I see no one has showed up yet. I guess all the smart folks have more interesting things to do than sit around at home reading Javaranch.com.

I will get it another try here. And this time I actually read some of the original post, and followed some of the links!

You have a Map which holds pointers to the Vertex[s] stored in the Vector data structure. This will give you that layer of redirection you are looking for. The Vextex[s] can be moved around the Vector all you want, the pointer in the Map will always be able to find the exact Vertex you are looking for. The Key entry in the Map is the name of the Vertex, and the Value is the Vertex (a pointer into the Vector).

I will get it another try here. And this time I actually read some of the original post, and followed some of the links!

You have a Map which holds pointers to the Vertex[s] stored in the Vector data structure. This will give you that layer of redirection you are looking for. The Vextex[s] can be moved around the Vector all you want, the pointer in the Map will always be able to find the exact Vertex you are looking for. The Key entry in the Map is the name of the Vertex, and the Value is the Vertex (a pointer into the Vector).

Please ignore post, I have no idea what I am talking about.

posted 13 years ago

The code below shows how you can create a level of redirection using two vectors. Both of the vectors maintain pointers to Vertex instances. You can move the elements around in the �PostionV� vector and the elements in the �LocationV� vector will not lose track of the elements.

I think that this is one of the items you are looking for.

Sorry about the ugly code. And I am sure that someone else will show up and give a better example.

I think that this is one of the items you are looking for.

Sorry about the ugly code. And I am sure that someone else will show up and give a better example.

Please ignore post, I have no idea what I am talking about.