Ask Your Question

tassio's profile - activity

2020-03-29 14:38:25 +0200 commented answer Iterate over Set partitions of given length

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

2020-03-28 22:22:19 +0200 asked a question Iterate over Set partitions of given length

(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.

2020-03-28 22:00:27 +0200 received badge  Popular Question (source)
2019-04-17 19:37:41 +0200 received badge  Scholar (source)
2017-05-17 18:11:24 +0200 asked a question Iterate over acyclic subdigraphs

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()
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

Any ideas would be greatly appreciated.