ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 26 Jul 2024 11:05:57 +0200Memory leak in is_planarhttps://ask.sagemath.org/question/78467/memory-leak-in-is_planar/I have been working with planar graphs using SageMath 10.3 in a Jupyter notebook on an M3 MacBook Pro.
My kernel kept crashing and restarting and when I searched for the reason, I discovered that the process was consuming all the RAM on my machine and eventually being killed.
I used command line `top -o mem` to watch the process consuming more and more memory until it was killed.
Here is a MWE illustrating the problem.
count = 0
for g in graphs.nauty_geng('-C 10'):
if g.is_planar():
count = count+1
print(count)
I have also tested this on the SageMath command line interface just in case it was some complication with Jupyter.
I first verified that the `nauty_geng` process was *not* consuming memory and then added various commands `is_antipodal`, `is_hamiltonian` etc just to be sure that it was only `is_planar` that was at fault.
What should I do (a) in the short term to work around it, and (b) in the long term to report the bug and get it fixed?
**EDIT** I reinstalled SageMath10.2 and the memory leak persisted, but when I reinstalled SageMath10.1 it no longer manifested. So I guess that I have answered my own short-term solution.GordonFri, 26 Jul 2024 11:05:57 +0200https://ask.sagemath.org/question/78467/How to find a longest cycle and a longest induced cycle in a graph?https://ask.sagemath.org/question/75124/how-to-find-a-longest-cycle-and-a-longest-induced-cycle-in-a-graph/Sage has `longest_path`. Do we have a command to find a longest cycle for a given graph? And an induced cycle is a cycle that is an induced subgraph of $G$; induced cycles are also called chordless cycles. Then do we have a function to find the longest induced cycle?lichengMon, 25 Dec 2023 14:59:10 +0100https://ask.sagemath.org/question/75124/Find all cycles in an undirected graphhttps://ask.sagemath.org/question/69318/find-all-cycles-in-an-undirected-graph/For **directed** graphs, we have a built-in command `all_simple_cycles` to search for specific length cycles or all cycles. However, it is indeed strange that there is no readily available command for undirected graphs. Although, we can convert an undirected graph into a directed graph by assigning two directions to each edge. For example:
g = graphs.CompleteGraph(4).to_directed();
all_cycles=g.all_simple_cycles()
print(all_cycles)
`[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2], [0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 2, 3, 1], [1, 3, 2, 1]]`
allcycles = []
for array in all_dcycles:
if len(array)>=4:
reversed_array = array[::-1]
if reversed_array not in allcycles:
allcycles.append(array)
print(allcycles)
`[[0, 2, 1, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 3, 2, 1], [0, 3, 2, 1, 0], [0, 2, 3, 1, 0], [0, 3, 1, 2, 0]]`
Reversing lists and eliminating all 2-cycles seems tedious. Does SageMath provide a direct command for undirected graphs to find all cycles or cycles of a specific length? It's somewhat similar to Mathematica's `FindCycle` (`FindCycle[CompleteGraph[4], Infinity, All]`).lichengWed, 21 Jun 2023 10:21:09 +0200https://ask.sagemath.org/question/69318/Graph sorting problemhttps://ask.sagemath.org/question/69146/graph-sorting-problem/If I do this in SageMath10.0:
G = Graph()
G.add_vertex('a')
G.add_vertex(1)
print(G.vertices())
I get a deprecation warning but also this error:
File ~/sage/sage-10.0/src/sage/graphs/generic_graph.py:11370, in GenericGraph.vertices(self, sort, key, degree, vertex_property)
11367 raise ValueError('sort keyword is False, yet a key function is given')
11369 if sort:
> 11370 return sorted(self.vertex_iterator(degree=degree, vertex_property=vertex_property), key=key)
11371 return list(self.vertex_iterator(degree=degree, vertex_property=vertex_property))
TypeError: '<' not supported between instances of 'int' and 'str'
According to the documentation, the name of a vertex should be immutable,
so an integer and a string should be fine. Is it a bug or am I doing something wrong?JosefTue, 13 Jun 2023 22:02:07 +0200https://ask.sagemath.org/question/69146/How can I compute the minimal fixing set?https://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automorphism in Aut(G) contains at least one of the nodes in a set S?
For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary.ASHTue, 21 Aug 2018 13:01:42 +0200https://ask.sagemath.org/question/43433/Isomorphism of planar graphshttps://ask.sagemath.org/question/64617/isomorphism-of-planar-graphs/Is there a way to check if two planar graphs (so plane graphs embedded in the 2-sphere) are isomorphic **as planar graphs**? The standard is_isomorphic() function does not care about planarity. Since one of the two graphs is obtained by another planar graph after some edge deletions, the get_embedding() does not appear to work!
Thanks!springfieldgionWed, 26 Oct 2022 08:45:39 +0200https://ask.sagemath.org/question/64617/The function crossing_number runs too slowly?https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/In graph theory, the crossing number *cr(G)* of a graph *G* is the lowest number of edge crossings of a plane drawing of the graph *G*. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them.
The *exact* and **non-heuristic** programs that I know of are the following:
- sagemath
- web crossing number (http://crossings.uos.de/) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.
- [OGDF](https://ogdf.uos.de/) (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)
I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.
- [cross number of the Grötzsch graph](https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph)
Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.
G = graphs.GrotzschGraph()
G.crossing_number()
It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?lichengWed, 31 Aug 2022 03:28:51 +0200https://ask.sagemath.org/question/63863/Effective resistance matrix and nonedgesonly=Truehttps://ask.sagemath.org/question/63701/effective-resistance-matrix-and-nonedgesonlytrue/ For undirected graphs, there is a method effective_resistance_matrix() which returns the matrix whose (i,j) entry is the effective resistance between vertices i and j. The current implementation has an optional boolean parameter nonedgesonly=True, whose default behavior has the effect that if (i,j) are adjacent then the corresponding matrix entry is 0.
I was wondering, what was the reason behind the choice of default value for this nonedgesonly parameter? I haven't come across cases myself where this feels natural, and there are some nice theorems regarding the effective resistance matrix with nonedgesonly=False.Harry RichmanFri, 19 Aug 2022 23:39:17 +0200https://ask.sagemath.org/question/63701/Question about displaying graphhttps://ask.sagemath.org/question/56551/question-about-displaying-graph/I need to show comments which explain the colors used in a graph.
As the display parameters are set up inside the show command
I wonder if there is a way to use such a command as graphic array.
And is it possible to display two graphs side by side?CyrilleThu, 08 Apr 2021 11:24:17 +0200https://ask.sagemath.org/question/56551/Find 25-vertex 4-regular planar graphs using plantrihttps://ask.sagemath.org/question/56405/find-25-vertex-4-regular-planar-graphs-using-plantri/I am using SageMath 9.2 and I have recently wanted to add the optional package **plantri**.
I found a link to a similar question before:
[Ask Sage question 52358](https://ask.sagemath.org/question/52358)
where a comment suggests this command:
sage: !sage -i plantri
An error occurred during the installation process that prevented it from proceeding.
make[3345]: Entering directory '/opt/sagemath-9.2'
0 [main] make (45584) C:\Users\asus\AppData\Local\SageMath 9.2\runtime\bin
\make.exe: *** fatal error in forked process - ccalloc would have returned NULL
0 [main] make 15063 dofork: child -1 - forked process 45584 died unexpect
dly, retry 0, exit code 0xC0000142, errno 11
make[3345]: *** [Makefile:31: bootstrap] Error 127
My computer runs the Windows10 64-bit operating system.
I don't know how to solve this installation problem.
In fact, the graph theory problem I encountered is as follows.
I 'd like to generate all **25-vertex 4 regular planar graphs that size of maximum face is 4**.
Of course it may not exist.
With the help of plantri, I think there should be no problem,
because I saw [James Preen's page on the degree-diameter problem](http://faculty.capebretonu.ca/jpreen/degdiam.html),
which contains the following paragraph.
> Additionally, using plantri it has been established that there exist
> **no 4-regular planar graphs with 28** vertices and similarly
> there are no 3-regular planar graphs with diameter 4 with
> between 20 and 30 vertices.
If someone has successfully installed it, can you help me see if there is such a graph?
Thanks in advance！
sage: for G in graphs.planar_graphs(25, minimum_degree=4):
....: if G.num_edges==50:
sage: show(G)
sage: print("nofind")
The above codes may need improvement.lichengSat, 27 Mar 2021 03:55:43 +0100https://ask.sagemath.org/question/56405/Generate certain number of planar graphs with graphs.planar_graphs?https://ask.sagemath.org/question/56313/generate-certain-number-of-planar-graphs-with-graphsplanar_graphs/I want to use `graphs.planar_graphs` (which is based on plantri)
to generate 1000 planar graphs of a certain size (e.g. 50 vertices),
i.e. I want to use the iterator exactly 1000 times and not until
it has created all possible solutions.
How can I do this with `graphs.planar_graphs`, since this is
an iterator that just creates **all** possible planar graphs
on 50 vertices (which is a lot more than I need and also
too computationally expensive)?lucvMon, 22 Mar 2021 15:43:12 +0100https://ask.sagemath.org/question/56313/How to have commentaries to a graphhttps://ask.sagemath.org/question/56246/how-to-have-commentaries-to-a-graph/ Two question for one
1) It seems that the thikness parameter has no effect on the following graph
g2={0:[1,3,4,5,6],1:[2,3,4,5,6],2:[0,4,5,6],3:[2,4,5,6],4:[5,6],5:[],6:[5]}
H2=DiGraph(g2)
H2.relabel({0:'A' , 1:'B', 2:'C', 3:'D', 4:'E', 5:'F', 6:'G'})
vene_red="#DC0005"
pink="#FFB6C1"
dark_turquoise="#00CED1"
mon_vert="#008000"
vieux_rose="#D8BFD8"
re1=H2.show(edge_thickness=0.1,layout="circular",vertex_colors={pink: ['G','F','E'],vene_red: ['A','B','C','D']},
edge_colors={dark_turquoise:[('A','E',None),('A','F',None),('A','G',None),('B','E',None),('B','F',None),('B','G',None),
('C','E',None),('C','F',None),('C','G',None),('D','E',None),('D','F',None),('D','G',None)],
vieux_rose:[('E','G',None),('E','F',None),('G','F',None)],
mon_vert:[('A','B',None),('A','D',None),('B','C',None),('B','D',None),
('C','A',None),('D','C',None)]})
2) In this graph colors have meaning. Is it possible to add some commentaries in the graph. I was expecting doing this by `graphics_array()` but it seems not to work. I think the problem comes from the options.
CyrilleFri, 19 Mar 2021 09:35:03 +0100https://ask.sagemath.org/question/56246/How to check if a graph has a given subgraph?https://ask.sagemath.org/question/56142/how-to-check-if-a-graph-has-a-given-subgraph/Consider the Petersen graph `G`.
I want to check if `G` has a given graph `H` as an induced subgraph or not.
Is it possible to check this? I am new to SageMath.
I wrote this:
G = graphs.PetersenGraph()
H = Graph({1: [2, 3, 4]})
How to check if `H` is an induced subgraph of `G` or not?CaptchaFri, 12 Mar 2021 16:10:53 +0100https://ask.sagemath.org/question/56142/Graph automorphism group and its source codehttps://ask.sagemath.org/question/55801/graph-automorphism-group-and-its-source-code/ I am looking for the source code of graph automorphism_group function. In GitHub, there are different automorphism group functions, so I am kind of lost because there are also NAUTY functions or bliss.
I am curious about how SAGE graph automorphism group function works. I assume that an automorphism group of a graph is constructed based on row entries. If we have adjacency matrix of a graph, starting with initial partition, the partition is refined for each row until the discrete partition is reached. These partitions are used for the construction of coset representatives (or transversals) for each row. The multiplication of these representatives returns us the automorphism group of the graph.
Can someone inform me about SAGE's graph automorphism group method and its source code ?
MehmetAzizYirikSun, 21 Feb 2021 19:38:15 +0100https://ask.sagemath.org/question/55801/Mapping isomorphism for posets or graphshttps://ask.sagemath.org/question/55675/mapping-isomorphism-for-posets-or-graphs/I know that we can check if two posets/graphs are isomorphic using is_isomorphic(), but is there any way that I can get Sage to output a possible mapping between the two posets/graphs that are isomorphic?sunflowerThu, 11 Feb 2021 18:59:45 +0100https://ask.sagemath.org/question/55675/Edge isoperimetric numberhttps://ask.sagemath.org/question/52410/edge-isoperimetric-number/This is probably a very silly question. How does one get the edge isoperimetric number of a graph?
As seen under [here](https://trac.sagemath.org/ticket/21942) there should be an algorithm for it, but when I define a graph (say H), then
<code>
edge_isoperimetric_number(H)
</code>
returns "name 'edge_isoperimetric_number' is not defined"
and
<code>
H.edge_isoperimetric_number()
</code>
returns "'Graph' object has no attribute 'edge_isoperimetric_number'"
(while
<code>
edge_isoperimetric_number?
</code>
returns "Object `edge_isoperimetric_number` not found."
So how do I load said algorithm for use?ARGFri, 10 Jul 2020 22:04:04 +0200https://ask.sagemath.org/question/52410/Changing display labels of nodes on a graphhttps://ask.sagemath.org/question/50764/changing-display-labels-of-nodes-on-a-graph/ Hi,
I have created a graph which is in fact a tree. Each node has a label that I gave at creation time. Now, when I plot the graph for each node this "internal" label is displayed. Is it possible to have different display labels than this "internal" label?
ThanksoldaniWed, 15 Apr 2020 09:33:36 +0200https://ask.sagemath.org/question/50764/How to use an image as a vertex label in a graph?https://ask.sagemath.org/question/48537/how-to-use-an-image-as-a-vertex-label-in-a-graph/Exactly what the title says. I have a graph, but I'd like to change the labels of the vertices so that I can display my own images at each vertex.
I figured something like the code below would work, but instead of showing the images at the vertices, I see a string of where the image is located in memory.
from PIL import Image
H = Graph({img0:[1], 1:[2], 2:[3]})
img0 = Image.open('image0.png')
img1 = Image.open('image1.png')
img2 = Image.open('image2.png')
img3 = Image.open('image3.png')
img_list = [img0 ,img1, img2, img3]
def my_label_function (vertex_number):
return img_list[vertex_number]
H.relabel(my_label_function)
H.plot()SultanTue, 29 Oct 2019 02:18:17 +0100https://ask.sagemath.org/question/48537/enter specific graphhttps://ask.sagemath.org/question/48541/enter-specific-graph/ Probably a very dumb question but I couldn't find the answer online...
How do I enter a specific graph in sage? I want to say how many vertices I have and then add the edges (0,2) for an edge that goes from vertice 0 to vertice 2.
For instance I only found specific graphs (full graphs, path graphs etc)keelamaTue, 29 Oct 2019 08:34:53 +0100https://ask.sagemath.org/question/48541/Changing the text in a vertex of a graphhttps://ask.sagemath.org/question/48517/changing-the-text-in-a-vertex-of-a-graph/This is a graph
T = Graph()
E = [(0, 1), (1, 2), (1, 3),(2, 3), (2, 4)]
T.add_edges(E)
T.set_embedding({0:[1],1:[0,3,2],2:[1,3,4],3:[1,2],4:[2]})
T.show()
I would like to know if it is possible to replace the name of the node by a text a photo ... Also how to label vertices ?CyrilleSun, 27 Oct 2019 09:12:17 +0100https://ask.sagemath.org/question/48517/How to draw the following graph in sagemath?https://ask.sagemath.org/question/48245/how-to-draw-the-following-graph-in-sagemath/ How to draw the following graph in sagemath?
I am uploading the image here:
https://imgur.com/Q3sUXn8
I know how to draw a graph but I am finding it difficult to draw the graph in exactly the same way as shown in the picture.
Is it possible to do this?
I will be very grateful if someone could kindly help me outCaptchaWed, 09 Oct 2019 14:27:58 +0200https://ask.sagemath.org/question/48245/Memory leak with matroid is_connected methodhttps://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/Hello.
I've been using Graphic Matroids to deal with some enumeration problems, where I filter a list of graphs based on their flats. Even without really undestanding what happens at low level, I could verify that the computation is faster when I build the equivalent representation of each graphic matroid using the Incidence matrix of the graph over GF(2).
One big issue that I am facing is that some memory leak is ocurring. As the size of my list of graphs grows, the ram memory got consumed until a point that my computer breaks down and restarts. My way out has been to use a bash script to keep calling the main program until I reach the end of an external text file (the input).
To force the `gc.collect()` seems to not be an option, because the program becomes really slow.
EDIT 1:
The memory leak seems to be related with the `is_connected` method. Here is a piece of my code showing two different situations:
With the use of `is_connected`:
sage: G = [g for g in graphs.nauty_geng("12 16:16 -Ct")]
sage: len(G)
11771
sage: print(get_memory_usage())
....:
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: if M.is_connected():
....: pass
....: print(get_memory_usage())
....:
3396.38671875
3418.06640625
and without:
sage: print(get_memory_usage())
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: for r in range(M.corank()):
....: for F in M.coflats(r):
....: pass
....:
....: print(get_memory_usage())
....:
3490.53515625
3490.53515625
EDIT 2:
Ok, I solved my problem by just explicitly declaring the function `is_connected` in the body of my code, instead of using the method present in the abstract matroid class. I'm not sure about why it really worked, I tried this approach because I thought it had something to do with the lists that are created by the `components` method, however I stopped investigating when I notice the memory leak vanished just by using the function. To be honest, I changed the script to not return any output (there was an option to input a certificate flag and return the components).
I'm letting the code below for the case someone faces a similar problem or has any better solution or clue about why it happened:
cpdef components(self):
B = self.basis()
components = [frozenset([e]) for e in self.groundset()]
for e in self.groundset() - B:
C = self.circuit(B | set([e]))
components2 = []
for comp in components:
if len(C & comp) != 0:
C = C | comp
else:
components2.append(comp)
components2.append(C)
components = components2
return components
cpdef is_connected(self):
comp = components(self)
if len(comp) == 1:
return True
else:
return FalsefmorlinThu, 12 Sep 2019 11:20:58 +0200https://ask.sagemath.org/question/47839/graphs of order nhttps://ask.sagemath.org/question/47359/graphs-of-order-n/ How to generate all the graphs of particular order $n$ in sage?
is it possible to do the same up to isomorphism at least for small $n$?
Thank you.GA316Sat, 03 Aug 2019 15:13:02 +0200https://ask.sagemath.org/question/47359/Sage graph backendhttps://ask.sagemath.org/question/47191/sage-graph-backend/A Sage graph `G` has a backend graph (say `GG`) accessible with the private `_backend` attribute. The later graph refers to two "C-graphs" (say `G1` and `G2`) accessibles via the `c-graph` attribute.
Some code with a weighted graph `G` to illustrate my question :
import string
ALPHA = string.ascii_uppercase
n = 10
wedges = [(0, 1, 7.0), (0, 3, 1.0), (0, 9, 9.0), (1, 7, 6.0), (2, 8, 7.0),
(2, 9, 2.0), (3, 6, 7.0), (4, 9, 5.0), (5, 9, 6.0), (6, 9, 9.0),
(6, 7, 1.0), (7, 8, 9.0), (7, 9, 5.0), (8, 9, 3.0)]
wedges = [(ALPHA[i], ALPHA[j], 10 * w) for (i, j, w) in wedges]
G = Graph()
G.add_edges(wedges)
G.weighted(True)
for v in G:
print v, ''.join(G[v])
print
print "G type:", type(G)
print "-----------------------------"
GG = G._backend
print "GG type:", type(GG)
print list(GG.iterator_verts())
print "-----------------------------"
G1, G2 = GG.c_graph()
print "G1 type:", type(G1)
print
for i in range(n):
print i, ''.join(map(str, G1.out_neighbors(i)))
outputting:
A BDJ
C JI
B AH
E J
D AG
G DJH
F J
I JHC
H BJIG
J AHCIGEF
G type: <class 'sage.graphs.graph.Graph'>
-----------------------------
GG type: <type 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
['A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'J']
-----------------------------
G1 type: <type 'sage.graphs.base.sparse_graph.SparseGraph'>
0 123
1 04
2 07
3 0456789
4 1367
5 36
6 345
7 234
8 3
9 3
The graphs above `G`, `GG` and `G1` have `n=10` vertices. The difference is that G1's vertices are labelled from 0 to `n-1`. As you can imagine, the two graph `G` and `G1` are isomorphic.
So my question is simple: does anybody know how to access the mapping between the vertice sets?
The documentation explains that two dictionaries `vertex_ints` and `vertex_labels` are available to make translation from vertices id to integers and vice-versa, unfortunately, `GG.vertex_ints` and `GG.vertex_labels` cause an attribute error.
As you may see, and contrary to what I was expecting, the correpondance is not $i\mapsto G[i]$.elasticaTue, 16 Jul 2019 21:53:34 +0200https://ask.sagemath.org/question/47191/Boost implementation of Dijkstra's algorithmhttps://ask.sagemath.org/question/47138/boost-implementation-of-dijkstras-algorithm/I have benchmarked Dijkstra's algorithm using the Boost Graph library interface provided by SageMath against a basic and academic one but written in pure Python. And the later performs always better. This is very surprising since Boost Graph library is a templated C++ library. Perphaps I'using it in the wrong way. Here is the code :
from time import clock
from heapq import heappush, heappop
def make_graph(n, p):
import networkx as nx
G=nx.erdos_renyi_graph(n, p)
G=nx.relabel_nodes(G, lambda k:'v'+str(k))
edges=list(G.edges())
wedges=[]
for u, v in edges:
w=float(randrange(1, 10))
G[u][v]["weight"]=w
wedges.append((u, v, w))
return G, wedges
def wedges2adjw(nodes, wedges):
"From weighted wedges to weighted adjacency list"
n=len(nodes)
node2int={node:i for (i,node) in enumerate(nodes)}
adj=[[] for _ in range(n)]
for a, b,w in wedges:
i=node2int[a]
j=node2int[b]
adj[i].append((j,w))
adj[j].append((i,w))
return adj, node2int
def dijkstra_int(adj, src):
"""
adj: weighted adjacency lists of a graph with n nodes
vertices indexed fropm 0 to n-1
Returns shortest path list from src to all vertices"""
n=len(adj)
processed=[0]*n
processed[src]=1
distances=[(0,src)]
INF=float("inf")
dist=[INF]*n
dist[src]=0
while distances:
d, u=heappop(distances)
if processed[u]==1:
processed[u]=2
for v,w in adj[u]:
dd=d+w
if processed[v]==0 or dd<dist[v]:
heappush(distances, (dd,v))
dist[v]=dd
if processed[v]==0:
processed[v]=1
return dist
def dijkstra(nodes, wedges, n, src):
adj, node2int=wedges2adjw(nodes, wedges)
int2node={i:node for (node,i) in node2int.items()}
src_int=node2int[src]
return {int2node[i]:d for (i, d) in enumerate(dijkstra_int(adj, src_int)) if d!=float("inf")}
print("------------ Generating Graph --------------------")
debut=clock()
n=3000
p=0.3
Gnx, wedges=make_graph(n, p)
src=sample(Gnx.nodes(),1)[0]
nodes=Gnx.nodes()
gtime=(clock()-debut)
print "Number of nodes:", len(Gnx)
print "Number of edges:", len(Gnx.edges())
print("Graph generation: %.2fs" %gtime)
print("------------ Boost --------------------")
G = Graph()
G.add_vertices(nodes)
G.add_edges(wedges)
G.weighted(True)
debut=clock()
dist_boost = G.shortest_path_lengths(src,by_weight = True, algorithm='Dijkstra_Boost')
boost=(clock()-debut)
print("Boost: %.2fs" %boost)
print("------------ Pure Python --------------------")
debut=clock()
dist_pp=dijkstra(nodes, wedges, n, src)
py_time=(clock()-debut)
print("Pure Python: %.2fs" %py_time)
print"----------"
print "Checking:", dist_boost==dist_pp
Output :
------------ Generating Graph --------------------
Number of nodes: 3000
Number of edges: 1350005
Graph generation: 11.76s
------------ Boost --------------------
Boost: 1.61s
------------ Pure Python --------------------
Pure Python: 1.48s
----------
Checking: True
EDIT
Now, the tested functions have the same interface:
from time import clock
from heapq import heappush, heappop
def make_graph(n, p):
G = Graph()
G.add_vertices(range(n))
G.add_edges([(u, v, float(randrange(1, 10)))
for (u, v, _) in graphs.RandomGNP(n, p).edges()])
G.weighted(True)
return G
def dijkstra(G, src):
adj = [[] for _ in range(len(G))]
for i, j, w in G.edges():
adj[i].append((j, w))
adj[j].append((i, w))
n = len(adj)
processed = [0] * n
processed[src] = 1
distances = [(0, src)]
INF = float("inf")
dist = [INF] * n
dist[src] = 0
while distances:
d, u = heappop(distances)
if processed[u] == 1:
processed[u] = 2
for v, w in adj[u]:
dd = d + w
if processed[v] == 0 or dd < dist[v]:
heappush(distances, (dd, v))
dist[v] = dd
if processed[v] == 0:
processed[v] = 1
return {i: dist[i] for i in G if dist[i] != INF}
print("------------ Generating Graph --------------------")
debut = clock()
n = 3000
p = 0.3
G = make_graph(n, p)
src = randrange(n)
nodes = G.vertices()
gtime = (clock() - debut)
print "Number of nodes:", len(G)
print "Number of edges:", len(G.edges())
print("Graph generation: %.2fs" % gtime)
print("------------ Sage --------------------")
debut = clock()
dist_sage = G.shortest_path_lengths(
src, by_weight=True)
default_time = (clock() - debut)
print("Default: %.2fs" % default_time)
print("------------ Boost --------------------")
debut = clock()
dist_boost = G.shortest_path_lengths(
src, by_weight=True, algorithm='Dijkstra_Boost')
boost_time = (clock() - debut)
print("Boost: %.2fs" % boost_time)
print("------------ Pure Python --------------------")
debut = clock()
dist_pp = dijkstra(G, src)
py_time = (clock() - debut)
print("Pure Python: %.2fs" % py_time)
print "----------"
print "Checking:", dist_sage == dist_boost == dist_pp
print "Time ratio: %.2f" %(py_time/boost_time)
output:
------------ Generating Graph --------------------
Number of nodes: 3000
Number of edges: 1349390
Graph generation: 7.74s
------------ Sage --------------------
Default: 2.23s
------------ Boost --------------------
Boost: 1.53s
------------ Pure Python --------------------
Pure Python: 2.54s
----------
Checking: True
Time ratio: 1.66
By the way, the docs explain about the default implementation:
> (default): Sage chooses the best algorithm: 'BFS' if by_weight is False, 'Dijkstra_Boost' if all weights are positive, 'Bellman-Ford_Boost' otherwise.
This is not consistent with the timing above.
[As explained by David Coudert in the comments, the difference is due to sign checking]elasticaFri, 12 Jul 2019 14:08:13 +0200https://ask.sagemath.org/question/47138/Obtaining all connected simply laced graphs with Sage for GAPhttps://ask.sagemath.org/question/44747/obtaining-all-connected-simply-laced-graphs-with-sage-for-gap/I work with GAP and have not much experience with Sage. I wonder whether there is an easy way to obtain a program with Sage that gives as output a list of all directed simply laced acyclic connected graphs on n points up to equivalence that is readable for GAP (via the GAP-package QPA). I know that Sage can generate the list of such combinatorial collections in an easy way but I do not know how to present it in the needed output and how to obtain all restrictions on the graphs. With acyclic I mean acyclic as an directed graph (but in case this makes problems, you can also assume acyclic as undirected graphs).
Here a more detailed description of what the program should do:
Input: A natural number n >= 2.
Output: The list of directed simply laced acyclic connected graphs on n points up to equivalence. Here we call two such graphs equivalent in case they have the same underlying undirected graph (in case it is a problem to do it up to equivalence, we can first look at the problem without up to equivalence).
It is not important what the concrete orientation of the arrows of a representative in an equivalence class is.
Note that graphs are also often called quivers. GAP reads those graphs as `Quiver(n, [[p1, p2, "a1"], ...,[pm, pn, "ar"]])` where we name the points `pi` and the arrows between them as `aj` for some index sets `i` and `j`. (I hope it will be clear with the following examples).
Here how to output should look in the first 2 cases for n <= 3 so that it is readable for GAP:
n=2: `[Quiver(2,[[1,2,"a1"]])];`
n=3: `[Quiver(3,[[1,2,"a1"],[2,3,"a2"]]),Quiver(3,[[1,2,"a1"],[2,3,"a2"],[1,3,"a3"]])];` (note for example here here that the quiver `Quiver(3,[[1,2,"a1"],[2,3,"a2"]])` is equivalent to the quiver `Quiver(3,[[1,2,"a1"],[3,2,"a2"]])` since they are equal when looking at their undirected graphs)
So for n=2 there is one equivalence class, while for n=3 there are two (so that for n=3 the output is a list of two elements readable by GAP).sagequstionsSat, 22 Dec 2018 22:08:20 +0100https://ask.sagemath.org/question/44747/Pairs of graphs with same spectral radius but with different diameter and different number of edgeshttps://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/ I know that graphs.cospectral_graphs() gives all pairs of graphs with same eigenvalues. But I need graphs with same spectral radius i.e. largest eigenvalue (the other eigenvalues may be different) and differing in diameter and number of edges.
What to do for this? Thank you in advance.Deepak SarmaThu, 12 Apr 2018 07:47:21 +0200https://ask.sagemath.org/question/41990/dimensions of imagehttps://ask.sagemath.org/question/45765/dimensions-of-image/ I am having a little trouble when trying to specify the dimensions of a poset which I wish to see the graph of. I use name.show(figsize=[x,y]) but it's not giving me the expected image since it's only conserving the ratio, so it leaves off the y variable. If I wish to see the graph of the poset with dimensions 8x10, it should let me do so with the option figsize=[8,10], but it does not.
Can anyone help me with this issue?
Thank you in advance.StivenTue, 12 Mar 2019 02:10:26 +0100https://ask.sagemath.org/question/45765/Change dimensions of graphhttps://ask.sagemath.org/question/45761/change-dimensions-of-graph/ I am having trouble when trying to define the dimensions of a graph. I wish to have the graph of a poset with dimesions 8x10 (8in length and 10in width) but I don't know how. I tried figsize=[8,10] but it did not work since all it does is conserve the ratio.
Any given help is much appreciated. Thank you.StivenMon, 11 Mar 2019 19:46:42 +0100https://ask.sagemath.org/question/45761/3dplot molecule drawinghttps://ask.sagemath.org/question/44843/3dplot-molecule-drawing/ Hello!
I have to make a 3d model of the sulfur acid molecule, so that the name and mass of the molecules are visible on it and the bonds too(if 1 or 2 between 2 atoms).
Can someone send a code or some info about 3d plotting?SpreeterWed, 02 Jan 2019 19:08:32 +0100https://ask.sagemath.org/question/44843/