Mailing List Archive: Python: Python

Any elegant way to construct the complete $k$-partite graph in Python?

Index | Next | Previous | View Threaded

paul.w.miller.please.dont.spam.me at wmich

Nov 23, 2009, 4:05 PM

Post #1 of 8 (285 views)
Permalink

Any elegant way to construct the complete $k$-partite graph in Python?

I was wondering if there were any neat tools (like for instance,
something from itertools) that would help me write the following function
more elegantly. The return value should, of course, be the complete $k$-
partite graph $K_{n_1, n_2, \dots, n_k}$:

def completeGraph (*ns):
'''
Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
the sequence \code {n_1, n_2, \dots, n_k}.
'''
if len (ns) == 1:
return completeGraph ( * ([1] * ns[0]) )
n = sum (ns)
vertices = range (n)
partition_indices = [sum (ns[:i]) for i in range (len (ns))]
partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
\
for i in range (len (partition_indices) - 1)]
partite_sets.append (vertices[partition_indices [-1]:] )

edges = []
for i in range (len (partite_sets)):
for j in range (i + 1, len (partite_sets)):
edges.extend ([ (u, v) for u in partite_sets [i] for v in \
partite_sets [j] ])

return graph.Graph (vertices = vertices, edges = edges)

Many thanks!
--
http://mail.python.org/mailman/listinfo/python-list

anand.ibmgsi at gmail

Nov 23, 2009, 4:25 PM

Post #2 of 8 (272 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

I am not sure what you mean by complete $k$-
partite graph....
There is the python-graph package(http://code.google.com/p/python-graph/)
you might wanna check out.
It does return a complete graph.. may be u can tweak it??
==============================================
Anand J
http://sites.google.com/a/cbcs.ac.in/students/anand
==============================================
The man who is really serious,
with the urge to find out what truth is,
has no style at all. He lives only in what is.
~Bruce Lee

Love is a trade with no accounting policies.
~Aang Jie

On Tue, Nov 24, 2009 at 05:35, Paul Miller <
paul.w.miller.please.dont.spam.me [at] wmich> wrote:

> I was wondering if there were any neat tools (like for instance,
> something from itertools) that would help me write the following function
> more elegantly. The return value should, of course, be the complete $k$-
> partite graph $K_{n_1, n_2, \dots, n_k}$:
>
> def completeGraph (*ns):
> '''
> Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
> the sequence \code {n_1, n_2, \dots, n_k}.
> '''
> if len (ns) == 1:
> return completeGraph ( * ([1] * ns[0]) )
> n = sum (ns)
> vertices = range (n)
> partition_indices = [sum (ns[:i]) for i in range (len (ns))]
> partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
> \
> for i in range (len (partition_indices) - 1)]
> partite_sets.append (vertices[partition_indices [-1]:] )
>
> edges = []
> for i in range (len (partite_sets)):
> for j in range (i + 1, len (partite_sets)):
> edges.extend ([ (u, v) for u in partite_sets [i] for v in \
> partite_sets [j] ])
>
> return graph.Graph (vertices = vertices, edges = edges)
>
> Many thanks!
> --
> http://mail.python.org/mailman/listinfo/python-list
>

debatem1 at gmail

Nov 23, 2009, 6:03 PM

Post #3 of 8 (271 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
<paul.w.miller.please.dont.spam.me [at] wmich> wrote:
> I was wondering if there were any neat tools (like for instance,
> something from itertools) that would help me write the following function
> more elegantly. The return value should, of course, be the complete $k$-
> partite graph $K_{n_1, n_2, \dots, n_k}$:
>
> def completeGraph (*ns):
> '''
> Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
> the sequence \code {n_1, n_2, \dots, n_k}.
> '''
> if len (ns) == 1:
> return completeGraph ( * ([1] * ns[0]) )
> n = sum (ns)
> vertices = range (n)
> partition_indices = [sum (ns[:i]) for i in range (len (ns))]
> partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
> \
> for i in range (len (partition_indices) - 1)]
> partite_sets.append (vertices[partition_indices [-1]:] )
>
> edges = []
> for i in range (len (partite_sets)):
> for j in range (i + 1, len (partite_sets)):
> edges.extend ([ (u, v) for u in partite_sets [i] for v in \
> partite_sets [j] ])
>
> return graph.Graph (vertices = vertices, edges = edges)
>
> Many thanks!

