# Graphs¶

Functions on graphs

slabbe.graph.clean_sources_and_sinks(G)

Return a copy of the graph where every vertices of the graph that have in or out degree 0 is removed (recursively).

EXAMPLES:

sage: from slabbe.graph import clean_sources_and_sinks
sage: L = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,3)]
sage: G = DiGraph(L,format='list_of_edges')
sage: H = clean_sources_and_sinks(G)
sage: H
Digraph on 3 vertices
sage: H.vertices()
[3, 4, 5]

sage: L = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,3),(1,0)]
sage: G = DiGraph(L, format='list_of_edges')
sage: H = clean_sources_and_sinks(G)
sage: H
Digraph on 6 vertices
sage: H.vertices()
[0, 1, 2, 3, 4, 5]

slabbe.graph.digraph_move_label_to_edge(G, label_function=None, loops=True, multiedges=False)

Return a digraph with labels moved from the arrival vertices to corresponding edges.

INPUT:

• G – graph, whose vertices are tuples of the form (vertex, label)
• label_function – function or None, a function to apply to each label
• loops – bool (default: True)
• multiedges – bool (default: False)

EXAMPLES:

sage: G = DiGraph()
sage: G.add_edges([((i, None), ((i+1)%10, 'plusone')) for i in range(10)])
sage: G.add_edges([((i, None), ((i+2)%10, 'plustwo')) for i in range(10)])
sage: G
Digraph on 30 vertices
sage: from slabbe.graph import digraph_move_label_to_edge
sage: digraph_move_label_to_edge(G)
Looped digraph on 10 vertices


Using a function to modify the labels:

sage: f = lambda label:"A"+label
sage: GG = digraph_move_label_to_edge(G, label_function=f)
sage: GG
Looped digraph on 10 vertices
sage: GG.edges()[0]
(0, 1, 'Aplusone')

slabbe.graph.induced_subgraph(G, filter)

Return the induced subdigraph of a digraph keeping only vertices that are map to True by the filter.

INPUT:

• G – graph
• filter – function, a function from vertices to boolean

EXAMPLES:

sage: from slabbe.graph import induced_subgraph
sage: G = DiGraph()
sage: G.add_edges([((i, None), ((i+1)%10, 'plusone')) for i in range(10)])
sage: G.add_edges([((i, None), ((i+2)%10, 'plustwo')) for i in range(10)])
sage: G
Digraph on 30 vertices
sage: GG = induced_subgraph(G, lambda v: v[0]%2 == 0)
sage: GG
Digraph on 15 vertices
sage: GG.edges()[0]
((0, None), (2, 'plustwo'), None)

slabbe.graph.merge_multiedges(G, label_function=<type 'tuple'>)

Return the (di)graph where multiedges are merged into one.

INPUT:

• G – graph
• label_function – function (default:tuple), a function to apply to each list of labels

OUTPUT:

(looped) (di)graph

EXAMPLES:

A digraph:

sage: from slabbe.graph import merge_multiedges
sage: G = DiGraph(multiedges=True)
sage: GG = merge_multiedges(G)
sage: GG
Digraph on 2 vertices
sage: GG.edges()
[(0, 1, ('alpha', 'one', 'two'))]


A graph:

sage: G = Graph(multiedges=True)
sage: GG = merge_multiedges(G)
sage: GG
Graph on 2 vertices
sage: GG.edges()
[(0, 1, ('alpha', 'one', 'two'))]


Using label_function:

sage: fn = lambda L: LatexExpr(','.join(map(str, L)))
sage: GG = merge_multiedges(G, label_function=fn)
sage: GG.edges()
[(0, 1, alpha,one,two)]

slabbe.graph.projection_graph(G, proj_fn, filename=None, verbose=False)

Return the image of a graph under a function on vertices.

INPUT:

• G – graph
• proj_fn – function
• filename – integer (default:None), save the graph to this pdf filename if filename is not None
• verbose – bool (default:False), print a table of data about the projection

EXAMPLES:

sage: from slabbe.graph import projection_graph
sage: g = graphs.PetersenGraph()
sage: g.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: f = lambda i: i % 5
sage: projection_graph(g, f)
Looped multi-digraph on 5 vertices


With verbose information:

sage: projection_graph(g, lambda i:i%4, verbose=True)
Number of vertices   Projected vertices
+--------------------+--------------------+
2                    3
2                    2
3                    1
3                    0
Looped multi-digraph on 4 vertices