DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Thread: Adjacecny Lists C++

  1. #1
    Join Date
    Jul 2006
    Posts
    4

    Adjacecny Lists C++

    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;
    }

    Node *Headnodes;
    HeadNodes = new Node[X];

    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
    HeadNode[0] = 0-->1-->2
    HeadNode[1] = 1-->0
    HeadNode[2] = 2-->0-->3
    HeadNode[3] = 3-->2

    The code I use, is what would be used in a regular stack code and it gives me answers like
    HeadNode[0] = 1-->1-->1-->1-->....(forever)
    HeadNode[1] = 0-->0-->0-->0-->....(forever)
    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;

    xPtr = &HeadNodes[xLoc];
    yPtr = &HeadNodes[yLoc];

    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. #2
    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. #3
    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. #4
    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. #5
    Join Date
    Jul 2006
    Posts
    4
    So is there no way to just use one Node Array?
    Its not as simple as
    headnode[0] = 0->1->3
    HeadNode[1] = 1->0
    HeadNode[2] = 2
    HeadNode[3] = 3->0
    ?
    i can't just make it that each index is its own linked list
    as if i'd be making a Stack?

  6. #6
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You asked about the classic structure of the adjacency lists representation of a graph.

    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. #7
    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. #8
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468

  9. #9
    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. #10
    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. #11
    Join Date
    May 2007
    Posts
    843
    Thanks for your explanation. I will look into that article.

  12. #12
    Join Date
    May 2007
    Posts
    843
    I have read that article.

    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


    Thanks for your help.
    Last edited by Peter_APIIT; 03-21-2008 at 03:58 AM.

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

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

    My Requirements is weighted graph represent in edge.
    Attached Files Attached Files

  15. #15
    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.

    You asked:

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

Similar Threads

  1. Linked Lists - hard exercise(help needed)
    By parallel in forum Java
    Replies: 6
    Last Post: 08-13-2013, 05:50 AM
  2. Replies: 0
    Last Post: 09-19-2005, 07:21 AM
  3. Replies: 0
    Last Post: 01-11-2002, 05:46 AM
  4. How do you Export Owners of Distribution Lists ?
    By Patrick in forum Enterprise
    Replies: 2
    Last Post: 04-09-2001, 11:48 PM
  5. automating distribution lists
    By Jamie Harsevoort in forum Enterprise
    Replies: 0
    Last Post: 11-30-2000, 05:34 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center