Graphine does this with the following:

from base import Graph

def K(n):
"""Generates a completely connected undirected graph of size n.

The verticies are numbered [0, n).

The edges are named after the verticies they connect such that
an edge connected verticies 1 and 2 is named (1,2).
"""
# create the graph
k = Graph()
# generate all the nodes
for i in range(n):
k.add_node(i)
# generate all the edges
for i in range(n):
for j in range(i+1, n):
k.add_edge(i, j, (i,j), is_directed=False)
# return the graph
return k

Disclaimer: I'm the author of graphine.

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

debatem1 at gmail

Nov 23, 2009, 6:10 PM

Post #4 of 8 (270 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <debatem1 [at] gmail> wrote:
> On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
> <paul.w.miller.please.dont.spam.me [at] wmich> wrote:
>> I was wondering if there were any neat tools (like for instance,
>> something from itertools) that would help me write the following function
>> more elegantly. The return value should, of course, be the complete $k$-
>> partite graph $K_{n_1, n_2, \dots, n_k}$:
>>
>> def completeGraph (*ns):
>> '''
>> Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
>> the sequence \code {n_1, n_2, \dots, n_k}.
>> '''
>> if len (ns) == 1:
>> return completeGraph ( * ([1] * ns[0]) )
>> n = sum (ns)
>> vertices = range (n)
>> partition_indices = [sum (ns[:i]) for i in range (len (ns))]
>> partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
>> \
>> for i in range (len (partition_indices) - 1)]
>> partite_sets.append (vertices[partition_indices [-1]:] )
>>
>> edges = []
>> for i in range (len (partite_sets)):
>> for j in range (i + 1, len (partite_sets)):
>> edges.extend ([ (u, v) for u in partite_sets [i] for v in \
>> partite_sets [j] ])
>>
>> return graph.Graph (vertices = vertices, edges = edges)
>>
>> Many thanks!
>
> Graphine does this with the following:
>
> from base import Graph
>
> def K(n):
> """Generates a completely connected undirected graph of size n.
>
> The verticies are numbered [0, n).
>
> The edges are named after the verticies they connect such that
> an edge connected verticies 1 and 2 is named (1,2).
> """
> # create the graph
> k = Graph()
> # generate all the nodes
> for i in range(n):
> k.add_node(i)
> # generate all the edges
> for i in range(n):
> for j in range(i+1, n):
> k.add_edge(i, j, (i,j), is_directed=False)
> # return the graph
> return k
>
>
> Disclaimer: I'm the author of graphine.
>
> Geremy Condra
>

Sorry, misread- to generate a k-partite graph, you'll need a bit
more legwork. Give me a bit and I'll add it to graphine.

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

debatem1 at gmail

Nov 23, 2009, 6:45 PM

Post #5 of 8 (270 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

