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]

(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

[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" <[e-mail]:

(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 <[e-mail]:

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]

On Oct 17, 3:20*pm, JD <[e-mail]:

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

[bearophileHUGS]

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

[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 <[e-mail]:

On Oct 17, 3:20 pm, JD <[e-mail]:

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

[JD]

Thanks,

This one really works.

JD

On Oct 17, 3:17 pm, [e-mail] 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

[Paul McGuire]

On Oct 17, 3:20*pm, JD <[e-mail]:

Hi,

I need help for a task looks very simple:

<snip>

I smell "homework assignment".

-- Paul

[Mensanator]

On Oct 17, 4:34*pm, JD <[e-mail]:

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 <[e-mail]:

On Oct 17, 3:20 pm, JD <[e-mail]:

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

[Gerard flanagan]

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

[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 <[e-mail]:

On Oct 17, 3:20 pm, JD <[e-mail]:Hi,

I need help for a task looks very simple:

<snip>

I smell "homework assignment".

-- Paul

[bearophileHUGS]

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

[Scott David Daniels]

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