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?

Aha, sounds like another electrical engineer at work! (Me too, 20 years
ago!) I once did this very thing to save us time checking the accuracy of a
PC (printed circuit) layout output file from REDAC software (I used Pascal
to write it). (I notice that your output has an error in it: Group 3 has
connection 45 in it, which should make it a member of group 2!)

I have 2 suggestions for the output format before working on this
algorithm:

1. Convert your list into 2 columns (this might be the easiest):

Group Connection
----- ----------
1 2
1 3
1 9
2 7
2 8
2 12
2 30
2 45
3 56
3 65

2. Convert your list into 2 columns, but condense column 2 into a single
cell (probably easier for an end user to read; apply word-wrap to the final
worksheet formatting):

Group Connections
----- --------------------------------
1 2,3,9
2 7,8,12,30,45
3 56,65

Which format would be preferable?
--
Regards,
Bill Renaud

On Oct 14, 12:23 am, "Bill Renaud"
wrote:
Aha, sounds like another electrical engineer at work! (Me too, 20 years
ago!) I once did this very thing to save us time checking the accuracy of a
PC (printed circuit) layout output file from REDAC software (I used Pascal
to write it). (I notice that your output has an error in it: Group 3 has
connection 45 in it, which should make it a member of group 2!)

I have 2 suggestions for the output format before working on this
algorithm:

1. Convert your list into 2 columns (this might be the easiest):

Group Connection
----- ----------
1 2
1 3
1 9
2 7
2 8
2 12
2 30
2 45
3 56
3 65

2. Convert your list into 2 columns, but condense column 2 into a single
cell (probably easier for an end user to read; apply word-wrap to the final
worksheet formatting):

Group Connections
----- --------------------------------
1 2,3,9
2 7,8,12,30,45
3 56,65

Which format would be preferable?
--
Regards,
Bill Renaud

:) You're right in saying that I'm an electrical engineer... You're
really experienced in reading people's minds I guess... Thank you for
the suggestion... Actually I'm sorry about that Group 2 issue... I did
a mistake while typing...

Actually the first option looks good though I still want to preserve
the parent-child relation here. For example, from the above list, I
want to retain the least information that when 2,3 and 3,9 belong to
the group, 2 and 3 are directly related; 3 and 9 are directly related
instead of falling into the assumption that 2 and 9 are directly
related. But either ways its fine... Would you suggest a workflow for
this please?

On Oct 14, 12:23 am, "Bill Renaud"
wrote:
Aha, sounds like another electrical engineer at work! (Me too, 20 years
ago!) I once did this very thing to save us time checking the accuracy of a
PC (printed circuit) layout output file from REDAC software (I used Pascal
to write it). (I notice that your output has an error in it: Group 3 has
connection 45 in it, which should make it a member of group 2!)

I have 2 suggestions for the output format before working on this
algorithm:

1. Convert your list into 2 columns (this might be the easiest):

Group Connection
----- ----------
1 2
1 3
1 9
2 7
2 8
2 12
2 30
2 45
3 56
3 65

2. Convert your list into 2 columns, but condense column 2 into a single
cell (probably easier for an end user to read; apply word-wrap to the final
worksheet formatting):

Group Connections
----- --------------------------------
1 2,3,9
2 7,8,12,30,45
3 56,65

Which format would be preferable?
--
Regards,
Bill Renaud

:) You're right in saying that I'm an electrical engineer... You're
really experienced in reading people's minds I guess... Thank you for
the suggestion... Actually I'm sorry about that Group 2 issue... I did
a mistake while typing...

Actually the first option looks good though I still want to preserve
the parent-child relation here. For example, from the above list, I
want to retain the least information that when 2,3 and 3,9 belong to
the group, 2 and 3 are directly related; 3 and 9 are directly related
instead of falling into the assumption that 2 and 9 are directly
related. But either ways its fine... Would you suggest a workflow for
this please?

On Oct 14, 12:23 am, "Bill Renaud"
wrote:
Aha, sounds like another electrical engineer at work! (Me too, 20 years
ago!) I once did this very thing to save us time checking the accuracy of a
PC (printed circuit) layout output file from REDAC software (I used Pascal
to write it). (I notice that your output has an error in it: Group 3 has
connection 45 in it, which should make it a member of group 2!)

