Thread: Graph -adjacency linked list

  1. #1
    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
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    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,318
    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
    28,413
    Quote Originally Posted by iMalc
    Wouldn't using a std::multi_map be easiest?
    Possibly, though it is std::multimap.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    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,318
    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