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.Tue, 14 Sep 2021 11:50:29 +0200Working 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/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/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/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/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/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 20:19:26 +0200https://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?k1monfaredThu, 13 Apr 2017 03:55:30 +0200https://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 09:12:08 +0100https://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 22:44:40 +0100https://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 18:29:51 +0100https://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 13:05:38 +0100https://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 21:15:24 +0200https://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 22:31:21 +0100https://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 22:18:52 +0200https://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 15:01:31 +0200https://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 21:21:14 +0200https://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 23:08:03 +0200https://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 17:25:08 +0200https://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 10:44:18 +0200https://ask.sagemath.org/question/33363/