Ask Your Question

David Coudert's profile - activity

2019-10-16 02:36:10 -0500 answered a question inverse binary string bit by bit

You can also use Bitset.

sage: B = Bitset('0110101')
sage: C = Bitset('0' * B.capacity())
sage: for i in range(B.capacity()):
....:     C.add(i)
....:     print(B.symmetric_difference(C))
....:     C.discard(i)
2019-10-14 01:51:51 -0500 commented answer Sage stalls during computation

are you sure feedback_edge_set uses GLPK by default even after installing cbc? to check, set verbose=1, the displayed information are different from a solver to another.

2019-10-05 10:41:27 -0500 commented question DiGraph, Latex, and same orientation

Have you tried latex(H0) ? For 2), you can simply set the position of vertices using H0.set_pos(...) instead of relying on the layout.

2019-08-30 01:37:38 -0500 commented answer StopIteration raised during G.eulerian_circuit()

if you still get the error, can you modify your code (the line if G.eulerian_circuit() is False:) with something like

    is_eulerian = G.eulerian_circuit()
    raise ValueError(G.edges())
if not is_eulerian:

and post the output so we can do tests on that specific graph. If it has too many edges, you can post instead G.graph6_string().

2019-08-05 06:58:03 -0500 commented answer caterpillar graphs in sage

Most of the methods are well documented, so please check the documentation of the Random Lobsters generator.

The parameters of graphs.RandomLobster(n, p, q) are the number of nodes n of the generated graph, the probability p of attaching a pending edge to the main path and the probability q of attaching an edge to an edge of previous level. Setting q=0 ensure that you get a Random Caterpillar.

Of course it's random, so two successive calls give different results.

Otherwise, use the method proposed by tmonteil

2019-08-05 02:54:00 -0500 answered a question caterpillar graphs in sage

You can use G = graphs.RandomLobster(20, .5, 0).

2019-07-14 15:29:42 -0500 commented question Boost implementation of Dijkstra's algorithm

If you are looking for the fastest code ever, then for sure go for C/C++ (boost, the backend of networkit, igraph, etc.) or some optimized Java libraries (webgraph,...).

But if you want a flexible graph library that can be used by many users with different expectations, that can handle various types of graphs (with loops, multiple edges, weights, etc.), that accepts vertices of any hashable type, etc., and that provides hundreds of algorithms... then Sagemath is a good candidate.

2019-07-14 07:51:43 -0500 commented question Boost implementation of Dijkstra's algorithm

Most of the time is lost in converting the graph from one format to another and checking the input. This is the price to pay for offering users a very generic tool: (im)mutable (di)graphs, various types of vertex/edge labels, etc. Significant speed up improvements can certainly be achieved in these tests and in the graph backend itself. Feel free to contribute if you have a proposal for improvement, help is more than welcome.

2019-07-13 23:27:30 -0500 commented question Boost implementation of Dijkstra's algorithm

The running difference in your experiment between Sage and Boost is the time to check if all weights are positive or not. When the algorithm is specified we don't do that test, and it's faster.

Sage graphs are written in Cython, but we must convert the format to boost graph before calling Dijkstra of boost (same for igraph, and also for BFS, etc.). This has a cost. We could try to speed up this conversion.

2019-07-13 16:04:45 -0500 received badge  Commentator
2019-07-13 16:04:45 -0500 commented question Boost implementation of Dijkstra's algorithm

Do the following test: write a pure Python method that takes as input a Sage Graph (or a networkx graph) and a source node. This method will then build adj and run dijkstra_int. For instance:

def dijsktra_int_complete(Gnx, src):
    wedges = [(u, v, label['weight']) for u, v, label in Gnx.edges(data=True)]
    return dijkstra_int(Gnx.nodes(), wedges, -1, src)

On my computer the longest operation is to build list wedges from the networkx graph. It takes roughly twice the time of the call to dijkstra_int. But you don't include that time in your measurement... That's why it's unfair.

2019-07-13 10:13:09 -0500 commented question Boost implementation of Dijkstra's algorithm

The reported experiment is unfair: the methods don't take the same parameters as input. To be fair, both methods should take as input a Sage Graph. If you count the time to build wedges from a Sage Graph, you will get very different results.

You can also use graphs.RandomGNP(n, p) to generate your random graph.

2019-06-09 09:13:57 -0500 received badge  Necromancer (source)
2019-06-09 07:42:35 -0500 received badge  Nice Answer (source)
2019-05-22 04:50:34 -0500 answered a question using cplex as a solver in sage - import error undefined symbol: CPXsetlogfile

CPXsetlogfile has been deprecated in cplex 12.8 and removed from cplex 12.9.

See ticket

2019-04-03 02:37:52 -0500 answered a question Bicyclic Graphs having highest second smallest laplacian eigen value from a collection

instead of graph(8), use graphs.nauty_geng("8 -c") to get only connected graphs.

2019-03-13 03:44:59 -0500 answered a question Number of neighbors of a set of vertices in a graph

You want the vertex boundary of a set of vertices.

sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.CycleGraph(4)
sage: t = polygen(ZZ, 't')
sage: sum(t^len(G.vertex_boundary(x)) for x in IndependentSets(G))
6*t^2 + 1
2019-03-13 03:31:22 -0500 answered a question Generating plane triangulations

plantri is an optional package that you can install using

sage -i plantri

You will then be able to use the iterator over connected planar triangulations

sage: list(graphs.triangulations(6))
[Graph on 6 vertices, Graph on 6 vertices]
sage: all(g.is_planar() for g in graphs.triangulations(10))
2018-11-27 08:16:48 -0500 received badge  Good Answer (source)
2018-11-27 08:16:48 -0500 received badge  Nice Answer (source)
2018-09-27 04:10:05 -0500 commented answer Why does this error arise?

See for instance This stackoverflow discussion for understanding the use and meaning of _. Here I used it to mean that we don't care of that value.

Concerning your code, you remove vertices of the graph in the while loop. In the end, the graph is empty, and so has nothing to display.

2018-09-25 06:26:21 -0500 answered a question Why does this error arise?

Consider the following code. It follows the description of your relabeling method (I'm not sure of what you really want to get). I can display the relabeled graph.

def relabeling(G):
    deg = sorted([(d,u) for u,d in G.degree_iterator(labels=True)], key=lambda x: x[0], reverse=True)
    L = dict()
    k = 0
    for _,u in deg:
        if u in L:
            # The vertex has already been labeled
        L[u] = k
        k += 1
        for v in G.neighbor_iterator(u):
            if v in L:
                # v has already been labeled
            L[v] = k
            k += 1
    H = G.relabel(perm=L, inplace=False)
    return H

G = graphs.RandomGNM(10,20)
H = relabeling(G)
2018-09-24 11:47:00 -0500 commented question Why does this error arise?

You remove vertices from the list v, but not from the graph. So you may later add a vertex j to the list s that has already been removed from v.

2018-09-05 10:48:02 -0500 answered a question How to find the spanning elementary subgraphs of a given graph

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

2018-08-28 04:51:34 -0500 commented question Why can't I find the spectral radius of a tree?

There is a bug in this method for trees. Thank you for reporting the issue. This is now ticket #26148.

2018-04-15 11:55:14 -0500 received badge  Supporter (source)
2018-03-18 05:21:32 -0500 answered a question Graph structure having maximum algebraic connectivity among some given blocks

You have two approaches to solve this exercise:

  1. Using Sagemath: generate all blocks (=biconnected graphs) of order k=3..n using graphs.nauty_geng("k -C"), then for each combination of 4 of them build a block graph with the required structure, compute its algebraic connectivity and record the maximum value.
  2. Using a sheet of paper: read carefully the definition of algebraic connectivity to understand what maximizes this value (hint: check the lower bounds), deduce the biconnected graph with maximum algebraic connectivity, use it to build the block graph you need, and finally prove that this graph answers your question (short proof). You can afterward use Sagemath to compute its algebraic connectivity.
2018-03-04 06:05:25 -0500 commented question Getting all non-backtracking walks of certain length in isogeny graph

Could you please define "non-backtracking walk".

2018-02-09 06:28:54 -0500 commented question To find trees having certain properties from a collection of trees on given number of vertices

This is good class exercise to learn how to manipulate graphs with SageMath and NetworkX.

2017-11-07 06:52:13 -0500 received badge  Nice Answer (source)
2017-10-15 09:07:22 -0500 commented question Edge color for undirected multiedge graphs

This is now ticket #24051

2017-09-21 03:39:42 -0500 received badge  Enthusiast
2017-09-16 13:51:52 -0500 received badge  Nice Answer (source)
2017-09-15 00:46:19 -0500 answered a question Line graph of a given graph

The vertices of the line_graph are the edges of the graph, including edge labels by default. If you don't want the labels, you can do:

sage: G = Graph([(2,3),(2,4),(2,1),(1,5),(5,6),(1,0),(0,12),(0,13),(14,0),(15,0),(7,0),(7,10),(11,7),(7,9),(7,8)])
sage: h = G.line_graph(labels=False)

Then you can either use the method that has already been proposed here, or use the Javascript plotting (it's better to increase the link distance).

2017-09-01 03:30:38 -0500 commented question plot graphs with graph in vertices

Ticket 21918 could help...

2017-08-21 19:56:47 -0500 received badge  Enlightened (source)
2017-08-21 19:56:47 -0500 received badge  Good Answer (source)
2017-08-21 11:40:53 -0500 received badge  Nice Answer (source)
2017-08-21 11:08:35 -0500 answered a question Changing the weights in a graph

You can use the set_edge_label

sage: G = graphs.PetersenGraph()
sage: print G.edges()
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None), (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]
sage: i = 0
sage: for u,v in G.edges(labels=0):
....:     G.set_edge_label(u, v, i)
....:     i += 1
sage: print G.edges()
[(0, 1, 0), (0, 4, 1), (0, 5, 2), (1, 2, 3), (1, 6, 4), (2, 3, 5), (2, 7, 6), (3, 4, 7), (3, 8, 8), (4, 9, 9), (5, 7, 10), (5, 8, 11), (6, 8, 12), (6, 9, 13), (7, 9, 14)]
2017-05-22 02:09:25 -0500 commented question Why is Sage calling 1 a variable?

The error message is local variable 'l' referenced before assignment. It's variable l (small cap L), not 1. I have reported the issue on sage-dev.

2017-05-19 07:40:07 -0500 answered a question Iterate over acyclic subdigraphs

This is certainly not an easy question and I have no better algorithm in mind.

I recommend to use Permutations(D.vertices()) instead. This is safer for instance if you remove vertex 0.

Furthermore, with your code you may generate multiple times the same acyclic orientation.

sage: D = DiGraph(graphs.PathGraph(3))
sage: print D.edges(labels=0)
[(0, 1), (1, 0), (1, 2), (2, 1)]
sage: for p in Permutations(D.vertices()):
....:     A = DiGraph([(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]])
....:     print A.edges(labels=0)
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 1), (1, 2)]

One solution is to keep track of previous sets of edges, but this is certainly not scalable. I'm using type Set since it is hashable.

sage: D = DiGraph(graphs.PathGraph(3))
sage: orientations = set()
sage: for p in Permutations(D.vertices()):
....:     E = [(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]]
....:     SE = Set(E)
....:     if SE in orientations:
....:         continue
....:     orientations.add(SE)
....:     A = DiGraph(E)
....:     print A.edges(labels=0)
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]

For the example you gave, your code generates 5040 graphs while my code generates only 4055 graphs.

2017-04-29 05:05:41 -0500 commented answer Random block graph

The first proposed method starts building a random tree with m edges and then replaces each edge with a k-clique. It is effectively not sufficient to get all possible random block graphs. I have added a new version that starts with a random tree with m vertices, replaces each vertex by a k-clique and then connect blocks corresponding to tree edges. This way we can get all possible random block graphs.

2017-04-29 05:00:36 -0500 edited answer Random block graph

Recall that a block graph is a graph in which every biconnected component is a clique.

A simple method to generate a connected block graph with m blocks of size k is to start from a random tree with m edges and then replace each edge by a clique of order k:

def RandomBlockGraph(m, k):
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        G.add_clique([u,v] + [G.add_vertex() for i in range(k-2)])
    return G

The add_clique method is a recent addition to sagemath. If you don't have it, you can do

def RandomBlockGraph(m, k):
    import itertools
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        V = [u,v] + [G.add_vertex() for i in range(k-2)]
        for x,y in itertools.combinations(V, 2):
            G.add_edge(x, y)
    return G

A call to G.add_vertex() adds an isolated vertex to the graph. You then add the edges of the clique.

EDIT: The method below starts with a random tree of order m. Then it creates a graph with one k-clique (block) per vertex of the tree. We connect blocks corresponding to end vertices of tree edges. To do so, we select one vertex per block and merge the two selected vertices. We use a disjoint set data structure to keep track of the merge operations and so get a unique identifier per set of merged vertices.

def RandomBlockGraph(m, k):
    import itertools
    import random

    # We start with a random tree of order m
    T = graphs.RandomTree(m)

    # We create a block of size k per vertex of the tree
    B = {u:[(u,i) for i in range(k)] for u in T}

    # For each edge of the tree, we choose 1 vertex in each of the corresponding
    # blocks and we merge them. We use a disjoint set data structure to keep a
    # unique identifier per merged vertices
    DS = DisjointSet([i for u in B for i in B[u]])
    for u,v in T.edges(labels=0):
        DS.union(random.choice(B[u]), random.choice(B[v]))

    # We finally build the block graph
    BG = Graph()
    for u in B:
        for x,y in itertools.combinations(B[u], 2):
            BG.add_edge(DS.find(x), DS.find(y))

    return BG