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] ])
<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] ])
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
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] ])
> 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.
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] ])
>> 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
> 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] ])
> >> 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
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). :-)
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
|
