algorizm to merge nodes

[JD]

Hi,

I need help for a task looks very simple:

I got a python list like:

[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]

Each item in the list need to be merged.

For example, 'a', 'b' will be merged, 'c', 'd' will be merged.

Also if the node in the list share the same name, all these nodes need
be merged.

For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']

The answer should be:

[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]

Anyone has a solution?

Thanks,

JD

[Chris Rebert]

Re: algorizm to merge nodes

(Disclaimer: completely untested)

from collections import defaultdict

merged = defaultdict(lis t)
for key, val in your_list_of_pa irs:
merged[key].append(val)

result = [[key]+vals for key, vals in merged.items()]

Cheers,
Chris
--
Follow the path of the Iguana...

http://rebertia.com

On Fri, Oct 17, 2008 at 1:20 PM, JD <Jiandong.Ge@gm ail.comwrote:

Hi,
>
I need help for a task looks very simple:
>
I got a python list like:
>
[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]
>
Each item in the list need to be merged.
>
For example, 'a', 'b' will be merged, 'c', 'd' will be merged.
>
Also if the node in the list share the same name, all these nodes need
be merged.
>
For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']
>
The answer should be:
>
[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]
>
Anyone has a solution?
>
Thanks,
>
JD
--

http://mail.python.org/mailman/listinfo/python-list

>

[JD]

Re: algorizm to merge nodes

Hi,

Thanks for the help,

but the result is not quite right:

[['a', 'b', 'g'], ['c', 'd', 'u'], ['b', 'p'], ['e', 'f', 'k']]

the ['b', 'p'] is not merged.

JD

On Oct 17, 2:35 pm, "Chris Rebert" <c...@rebertia. comwrote:

(Disclaimer: completely untested)
>
from collections import defaultdict
>
merged = defaultdict(lis t)
for key, val in your_list_of_pa irs:
merged[key].append(val)
>
result = [[key]+vals for key, vals in merged.items()]
>
Cheers,
Chris
--
Follow the path of the Iguana...http://rebertia.com
>
On Fri, Oct 17, 2008 at 1:20 PM, JD <Jiandong...@gm ail.comwrote:

Hi,

>

I need help for a task looks very simple:

>

I got a python list like:

>

[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]

>

Each item in the list need to be merged.

>

For example, 'a', 'b' will be merged, 'c', 'd' will be merged.

>

Also if the node in the list share the same name, all these nodes need
be merged.

>

For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']

>

The answer should be:

>

[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]

>

Anyone has a solution?

>

Thanks,

>

JD
--
http://mail.python.org/mailman/listinfo/python-list

[Mensanator]

Re: algorizm to merge nodes

On Oct 17, 3:20 pm, JD <Jiandong...@gm ail.comwrote:

Hi,
>
I need help for a task looks very simple:
>
I got a python list like:
>
[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]
>
Each item in the list need to be merged.
>
For example, 'a', 'b' will be merged, 'c', 'd' will be merged.
>
Also if the node in the list share the same name, all these nodes need
be merged.
>
For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']
>
The answer should be:
>
[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]
>
Anyone has a solution?

A = [['a', 'b'], \
['c', 'd'], \
['e', 'f'], \
['a', 'g'], \
['e', 'k'], \
['c', 'u'], \
['b', 'p']]

merged = []

for i in A:
if len(merged)==0:
merged.append(s et(i))
else:
gotit = False
for k,j in enumerate(merge d):
u = j.intersection( set(i))
if len(u):
merged[k] = j.union(set(i))
gotit = True
if not gotit:
merged.append(s et(i))

print merged

##
## [set(['a', 'p', 'b', 'g']), set(['c', 'u', 'd']), set(['k', 'e',
'f'])]
##

>
Thanks,
>
JD

[bearophileHUGS@lycos.com]

Re: algorizm to merge nodes

JD, you probably need the algorithm for connected components of an
undirected graph.

For example you can do that with my graph lib:

http://sourceforge.net/projects/pynetwork/

from graph import Graph
g = Graph()
data = [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'],
['c', 'u'], ['b', 'p']]
g.addArcs(data, bi=True)

