Disjoint set

This is a discussion on Disjoint set within the C++ Programming forums, part of the General Programming Boards category; i wanted to check the connectivity of of graph... i can use the disjoint data structure...but heard one can use ...

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

    Disjoint set

    i wanted to check the connectivity of of graph...

    i can use the disjoint data structure...but heard one can use multimaps...is it possible...

    it ll be helpful if i am provided with an example or sample code...

    thanks

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    but heard one can use multimaps
    Well, if you want the nodes of each connected set, yes. Use a standard simple disjoint subgraph finder (pretty trivial using any kind of search), and keep a counter that counts the number of subgraphs you've found. And, while you walk the graph, add each node to the multimap, using the current count as an index. When you're done, the multimap will contain one key per subgraph, and all the nodes of the subgraph will be mapped at this key.

    But since the key set is integral, 0-based and continuous, it intuitively sounds better to use a simple array/vector as the map, mapping to another container type.

    http://www.boost.org/doc/libs/1_36_0...omponents.html
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks for the reply..
    i seem to partially understand ur statement...
    say edges 1 2 and 3 4 ..means there are 2 components...graph is not connected...
    for my scenario each vertex is a character
    so i did
    Code:
    for each node
    makeset(v)
    
    for each edge :if(fibnset(u)!=findset(v)
    union(u,v)
    finally i check findset(all vertices)whether lie in same component ....if yes ,its ok ,,,,,else not connected

    can u just explain with maps with a sample code

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Do you understand how depth first visitation works? Given such a visitation function, you could write it as pseudo-code:
    Code:
    multimap<int, vertex> components;
    graph g;
    int currentComponent = 0;
    
    for every vertex v in g {
      if v not marked {
        visit_depth(v, visitor);
        ++currentComponent;
      }
    }
    where visitor = function(vertex w) {
      mark w;
      insert w into components with key currentComponent;
    }
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SystemParametersInfo set wallpaper issues
    By A10 in forum Windows Programming
    Replies: 5
    Last Post: 03-14-2008, 07:39 PM
  2. Replies: 8
    Last Post: 01-18-2008, 03:06 AM
  3. The new FAQ
    By Hammer in forum A Brief History of Cprogramming.com
    Replies: 34
    Last Post: 08-30-2006, 10:05 AM
  4. Menu Item Caption - /a for right aligned Accelerator?
    By JasonD in forum Windows Programming
    Replies: 6
    Last Post: 06-25-2003, 11:14 AM
  5. Set default directory with GetTempDir?
    By Bajanine in forum Windows Programming
    Replies: 2
    Last Post: 05-04-2003, 11:36 PM

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