line_graph does not handle loops correctly

[davidp]

The line graph of a graph consisting of a single loop should again be
a single loop.

sage: g = DiGraph(matrix([[1]]),format='adjacency_matrix')
sage: g.loops()
[(0, 0, None)]
sage: lg = g.line_graph()
sage: lg.num_edges() # PROBLEM: there should be one
edge
0

My motivation:

The de Bruijn graphs are defined recursively by

DB_n = line_graph(DB_{n-1}), n >= 1

starting with DB_0 the graph with one vertex and two loops. The
number of vertices of DB_n is then 2^n.

sage: DB0 = DiGraph(matrix([[2]]),format='adjacency_matrix')
sage: DB0.loops()
[(0, 0, None), (0, 0, None)]
sage: DB1 = DB0.line_graph()
sage: DB1.num_verts() # there should be 2 vertices
1
sage: DB1.num_edges() # and 4 edges
0

Starting with the correct DB1, which does not have multiple loops,
there is still a problem:

sage: DB1 = DiGraph(matrix([[1,1],[1,1]]),format='adjacency_matrix')
sage: DB2 = DB1.line_graph()
sage: DB2.num_edges() # there should be 8 edges
(loops missing)
6

Dave

[davidp]

Solution?:

The beginning of the code for line_graph:

if self._directed:
G=DiGraph()
G.add_vertices(self.edges(labels=labels))
for v in self:
# Connect appropriate incident edges of the vertex v
G.add_edges([(e,f) for e in self.incoming_edge_iterator
(v, labels=labels) \
for f in self.outgoing_edge_iterator(v,
labels=labels)])
return G

I think that if self.allow_loops() == True, then

G = DiGraph()

should be

G = DiGraph(loops=True)

Dave

[davidp]

But then there is the problem of needing distinct names for the
vertices of the line graph. Thus, line_graph doesn't handle multiple
edges correctly either.

Dave