# Graphs¶

Functions on graphs

slabbe.graph.bispecial_vertices(G)

Return the list of vertices v such that v is bispecial, that is, `G.in_degree(v)>1` but `G.out_degree(v)>1`.

INPUT:

• `G` – digraph

EXAMPLES:

```sage: from slabbe.graph import bispecial_vertices
sage: G = DiGraph([(4,6), (5,6), (6,7), (6,8)], format='list_of_edges')
sage: bispecial_vertices(G)
[6]
sage: G = DiGraph([(6,5), (7,6), (8,6)], format='list_of_edges')
sage: bispecial_vertices(G)
[]
```
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.get_bispecial_vertex(G)

Return a vertex v such that v is bispecial, that is, `G.in_degree(v)>1` but `G.out_degree(v)>1`.

Return `None` if no such vertex is found.

INPUT:

• `G` – digraph

OUTPUT:

a vertex or `None` if no such vertex is found.

EXAMPLES:

```sage: from slabbe.graph import get_bispecial_vertex
sage: G = DiGraph([(4,6), (5,6), (6,7), (6,8)], format='list_of_edges')
sage: get_bispecial_vertex(G)
6
sage: G = DiGraph([(6,5), (7,6), (8,6)], format='list_of_edges')
sage: get_bispecial_vertex(G) is None
True
```
slabbe.graph.get_funnel(G)

Return an edge (u,v) such that u and v are distinct, G.out_degree(u) is 1 and G.in_degree(v) is 1. Return `None` if no such funnel is found.

INPUT:

• `G` – digraph

EXAMPLES:

```sage: from slabbe.graph import get_funnel
sage: G = DiGraph([(str(a),str(a+1)) for a in range(5)], format='list_of_edges')
sage: get_funnel(G)
('0', '1')
```
slabbe.graph.get_left_special_vertex(G)

Return a vertex v such that v is left special but not bispecial, that is, `G.in_degree(v)>1` but `G.out_degree(v)<=1`.

Return `None` if no such vertex is found.

INPUT:

• `G` – digraph

OUTPUT:

a vertex or `None` if no such vertex is found.

EXAMPLES:

```sage: from slabbe.graph import get_left_special_vertex
sage: G = DiGraph([(5,6), (6,7), (6,8)], format='list_of_edges')
sage: get_left_special_vertex(G) is None
True
sage: G = DiGraph([(6,5), (7,6), (8,6)], format='list_of_edges')
sage: get_left_special_vertex(G)
6
```

If there is a bispecial, but no left special it returns `None`:

```sage: G = DiGraph([(2,3),(3,4),(4,2),(2,5),(5,6),(6,2)], format='list_of_edges')
sage: get_left_special_vertex(G) is None
True
```
slabbe.graph.get_right_special_vertex(G)

Return a vertex v such that v is right special but not bispecial, that is, `G.in_degree(v)<=1` but `G.out_degree(v)>1`.

Return `None` if no such vertex is found.

INPUT:

• `G` – digraph

OUTPUT:

a vertex or `None` if no such vertex is found.

EXAMPLES:

```sage: from slabbe.graph import get_right_special_vertex
sage: G = DiGraph([(5,6), (6,7), (6,8)], format='list_of_edges')
sage: get_right_special_vertex(G)
6
sage: G = DiGraph([(6,5), (7,6), (8,6)], format='list_of_edges')
sage: get_right_special_vertex(G) is None
True
```
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, ''), ((i+1)%10, 'plusone')) for i in range(10)])
sage: G.add_edges([((i, ''), ((i+2)%10, 'plustwo')) for i in range(10)])
sage: GG = induced_subgraph(G, lambda v: v[0]%2 == 0)
sage: G
Digraph on 30 vertices
sage: GG
Digraph on 15 vertices
sage: GG.edges()[0]
((0, ''), (2, 'plustwo'), None)
```
slabbe.graph.merge_multiedges(G, label_function=<class '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
```
slabbe.graph.reduce_bispecial_vertices(G, merge_function, filter=None)

Merge all bispecial vertices with its in-neighbor(s) `u` using `merge_function(u,v)` to create the new vertex. Only edges such that `filter(u,v)` is True are kept.

INPUT:

• `G` – digraph

• `merge_function` – function taking two vertices as input and returning a new vertex

• `filter` – function from pair of vertices to boolean (default:`None`), Only creates edges `(u,v)` such that `filter(u,v) is True` are kept. If `None`, then `filter = lambda a,b:True` is used.