On Mon, Nov 23, 2009 at 9:10 PM, geremy condra <debatem1 [at] gmail> wrote:
> On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <debatem1 [at] gmail> wrote:
>> On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
>> <paul.w.miller.please.dont.spam.me [at] wmich> wrote:
>>> I was wondering if there were any neat tools (like for instance,
>>> something from itertools) that would help me write the following function
>>> more elegantly. The return value should, of course, be the complete $k$-
>>> partite graph $K_{n_1, n_2, \dots, n_k}$:
>>>
>>> def completeGraph (*ns):
>>> '''
>>> Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
>>> the sequence \code {n_1, n_2, \dots, n_k}.
>>> '''
>>> if len (ns) == 1:
>>> return completeGraph ( * ([1] * ns[0]) )
>>> n = sum (ns)
>>> vertices = range (n)
>>> partition_indices = [sum (ns[:i]) for i in range (len (ns))]
>>> partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
>>> \
>>> for i in range (len (partition_indices) - 1)]
>>> partite_sets.append (vertices[partition_indices [-1]:] )
>>>
>>> edges = []
>>> for i in range (len (partite_sets)):
>>> for j in range (i + 1, len (partite_sets)):
>>> edges.extend ([ (u, v) for u in partite_sets [i] for v in \
>>> partite_sets [j] ])
>>>
>>> return graph.Graph (vertices = vertices, edges = edges)
>>>
>>> Many thanks!
>>
>> Graphine does this with the following:
>>
>> from base import Graph
>>
>> def K(n):
>> """Generates a completely connected undirected graph of size n.
>>
>> The verticies are numbered [0, n).
>>
>> The edges are named after the verticies they connect such that
>> an edge connected verticies 1 and 2 is named (1,2).
>> """
>> # create the graph
>> k = Graph()
>> # generate all the nodes
>> for i in range(n):
>> k.add_node(i)
>> # generate all the edges
>> for i in range(n):
>> for j in range(i+1, n):
>> k.add_edge(i, j, (i,j), is_directed=False)
>> # return the graph
>> return k
>>
>>
>> Disclaimer: I'm the author of graphine.
>>
>> Geremy Condra
>>

Alright, how does this look:

def k_partite(*partition_sizes):
g = Graph()
for pos, num_nodes in enumerate(partition_sizes):
for i in range(num_nodes):
n = g.add_node(name=(pos,i), partition=pos)
for node1 in g.nodes:
for node2 in g.nodes:
if node1.partition != node2.partition:
g.add_edge(node1, node2, is_directed=False)
return g

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

chardster at gmail

Nov 23, 2009, 7:57 PM

Post #6 of 8 (269 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

On Nov 24, 2:45 am, geremy condra <debat...@gmail.com> wrote:
> On Mon, Nov 23, 2009 at 9:10 PM, geremy condra <debat...@gmail.com> wrote:
> > On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <debat...@gmail.com> wrote:
> >> On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
> >> <paul.w.miller.please.dont.spam...@wmich.edu> wrote:
> >>> I was wondering if there were any neat tools (like for instance,
> >>> something from itertools) that would help me write the following function
> >>> more elegantly. The return value should, of course, be the complete $k$-
> >>> partite graph $K_{n_1, n_2, \dots, n_k}$:
>
> >>> def completeGraph (*ns):
> >>> '''
> >>> Returns the complete graph $K_{n_1, n_2, \dots, n_k}$ when passed
> >>> the sequence \code {n_1, n_2, \dots, n_k}.
> >>> '''
> >>> if len (ns) == 1:
> >>> return completeGraph ( * ([1] * ns[0]) )
> >>> n = sum (ns)
> >>> vertices = range (n)
> >>> partition_indices = [sum (ns[:i]) for i in range (len (ns))]
> >>> partite_sets = [vertices[partition_indices[i]:partition_indices[i+1]]
> >>> \
> >>> for i in range (len (partition_indices) - 1)]
> >>> partite_sets.append (vertices[partition_indices [-1]:] )
>
> >>> edges = []
> >>> for i in range (len (partite_sets)):
> >>> for j in range (i + 1, len (partite_sets)):
> >>> edges.extend ([ (u, v) for u in partite_sets [i] for v in \
> >>> partite_sets [j] ])
>
> >>> return graph.Graph (vertices = vertices, edges = edges)
>
> >>> Many thanks!
>
> >> Graphine does this with the following:
>
> >> from base import Graph
>
> >> def K(n):
> >> """Generates a completely connected undirected graph of size n.
>
> >> The verticies are numbered [0, n).
>
> >> The edges are named after the verticies they connect such that
> >> an edge connected verticies 1 and 2 is named (1,2).
> >> """
> >> # create the graph
> >> k = Graph()
> >> # generate all the nodes
> >> for i in range(n):
> >> k.add_node(i)
> >> # generate all the edges
> >> for i in range(n):
> >> for j in range(i+1, n):
> >> k.add_edge(i, j, (i,j), is_directed=False)
> >> # return the graph
> >> return k
>
> >> Disclaimer: I'm the author of graphine.
>
> >> Geremy Condra
>
> Alright, how does this look:
>
> def k_partite(*partition_sizes):
> g = Graph()
> for pos, num_nodes in enumerate(partition_sizes):
> for i in range(num_nodes):
> n = g.add_node(name=(pos,i), partition=pos)
> for node1 in g.nodes:
> for node2 in g.nodes:
> if node1.partition != node2.partition:
> g.add_edge(node1, node2, is_directed=False)
> return g
>
> Geremy Condra

