DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Jul 2006
Posts
4

Hi this is my first time to the forums and I am hoping to recieve some help on a project I am working on.

I am trying to create an undirected graph using adjacency lists
I have my class that creates the links between vertices, and i have a struct that contains
struct Node
{
int vertex;
Node * next;
}

How can I go through each and be able to add to each subscripted array and go through the list
so if the user enters (1,0), (2,0) (3,2);
then

The code I use, is what would be used in a regular stack code and it gives me answers like
i stepped through the code and can't figure out why its doing it that way at all

void CGraph::CCreate(int xLoc, int yLoc)
{
node *yPtr;
node *xPtr;

node *Xtemp;
node *Ytemp;

xPtr = new node;
yPtr = new node;

Xtemp = new node;
Ytemp = new node;

Xtemp->vertex = xLoc;
Xtemp->next = yPtr;
yPtr = Xtemp;
HeadNodes[yLoc] = *yPtr; //This is where it erases both the *yPtr and the HeadNodes[yLoc] to a forever list

Ytemp->vertex = yLoc;
Ytemp->next = xPtr;
xPtr = Ytemp;
HeadNodes[xLoc] = *xPtr; //Same problem here
}
Any help would be greatly appreciated, thank you so much in advance for the help.

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
You need to have two separate sets of lists: the list of the vertices, and a list which might or might not exist representing the various out edges from a particular vertex. So - have two node pointers - vNode and eNode - and you should be covered [all of the eNode[s] will have vNode = null].

3. Registered User
Join Date
Jul 2006
Posts
4
Umm I don't get what you mean, why would I need to have two different nodes?
and do you mean structs or two declarations of type "Node"

and why would I need two? what would be the purpose?

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
No ... each node would have two Node* pointers - one being vNode and the other being eNode

in your example, the nodes would be linked 0-1-2-3 by their vNode pointers

then you would have a list from the "0" node with eNode pointers going to 1 to 2
from the 1 node pointing to 0
from the 2 node pointing to 0 and 3
from the 3 node pointing to 2

you can make the "vNode" list be a backbone, then have a linked list of Nodes "coming off" the back bone at each level ...

5. Registered User
Join Date
Jul 2006
Posts
4
So is there no way to just use one Node Array?
Its not as simple as
?
i can't just make it that each index is its own linked list
as if i'd be making a Stack?

6. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468

Sure, I don't know why you cannot have the various "edge" lists come off array backing. There is no magic on the "list" being "linked" or "indexed in an array".

You might also decide to have a collection of pointers stored for "nextNode" - 0-1, 0-2 - stored in a vector which is part of your node struc or class.

So yes, you have the freedom to do this. It might work for you. Do some research into the functionality you will have to create to make your structure do what you want.

Don't sell the two "nodeTypes" idea short, however, and the power of having real information being stored in these nodes. In the "real world" graphs are used to represent MANY real relationships - Sudoku challenges, maps, schedules, people, all sorts of things which have relationships. Vertex nodes will store very different information from that stored in Edge nodes. Vertex nodes will hold location information - how hot it is, elevation, restaurants available, classrooms at the location, class description and prerequisites and current enrollment, etc. Edges nodes will hold "weight" information - distance, time, difficulty, scenery - and this information will be very different for a trip from 0-1 than for 2-1. Where does your structure provide a place for that different information? How do you propose to have a node located at 0 in your array hold its "location" data as well as the "weight" data for each of the trips to the nodes it is adjacent to?
Last edited by nspils; 07-16-2006 at 09:07 AM.

7. Registered User
Join Date
Jul 2006
Posts
4
Well for now I am not going to worry about the edge idea, as far as the weight of the graph between each vertex.

I just want to be able to show each node and what they would be connected to.
So that is why I don't get why I need to have two Nodes, is there maybe a site that may explain how it all works and can anyone tell me why I can't just have an Array of linked lists...

Maybe explaining it in some other way b/c I just don't get it.

Thanks for your time again, I really appreciate this!

8. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468

9. Registered User
Join Date
May 2007
Posts
843
I think i have understand why we need two structure.
0-1-2-3 -- Represent using struct vertex

0 edges point to 1 and 3 - Represent using struct edges.

Please correct me if i wrong.

10. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
What you wrote is certainly do-able, Peter. You provide a storage structure which holds your representation of the vertices (nodes) of the graph. Each vertex can have a storage structure which holds a representation (be it a struct or a class object) of the "edges" which originate (are outbound) from that vertex.

I found another reference which is a good one page summary of graph theory.

http://www.boost.org/libs/graph/doc/...ry_review.html

11. Registered User
Join Date
May 2007
Posts
843
Thanks for your explanation. I will look into that article.

12. Registered User
Join Date
May 2007
Posts
843

What is edge-list representation ? what is the advantages of this representation compare to array of pointers ?

Insertion takes O(n);

Is a representation edges coming out from every vertex

Therefore, 1-4 and 2-3 is represented using edge node.

Below is my understanding :

1-2-3-4 -- Represent using vertex

Please correct me if i wrong.

Another question is if i understand the graph the theory, then how to build a graph ? A function declaration is the hint

Last edited by Peter_APIIT; 03-21-2008 at 03:58 AM.

13. Registered User
Join Date
May 2007
Posts
843
Another graph theory other user may benefits from it.

14. Registered User
Join Date
May 2007
Posts
843
This is the representation i looking for.

My Requirements is weighted graph represent in edge.

15. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
Peter - I could not open your .zip file.

One of the data members of your "edge" class could be the weight of that edge. You might also store the two vertices connected by that edge, but that's up to you. If the graph is undirected, I suggest having two edge objects for each edge of the graph - so each edge represents one direction of traversal in the graph.

"What is edge-list representation ? what is the advantages of this representation compare to array of pointers ?"

You can use arrays of pointers for your work in your program. However, you need to have data which is being pointed to by those pointers. The object you choose to use as the representation of each vertex and the object you choose to use as the representation of each edge are the data which can be pointed to by your pointers.

The two main representations of a graph usually used in graph theory are adjacency list/edge-list and matrix. You can use pointers in either representation.
Last edited by nspils; 03-21-2008 at 07:50 AM.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise