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) 1110101 0010101 0100101 0111101 0110001 0110111 0110100  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 try: is_eulerian = G.eulerian_circuit() except: 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 https://trac.sagemath.org/ticket/27790 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)) True  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 G.show() 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 continue L[u] = k k += 1 for v in G.neighbor_iterator(u): if v in L: # v has already been labeled continue L[v] = k k += 1 H = G.relabel(perm=L, inplace=False) return H G = graphs.RandomGNM(10,20) H = relabeling(G) H.show()  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: 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. 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). sage: h.show(method='js',link_distance=100)  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]