ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 05 Jul 2020 13:36:40 -0500Combination 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 13:36:40 -0500https://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?KuldeepWed, 24 Jun 2020 15:24:16 -0500https://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?
dazedANDconfusedTue, 18 Feb 2020 21:38:26 -0600https://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?merluzaFri, 21 Jun 2019 17:05:51 -0500https://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 15:47:42 -0500https://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!MagusMon, 11 Mar 2019 19:29:53 -0500https://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 07:22:30 -0600https://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 08:56:10 -0600https://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 11:33:14 -0500https://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 07:00:59 -0600https://ask.sagemath.org/question/40548/Stochastic block modelhttps://ask.sagemath.org/question/38929/stochastic-block-model/Hi all,
I would like to draw a random graph by Sage. The general stochastic model is the following: The graph contains $n$ vertices and the n vertices are divided into $r$ communities $C_1\cdots,C_r$. For two vertices within the same community, there is a probability $P_r$ that they are connected directly by an edge. How do I plot such a graph in Sage? References appreciated.Dianbin BaoThu, 21 Sep 2017 13:19:26 -0500https://ask.sagemath.org/question/38929/networkx can't compute algebraic connectivityhttps://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/I can compute the algebraic connectivity of the complete graph on 20 vertices in a fraction of a second using
import networkx
D = {}
for i in range(20):
D[i] = [j for j in range(20)]
G = networkx.Graph(D)
networkx.algebraic_connectivity(G)
However, in a process I generate a graph (on 20 nodes) that I ask networkx to compute its algebraic connectivity, and it keeps running for ever with no errors. Here is the graph:
import networkx
D = {0: [32, 33, 19, 5, 21, 37, 6, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 5: [32, 0, 33, 19, 37, 21, 6, 22, 38, 39, 41, 26, 42, 11, 43, 44, 28, 15, 31], 6: [0, 32, 33, 19, 5, 37, 21, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 11: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 43, 28, 44, 15, 31], 15: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31], 19: [0, 32, 33, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 21: [32, 0, 33, 19, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 22: [32, 33, 19, 5, 21, 37, 6, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 26: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 42, 11, 43, 28, 44, 15, 31], 28: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 43, 44, 15, 31], 31: [32, 0, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15], 32: [0, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31, 15], 33: [0, 32, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 37: [32, 0, 33, 19, 5, 21, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31, 15], 38: [32, 0, 33, 19, 21, 37, 5, 6, 22, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 39: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 41, 26, 42, 11, 43, 28, 44, 15, 31], 41: [32, 0, 33, 19, 21, 37, 5, 38, 6, 22, 39, 26, 42, 11, 43, 28, 44, 15, 31], 42: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 11, 43, 28, 44, 15, 31], 43: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 28, 44, 15, 31], 44: [32, 0, 33, 19, 5, 21, 37, 38, 6, 22, 39, 41, 42, 26, 11, 43, 28, 15, 31]}
G = networkx.Graph(D)
networkx.algebraic_connectivity(G)
Any reasons why it is so, and any idea on how to fix it?k1monfaredWed, 12 Apr 2017 20:55:30 -0500https://ask.sagemath.org/question/37273/Multi-Commodity Flow problem, solution referencehttps://ask.sagemath.org/question/37029/multi-commodity-flow-problem-solution-reference/ Hello,
I am using "multicommodity_flow()" method for my research and I would like to know the reference behind the solution, like a paper, book or an article.
Thanks,
AmirAmir19Wed, 22 Mar 2017 03:12:08 -0500https://ask.sagemath.org/question/37029/The interval I(u,v) between a pair of vertices u,v in graphhttps://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/Hello Everyone,
I am really new to the sagemath and I need your help with finding the interval between **all pair of vertices** in a graph.
Def: In graph G, the Interval between a pair of vertices u and v is: I(u,v)={w|d(u,v)=d(u,w)+d(w,v)}
In other words, the interval between a pair of vertices u and v is : all vertices that lies on all shortest paths between them.
I want to find the interval between all pairs of vertices in graph. I do not know if such function already exists in sagemath or I do need to implement my own.
Thanks,
HakeemHakeemSat, 03 Dec 2016 15:44:40 -0600https://ask.sagemath.org/question/35905/Does there exist a GUI web-app that allows for edge contractions and vertex splits?https://ask.sagemath.org/question/35825/does-there-exist-a-gui-web-app-that-allows-for-edge-contractions-and-vertex-splits/I am interested in creating a web-app that allows for graph creation, edge contraction, vertex splits, and then exports to sage.
If anyone knows of something like this already developed please let me know, otherwise any suggestions on how to begin?
ThanksfieldofnodesWed, 30 Nov 2016 11:29:51 -0600https://ask.sagemath.org/question/35825/Edges associated to the variables in G.kirchhoff_symanzik_polynomial()https://ask.sagemath.org/question/35610/edges-associated-to-the-variables-in-gkirchhoff_symanzik_polynomial/ How do the variables t0, t1, t2,... in G.kirchhoff_symanzik_polynomial(), for a given undirected graph G, correspond to the edges of G? (i.e. what is the bijection between the variables ti and the edges of G?) The variables do not follow the same order as in the list G.edges(), which I thought was the case.
pmWed, 16 Nov 2016 06:05:38 -0600https://ask.sagemath.org/question/35610/hamiltonian paths?https://ask.sagemath.org/question/34584/hamiltonian-paths/A Hamiltonian cycle is a traversal of a graph that visits all vertices just once and then returns to the starting vertex. SageMath can find one for you with G.traveling_salesman_problem. A Hamiltonian **path** drops the requirement that the path form a cycle. Does SageMath offer a convenient way to list all Hamiltonian paths of a graph?iconjackThu, 25 Aug 2016 14:15:24 -0500https://ask.sagemath.org/question/34584/How do I add an attribute to the object/class "Graph?"https://ask.sagemath.org/question/35439/how-do-i-add-an-attribute-to-the-objectclass-graph/ Hi,
I am researching methods that relate to graph minors. Currently I am looking at creating a method/function/attribute (I give the options as I do not know the best means, . . . , yet) which will allow me to test for forbidden minors.
An example is the complete graph on 6 vertices is a forbidden minor for the class of graphs that are not apex. Meaning, that given a graph G and a $v\in V(G)$, that $G-v$ is not planar. So the code that I have been working on should test if a graph matches a certain criteria. I would be able to ask SageMath in the following way
K6=graphs.CompleteGraph(6); K6.is_apex()
Of which the response would be
False
This is the code that I have been working on
def is_apex(g):
for v in g.vertex_iterator():
l = g.neighbors(v)
g.delete_vertex(v)
if g.is_planar():
return True
g.add_vertex(v)
g.add_edges([(v, y) for y in l])
return False
Now I had help on this from another member in the AskSage community, so thank you.
But now I am trying to do something like this:
class Graph():
not_apex = False
def is_apex(self):
for v in self.vertex_iterator():
l = self.neighbors(v)
g.delete_vertex(v)
if self.is_planar():
return True
self.add_vertex(v)
self.add_edges([(v, y) for y in l])
return False
Which when I enter
x.is_apex()
Of which the response that I get
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-15-e74e0334c694> in <module>()
----> 1 x.is_apex()
AttributeError: 'Graph' object has no attribute 'is_apex'
I am still a nooooooooob, so any help in understanding what I need to do would be great.
Thank you
fieldofnodesFri, 04 Nov 2016 16:31:21 -0500https://ask.sagemath.org/question/35439/How do I write function to test if a graph is apex?https://ask.sagemath.org/question/35112/how-do-i-write-function-to-test-if-a-graph-is-apex/ I am working on topological graph theory problems and using SageMath.
I want to create a function that give a boolean True or False answer, so I can use this answer for further use.
My current function that I use:
def is_apex(a):
for v in a.vertex_iterator():
l=a.neighbors(v)
if a.is_planar(a.delete_vertex(v)):
print("Deleting vertex ",v," makes a planar graph")
a.add_vertex(v)
a.add_edges([(v, y) for y in l])
else:
a.add_vertex(v)
a.add_edges([(v, y) for y in l])
print("Deleting vertex ",v," does not make a planar graph")
I am a noob when it comes to programming, and any help would be awesome.
I want a True returned if the graph is apex and a False value to return for not apex.
Thoughts?fieldofnodesMon, 10 Oct 2016 15:18:52 -0500https://ask.sagemath.org/question/35112/Finding number of strongly connected componentshttps://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/I need to find the number of strongly connected components of a digraph, and I looked at the documentation for the ~DiGraph.strongly_connected_components() method. Tabbing .strongly_connected_components? gives the documentation from sage/graphs/base/static_sparse_graph.pyx for tarjan_strongly_connected_components(G) that says,
This routine returns a pair ``[nscc, scc]``, where ``nscc`` is the number of
SCCs and ``scc`` is a dictionary associating to each vertex ``v`` an
integer between ``0`` and ``nscc-1``, corresponding to the SCC containing
``v``. SCCs
are numbered in reverse topological order, that is, if ``(v,w)`` is an edge
in the graph, ``scc[v] <= scc[w]``
Which would be great, as I just need the result of tarjan_strongly_connected_components_C. However, 1) this is only called during tarjan_strongly_connected_components, which does the (admittedly minor) additional work of topologically sorting SCCs and 2) the examples (and testing) show the output of ~DiGraph.strongly_connected_components() is a list of vertex lists for each connected component. This is perfectly reasonable and clear, but more than I want, particularly as there's some work in the back end that determines what I'm looking for earlier in the process.
1) Should I just use len(~DiGraph.strongly_connected_components())?
2) Am I badly misreading the documentation for this method?
I'm in Sage 7.2.
Thanks in advance for help here!JEFLSUFri, 10 Jun 2016 08:01:31 -0500https://ask.sagemath.org/question/33735/Graph theory for symbolic electrical circuit analysis?https://ask.sagemath.org/question/32977/graph-theory-for-symbolic-electrical-circuit-analysis/Looking for how to go from graph theory directly to solve circuit/nodal analysis.
This link has been helpful: (have to google graphsandckts.pdf because I can't post the link) but I seem to be getting lost in the graph theory part. Circuit analysis software like SPICE must do something like this numerically.
I can build a directed graph in Sagemath by adding vertices/edges.
Sagemath will return the incidence matrix. Or you can enter the incidence matrix directly but for something like a circuit netlist it can be a lot easier to enter nodes, ie. vertices of the graph.
Resistances/impedances go into a diagonal matrix R, known voltages/currents go into a vector.
I'm not clear on finding the spanning tree/re-arranging the incidence matrix.
Seems like this should be some standard graph theory or linear algebra functions. You eliminate one row/column and should have a matrix A =[ At I ]
where At = edges in the graph spanning tree and I = n x n identity matrix.
The rest should be basic linear algebra: transpose, inverse, multiplying it out
John Paul MorrisonSun, 03 Apr 2016 14:21:14 -0500https://ask.sagemath.org/question/32977/How to define a graph using Cartesian coordinateshttps://ask.sagemath.org/question/33565/how-to-define-a-graph-using-cartesian-coordinates/I am trying to figure out (1) how to input a graph into Sage where the vertices are described as Cartesian coordinates (3-tuples), and then (2) for each pair of vertices, compute the Euclidean distance between the two and, if the Euclidean distance is some fixed value $d$, add an edge between these two vertices.
Specifically, here are my questions:
1. How do I input a graph into Sage where the vertices are described as Cartesian coordinates (3-tuples)?
2. Is there a pre-defined function in Sage for computing the Euclidean distance between two Cartesian coordinates?
JEAFri, 27 May 2016 16:08:03 -0500https://ask.sagemath.org/question/33565/How to create random cubic planar graphs?https://ask.sagemath.org/question/33401/how-to-create-random-cubic-planar-graphs/ Hi,
I need to create random cubic planar graphs.
Do you know how can I do that?
Or alternatively, do you know a can create the dual of a random planar triangulation?
I saw that I can create triangulation using:
G = graphs.RandomTriangulation(n)
Bye and thanksstefanuttiFri, 13 May 2016 10:25:08 -0500https://ask.sagemath.org/question/33401/How do I get the external face of a planar embedded graph?https://ask.sagemath.org/question/33363/how-do-i-get-the-external-face-of-a-planar-embedded-graph/ First of all I am new to Sage and Python.
I need to get the external face a planar embedding and I immagined that it is always the first element returned by the function faces().
But in this example it seems to change. See the first and the second run.
Is it something about the function faces() or an error in this program?
print ("--- Create a graph")
G = Graph(sparse=True)
G.add_edge(1,2,"1-2")
G.add_edge(2,3,"2-3")
G.add_edge(3,4,"3-4")
G.add_edge(4,5,"4-5")
G.add_edge(5,1,"5-1")
G.add_edge(1,6,"1-6")
G.add_edge(2,10,"2-10")
G.add_edge(3,12,"3-12")
G.add_edge(4,11,"4-11")
G.add_edge(5,7,"5-7")
G.add_edge(6,7,"6-7")
G.add_edge(6,8,"6-8")
G.add_edge(8,10,"8-10")
G.add_edge(10,12,"10-12")
G.add_edge(12,11,"12-11")
G.add_edge(7,9,"7-9")
G.add_edge(8,9,"8-9")
G.add_edge(9,11,"9-11")
print ("--- Embed on a plane")
void = G.layout(layout = "planar", save_pos = True)
G.plot()
# Kempe reduction: for each loop remove an edge from faces <= F5
#
while len(G.faces()) > 2:
print ("Number of faces: ", len(G.faces()))
# Remove the external face. Is it always faces[0]???
#
faces = G.faces()
externalFace = faces[0]
facesWithoutTheExternalFace = copy(faces)
facesWithoutTheExternalFace.remove(externalFace)
print ("faces: ", faces)
print ("externalFace: ", externalFace)
print ("facesWithoutTheExternalFace: ", facesWithoutTheExternalFace)
# Find the fist face [0] with len <= 5. It always exists: unavoidable set
#
faceToReduce = [x for x in facesWithoutTheExternalFace if len(x) <= 5][0]
print ("Face <= 5: ", faceToReduce)
# Find the first edge of the faceToReduce that is not on an edge on the external face
#
edgeToRemove = [x for x in faceToReduce if not x in externalFace][0]
print ("edgeToRemove: ", edgeToRemove)
verticesToRemove = G.get_vertices(edgeToRemove)
print ("verticesToRemove ", verticesToRemove)
G.delete_edge(edgeToRemove)
neighborsOfTheFirstVertex = G.neighbors(verticesToRemove.keys()[0])
neighborsOfTheSecondVertex = G.neighbors(verticesToRemove.keys()[1])
print ("neighborsOfTheFirstVertex = ", neighborsOfTheFirstVertex)
print ("neighborsOfTheSecondVertex = ", neighborsOfTheSecondVertex)
G.delete_vertices(verticesToRemove)
G.add_edge(neighborsOfTheFirstVertex[0], neighborsOfTheFirstVertex[1])
G.add_edge(neighborsOfTheSecondVertex[0], neighborsOfTheSecondVertex[1])
G.plot()stefanuttiWed, 11 May 2016 03:44:18 -0500https://ask.sagemath.org/question/33363/How to make a graph from an latin square matrix ?https://ask.sagemath.org/question/31564/how-to-make-a-graph-from-an-latin-square-matrix/As the question says I want to write a program that will make a graph from the given matrix ?
How can I do that in Sage?vicariousMon, 14 Dec 2015 13:20:10 -0600https://ask.sagemath.org/question/31564/How to plot a colored graph from a latin square?https://ask.sagemath.org/question/31562/how-to-plot-a-colored-graph-from-a-latin-square/ The program will get input in form of a matrix that is a latin square.
This matrix will be dealt with as a blueprint for a complete graph, each cell of the matrix representing the color.
How can I plot such matrices?vicariousMon, 14 Dec 2015 13:08:13 -0600https://ask.sagemath.org/question/31562/Check SDR in a bipartite graph by Hall's theorem.https://ask.sagemath.org/question/31379/check-sdr-in-a-bipartite-graph-by-halls-theorem/How can I check existence of a complete SDR in a bipartite graph ?
This will be done by checking if there is a perfect matching in the graph(Hall's marriage theorem), but How can I implement this in SAGE?
vicariousMon, 07 Dec 2015 10:39:04 -0600https://ask.sagemath.org/question/31379/Dotted and dashed lines in directed graphshttps://ask.sagemath.org/question/31304/dotted-and-dashed-lines-in-directed-graphs/Hi,
I would like to know if it is possible to do (one of) the following with Sage.
Reading
http://doc.sagemath.org/html/en/reference/plotting/sage/graphs/graph_plot.html
I saw that it is possible to draw dashed and dotted lines. Now my questions are
1) Is it possible to produce an output graphic where some edges are dotted and some edges are dashed?
2) Is it possible to force the text in the labels of the vertices, e.g. M2, M4, M1 instead of 0,1,2?
Thanks for the help!
BernThu, 03 Dec 2015 20:39:18 -0600https://ask.sagemath.org/question/31304/How to make pygraphviz and sage compatible?https://ask.sagemath.org/question/31070/how-to-make-pygraphviz-and-sage-compatible/ Hi,
I would like sage to help me when I am working with (un)directed graphs and quivers, and so on. After having played around with various possibilities, I would like to convert some stuff into a string and then let sage print something like a .ps - file that contains an image from dot (or something similar to this).
> Unfortunately, I came across the following issue(s) and have no idea what to do now. With the sage version I installed, there is python 2.x as a delivered package. But it seems that sage complains about python3, what doesn't make sense to me.
Could you help me understand and solve the following:
boehmler@boehmler-X55A:~/Schreibtisch/bb/sage-6.9-x86_64-Linux$ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: import networkx as nx
sage: import matplotlib.pyplot as plt
sage: import matplotlib.image as mpimg
sage: from cStringIO import StringIO
sage: g = nx.dodecahedral_graph()
sage: d = nx.to_pydot(g)
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-6-0d33c400a5cf> in <module>()
----> 1 d = nx.to_pydot(g)
AttributeError: 'module' object has no attribute 'to_pydot'
sage: d = nx.to_agraph(g)
---------------------------------------------------------------------------
ImportError Traceback (most recent call last)
<ipython-input-7-d9254026fb59> in <module>()
----> 1 d = nx.to_agraph(g)
/home/boehmler/Schreibtisch/bb/sage-6.9-x86_64-Linux/local/lib/python/networkx/drawing/nx_agraph.pyc in
to_agraph(N)
132 raise ImportError('requires pygraphviz ',
133 'http://networkx.lanl.gov/pygraphviz ',
--> 134 '(not available for Python3)')
135 directed=N.is_directed()
136 strict=N.number_of_selfloops()==0 and not N.is_multigraph()
ImportError: ('requires pygraphviz ', 'http://networkx.lanl.gov/pygraphviz ', '(not available for Python3)')
sage:
Exiting Sage (CPU time 0m3.33s, Wall time 56m28.80s).
After typing
boehmler@boehmler-X55A:~/Schreibtisch/bb/sage-6.9-x86_64-Linux$ sudo -H pip install pygraphviz
I get the message
Wall -Wstrict-prototypes -fPIC -I/usr/include/graphviz -I/usr/include/python2.7 -c pygraphviz/graphviz_wrap.c -o build/temp.linux-x86_64-2.7/pygraphviz/graphviz_wrap.o
pygraphviz/graphviz_wrap.c:130:21: fatal error: Python.h: Datei oder Verzeichnis nicht gefunden
# include <Python.h>
^
compilation terminated.
error: command 'x86_64-linux-gnu-gcc' failed with exit status 1
----------------------------------------
Command "/usr/bin/python -c "import setuptools, tokenize;__file__='/tmp/pip-build-6yZh3l/pygraphviz/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /tmp/pip-a6o8Fg-record/install-record.txt --single-version-externally-managed --compile" failed with error code 1 in /tmp/pip-build-6yZh3l/pygraphviz
in the end. I would be grateful for any hints how to solve / fix this.
Thanks for the help!
BernWed, 25 Nov 2015 20:42:50 -0600https://ask.sagemath.org/question/31070/Finding all shortest paths between given (specific) pair of verticeshttps://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices.
Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths.
I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.
Thank you for answers!MorgothTue, 09 Jul 2013 00:45:53 -0500https://ask.sagemath.org/question/10332/