Graph -adjacency linked list

This is a discussion on Graph -adjacency linked list within the C++ Programming forums, part of the General Programming Boards category; hi i want to implement graph using adjacency linked list cos adjacency matrix consumes o(n^2).... any help or suggestions on ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    Graph -adjacency linked list

    hi i want to implement graph using adjacency linked list cos adjacency matrix consumes o(n^2)....

    any help or suggestions on how to implement adjacency linked list using c++ stl

    thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,734
    It depends on how you want to do it. For example, you could use a std::map to map the nodes to a std::list (a doubly linked list) of pointers or iterators to adjacent nodes.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks.....can i have an example .....implementation using nodes and list using stl's

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Wouldn't using a std::multi_map be easiest?
    An adjacency matrix should give better performance though. The graph would have to be pretty large, and sparsely connected, for me to want to use a multi_map instead.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,734
    Quote Originally Posted by iMalc
    Wouldn't using a std::multi_map be easiest?
    Possibly, though it is std::multimap.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by iMalc View Post
    Wouldn't using a std::multi_map be easiest?
    Depending on how multimap is implemented, mightn't using a multimap defeat much of the efficiency that an adjacency list implementation should provide?

    Wouldn't it be simpler and more efficient to represent the graph as a (probably sorted) std::list of nodes, with each node having (in addition to "value", "color", etc.) a std::vector of pointers to its neighbors? I'm suggesting vector since "in general" the adjacency lists don't have to be sorted. But if the application requires searching the adjacency lists for specific entries, each node can have a sorted std::list of neighbor pointers.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by R.Stiltskin View Post
    Depending on how multimap is implemented, mightn't using a multimap defeat much of the efficiency that an adjacency list implementation should provide?

    Wouldn't it be simpler and more efficient to represent the graph as a (probably sorted) std::list of nodes, with each node having (in addition to "value", "color", etc.) a std::vector of pointers to its neighbors? I'm suggesting vector since "in general" the adjacency lists don't have to be sorted. But if the application requires searching the adjacency lists for specific entries, each node can have a sorted std::list of neighbor pointers.
    Oops yeah no underscore, my blunder.

    I don't think an adjacency list provides much efficiency. Seeing if two nodes are neighbours is an O(n*m) operation where n = the number of items in the list, and m = the number of items in the vector. Compare that to the O(1) of an adjacency matrix and that's just pitiful.
    If you don't specifically need to access items in a std::list in sorted order, then there isn't any point in sorting it. It's not like sorting it would allow you to perform a binary search on it anyway.

    Depending on how often you need to connect, disconnect, add, or remove nodes, the fastest solution (outside of a matrix) is probably to use a vector of pairs with std::lower_bound / std::upper_bound / std::equal_range. That way once you've built it, queries can be done in O(log n) time, and in contiguous memory so its fast and has no per-item overhead.

    Seriously, an adjacency matrix is still a great idea even for a moderate-sized matrix though. You can pack each connection into 1 bit meaning that a 64 node graph's adjacency information could be stored in just 64 bytes. (64 bits * 64 bits = 512 bits = 64 bytes)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User DeadlyWarrior's Avatar
    Join Date
    Dec 2009
    Location
    Pakistan
    Posts
    5
    Plz tell me a good website to learn about graphs in C++ completely.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21