Ask Your Question

David Coudert's profile - activity

2018-11-27 08:16:48 -0600 received badge  Good Answer (source)
2018-11-27 08:16:48 -0600 received badge  Nice Answer (source)
2018-09-27 04:10:05 -0600 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 -0600 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 -0600 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 -0600 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 -0600 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 -0600 received badge  Supporter (source)
2018-03-18 05:21:32 -0600 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 -0600 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 -0600 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 -0600 received badge  Nice Answer (source)
2017-10-15 09:07:22 -0600 commented question Edge color for undirected multiedge graphs

This is now ticket #24051

2017-09-21 03:39:42 -0600 received badge  Enthusiast
2017-09-16 13:51:52 -0600 received badge  Nice Answer (source)
2017-09-15 00:46:19 -0600 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 -0600 commented question plot graphs with graph in vertices

Ticket 21918 could help...

2017-08-21 19:56:47 -0600 received badge  Enlightened (source)
2017-08-21 19:56:47 -0600 received badge  Good Answer (source)
2017-08-21 11:40:53 -0600 received badge  Nice Answer (source)
2017-08-21 11:08:35 -0600 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 -0600 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 -0600 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 -0600 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 -0600 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 -0600 received badge  Editor (source)
2017-04-28 04:05:16 -0600 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 -0600 received badge  Nice Answer (source)
2016-12-04 11:37:25 -0600 received badge  Teacher (source)
2016-12-04 10:57:06 -0600 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