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.Thu, 02 May 2024 09:57:19 +0200Functions source codehttps://ask.sagemath.org/question/77199/functions-source-code/I am currently engaged in the study of graph theory for my master's thesis. For my work, I need to use the functions `is_isomorphic` and `is_subgraph`. I want to gain a deeper understanding of the underlying code for these two functions.
However, when I attempt to access the documentation using the `search_src()` function, I receive the following warning message: "Warning: the Sage documentation is not available".
Could you kindly guide me to where I can find the source code of these functions?
I appreciate your assistance in advance.
Best regards.Andrea ZattiThu, 02 May 2024 09:57:19 +0200https://ask.sagemath.org/question/77199/How to see the source code of the function distance_graphhttps://ask.sagemath.org/question/76543/how-to-see-the-source-code-of-the-function-distance_graph/I noticed the documentation for the distance_graph function, and I wanted to view its source code.
However, when I tried to run `? graphs.distance_graph`， it didn't work.
So, I searched for it on Sage's GitHub repository. I came across this line: `:meth:sage.graphs.generic_graph.distance_graph` for diameter distance. However, I still couldn't find the relevant description in the file [sage.graphs.generic_graph](https://github.com/sagemath/sage/blob/e417e2205be84d6d567b8897527fa6945ad09bdb/src/sage/graphs/generic_graph.py). Or running `? graphs.generic_graph.distance_graph` also does not work.
How can I locate its implementation?lichengSun, 17 Mar 2024 06:11:55 +0100https://ask.sagemath.org/question/76543/How to determine whether a graph has l cycles of length k exactly?https://ask.sagemath.org/question/76357/how-to-determine-whether-a-graph-has-l-cycles-of-length-k-exactly/Given integers$ l\ge 0$, $k\ge 3$, and a graph, I want to know if it contains $l$ $k$-cycles exactly. I could enumerate all cycles of length k using the link below and count them, but this might not be very efficient.
- [subgraph_search_iterator-gives-duplicate-subgraphs](https://ask.sagemath.org/question/69402/subgraph_search_iterator-gives-duplicate-subgraphs/)
G=graphs.OctahedralGraph()
H = graphs.CycleGraph(3)
print( sum(1 for _ in G.subgraph_search_iterator(H, induced=False,return_graphs=False) ) )
L = { tuple(g.edges(labels=False,sort_vertices=True,sort=True)) for g in G.subgraph_search_iterator(H, induced=False) }
print(len(L))
In an import case for me, determinie if a graph has a unique $k$-cycle (when $k=1$), I don't need to list all cycles and then check; instead, obtaining two cycles would suffice, and the algorithm stops.
Similarly, such questions can be asked about subgraphslichengTue, 05 Mar 2024 12:18:33 +0100https://ask.sagemath.org/question/76357/How can I check for the new functions in sage 10.1?https://ask.sagemath.org/question/72891/how-can-i-check-for-the-new-functions-in-sage-101/Sage 10.1 was recently released, but I'm not quite sure how to check for the newly added functions in the updated version. My main area of focus is graph theory research, so I noticed that the documentation PDF(see [graphs.pdf](https://doc.sagemath.org/pdf/en/reference/graphs/graphs.pdf)) for "graphs" has been updated. However, I want see what functions have been modified (added or removed).lichengThu, 24 Aug 2023 12:36:13 +0200https://ask.sagemath.org/question/72891/Problems with memory usage with bliss algorithmhttps://ask.sagemath.org/question/72676/problems-with-memory-usage-with-bliss-algorithm/I am trying to run a very long (weeks long) process that constructs a large collection of graphs.
The collection is too large to keep in memory and so as each graph is found it is stored on disk (rather than in an array).
However when I set it running, I noticed that the amount of RAM used by the process was continuously increasing until the rest of the machine ground to a halt. My computer has 64Gb RAM and it takes a bit more than a day for the process to grow to that size.
I have tried to isolate the part of the program that was causing the memory usage to grow, and I think that I have isolated it to the canonical labelling algorithm "bliss".
Here is a simple program that just creates random graphs and canonically labels them (but does nothing more):
for it in range(1000000):
g = graphs.RandomGNP(20,0.5)
gc = g.canonical_label(algorithm="bliss")
if it % 1000 == 0:
print(it)
When I run this program the memory consumed grows and grows.
If I change the program to use the built-in Sage method,
for it in range(1000000):
g = graphs.RandomGNP(20,0.5)
gc = g.canonical_label(algorithm="sage")
if it % 1000 == 0:
print(it)
then the program runs to completion with no increase in memory used - the memory is correctly being recovered as it goes out of scope each time through the loop.
What should I do in this situation?
GordonFri, 18 Aug 2023 04:24:53 +0200https://ask.sagemath.org/question/72676/Some "strange behaviors“ of longest_pathhttps://ask.sagemath.org/question/69746/some-strange-behaviors-of-longest_path/**version:** Sage 10.
I want to find a longest path starting from a given vertex in a graph. Below is my graph, and I have observed that if the longest path starting from a given vertex is a Hamiltonian path, `longest_path` responds very quickly. However, if it is not a Hamiltonian path, the response time is slow.
g1=Graph({0: [2, 3, 4, 15], 1: [16, 2, 3, 15], 2: [0, 1, 3, 4], 3: [0, 1, 2, 4], 4: [0, 2, 3, 15], 5: [7, 8, 9, 14], 6: [16, 7, 8, 9], 7: [5, 6, 8, 9], 8: [5, 6, 7, 9], 9: [5, 6, 7, 8], 10: [11, 12, 13, 14], 11: [16, 10, 12, 13], 12: [10, 11, 13, 14], 13: [16, 10, 11, 12], 14: [5, 10, 12, 15], 15: [0, 1, 4, 14], 16: [1, 6, 11, 13]})
Here is the calculation process.
g1.longest_path(1) # quckily
g1.longest_path(14) # long time, about 100s
![image description](/upfiles/16886104355878026.png)
![image description](/upfiles/16886104496539846.png)
Additionally, I have noticed that the option **backtracking** in `longest_path`does not seem to work when we specify the starting vertex. Looking at the output below, it is 1 or 9, not the longest path starting from vertex 14.
g1.longest_path(14,algorithm="backtrack")
![image description](/upfiles/16886106896341442.png)
**Question 1.** Why is there such a significant difference between the two cases?( When a vertex is given and there exists a Hamiltonian path that contains it as the starting vertex, it is puzzling why it is found quickly, while non-Hamiltonian paths take much longer.)
**Question 2.** Does the backtracking method not work when a starting vertex is given?lichengThu, 06 Jul 2023 04:37:51 +0200https://ask.sagemath.org/question/69746/Mysterious Disappearance of an edgehttps://ask.sagemath.org/question/69703/mysterious-disappearance-of-an-edge/Software version: **Sage 10.0**
The following codes can find all connected subgraphs.
g = graphs.CubeGraph(2)
subgraphs = list(g.connected_subgraph_iterator())
G=graphics_array([[v.plot() for v in subgraphs]],3,5)
G.show(axes=False, frame=False, figsize=5)
We will notice that there is an image missing an edge (due to the non-unique nature of iteration order, in my execution, it is the 6th one, and its image should be one edge instead of two isolated vertices).
![image description](/upfiles/16884710505555375.png)
The previous images might appear confusing because they are not separated by borders. I'm not know how to **uniformly add nice borders** to them (**which is also the question I've been wanting to ask**), otherwise, it would make the above issue more clear. The following images have been processed by using Inkscape. We can clearly see that the 6th image is missing an edge.
subgraphs[5].edges(sort=true,labels=False) # output: [('00', '01')]
![image description](/upfiles/16884717102411836.png)lichengTue, 04 Jul 2023 14:03:04 +0200https://ask.sagemath.org/question/69703/List all connected subgraphs with exactly k verticeshttps://ask.sagemath.org/question/69579/list-all-connected-subgraphs-with-exactly-k-vertices/I love `connected_subgraph_iterator`, but it always lists all connected subgraphs or those with **at most** $k$ vertices .
What if I only want to obtain connected subgraphs with **exactly** $k$ vertices? We can, of course, produce connected subgraphs with no more than $k$ vertices and then pick them, but **when $k$ is close to the odder of the input graph**, It appears that there is room for improvement.
# Example usage
G = graphs.CubeGraph(5) #order of G is 32
k=30
s=[g for g in G.connected_subgraph_iterator() if g.order()==k]
In Sage, must the generation of kth-order subgraphs rely on (k-1)-th or even smaller-order subgraphs?lichengWed, 28 Jun 2023 10:23:35 +0200https://ask.sagemath.org/question/69579/subgraph_search_iterator gives duplicate subgraphshttps://ask.sagemath.org/question/69402/subgraph_search_iterator-gives-duplicate-subgraphs/I use `subgraph_search_iterator` to obtain all the subgraphs isomorphic to $H$ of a graph $G$. However, in the following example, I found that many obtained subgraphs appear to be duplicates, which surprises me. Have I misunderstood this function?
G=graphs.OctahedralGraph()
H = graphs.CycleGraph(3)
L = list(G.subgraph_search_iterator(H, induced=False,return_graphs=False))
len(L)
![image description](/upfiles/16875225601766413.png)
L[1]
L[4]
L[18]
We will see that the 3-cycle formed by vertices 0, 1, and 3 appears three times. What could be the reason for this?
How can we avoid such occurrences?
----------
**Edits:** In fact, the 3-cycle formed by vertices 0, 1, and 3 appears six times.
Perhaps the $C_3$ are too specific and overshadowing something. If we consider the following example, we will discover that $H$ appears as many times as the number of copies of H without labels multiplied by the order of automorphisms of $H$. (label $H$ ?)
G=graphs.OctahedralGraph()
H=copy(G)
H.delete_edges( [(0,1), (1,2), ( 0,2 )])
print( sum(1 for _ in G.subgraph_search_iterator(H, induced=False,return_graphs=False) ) )
L = { tuple(g.edges(labels=False,sort_vertices=True,sort=True)) for g in G.subgraph_search_iterator(H, induced=False) }
print(len(L))
H.automorphism_group( ).order( )
![image description](/upfiles/16875925821091901.png)
48
8
6lichengFri, 23 Jun 2023 14:26:24 +0200https://ask.sagemath.org/question/69402/Rooted Product Graphs on Sagemathhttps://ask.sagemath.org/question/58122/rooted-product-graphs-on-sagemath/How does one implement rooted product graphs on Sagemath? For those who haven't heard about it before, there is a Wikipedia page for it!
Any help would be highly appreciated!
Link: https://en.wikipedia.org/wiki/Rooted_product_of_graphsmorganhouseMon, 26 Jul 2021 20:42:36 +0200https://ask.sagemath.org/question/58122/Can the bytes returned by pynauty's "certificate" function be converted into a graph format readable by Sage?https://ask.sagemath.org/question/68741/can-the-bytes-returned-by-pynautys-certificate-function-be-converted-into-a-graph-format-readable-by-sage/I know [nauty](https://pallini.di.uniroma1.it/) has been integrated with Sage. Has [pynauty](https://github.com/pdobsan/pynauty) been integrated in Sage 10?
I am using Sage 9.5, and it doesn't seem to have pynauty integrated. So, I installed this third-party package. I'm particularly interested in one of its functions, `certificate`. The function "certificate" serves a similar purpose to the `canonical_label` in Sage. (A **canonical graph** is the representative graph of an isomorphism class by some canonization function $c$. If $G$ and $H$ are graphs, then $G \cong c(G)$, and $c(G)==c(H)$ if and only if $G \cong H$.)
However, `certificate(g)` provides bytes instead of a graph. I'm not sure how to interpret them. I'm thinking of converting a graph after applying `certificate(g)` into the graph format used in Sage.
from pynauty import *
g = Graph(5)
g.connect_vertex(0, [1, 2, 3])
g.connect_vertex(2, [1, 3, 4])
g.connect_vertex(4, [3])
print(g)
g1=certificate(g)
b'\x00\x00\x00\x00\x00\x00\x00(\x00\x00\x00\x00\x00\x00\x00\x18\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00h\x00\x00\x00\x00\x00\x00\x00\xf0'
I cannot convert the above bytes to graphs. It preferable to preserve its "canonical" form when converting the bytes into a graph format in Sage.
I opened an issue on the developer's interface, but it seems like there hasn't been a response yet. See the following link:
- [How can we read the graph information after certificate in Pynauty?](https://github.com/pdobsan/pynauty/issues/30)lichengFri, 26 May 2023 08:44:07 +0200https://ask.sagemath.org/question/68741/How to find the graphs having exactly one perfect matching from the following collection and whose determinant is maximum?https://ask.sagemath.org/question/65859/how-to-find-the-graphs-having-exactly-one-perfect-matching-from-the-following-collection-and-whose-determinant-is-maximum/
for g in graphs.nauty_geng('8 -c'):
if g.size()==10:
A=g.adjacency_matrix()
k=A.determinant()
show(k)
g.show()
Here I am trying to obtain those graph(s) which have exactly one perfect matching and among all those graphs I need to obtain only that graph(s) whose adjacency matrix have highest determinant.rewiTue, 10 Jan 2023 20:20:05 +0100https://ask.sagemath.org/question/65859/Subdivisions of a graphhttps://ask.sagemath.org/question/64296/subdivisions-of-a-graph/Let $G$ and $H$ be two given graphs. Suppose $H$ is smaller than $G$.
How do I check whether $G$ contains a subgraph which is an even (or odd) subdivision of $H$?
I know that the command: G.minor(H) will tell whether $G$ contains a subgraph which is a subdivision of $H$.
But I'm looking for whether it contains an even subdivision. How do I do this?the1diotTue, 04 Oct 2022 11:31:40 +0200https://ask.sagemath.org/question/64296/How to put the drawing of graphs in a matrix or listhttps://ask.sagemath.org/question/54381/how-to-put-the-drawing-of-graphs-in-a-matrix-or-list/I have got some graphs on 5 vertices.
count = 0
for g in graphs.nauty_geng("5 1:5"):
count = count+1
print(count)
we got 19 graphs. I want to show them but get long output using following codes, and it is very bad for viewing.
for g in graphs.nauty_geng("5 1:5"):
g.show()
I thought of using matrix or list storage these drawings of graph , but it failed.
glist= [g for g in graphs.nauty_geng("5 1:5")]
map(show,glist)
we got noting from outputs:
<map object at 0x6fdf37c3cf8>
This is what Maple did well.
with(GraphTheory):
graphsof5c := [NonIsomorphicGraphs(5, 1..5,output = graphs, outputform = graph)]:
DrawGraph~(graphsof5c,size=[300,300],stylesheet=[vertexborder=false,vertexpadding=20,edgecolor = "Blue",
vertexcolor="Gold"])
My points are less than 60 points, I can’t upload
corresponding pictures, sorry.lichengWed, 25 Nov 2020 10:27:09 +0100https://ask.sagemath.org/question/54381/Spanning elementary subgraphs on a given number of verticeshttps://ask.sagemath.org/question/60937/spanning-elementary-subgraphs-on-a-given-number-of-vertices/Consider the following definition:
> A subgraph H of a graph $G$ is called an elementary subgraph
> if each component of $H$ is either an edge or a simple cycle of length
> at least $3$.
> A spanning elementary subgraph is a subgraph having
> all components either edge (edge is a path on two vertices)
> or simple cycles.
Now my problem is: Consider the following code:
G = graphs.EmptyGraph()
G.add_edges([(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (6, 5), (6, 7)])
G.show()
Can we have a Sage code that gives all possible spanning subgraphs
on $6$ vertices of the above graph?
Actually I am trying to find the all possible spanning elementary
subgraphs on $6$ vertices of the above graph. By $6$ vertices,
I mean the subgraphs of order 6 of the original graph.rewiFri, 04 Feb 2022 13:18:25 +0100https://ask.sagemath.org/question/60937/how to find subdivision graph of any graph ?https://ask.sagemath.org/question/60000/how-to-find-subdivision-graph-of-any-graph/Strictly speaking, a subdivision of graph is graph obtained by placing a vertex between two adjacent vertices. path of length 2 is subdivision of path on length 1.Vinayak guptaMon, 29 Nov 2021 08:47:00 +0100https://ask.sagemath.org/question/60000/Working with unlabelled graphshttps://ask.sagemath.org/question/59010/working-with-unlabelled-graphs/ I'm studying certain properties of graphs but I want to work with unlabelled ones i.e. I do not want to distinguish graphs that differs only by the numbering of vertices, which is the case by default if I have correctly understood. Is it possible?
ThanksoldaniTue, 14 Sep 2021 11:50:29 +0200https://ask.sagemath.org/question/59010/Any Built in code for Crossed Prism Graphs on sagemath?https://ask.sagemath.org/question/58114/any-built-in-code-for-crossed-prism-graphs-on-sagemath/I have been working on a research question regarding a certain property of Crossed Prism Graphs that requires me to use Sage (i.e., Python). I have found on an article entitled: "A new generalization of generalized Petersen graphs" that the family GDGP_2(n; 1, n-3) is also known as Crossed Prism Graph, where GDGP stands for Divisible Generalized Petersen Graphs. Any idea how to code that up in Sage? I would love some guidance!morganhouseSun, 25 Jul 2021 19:24:19 +0200https://ask.sagemath.org/question/58114/Is it possible for the spectrum() method to use all CPU cores?https://ask.sagemath.org/question/57824/is-it-possible-for-the-spectrum-method-to-use-all-cpu-cores/I need to compute the Laplacian spectrum of a ton of graphs and was wondering if it's possible to use all CPU cores instead of only one.lisandraspWed, 30 Jun 2021 18:41:11 +0200https://ask.sagemath.org/question/57824/CubeConnectedCycle not there? Attribute Errorhttps://ask.sagemath.org/question/57015/cubeconnectedcycle-not-there-attribute-error/In [the documentation for CubeConnectedCycle](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.CubeConnectedCycle), it says
static CubeConnectedCycle(d)
But when I try to run the following example given in the same page above it is giving an error.
d = 3
g = graphs.CubeConnectedCycle(d)
The error shown is
AttributeError: GraphGenerators instance has no attribute 'CubeConnectedCycle'
Can someone tell me what went wrong?
Thanks in advance.Anoop S K MSat, 08 May 2021 06:29:01 +0200https://ask.sagemath.org/question/57015/Combination under constrained situation with a conditionhttps://ask.sagemath.org/question/52345/combination-under-constrained-situation-with-a-condition/Step 1: I want to take a number `n` as input from user
Step 2: We form the set `S` consisting of elements from `0` to `n*(2^{n-1})`
Step 3: Now I pick each possible two-element subsets of `S` and store it in `P`.
Step 4: Now I need to pick `n*(2^{n-1})` two-element subsets from `P`
such that each number that occurs in that set occurs exactly `n` times
neither less nor more and put them all in a list.
Example
n = 2
n*(2^{n-1}) = 2*(2^{2-1}) = 4
S = {0,1,2,3,4}
p = {(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
Step 4 One element which satisfies condition of step 4; HERE `n = 2`.
`{(0,1),(1,2),(2,3),(0,3)}` which has `2*(2^{n-1}) = 2*(2^{2-1}) = 4` elements.
Now see in the above set
- `0` occurred `n=2` times only in `(0,1)` and `(0,3)` only
- `1` occurred `n=2` times only in `(0,1)` and `(1,2)` only
- `2` occurred `n=2` times only in `(1,2)` and `(2,3)` only
- `3` occurred `n=2` times only in `(2,3)` and `(0,3)` only
Similarly we may get for `{(0,1),(1,4),(4,2),(2,0)}` we can easily verify like above.
Now based on `n` the number of elements size etc will vary.
Kindly help if possible any one.sriramSun, 05 Jul 2020 20:36:40 +0200https://ask.sagemath.org/question/52345/How to obtain the graph having highest algebraic connectivity?https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/ for G in graphs.nauty_geng("10-c"):
if G.size()==11:
L = G.laplacian_matrix().eigenvalues()
L.sort()
show(L)
G.show()
Using this code I have obtained the connected graphs on 10 vertices with 11 edges. Also I have obtained the Laplacian eigenvalues also for the corresponding graphs. The second smallest eigenvalue of Laplacian matrix is called the algebraic connectivity. Now among all these graphs, I need those graphs which have highest algebraic connectivity among all the graphs on 10 vertices with 11 edges. How we can do that?rewiWed, 24 Jun 2020 22:24:16 +0200https://ask.sagemath.org/question/52205/Displaying Chessboard Graphshttps://ask.sagemath.org/question/49976/displaying-chessboard-graphs/I'm looking at various graphs and their plotting methods. For the code
G = graphs.KnightGraph([3,3])
G.show()
Sage displays:
![image description](/upfiles/15820828503619033.jpg)
I'd like the vertices to be arranged in a 3 by 3 grid so that the chessboard nature of the graph is more apparent.
From the documentation [here](http://doc.sagemath.org/html/en/reference/plotting/sage/graphs/graph_plot.html) I tried specifying the position by using a dictionary:
G = graphs.KnightGraph([3,3])
pos_dict = {}
for i in range(0,2):
for j in range(0,2):
pos_dict[G.vertices()[3*i+j]] = [i*.5,j*.5]
pl = G.graphplot(pos=pos_dict)
pl.show()
This doesn't give the intended result. Even stranger, running the code multiple times shows the position of only some of the
vertices is fixed while others change position.
How can I display an n by n chessboard graph so that it's vertices form an n by n square?
dazedANDconfusedWed, 19 Feb 2020 04:38:26 +0100https://ask.sagemath.org/question/49976/find all matchings in a graphhttps://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/ Given a graph $G$, is it possible to ask Sage to generate all possible matchings of $G$? I know that G.matching() gives a maximum matching of $G$ and I also know that Sage has an iterator which finds all perfect matchings of $G$.
If no command exists which asks Sage to give me all possible matchings of $G$, does anyone have an idea of how to write a program to ask Sage to do this?merluzaSat, 22 Jun 2019 00:05:51 +0200https://ask.sagemath.org/question/46964/Constructing graphs using permutation or symmetric groupshttps://ask.sagemath.org/question/46450/constructing-graphs-using-permutation-or-symmetric-groups/ I'm trying to construct a graph whose vertices are the elements of a permutation group or a symmetric group. Whenever I do this, it ignores the identity element (). For instance, when I use the Symmetric Group S3, it prints a graph with 5 vertices and the missing vertex is the identity.
Any ideas on why this happening and how I can fix it? homiermorphismSat, 04 May 2019 22:47:42 +0200https://ask.sagemath.org/question/46450/Number of neighbors of a set of vertices in a graphhttps://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/Hi all,
I'd like to know how to get the number of vertices that are adjacent to a given set of vertices in a graph. I have the following skeleton:
from sage.graphs.independent_sets import IndependentSets
G=[some graph]
J=IndependentSets(G)
And I would like to know the number of neighbors of x for each x in J (i.e., the number of vertices of G\x that are adjacent to some vertex in x). Ideally I would like something like:
F=0
t=var('t')
for x in J:
N=number_of_neighbors(x)
F += t^N
F
If G is a four cycle then number_of_neighbors(x)=2 for any subset x of two vertices of G, and the polynomial F above should be 1+6t^2 (because there is the empty independent set, 4 independent sets of size 1 each with 2 neighbors, and 2 independent sets of size 2 each with 2 neighbors). I appreciate your help!MagusTue, 12 Mar 2019 01:29:53 +0100https://ask.sagemath.org/question/45764/Generating plane triangulationshttps://ask.sagemath.org/question/10851/generating-plane-triangulations/Does sage have a function that generates plane triangulations? Something like PLANTRI? If not, is it possible to use plantri from within sage and how?
Thank youhbmSat, 21 Dec 2013 14:22:30 +0100https://ask.sagemath.org/question/10851/Graph.subgraph_search() obtaining the indices?https://ask.sagemath.org/question/44792/graphsubgraph_search-obtaining-the-indices/It is nice that Graph.subgraph_search() returns a subgraph, but I need the indices of the larger graph to manipulate it, for example finding the subgraph neighbors. Is there a way to obtain the original indices?RushBackThu, 27 Dec 2018 15:56:10 +0100https://ask.sagemath.org/question/44792/Why does this error arise?https://ask.sagemath.org/question/43736/why-does-this-error-arise/I want to relabell the vertices of a randomly generated graph in Sage. Let $v$ be the set of vertices ordered according to their appearance in the degree sequence. The labelling strategy is like this:
1. Initialize: $k=0$
2. While $v\neq \emptyset$ do:
3. Pick the first element $u$ of $v$, $u\to k$, $k=k+1$
4. For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.
In order to achieve that I wrote the following code but it gives me the folowing error: ValueError: list.remove(x): x not in list, which I do not know how to fix. I know that the problem is in the last part because the rest of the code works. In my understanding, all the elements of $s$ are also elements of $v$. So I do not know why the error is coming up.
def t(n,m):
G=graphs.RandomGNM(n,m)
G.show()
#***********forming the list b of tuples (vertex, deg(vertex))
a=[]
for i in G.vertices():
a.append((i,G.degree(i)))
b=sorted(a, key=lambda x: x[1],reverse=True)
#************** degree sequence d of the graph G
d=[]
for i in xrange(0,len(b)):
d.append(b[i][1])
print("degree sequence",d)
#*************** sorting vertices in a list v according to the order they appear
#in the degree sequence
v=[]
for i in xrange(0,len(b)):
v.append(b[i][0])
print("vertices ",v)
#**************** relabelling vertices
v_1=v[:]
v_2=list([0 for i in xrange(0,len(v))]) #~list which will hold the new labels
k=1
while v<>[]:
s=[]
v_2[v_1.index(v[0])]=k #relabeling the vertex with the highest degree in v
s.append(v_1.index(v[0]))
k=k+1
for j in G.neighbors(v_1.index(v[0])): #~relabeling its neighbors
v_2[v_1.index(j)]=k
s.append(j)
k=k+1
for f in s: #removing from v the relabeled vertices
v.remove(f)
print(v_2)
UPDATE: The new code:
def ver(d):#the function returns the list v of vertices of the
#Graph(d) in the order they appear in the degree sequence
G=Graph(d)
if G.vertices()<>[]:
G.show()
#*****forming the list b of tuples (vertex,deg(vertex))
a=[]
for i in G.vertices():
a.append((i,G.degree(i)))
b=sorted(a, key=lambda x: x[1],reverse=True)
#*****degree sequence d of the graph G
d=[]
for i in xrange(0,len(b)):
d.append(b[i][1])
#*****sorting vertices in a list v according to
#**** the order they appear in the degree sequence
v=[]
for i in xrange(0,len(b)):
v.append(b[i][0])
print("vertices ",v)
return(v)
G=graphs.RandomGNM(10,14)
v=ver(G.to_dictionary())
v_1=v[:]
v_2=[0 for i in xrange(0,len(v))]
k=0
while v<>[]:
v_2[v_1.index(v[0])]=k
k=k+1
for i in G.neighbors(v[0]):
v_2[v_1.index(i)]=k
k=k+1
G.delete_vertices(G.neighbors(v[0]))
G.delete_vertex(v[0])
v=ver(G.to_dictionary())
d=dict(zip(v_1,v_2))
G.relabel(d)
G.show()
It works but `G.show()` does not produce any output.kristiMon, 24 Sep 2018 18:33:14 +0200https://ask.sagemath.org/question/43736/Drawing a planar multigraph with loopshttps://ask.sagemath.org/question/40548/drawing-a-planar-multigraph-with-loops/ I would like to draw a planar graph with multiple edges and loops in Sage. Unfortunately, the default algorithm draws may intersecting edges and Sage is unable to compute an embedding for graphs with loops multiple edges.
Fortunately I know a planar embedding of this graph, so I tried using the `set_embedding` method, but it doesn't seem to work, either. If I only list a vertice's the neighbours, omitting their multiplicities, Sage complains that the list is shorter than the vertice's degree, while if I include multiple copies of each neighbour according to multiplicity, then Sage complains that elements of the list aren't unique.
Is there a way to achieve what I need?A.P.Wed, 10 Jan 2018 14:00:59 +0100https://ask.sagemath.org/question/40548/