CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 32
  1. #1
    Join Date
    Oct 2007
    Posts
    60

    A weird requirement - unable to think of anything...

    Suppose that I have some data:

    12,30
    12,45
    2,3
    7,8
    3,9
    30, 8
    45,54
    56,65

    Where (a,b) indicates that a is connected to b. I want to get all connected nodes to one point. For instance, the output of the above example should be something like:

    Group 1
    2,3
    3,9
    Group 2
    12,30
    12,45
    30,8
    7,8
    Group 3
    45,54
    Group 4
    56,65

    The order is not important as long as the whole group stays together. Reason why they are grouped like that:

    1. 2 is connected to 3 and 3 is connected to 9 and so we put all the three, i.e. 2,3,9 into one group.
    2. 12 is connected to 45 and 12 is also connected to 30 so we put these in the same group but 30 is connected to 8 and 8 is connected to 7 so ultimately we put all these into the same group.
    3. 45 and 54 are connected but not related to any other numbers so we put them into another group
    4. 56 and 65 are connected but not related to any other numbers so we put them into another group

    I am unable to figure out an algorithm for this. Can someone guide me?

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    Quote Originally Posted by legend986
    I am unable to figure out an algorithm for this. Can someone guide me?
    Fortunately for you, someone else already figured out an algortihm for this problem. See this link on Strongly Connected Components.
    The 1st step is to transform your data into a bidirectional graph. Since all edges are bidirectional, running a DFS (Depth 1st Search) while marking each visited node as "visited", starting from each unvisited node will give you what you ask for.

    Algorithm goes:
    Code:
    1. Convert data into a bidirectional graph G.
    2. For each node v in G:
    	 2.1 If v is not "visited" yet:
    			 2.2 Run DFS(v), and mark all nodes reached
    				as "visited" (and add them to a list L).
    			 2.3 Output the list L.
    The outputed L lists are the connected components you wanted to find.
    Last edited by Zachm; October 14th, 2007 at 12:53 AM.

  3. #3
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    :worship: So you do know about my problem...! Can you please tell me how to transform it into a bidirectional graph? My research team has access to MATLAB. You think I can use that to achieve this?

    Also, just a small clarification... With the procedure you mentioned, I will be able to get all the connected components as separate groups is it? Because, I'm interested in all the chains that are possible...
    Last edited by legend986; October 14th, 2007 at 01:06 AM.

  4. #4
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    One simple way is to create an Adjacency list from the data. If you are using matlab, then maybe it would be simpler for you to use an Adjacency matrix to represent the graph.
    Adding edges to the data structure is simple from the type of data you described.

  5. #5
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    Quote Originally Posted by legend986
    Also, just a small clarification... With the procedure you mentioned, I will be able to get all the connected components as separate groups is it? Because, I'm interested in all the chains that are possible...
    Each group (or list) will have all nodes that are connected, meaning that there is a path from each one of them to each other of the same group. Alternatively you can create lists of edges (pairs of nodes) in the same manner, if it helps you more.
    What do you mean by "all the chains that are possible", please define a "chain".

  6. #6
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    Thats the problem... If it was for some small data, I would've described the matrix myself but I have some thousands of such records and I know of no simple way of forming an adjacency matrix for the same... Any advice that you think would be useful?

  7. #7
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    And yeah sorry about that... I accidentally typed chain instead of a list... I'm new to graph theory so kindly excuse my typos...

  8. #8
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    How many records ? 1000 ? 10000 ? actually the number that really matters is the number of nodes and not the number of tuples, because it dictates the size of the matrix. The disadvantage of an adjaceny matrix is that it is inefficient in memory consumption - the link between two nodes is assigned a memory even if it doesn't exist.
    If you have more than ~5000 nodes, than maybe better use an adjacency list, and better not use matlab for it.

  9. #9
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    Oh... unfortunately the number could be somewhere around half a million to one million... I'm still gathering the data actually so I only know of the approximate number...

  10. #10
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    the number could be somewhere around half a million to one million...
    If this is the approx. number of different possible numbers (not number of pairs), you definitely should use an Adjacency List data structure. Read about it a little bit - you'll see that it's really easy to implement and use.
    Are you familiar with C++ ?

    If so, I can provide a code for the algorithm I described, using an adjacency list, I'm just re-using some classes that I wrote during my CS studies.
    It would be easier than to try and explain how to do it, and from reading it, maybe it would be easier to understand the concepts. But I won't take the effort (as small as it is) unless I know it will be useful for you.

  11. #11
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    Well, I'm afraid its not the numbers that I was talking about. Its the total number of pairs... I've been reading about the Adjacency Matrix recently and thought it would solve my problem but I had no clue on how to construct one for this data...

    And regarding C++, I'm not so familiar with it but I think I'll give it a shot. I know great deal of PHP and I'm sure I can familiarize myself with C++ in a few days... Thank you so much for your help... So what do you think I should be doing now? I've started reading about the connectivity and adjacency as such...

  12. #12
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    But how do you think I should organize my data? Consider them as vertices or simple numbers? Because, I can think of connectivity between vertices or just numbers... and can't really make out how the plan would differ depending on this... What I mean is, should I be considering (2,3) as a vertex or 2,3 as two numbers that are just linked... I don't know how this would make any difference but I think you have considered a particular case right? Which one is it? Vertices or individual numbers?

  13. #13
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    Can you approximate the total number of different numbers ? - if it is up to ~5000 than maybe an adjacency matrix will be simpler.

  14. #14
    Join Date
    Oct 2006
    Posts
    616

    Re: A weird requirement - unable to think of anything...

    Each vertex should represent a number and each edge represents a pair of numbers - or the link between them.

  15. #15
    Join Date
    Oct 2007
    Posts
    60

    Re: A weird requirement - unable to think of anything...

    Oh... I'm not sure myself but what if I use a very powerful computer to do this task? As part of my research, I have a few powerful computers at my disposal... Would that make any difference?

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured