tassio's profile - activity

Indeed, I apologize. I was experimenting with this function as of last night. Thanks! (I guess one mistake was only looking in the documentations for graph functions, hoping to find something in the methods for chromatic number calculation & related things.)

(Definition: for a set $S$, and a partition $P=\{P_1,P_2,\ldots,P_k\}$ of $S$, we say that the length of $P$ is $k$.)

I want to iterate over all partitions of $S$ whose length is $k$.

Motivation: I am testing a property for graphs which satisfy a certain coloring-property (which is not standard coloring). So I need to check, in turn, whether a partition in $1,2,\ldots,p$ parts will satisfy the restriction for this particular type of coloring, before I can proceed to the test I want to make.

If it helps, for traditional (proper) graph coloring there is an iterator that does precisely the type of thing I am looking for; it is called all_graph_colorings.

I have a graph D, and would like to iterate over its (maximal) acyclic subdigraphs (not necessarily induced).

My current best bet is to iterate over all permutations of the vertex set of D and, for each one, create an acyclic digraph A by going through each edge of D in turn and adding to A only those edges ij where i is less than j in the current permutation.

But this seems awfully inefficient.

More precisely:

D = DiGraph()
D.add_edges([[0,1],[0,2],[1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6],[5,0],[6,0]])
n = D.num_verts()

for p in Permutations(n):
    A = DiGraph()
    for e in D.edges():
        if p[e[0]] < p[e[1]]:
            A.add_edge(p[e[0]] -1,p[e[1]] -1)

    # Here A is a maximal acyclic subdigraph of D
    do_stuff(A)

Any ideas would be greatly appreciated.