Ask Your Question

David Coudert's profile - activity

2019-03-13 03:44:59 -0500 answered a question Number of neighbors of a set of vertices in a graph

You want the vertex boundary of a set of vertices.

sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.CycleGraph(4)
sage: t = polygen(ZZ, 't')
sage: sum(t^len(G.vertex_boundary(x)) for x in IndependentSets(G))
6*t^2 + 1
2019-03-13 03:31:22 -0500 answered a question Generating plane triangulations

plantri is an optional package that you can install using

sage -i plantri

You will then be able to use the iterator over connected planar triangulations

sage: list(graphs.triangulations(6))
[Graph on 6 vertices, Graph on 6 vertices]
sage: all(g.is_planar() for g in graphs.triangulations(10))
True
2018-11-27 08:16:48 -0500 received badge  Good Answer (source)
2018-11-27 08:16:48 -0500 received badge  Nice Answer (source)
2018-09-27 04:10:05 -0500 commented answer Why does this error arise?

See for instance This stackoverflow discussion for understanding the use and meaning of _. Here I used it to mean that we don't care of that value.

Concerning your code, you remove vertices of the graph in the while loop. In the end, the graph is empty, and so G.show() has nothing to display.

2018-09-25 06:26:21 -0500 answered a question Why does this error arise?

Consider the following code. It follows the description of your relabeling method (I'm not sure of what you really want to get). I can display the relabeled graph.

def relabeling(G):
    deg = sorted([(d,u) for u,d in G.degree_iterator(labels=True)], key=lambda x: x[0], reverse=True)
    L = dict()
    k = 0
    for _,u in deg:
        if u in L:
            # The vertex has already been labeled
            continue
        L[u] = k
        k += 1
        for v in G.neighbor_iterator(u):
            if v in L:
                # v has already been labeled
                continue
            L[v] = k
            k += 1
    H = G.relabel(perm=L, inplace=False)
    return H

G = graphs.RandomGNM(10,20)
H = relabeling(G)
H.show()
2018-09-24 11:47:00 -0500 commented question Why does this error arise?

You remove vertices from the list v, but not from the graph. So you may later add a vertex j to the list s that has already been removed from v.

2018-09-05 10:48:02 -0500 answered a question How to find the spanning elementary subgraphs of a given graph

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

2018-08-28 04:51:34 -0500 commented question Why can't I find the spectral radius of a tree?

There is a bug in this method for trees. Thank you for reporting the issue. This is now ticket #26148.

2018-04-15 11:55:14 -0500 received badge  Supporter (source)
2018-03-18 05:21:32 -0500 answered a question Graph structure having maximum algebraic connectivity among some given blocks

You have two approaches to solve this exercise:

  1. Using Sagemath: generate all blocks (=biconnected graphs) of order k=3..n using graphs.nauty_geng("k -C"), then for each combination of 4 of them build a block graph with the required structure, compute its algebraic connectivity and record the maximum value.
  2. Using a sheet of paper: read carefully the definition of algebraic connectivity to understand what maximizes this value (hint: check the lower bounds), deduce the biconnected graph with maximum algebraic connectivity, use it to build the block graph you need, and finally prove that this graph answers your question (short proof). You can afterward use Sagemath to compute its algebraic connectivity.
2018-03-04 06:05:25 -0500 commented question Getting all non-backtracking walks of certain length in isogeny graph

Could you please define "non-backtracking walk".

2018-02-09 06:28:54 -0500 commented question To find trees having certain properties from a collection of trees on given number of vertices

This is good class exercise to learn how to manipulate graphs with SageMath and NetworkX.

2017-11-07 06:52:13 -0500 received badge  Nice Answer (source)
2017-10-15 09:07:22 -0500 commented question Edge color for undirected multiedge graphs

This is now ticket #24051

2017-09-21 03:39:42 -0500 received badge  Enthusiast
2017-09-16 13:51:52 -0500 received badge  Nice Answer (source)
2017-09-15 00:46:19 -0500 answered a question Line graph of a given graph

The vertices of the line_graph are the edges of the graph, including edge labels by default. If you don't want the labels, you can do:

sage: G = Graph([(2,3),(2,4),(2,1),(1,5),(5,6),(1,0),(0,12),(0,13),(14,0),(15,0),(7,0),(7,10),(11,7),(7,9),(7,8)])
sage: h = G.line_graph(labels=False)

Then you can either use the method that has already been proposed here, or use the Javascript plotting (it's better to increase the link distance).

sage: h.show(method='js',link_distance=100)
2017-09-01 03:30:38 -0500 commented question plot graphs with graph in vertices

Ticket 21918 could help...

2017-08-21 19:56:47 -0500 received badge  Enlightened (source)
2017-08-21 19:56:47 -0500 received badge  Good Answer (source)
2017-08-21 11:40:53 -0500 received badge  Nice Answer (source)
2017-08-21 11:08:35 -0500 answered a question Changing the weights in a graph

You can use the set_edge_label

sage: G = graphs.PetersenGraph()
sage: print G.edges()
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None), (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]
sage: i = 0
sage: for u,v in G.edges(labels=0):
....:     G.set_edge_label(u, v, i)
....:     i += 1
sage: print G.edges()
[(0, 1, 0), (0, 4, 1), (0, 5, 2), (1, 2, 3), (1, 6, 4), (2, 3, 5), (2, 7, 6), (3, 4, 7), (3, 8, 8), (4, 9, 9), (5, 7, 10), (5, 8, 11), (6, 8, 12), (6, 9, 13), (7, 9, 14)]
2017-05-22 02:09:25 -0500 commented question Why is Sage calling 1 a variable?

The error message is local variable 'l' referenced before assignment. It's variable l (small cap L), not 1. I have reported the issue on sage-dev.

2017-05-19 07:40:07 -0500 answered a question Iterate over acyclic subdigraphs

This is certainly not an easy question and I have no better algorithm in mind.

I recommend to use Permutations(D.vertices()) instead. This is safer for instance if you remove vertex 0.

Furthermore, with your code you may generate multiple times the same acyclic orientation.

sage: D = DiGraph(graphs.PathGraph(3))
sage: print D.edges(labels=0)
[(0, 1), (1, 0), (1, 2), (2, 1)]
sage: for p in Permutations(D.vertices()):
....:     A = DiGraph([(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]])
....:     print A.edges(labels=0)
....:     
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 1), (1, 2)]

