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.Mon, 25 Feb 2013 04:36:07 +0100How to get an arbitrary orientation of a graph.https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/**I'VE COMPLETELY REVISED MY QUESTION**
I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.
However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.
**That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.**
Here's what I am trying to work out:
G = graphs.RandomGNP(4,1)
GD = G.to_directed() #orients G
m = GD.size() #number of edges of digraph GD
LG = GD.line_graph() #the line graph of the digraph
IM = identity_matrix(QQ,GD.size())
T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph
var('u') #defines u as a variable
X=IM-u*T #defines a new matrix X
Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function
Z #computes determinant of X
Z.coefficients(u) #extracts coefficients
considering my graph is a complete graph on 4 vertices - the coefficients should be as such:
[coeff,degree of u]
[1,0], [0,1], [0,2],[-8,3],[-2,4]
**NOTE:**
im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4.
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4
**Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want**
![Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after](http://dl.dropbox.com/u/2399196/graph.png)Fri, 22 Feb 2013 20:59:05 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/Comment by fidbc for <p><strong>I'VE COMPLETELY REVISED MY QUESTION</strong> </p>
<p>I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.</p>
<p>However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.</p>
<p><strong>That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.</strong></p>
<p>Here's what I am trying to work out:</p>
<pre><code>G = graphs.RandomGNP(4,1)
GD = G.to_directed() #orients G
m = GD.size() #number of edges of digraph GD
LG = GD.line_graph() #the line graph of the digraph
IM = identity_matrix(QQ,GD.size())
T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph
var('u') #defines u as a variable
X=IM-u*T #defines a new matrix X
Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function
Z #computes determinant of X
Z.coefficients(u) #extracts coefficients
</code></pre>
<p>considering my graph is a complete graph on 4 vertices - the coefficients should be as such: <br/>
[coeff,degree of u] <br/>
[1,0], [0,1], [0,2],[-8,3],[-2,4]</p>
<p><strong>NOTE:</strong> <br/>
im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4. <br/>
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4 <br/>
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4</p>
<p><strong>Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want</strong>
<img alt="Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after" src="http://dl.dropbox.com/u/2399196/graph.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18186#post-id-18186I think the `line_graph` method is correct, so I'll edit the title so it is not misleading.Sat, 23 Feb 2013 09:49:36 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18186#post-id-18186Answer by Nathann for <p><strong>I'VE COMPLETELY REVISED MY QUESTION</strong> </p>
<p>I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.</p>
<p>However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.</p>
<p><strong>That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.</strong></p>
<p>Here's what I am trying to work out:</p>
<pre><code>G = graphs.RandomGNP(4,1)
GD = G.to_directed() #orients G
m = GD.size() #number of edges of digraph GD
LG = GD.line_graph() #the line graph of the digraph
IM = identity_matrix(QQ,GD.size())
T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph
var('u') #defines u as a variable
X=IM-u*T #defines a new matrix X
Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function
Z #computes determinant of X
Z.coefficients(u) #extracts coefficients
</code></pre>
<p>considering my graph is a complete graph on 4 vertices - the coefficients should be as such: <br/>
[coeff,degree of u] <br/>
[1,0], [0,1], [0,2],[-8,3],[-2,4]</p>
<p><strong>NOTE:</strong> <br/>
im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4. <br/>
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4 <br/>
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4</p>
<p><strong>Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want</strong>
<img alt="Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after" src="http://dl.dropbox.com/u/2399196/graph.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?answer=13731#post-id-13731By the way, there's a method called `digraphs.RandomDirectedGNP` that you may like. It will also produce 2-cycles though `:-)`
NathannSat, 23 Feb 2013 03:03:39 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?answer=13731#post-id-13731Answer by fidbc for <p><strong>I'VE COMPLETELY REVISED MY QUESTION</strong> </p>
<p>I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.</p>
<p>However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.</p>
<p><strong>That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.</strong></p>
<p>Here's what I am trying to work out:</p>
<pre><code>G = graphs.RandomGNP(4,1)
GD = G.to_directed() #orients G
m = GD.size() #number of edges of digraph GD
LG = GD.line_graph() #the line graph of the digraph
IM = identity_matrix(QQ,GD.size())
T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph
var('u') #defines u as a variable
X=IM-u*T #defines a new matrix X
Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function
Z #computes determinant of X
Z.coefficients(u) #extracts coefficients
</code></pre>
<p>considering my graph is a complete graph on 4 vertices - the coefficients should be as such: <br/>
[coeff,degree of u] <br/>
[1,0], [0,1], [0,2],[-8,3],[-2,4]</p>
<p><strong>NOTE:</strong> <br/>
im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4. <br/>
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4 <br/>
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4</p>
<p><strong>Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want</strong>
<img alt="Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after" src="http://dl.dropbox.com/u/2399196/graph.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?answer=14585#post-id-14585The line graph you obtain contains cycles of length 2 because the digraph `D` that `to_directed()` returns contains arcs `(x,y)` and `(x,y)` for each edge `xy` in the original graph `G`.
From what you show in your diagram you want the line graph of of `D` minus all the arcs connecting vertices that came from the same edge in `G`. Maybe this will do the job
G=graphs.CompleteGraph(4)
D=G.to_directed()
L=D.line_graph()
L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ])
L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])
Here is what L looks like using this code.
![Line graph minus some arcs.](http://img688.imageshack.us/img688/7189/sage0.png)Fri, 22 Feb 2013 21:58:42 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?answer=14585#post-id-14585Comment by jtaa for <p>The line graph you obtain contains cycles of length 2 because the digraph <code>D</code> that <code>to_directed()</code> returns contains arcs <code>(x,y)</code> and <code>(x,y)</code> for each edge <code>xy</code> in the original graph <code>G</code>.</p>
<p>From what you show in your diagram you want the line graph of of <code>D</code> minus all the arcs connecting vertices that came from the same edge in <code>G</code>. Maybe this will do the job</p>
<pre><code>G=graphs.CompleteGraph(4)
D=G.to_directed()
L=D.line_graph()
L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ])
L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])
</code></pre>
<p>Here is what L looks like using this code.</p>
<p><img alt="Line graph minus some arcs." src="http://img688.imageshack.us/img688/7189/sage0.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18165#post-id-18165Ok, it worked! thanksMon, 25 Feb 2013 04:36:07 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18165#post-id-18165Comment by jtaa for <p>The line graph you obtain contains cycles of length 2 because the digraph <code>D</code> that <code>to_directed()</code> returns contains arcs <code>(x,y)</code> and <code>(x,y)</code> for each edge <code>xy</code> in the original graph <code>G</code>.</p>
<p>From what you show in your diagram you want the line graph of of <code>D</code> minus all the arcs connecting vertices that came from the same edge in <code>G</code>. Maybe this will do the job</p>
<pre><code>G=graphs.CompleteGraph(4)
D=G.to_directed()
L=D.line_graph()
L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ])
L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])
</code></pre>
<p>Here is what L looks like using this code.</p>
<p><img alt="Line graph minus some arcs." src="http://img688.imageshack.us/img688/7189/sage0.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18183#post-id-18183maybe to clarify further: the to_directed() method was ok, as it gave me directed edges and their inverses, however i need a method in which the line graph recognises an edge's inverse and doesn't show a connection with the original edge. i.e. in the line graph edge(x,y) is not connected to edge (y,x) for all x,y in the edge set. Note: I added an image of what i'm after in the original post for further claritySat, 23 Feb 2013 12:03:45 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18183#post-id-18183Comment by jtaa for <p>The line graph you obtain contains cycles of length 2 because the digraph <code>D</code> that <code>to_directed()</code> returns contains arcs <code>(x,y)</code> and <code>(x,y)</code> for each edge <code>xy</code> in the original graph <code>G</code>.</p>
<p>From what you show in your diagram you want the line graph of of <code>D</code> minus all the arcs connecting vertices that came from the same edge in <code>G</code>. Maybe this will do the job</p>
<pre><code>G=graphs.CompleteGraph(4)
D=G.to_directed()
L=D.line_graph()
L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ])
L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])
</code></pre>
<p>Here is what L looks like using this code.</p>
<p><img alt="Line graph minus some arcs." src="http://img688.imageshack.us/img688/7189/sage0.png"/></p>
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18184#post-id-18184When I create a line graph from D as you defined above it doesn't give me representations of the directed edges inverses. I need the inverses of the arbitrarily oriented edges too, but obviously not having an inverse connected to its original edge. Anyway to do that?Sat, 23 Feb 2013 11:00:21 +0100https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/?comment=18184#post-id-18184