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

Discussion in 'Python' started by Paul Miller, Nov 24, 2009.

  1. Paul Miller

    Paul Miller Guest

    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: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 for v in \
    partite_sets [j] ])

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

    Many thanks!
    Paul Miller, Nov 24, 2009
    #1
    1. Advertising

  2. On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
    <> 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: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 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
    geremy condra, Nov 24, 2009
    #2
    1. Advertising

  3. On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <> wrote:
    > On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
    > <> 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: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 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
    geremy condra, Nov 24, 2009
    #3
  4. On Mon, Nov 23, 2009 at 9:10 PM, geremy condra <> wrote:
    > On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <> wrote:
    >> On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
    >> <> 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: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 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
    geremy condra, Nov 24, 2009
    #4
  5. On Nov 24, 2:45 am, geremy condra <> wrote:
    > On Mon, Nov 23, 2009 at 9:10 PM, geremy condra <> wrote:
    > > On Mon, Nov 23, 2009 at 9:03 PM, geremy condra <> wrote:
    > >> On Mon, Nov 23, 2009 at 7:05 PM, Paul Miller
    > >> <> 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: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 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
    Richard Thomas, Nov 24, 2009
    #5
  6. Paul Miller

    Paul Miller Guest

    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, Nov 24, 2009
    #6
  7. 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
    Malte Helmert, Nov 24, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Morten Wennevik

    Any elegant way of doing this?

    Morten Wennevik, Nov 8, 2005, in forum: ASP .Net
    Replies:
    4
    Views:
    377
    Morten Wennevik
    Nov 8, 2005
  2. P L

    Any elegant way to do this?

    P L, Oct 17, 2003, in forum: C Programming
    Replies:
    1
    Views:
    340
    Mark A. Odell
    Oct 17, 2003
  3. Dr Ann Huxtable

    Missing Graph.h and (Graph.lib) woes - any help

    Dr Ann Huxtable, Dec 21, 2004, in forum: C Programming
    Replies:
    6
    Views:
    630
    Dr Ann Huxtable
    Dec 21, 2004
  4. Mukesh
    Replies:
    4
    Views:
    608
    Paul N
    Mar 26, 2010
  5. Emilio Mayorga
    Replies:
    6
    Views:
    319
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page