Ask Your Question
2

Sage graph backend

asked 2019-07-16 14:53:34 -0600

elastica gravatar image

updated 2019-07-16 17:58:00 -0600

A Sage graph G has a backend graph (say GG) accessible with the private _backend attribute. The later graph refers to two "C-graphs" (say G1 and G2) accessibles via the c-graph attribute. Some code with a weighted graph G to illustrate my question :

import string
ALPHA = string.ascii_uppercase

n = 10
wedges = [(0, 1, 7.0), (0, 3, 1.0), (0, 9, 9.0), (1, 7, 6.0), (2, 8, 7.0),
          (2, 9, 2.0), (3, 6, 7.0), (4, 9, 5.0), (5, 9, 6.0), (6, 9, 9.0),
          (6, 7, 1.0), (7, 8, 9.0), (7, 9, 5.0), (8, 9, 3.0)]

wedges = [(ALPHA[i], ALPHA[j], 10 * w) for (i, j, w) in wedges]
G = Graph()
G.add_edges(wedges)
G.weighted(True)

for v in G:
    print v, ''.join(G[v])

print

print "G type:", type(G)
print "-----------------------------"
GG = G._backend
print "GG type:", type(GG)
print list(GG.iterator_verts())

print "-----------------------------"
G1, G2 = GG.c_graph()
print "G1 type:", type(G1)
print

for i in range(n):
    print i, ''.join(map(str, G1.out_neighbors(i)))

outputting:

A BDJ
C JI
B AH
E J
D AG
G DJH
F J
I JHC
H BJIG
J AHCIGEF

G type: <class 'sage.graphs.graph.Graph'>
-----------------------------
GG type: <type 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
['A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'J']
-----------------------------
G1 type: <type 'sage.graphs.base.sparse_graph.SparseGraph'>

0 123
1 04
2 07
3 0456789
4 1367
5 36
6 345
7 234
8 3
9 3

The graphs above G, GG and G1 have n=10 vertices. The difference is that G1's vertices are labelled from 0 to n-1. As you can imagine, the two graph G and G1 are isomorphic.

So my question is simple: does anybody know how to access the mapping between the vertice sets?

The documentation explains that two dictionaries vertex_ints and vertex_labels are available to make translation from vertices id to integers and vice-versa, unfortunately, GG.vertex_ints and GG.vertex_labels cause an attribute error.

As you may see, and contrary to what I was expecting, the correpondance is not $i\mapsto G[i]$.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2019-07-17 14:36:42 -0600

vdelecroix gravatar image

The attributes vertex_ints and vertex_labels are Cython attributes. They are declared in c_graph.pxd. In particular, they can not be accessed at Python level.

It is possible to provide access to them, but this requires modifications to the SageMath source code... which you are welcome to provide on the trac server.

edit flag offensive delete link more

Comments

That's unfortunate. Thanks for the answer.

elastica gravatar imageelastica ( 2019-07-17 15:55:38 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-07-16 14:53:34 -0600

Seen: 94 times

Last updated: Jul 17