One solution is to keep track of previous sets of edges, but this is certainly not scalable. I'm using type Set since it is hashable.

sage: D = DiGraph(graphs.PathGraph(3))
sage: orientations = set()
sage: for p in Permutations(D.vertices()):
....:     E = [(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]]
....:     SE = Set(E)
....:     if SE in orientations:
....:         continue
....:     orientations.add(SE)
....:     A = DiGraph(E)
....:     print A.edges(labels=0)
....:     
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]

For the example you gave, your code generates 5040 graphs while my code generates only 4055 graphs.

2017-04-29 03:03:54 -0500 commented answer Random block graph

The first proposed method starts building a random tree with m edges and then replaces each edge with a k-clique. It is effectively not sufficient to get all possible random block graphs. I have added a new version that starts with a random tree with m vertices, replaces each vertex by a k-clique and then connect blocks corresponding to tree edges. This way we can get all possible random block graphs.

2017-04-29 02:55:19 -0500 commented answer Random block graph

You are right, add_clique is a recent addition. I have edited my answer in case you don't have it.

2017-04-29 02:50:34 -0500 received badge  Editor (source)
2017-04-28 04:05:16 -0500 answered a question Random block graph

Recall that a block graph is a graph in which every biconnected component is a clique.

A simple method to generate a connected block graph with m blocks of size k is to start from a random tree with m edges and then replace each edge by a clique of order k:

def RandomBlockGraph(m, k):
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        G.add_clique([u,v] + [G.add_vertex() for i in range(k-2)])
    return G

The add_clique method is a recent addition to sagemath. If you don't have it, you can do

def RandomBlockGraph(m, k):
    import itertools
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        V = [u,v] + [G.add_vertex() for i in range(k-2)]
        for x,y in itertools.combinations(V, 2):
            G.add_edge(x, y)
    return G

A call to G.add_vertex() adds an isolated vertex to the graph. You then add the edges of the clique.

EDIT: The method below starts with a random tree of order m. Then it creates a graph with one k-clique (block) per vertex of the tree. We connect blocks corresponding to end vertices of tree edges. To do so, we select one vertex per block and merge the two selected vertices. We use a disjoint set data structure to keep track of the merge operations and so get a unique identifier per set of merged vertices.

def RandomBlockGraph(m, k):
    import itertools
    import random

    # We start with a random tree of order m
    T = graphs.RandomTree(m)

    # We create a block of size k per vertex of the tree
    B = {u:[(u,i) for i in range(k)] for u in T}

    # For each edge of the tree, we choose 1 vertex in each of the corresponding
    # blocks and we merge them. We use a disjoint set data structure to keep a
    # unique identifier per merged vertices
    DS = DisjointSet([i for u in B for i in B[u]])
    for u,v in T.edges(labels=0):
        DS.union(random.choice(B[u]), random.choice(B[v]))

    # We finally build the block graph
    BG = Graph()
    for u in B:
        for x,y in itertools.combinations(B[u], 2):
            BG.add_edge(DS.find(x), DS.find(y))

    return BG
2016-12-04 17:04:35 -0500 received badge  Nice Answer (source)
2016-12-04 11:37:25 -0500 received badge  Teacher (source)
2016-12-04 10:57:06 -0500 answered a question The interval I(u,v) between a pair of vertices u,v in graph

This will be faster to compute all intervals at once.

def intervals(g):
    import itertools
    dist = g.distance_all_pairs()
    intervals = dict()
    for u,v in itertools.combinations(g.vertices(), 2):
        intervals[u,v] = list()
        for w in g.vertices():
            if u!=w and v!=w and dist[u][v]==dist[u][w]+dist[w][v]:
                intervals[u,v].append(w)
        intervals[v,u] = copy(intervals[u,v])
    return intervals