469,916 Members | 2,147 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,916 developers. It's quick & easy.

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
Oct 17 '08 #1
12 1505
(Disclaimer: completely untested)

from collections import defaultdict

merged = defaultdict(list)
for key, val in your_list_of_pairs:
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 <Ji*********@gmail.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
Oct 17 '08 #2
JD
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(list)
for key, val in your_list_of_pairs:
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...@gmail.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
Oct 17 '08 #3
On Oct 17, 3:20*pm, JD <Jiandong...@gmail.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(set(i))
else:
gotit = False
for k,j in enumerate(merged):
u = j.intersection(set(i))
if len(u):
merged[k] = j.union(set(i))
gotit = True
if not gotit:
merged.append(set(i))

print merged

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

>
Thanks,

JD
Oct 17 '08 #4
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.connectedComponents()
# Output: [['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile
Oct 17 '08 #5
JD
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...@gmail.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(set(i))
else:
gotit = False
for k,j in enumerate(merged):
u = j.intersection(set(i))
if len(u):
merged[k] = j.union(set(i))
gotit = True
if not gotit:
merged.append(set(i))

print merged

##
## [set(['a', 'p', 'b', 'g']), set(['c', 'u', 'd']), set(['k', 'e',
'f'])]
##
Thanks,
JD
Oct 17 '08 #6
JD
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.connectedComponents()
# Output: [['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile
Oct 17 '08 #7
On Oct 17, 3:20*pm, JD <Jiandong...@gmail.comwrote:
Hi,

I need help for a task looks very simple:
<snip>

I smell "homework assignment".

-- Paul
Oct 17 '08 #8
On Oct 17, 4:34*pm, JD <Jiandong...@gmail.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...@gmail.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(set(i))
* * else:
* * * * gotit = False
* * * * for k,j in enumerate(merged):
* * * * * * u = j.intersection(set(i))
* * * * * * if len(u):
* * * * * * * * merged[k] = j.union(set(i))
* * * * * * * * gotit = True
* * * * if not gotit:
* * * * * * merged.append(set(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

Oct 18 '08 #9
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(outlist)):
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
Oct 18 '08 #10
JD
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.rr.comwrote:
On Oct 17, 3:20 pm, JD <Jiandong...@gmail.comwrote:Hi,
I need help for a task looks very simple:

<snip>

I smell "homework assignment".

-- Paul
Oct 18 '08 #11
JD:
Thanks,
This one really works.
Note that you can save some RAM (almost half) creating a directed
graph, because later the connectedComponents() 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(data)
g.connectedComponents()
[['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile
Oct 18 '08 #12
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()).values()

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

--Scott David Daniels
Sc***********@Acm.Org
Oct 18 '08 #13

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Luke Airig | last post: by
4 posts views Thread by Andreas Kasparek | last post: by
9 posts views Thread by anunaygupta | last post: by
7 posts views Thread by Meelis Lilbok | last post: by
7 posts views Thread by Zeba | last post: by
16 posts views Thread by Sam Durai | last post: by
1 post views Thread by vekka | last post: by
1 post views Thread by Waqarahmed | last post: by
reply views Thread by Salome Sato | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.