On 14 Říj, 06:18, Legend <[EMAIL PROTECTED]> wrote:
> 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?
Arrange all pairs into a matrix G (g[1,12] = 1, g[1,3 0] = 1, 0
otherwise in the first row. Find G^(T)G. In it, all connected
subgraphs will be identifiable.
kunzmilan
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