print g.connectedComp onents()
# Output: [['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile

[JD]

Re: algorizm to merge nodes

Hi,

Thanks,

It works for this example,

but if I add another item ['e', 'd']:
[['a', 'b'], \
['c', 'd'], \
['e', 'f'], \
['a', 'g'], \
['e', 'k'], \
['c', 'u'], \
['b', 'p'],\
['e', 'd']]

The result is
set(['a', 'p', 'b', 'g']), set(['e', 'c', 'u', 'd']), set(['k', 'e',
'd', 'f'])

The right result should be:

['a', 'p', 'b', 'g'], ['c', 'u', 'e', 'd', 'k', 'f']

JD




On Oct 17, 3:00 pm, Mensanator <mensana...@aol .comwrote:

On Oct 17, 3:20 pm, JD <Jiandong...@gm ail.comwrote:
>
>
>

Hi,

>

I need help for a task looks very simple:

>

I got a python list like:

>

[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]

>

Each item in the list need to be merged.

>

For example, 'a', 'b' will be merged, 'c', 'd' will be merged.

>

Also if the node in the list share the same name, all these nodes need
be merged.

>

For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']

>

The answer should be:

>

[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]

>

Anyone has a solution?

>
A = [['a', 'b'], \
['c', 'd'], \
['e', 'f'], \
['a', 'g'], \
['e', 'k'], \
['c', 'u'], \
['b', 'p']]
>
merged = []
>
for i in A:
if len(merged)==0:
merged.append(s et(i))
else:
gotit = False
for k,j in enumerate(merge d):
u = j.intersection( set(i))
if len(u):
merged[k] = j.union(set(i))
gotit = True
if not gotit:
merged.append(s et(i))
>
print merged
>
##
## [set(['a', 'p', 'b', 'g']), set(['c', 'u', 'd']), set(['k', 'e',
'f'])]
##
>
>
>

Thanks,

>

JD

[JD]

Re: algorizm to merge nodes

Thanks,

This one really works.

JD

On Oct 17, 3:17 pm, bearophileH...@ lycos.com wrote:

JD, you probably need the algorithm for connected components of an
undirected graph.
>
For example you can do that with my graph lib:http://sourceforge.net/projects/pynetwork/
>
from graph import Graph
g = Graph()
data = [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'],
['c', 'u'], ['b', 'p']]
g.addArcs(data, bi=True)
>
print g.connectedComp onents()
# Output: [['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]
>
Bye,
bearophile

[Paul McGuire]

Re: algorizm to merge nodes

On Oct 17, 3:20 pm, JD <Jiandong...@gm ail.comwrote:

Hi,
>
I need help for a task looks very simple:
>

<snip>

I smell "homework assignment".

-- Paul

[Mensanator]

Re: algorizm to merge nodes

On Oct 17, 4:34 pm, JD <Jiandong...@gm ail.comwrote:

Hi,
>
Thanks,
>
It works for this example,
>
but if I add another item ['e', 'd']:
[['a', 'b'], \
     ['c', 'd'], \
     ['e', 'f'], \
     ['a', 'g'], \
     ['e', 'k'], \
     ['c', 'u'], \
     ['b', 'p'],\
     ['e', 'd']]
>
The result is
set(['a', 'p', 'b', 'g']), set(['e', 'c', 'u', 'd']), set(['k', 'e',
'd', 'f'])
>
The right result should be:
>
['a', 'p', 'b', 'g'], ['c', 'u', 'e', 'd', 'k', 'f']
>
JD
>
On Oct 17, 3:00 pm, Mensanator <mensana...@aol .comwrote:
>
>
>

On Oct 17, 3:20 pm, JD <Jiandong...@gm ail.comwrote:

>

Hi,

>

I need help for a task looks very simple:

>

I got a python list like:

>

[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]

>

Each item in the list need to be merged.

>

For example, 'a', 'b' will be merged, 'c', 'd' will be merged.

>

Also if the node in the list share the same name, all these nodes need
be merged.