I have 2 suggestions for the output format before working on this
algorithm:

1. Convert your list into 2 columns (this might be the easiest):

Group Connection
----- ----------
1 2
1 3
1 9
2 7
2 8
2 12
2 30
2 45
3 56
3 65

2. Convert your list into 2 columns, but condense column 2 into a single
cell (probably easier for an end user to read; apply word-wrap to the final
worksheet formatting):

Group Connections
----- --------------------------------
1 2,3,9
2 7,8,12,30,45
3 56,65

Which format would be preferable?
--
Regards,
Bill Renaud

:) You're right in saying that I'm an electrical engineer... You're
really experienced in reading people's minds I guess... Thank you for
the suggestion... Actually I'm sorry about that Group 2 issue... I did
a mistake while typing...

Actually the first option looks good though I still want to preserve
the parent-child relation here. For example, from the above list, I
want to retain the least information that when 2,3 and 3,9 belong to
the group, 2 and 3 are directly related; 3 and 9 are directly related
instead of falling into the assumption that 2 and 9 are directly
related. But either ways its fine... Would you suggest a workflow for
this please?

<<I still want to preserve the parent-child relation here. For example,
from the above list, I want to retain the least information that when 2,3
and 3,9 belong to the group, 2 and 3 are directly related; 3 and 9 are
directly related instead of falling into the assumption that 2 and 9 are
directly related.

Sounds like you want to more-or-less keep the original list, just resort
the rows so that all connections in the same group are listed together.
Maybe you just need to check your PC layout software package to see if it
will output connections grouped by net, rather than at random (?).

Is that possible? I'm not sure at this point that you need to go to a lot
of trouble writing an Excel macro.

Normally, you don't care exactly what the connections are in a single net,
you simply want to verify that all connections are connected that are
supposed to be, so that you don't have a floating gate input somewhere. I
suppose you might care about the detailed copper routing if you are doing
high frequency RF or high power work somehow, but this requires a look at
the actual layout anyway, and cannot be determined by a net list alone.

Anyway, I was thinking along the lines of using an array of collections to
input and store the net, or using another worksheet with the Find method to
look for connections while re-grouping everything. But, these methods may
not work now, since your follow-up reply adds additional, complicating,
criteria.
--
Regards,
Bill Renaud

On Oct 14, 2:41 pm, "Bill Renaud"
wrote:
<<I still want to preserve the parent-child relation here. For example,
from the above list, I want to retain the least information that when 2,3
and 3,9 belong to the group, 2 and 3 are directly related; 3 and 9 are
directly related instead of falling into the assumption that 2 and 9 are
directly related.

Sounds like you want to more-or-less keep the original list, just resort
the rows so that all connections in the same group are listed together.
Maybe you just need to check your PC layout software package to see if it
will output connections grouped by net, rather than at random (?).

Is that possible? I'm not sure at this point that you need to go to a lot
of trouble writing an Excel macro.

Normally, you don't care exactly what the connections are in a single net,
you simply want to verify that all connections are connected that are
supposed to be, so that you don't have a floating gate input somewhere. I
suppose you might care about the detailed copper routing if you are doing
high frequency RF or high power work somehow, but this requires a look at
the actual layout anyway, and cannot be determined by a net list alone.

Anyway, I was thinking along the lines of using an array of collections to
input and store the net, or using another worksheet with the Find method to
look for connections while re-grouping everything. But, these methods may
not work now, since your follow-up reply adds additional, complicating,
criteria.
--
Regards,
Bill Renaud