Not sure exactly how you're representing graphs, this seems like the
simplest way of listing the edges.

def complete_partite(*sizes):
total = sum(sizes)
nodes, edges = range(total), []
for group in xrange(len(sizes)):
low = sum(sizes[:group-1])
high = sum(sizes[:group])
edges.extend((i, j) for i in xrange(low, high)
for j in xrange(high, total))
return nodes, edges

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

paul.w.miller.please.dont.spam.me at wmich

Nov 23, 2009, 10:23 PM

Post #7 of 8 (268 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

On Mon, 23 Nov 2009 19:57:05 -0800, Richard Thomas wrote:

> Not sure exactly how you're representing graphs, this seems like the
> simplest way of listing the edges.
>
> def complete_partite(*sizes):
> total = sum(sizes)
> nodes, edges = range(total), []
> for group in xrange(len(sizes)):
> low = sum(sizes[:group-1])
> high = sum(sizes[:group])
> edges.extend((i, j) for i in xrange(low, high)
> for j in xrange(high, total))
> return nodes, edges

Thanks! I think this is what I was looking for (unless the collective
wisdom of c.l.py can come up with something *even more* elegant). :-)
--
http://mail.python.org/mailman/listinfo/python-list

helmert at informatik

Nov 24, 2009, 5:02 AM

Post #8 of 8 (246 views)
Permalink

Re: Any elegant way to construct the complete $k$-partite graph in Python? [In reply to]

Paul Miller wrote:
> On Mon, 23 Nov 2009 19:57:05 -0800, Richard Thomas wrote:
>
>> Not sure exactly how you're representing graphs, this seems like the
>> simplest way of listing the edges.
>>
>> def complete_partite(*sizes):
>> total = sum(sizes)
>> nodes, edges = range(total), []
>> for group in xrange(len(sizes)):
>> low = sum(sizes[:group-1])
>> high = sum(sizes[:group])

I think this has a conceptual off-by-one error. Add

print group, low, high

to see what I mean (especially the first iteration). It still works, but
I think this would be clearer:

low = sum(sizes[:group])
high = sum(sizes[:group + 1])

or to avoid doing essentially the same summation twice:

low = sum(sizes[:group])
high = low + sizes[group]

>> edges.extend((i, j) for i in xrange(low, high)
>> for j in xrange(high, total))
>> return nodes, edges

Here's a variant that uses a running total instead of recomputing the
sum in every iteration, thus getting rid of xrange(len(...)).

def complete_partite(*sizes):
total = sum(sizes)
nodes, edges = range(total), []
curr_total = 0
for size in sizes:
edges.extend((i, j) for i in xrange(curr_total, curr_total+size)
for j in xrange(curr_total+size, total))
curr_total += size
return nodes, edges

Finally, here is a variant that is a bit shorter because it produces the
edges in a different way and hence gets rid of the need for knowing the
total up front and uses total as running total instead. It has the
drawback of not generating the edges in ascending order though, so I
think the previous one is nicer:

def complete_partite(*sizes):
total, edges = 0, []
for size in sizes:
edges.extend((i, j) for i in xrange(total)
for j in xrange(total, total + size))
total += size
return range(total), edges

Finally, here's a variation on the same theme:

def complete_partite(*sizes):
nodes, edges = [], []
for size in sizes:
partition = xrange(len(nodes), len(nodes) + size)
edges.extend((i, j) for i in nodes for j in partition)
nodes.extend(partition)
return nodes, edges

Malte

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

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads