Generate Disconnected Graph in C

This is a discussion on Generate Disconnected Graph in C within the C Programming forums, part of the General Programming Boards category; I am doing a program in C on graph theory. So I need an idea with which i can generate ...

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Generate Disconnected Graph in C

    I am doing a program in C on graph theory. So I need an idea with which i can generate random graphs which are mostly highly disconnected. Can anyone give me any idea please?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,671
    Create N nodes and log2(N) paths between random pairs of nodes.

    Eg, if N = 256, then log2(N) will be 8 (that's going to be pretty well disconnected).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Oh thanks! Nice idea let me try! Will ask here if I get struck! Thanks a lot!

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Create N nodes and 0 edges. That's the most disconnected you can get.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template metaprogramming, whats the point?
    By Cogman in forum C++ Programming
    Replies: 26
    Last Post: 02-01-2009, 10:47 PM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  3. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 10:25 PM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 11:21 AM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 03:48 AM

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