>

For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']

>

The answer should be:

>

[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]

Well, you should have asked for that, if that's what you wanted.

>

Anyone has a solution?

>

A = [['a', 'b'], \
     ['c', 'd'], \
     ['e', 'f'], \
     ['a', 'g'], \
     ['e', 'k'], \
     ['c', 'u'], \
     ['b', 'p']]

>

A.sort()

merged = []

>

for i in A:
    if len(merged)==0:
        merged.append(s et(i))
    else:
        gotit = False
        for k,j in enumerate(merge d):
            u = j.intersection( set(i))
            if len(u):
                merged[k] = j.union(set(i))
                gotit = True
        if not gotit:
            merged.append(s et(i))

>

print merged

>

##
##    [set(['a', 'p', 'b', 'g']), set(['c', 'u', 'd']), set(['k', 'e',
'f'])]
##

## [set(['a', 'p', 'b', 'g']), set(['c', 'e', 'd', 'f', 'u', 'k'])]

>

Thanks,

>

JD

[Gerard flanagan]

Re: algorizm to merge nodes

JD wrote:

Hi,
>
I need help for a task looks very simple:
>
I got a python list like:
>
[['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
'u'], ['b', 'p']]
>
Each item in the list need to be merged.
>
For example, 'a', 'b' will be merged, 'c', 'd' will be merged.
>
Also if the node in the list share the same name, all these nodes need
be merged.
>
For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
'b', 'g', 'p']
>
The answer should be:
>
[['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]
>
Anyone has a solution?
>

data = [
['a', 'b'],
['c', 'd'],
['e', 'f'],
['a', 'g'],
['e', 'k'],
['c', 'u'],
['b', 'p'],
]


def merge(inlist):
n = len(inlist)
outlist = [set(inlist.pop( ))]
while inlist:
s = set(inlist.pop( ))
merged = False
for i in range(len(outli st)):
t = outlist[i]
u = s | t
if len(u) < len(s) + len(t):
outlist[i] = u
merged = True
break
if not merged:
outlist.append( s)
if len(outlist) == n:
return outlist
else:
return merge(outlist)

for s in merge(data):
print s

[JD]

Re: algorizm to merge nodes

It could be a very good "homework assignmet".

This is for a real application.

each item in the list represent two terminals of a resistor. All the
resistors in the list are shorted, I need to figure out how many
independent nets are there.

JD

On Oct 17, 4:16 pm, Paul McGuire <pt...@austin.r r.comwrote:

On Oct 17, 3:20 pm, JD <Jiandong...@gm ail.comwrote:Hi ,
>

I need help for a task looks very simple:

>
<snip>
>
I smell "homework assignment".
>
-- Paul

[bearophileHUGS@lycos.com]

Re: algorizm to merge nodes

JD:

Thanks,
This one really works.

Note that you can save some RAM (almost half) creating a directed
graph, because later the connectedCompon ents() manages the arcs as
undirected anyway:

>>from graph import Graph
>>g = Graph()
>>data = [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c', 'u'], ['b', 'p']]
>>g.addArcs(dat a)
>>g.connectedCo mponents()

[['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile

[Scott David Daniels]

Re: algorizm to merge nodes

JD wrote:

It could be a very good "homework assignment".
This is for a real application.

def do_nets(pairs):
r = {}
for a, b in pairs:
if a in r:
a_net = r[a]
if b not in a_net: # if not redundant link
if b in r: # Need to merge nets
a_net |= r[b]
for x in r[b]:
r[x] = a_net
else: # add a single node to the net
a_net.add(b)
r[b] = a_net
elif b in r: # add this node to another net
r[b].add(a)
r[a] = q[b]
else: # create a new net
r[a] = r[b] = set([a, b])
# r holds the result nets, but each net is in values multiple times
# So, get the unique elements in r's values.
return dict((id(x), x) for x in r.values()).val ues()

for group in do_nets([['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'],
['e', 'k'], ['c', 'u'], ['b', 'p']]):
print group

--Scott David Daniels
Scott.Daniels@A cm.Org