Oh... Thank you for the opinion. However, these are not related to
circuit board analysis :( It is something related to Computer Node
analysis - Packet Tx/Rx... So any change in your suggestions? I am
really sorry for taking your time...

<<However, these are not related to circuit board analysis :( It is
something related to Computer Node analysis - Packet Tx/Rx... So any change
in your suggestions?

No problem; faulty assumption on my part, but still interesting
nevertheless.

I guess I would still consider my earlier format suggestion of inserting a
column to the left of your data to hold the Group number. The main part of
the algorithm would have to deal with the problem of "merging" groups
together. Take the following example:

Suppose you have data like the following:

1,2
3,4
2,3

I see the process as follows (data processing operations in progress shown
below):

Group Conn1 Conn2
1 1 2
2 3 4
2 3

1. Parse the data out into separate columns. This can be done with the
TextToColumns function in Excel, which is a single line of code.
2. Insert a new column in front of column $A.
3. Insert a new row at the top of the data and enter column labels (Group,
Conn1, Conn2), so the data can be treated as a list. This is because you
will be doing sort operations during and at the end of the process.
4. Number the first row of data (1,2) as Group 1.
5. Since the second row of data (3,4) has nothing in common (yet) with
Group 1, start a new Group (2).
6. Now on the third row of data (2,3), it becomes apparent that one of
these connections (2 in column Conn1) is common to Group 1, so this row has
to be put in Group 1. On further examination, the other connection of this
pair (3 in column Conn2) is common to the second row of data, meaning that
this row will have to be renumbered to Group 1. In other words, row 2 now
has to be "merged" with the data in rows 1 and 3 (Group 1).

Your table will now be renumbered to look like the following:

Group Conn1 Conn2
1 1 2
1 3 4
1 2 3

As you can see, the analysis of each successive line will require
"back-checking" of all previous Groups (and rows of data) to see if this
merging process needs to be accomplished. This will become the major part
of your algorithm, and may require frequent sorting if done on a worksheet
(hence the need for column labels). You might also consider Data
AutoFiltering, to quickly hide all rows not needed in the Group renumbering
process.

At the end of the process, the Group column could be converted into the
format you originally suggested and this column deleted. I think this would
just be extra work, though, and wouldn't really add anything to the
usability of the final data set.

Let the newsgroup know, if you need some help writing some of the routines.
Have fun!
--
Regards,
Bill Renaud

This version does not use recursion, but it does parse your data out first,
if it is in a single column with commas between connection pairs. It also
adds headers (column labels) at the top of the worksheet. The data is moved
1 column to the right to make room for the Group numbers, which are
inserted in column A. The data is sorted by Group number, then by
Connection number at the end. I did not write a routine to renumber the
Groups to be consecutive.

'----------------------------------------------------------------------
'Sorts pairs of connections together by Group number,
'but does not renumber the Groups to be consecutive
'after some groups are merged into single groups.

Public Sub RegroupConnectionData()
'Code by Bill Renaud.
Dim wsData As Worksheet 'Worksheet containing the data.
Dim rngAllData As Range 'Add connection data and headers.
Dim lngLastRow As Long 'The last row of data to process.
Dim rngCurrentRow As Range 'Reference to single cell in column $A.
Dim rngSearchRange As Range 'Previous rows of connections.
Dim ilngRow As Long 'Index to current row of data.
Dim lngGroup As Long 'Last Group number assigned.
Dim lngConn1 As Long 'First connection listed on the row.
Dim lngConn2 As Long 'Second connection listed on the row.
Dim lngGroup1 As Long 'Group number of lngConn1.
Dim lngGroup2 As Long 'Group number of lngConn2.

Application.ScreenUpdating = False

'Assume the active worksheet is the one to process.
Set wsData = ActiveSheet

InitializeDataWorksheet wsData

Set rngAllData = wsData.UsedRange

With rngAllData
lngLastRow = .Row + .Rows.Count - 1
If lngLastRow < 3 Then GoTo ExitSub 'No more data to process.
End With

'First row of data is automatically Group 1.
lngGroup = 1
wsData.Range("A2").Value = lngGroup

'Initialize other variables to start iterative process.
With wsData
Set rngCurrentRow = .Range("A3")
Set rngSearchRange = .Range("B2:C2")
End With

For ilngRow = 3 To lngLastRow
'Get value of each connection.
lngConn1 = rngCurrentRow.Offset(ColumnOffset:=1).Value
lngConn2 = rngCurrentRow.Offset(ColumnOffset:=2).Value

'Now determine if either connection belongs to a previous group.
'If 0 is returned, then connection was not found in previous data.
lngGroup1 = GetGroup(lngConn1, rngSearchRange)
lngGroup2 = GetGroup(lngConn2, rngSearchRange)

If (lngGroup1 = 0) And (lngGroup2 = 0) _
Then
'Assign a new Group number. Just use the next higher number,
'even if a lower number is now available because of merging.
lngGroup = lngGroup + 1
rngCurrentRow.Value = lngGroup
Else
If (lngGroup1 < 0) And (lngGroup2 < 0) _
And (lngGroup1 < lngGroup2) _
Then
With Application.WorksheetFunction
'Assign the lowest Group number to this connection.
rngCurrentRow.Value = .Min(lngGroup1, lngGroup2)

'Merge the higher numbered Group with the lower Group.
MoveGroup .Max(lngGroup1, lngGroup2), _
.Min(lngGroup1, lngGroup2), _
rngAllData
End With
Else
With Application.WorksheetFunction
'One of the connections belongs to a previous
'Group or both belong to the same Group.
'Assign the highest Group number to this connection.
rngCurrentRow.Value = .Max(lngGroup1, lngGroup2)
End With
End If
End If

'Move pointers.
Set rngCurrentRow = rngCurrentRow.Offset(1, 0)
With rngSearchRange
Set rngSearchRange = .Resize(RowSize:=.Rows.Count + 1)
End With
Next ilngRow

'Autofit columns of data, freeze window pane.
FinishFormatting wsData

ExitSub:
End Sub

'----------------------------------------------------------------------
Private Sub InitializeDataWorksheet(wsData As Worksheet)
With wsData
'Parse comma-separated data out to separate columns
'(works even if not needed).
.UsedRange.TextToColumns DataType:=xlDelimited, Comma:=True

'Insert column at the left to hold Group numbers.
.Columns("A").Insert

'Create header row on row 1.
.Rows(1).Insert
.Range("A1").Value = "Group"
.Range("B1").Value = "Conn1"
.Range("C1").Value = "Conn2"
With .Range("A1:C1")
.Font.Bold = True
With .Borders(xlEdgeBottom)
.LineStyle = xlContinuous
.Weight = xlThin
End With
End With
End With
End Sub

'----------------------------------------------------------------------
Private Function GetGroup(Connection As Long, _
SearchRange As Range) _
As Long

Dim rngFindResult As Range

On Error Resume Next

Set rngFindResult = SearchRange.Find(What:=Connection, _
LookIn:=xlValues, _
LookAt:=xlWhole)

If rngFindResult Is Nothing _
Then
'Connection not found in previous connections.
GetGroup = 0
Else
'Return Group number from column $A.
GetGroup = rngFindResult.EntireRow.Cells(1, 1).Value
End If
End Function

'----------------------------------------------------------------------
Private Sub MoveGroup(FromGroup As Long, _
ToGroup As Long, _
rngData As Range)

Dim rngGroup As Range 'Cells in the entire Group column.
Dim rngFromGroup As Range 'Cells in the Group column to be renumbered.

With rngData
Set rngGroup = .Resize(RowSize:=.Rows.Count - 1, ColumnSize:=1) _
.Offset(RowOffset:=1)
End With

rngData.AutoFilter Field:=1, Criteria1:="=" & CStr(FromGroup)

Set rngFromGroup = rngGroup.SpecialCells(xlCellTypeVisible)

'Convert Group from old value to new value to merge with ToGroup.
rngFromGroup.Value = ToGroup

'Turn AutoFilter off.
rngData.Parent.AutoFilterMode = False
End Sub

'----------------------------------------------------------------------
Private Sub FinishFormatting(wsData As Worksheet)
Dim rngData As Range

Set rngData = wsData.UsedRange

With rngData
'Sort the final list of data in ascending
'order by Group, Conn1, and Conn2.
.Sort Key1:="Group", Order1:=xlAscending, _
Key2:="Conn1", Order2:=xlAscending, _
Key3:="Conn2", Order3:=xlAscending, _
Header:=xlYes, _
Orientation:=xlTopToBottom

'Autofit column widths to fit the data.
.Columns.AutoFit
End With

'Freeze window at row 2 of the data.
wsData.Range("A2").Activate
wsData.Parent.Windows(1).FreezePanes = True
End Sub

--
Regards,
Bill Renaud