OUTPUT:

a digraph

EXAMPLES:

```sage: from slabbe.graph import reduce_left_special_vertices
sage: from slabbe.graph import reduce_bispecial_vertices
sage: edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(2,5),(5,6),(6,7),(7,0)]
sage: edges = [(str(u),str(v)) for (u,v) in edges]
sage: G = DiGraph(edges, format='list_of_edges')
sage: merge_function = lambda u,v:u+v
sage: GG = reduce_left_special_vertices(G, merge_function)
sage: GGG = reduce_bispecial_vertices(GG, merge_function)
sage: sorted((a,b) for (a,b,_) in GGG.edges())
[('3', '4012'),
('4012', '3'),
('4012', '5'),
('5', '6'),
('6', '7012'),
('7012', '3'),
('7012', '5')]
```

It is idempotent:

```sage: GGGG = reduce_bispecial_vertices(GGG, merge_function)
sage: GGGG == GGG
True
```
slabbe.graph.reduce_funnel_edges(G, merge_function)

Reduce a graph by merging all funnel edge.

We say that an edge (u,v) is a “funnel” edge if u is not v and the out degree of u and the in degree of v are both equal to 1.

INPUT:

• `G` – digraph

• `merge_function` – function taking two vertices as input and returning a new vertex

EXAMPLES:

```sage: from slabbe.graph import reduce_funnel_edges
sage: G = DiGraph([(str(a),str(a+1)) for a in range(5)], format='list_of_edges')
sage: merge_function = lambda a,b:a+b
sage: GG = reduce_funnel_edges(G, merge_function)
sage: GG.vertices()
['012345']
```
```sage: G = DiGraph([(str(a),str((a+1)%5)) for a in range(5)], format='list_of_edges')
sage: merge_function = lambda a,b:a+b
sage: GG = reduce_funnel_edges(G, merge_function)
sage: GG.vertices()
['01234']
```

The following result does not seem right:

```sage: w = words.FibonacciWord()[:100]
sage: G = w.rauzy_graph(11)
sage: merge_function = lambda a,b:a+b[-1:]
sage: GG = reduce_funnel_edges(G, merge_function)
sage: GG.vertices()
[word: 01001010010, word: 100101001001, word: 100101001011]
```
slabbe.graph.reduce_left_special_vertices(G, merge_function)

Merge all left special vertices with its in-neighbor(s) `u` using `merge_function(u,v)` to create the new vertex.

INPUT:

• `G` – digraph

• `merge_function` – function taking two vertices as input and returning a new vertex

OUTPUT:

a digraph

EXAMPLES:

```sage: from slabbe.graph import reduce_left_special_vertices
sage: edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(2,5),(5,6),(6,7),(7,0)]
sage: edges = [(str(u),str(v)) for (u,v) in edges]
sage: G = DiGraph(edges, format='list_of_edges')
sage: merge_function = lambda u,v:u+v
sage: GG = reduce_left_special_vertices(G, merge_function)
sage: sorted((a,b) for (a,b,_) in GG.edges())
[('2', '3'),
('2', '5'),
('3', '401'),
('401', '2'),
('5', '6'),
('6', '701'),
('701', '2')]
```

It is idempotent:

```sage: GGG = reduce_left_special_vertices(GG, merge_function)
sage: GGG == GG
True
```
slabbe.graph.reduce_right_special_vertices(G, merge_function)

Merge all right special vertices with its in-neighbor(s) `u` using `merge_function(u,v)` to create the new vertex.

INPUT:

• `G` – digraph

• `merge_function` – function taking two vertices as input and returning a new vertex

OUTPUT:

a digraph

EXAMPLES:

```sage: from slabbe.graph import reduce_right_special_vertices
sage: edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(2,5),(5,6),(6,7),(7,0)]
sage: edges = [(str(u),str(v)) for (u,v) in edges]
sage: G = DiGraph(edges, format='list_of_edges')
sage: merge_function = lambda u,v:u+v
sage: GG = reduce_right_special_vertices(G, merge_function)
sage: sorted((a,b) for (a,b,_) in GG.edges())
[('0', '123'),
('0', '125'),
('123', '4'),
('125', '6'),
('4', '0'),
('6', '7'),
('7', '0')]
```

It is idempotent:

```sage: GGG = reduce_right_special_vertices(GG, merge_function)
sage: GGG == GG
True
```