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(sort=True)
[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(sort=True)
[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(sort=True)[0]
(0, 1, 'Aplusone')
slabbe.graph.digraphs_with_n_edges(connected=None)

Return the list of directed multigraphs with loops with n edges with no sink nor sources up to graph isomorphisms.

This is an initial naive straight-forward implementation. Something more clever needs to be done to handle 6 edges or more.

INPUT:

  • n_edges – integer

  • connected – bool (defaut: None), if True, returns only those that are connected.

EXAMPLES:

sage: from slabbe.graph import digraphs_with_n_edges
sage: digraphs_with_n_edges(1)
[Looped multi-digraph on 1 vertex]
sage: digraphs_with_n_edges(2)
[Looped multi-digraph on 1 vertex,
 Looped multi-digraph on 2 vertices,
 Looped multi-digraph on 2 vertices]
sage: digraphs_with_n_edges(3)
[Looped multi-digraph on 1 vertex,
 Looped multi-digraph on 2 vertices,
 Looped multi-digraph on 2 vertices,
 Looped multi-digraph on 2 vertices,
 Looped multi-digraph on 3 vertices,
 Looped multi-digraph on 3 vertices,
 Looped multi-digraph on 2 vertices,
 Looped multi-digraph on 3 vertices]
sage: [g.edges(labels=False) for g in digraphs_with_n_edges(3)]
[[(0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (1, 1)],
 [(0, 0), (0, 1), (1, 0)],
 [(0, 0), (0, 1), (1, 1)],
 [(0, 0), (1, 1), (2, 2)],
 [(0, 0), (1, 2), (2, 1)],
 [(0, 1), (0, 1), (1, 0)],
 [(0, 1), (1, 2), (2, 0)]]
sage: len(digraphs_with_n_edges(4)) # long time (10s)
29
sage: len(digraphs_with_n_edges(5)) # not tested (1h)
110
sage: len(digraphs_with_n_edges(6)) # not tested (6d 18h 48min 21s)
509

Note

List [1,3,8,29,110,509] does not exist in OEIS but is almost related to https://oeis.org/A350907 “Number of unlabeled initially connected digraphs with n arcs.”

Those that are connected:

sage: [len(digraphs_with_n_edges(i, connected=True)) for i in range(1,6)] # not tested (<1h)
[1, 2, 5, 18, 71]
sage: [len(digraphs_with_n_edges(i, connected=True)) for i in range(1,7)] # not tested (<7days)
[1, 2, 5, 18, 71, 344]
slabbe.graph.eulerian_paths(G)

Return a sequence of paths covering all edges of the graph exactly once.

INPUT:

  • G – undirected graph

ALGORITHM:

Euler’s Theorem says that (https://en.wikipedia.org/wiki/Eulerian_path):

A connected graph has an Euler cycle if and only if every vertex has even degree.

Therefore, we may construct a partition of the edges of any graph into a union of k paths where k is equal to the number of odd degree vertices divided by 2. The idea is to add an additional dummy vertex and link every odd degree vertex to it and solve for the Eulerian circuit in that even degree graph.

EXAMPLES:

The following graph has two vertices of odd degree. Thus, it has no Eulerian circuit, but it has an Eulerian path:

sage: G = Graph([(0,1), (1,2), (0,3), (3,2), (0,4), (4,2)])
sage: G
Graph on 5 vertices
sage: G.degree()
[3, 2, 3, 2, 2]
sage: G.eulerian_circuit()
False
sage: G.eulerian_circuit(path=True)
[(2, 4, None),
 (4, 0, None),
 (0, 3, None),
 (3, 2, None),
 (2, 1, None),
 (1, 0, None)]
sage: from slabbe.graph import eulerian_paths
sage: eulerian_paths(G)
[[2, 4, 0, 3, 2, 1, 0]]

The following has four odd degree vertices. Thus, it has no Eulerian circuit nor Eulerian paths. But we can cover all the edges with two paths:

sage: G = Graph([(0,1), (1,2), (0,3), (3,2), (0,4), (4,2), (1,4)])
sage: G.eulerian_circuit()
False
sage: G.eulerian_circuit(path=True)
False
sage: eulerian_paths(G)
[[1, 0], [4, 2, 3, 0, 4, 1, 2]]

Works if G is already Eulerian:

sage: G = Graph([(0,1), (1,2), (2,3), (3,4), (4,0)])
sage: eulerian_paths(G)
[[0, 4, 3, 2, 1, 0]]
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.has_claw_decomposition(G, certificate=False)

Return whether a graph has a claw decomposition.

This is an answer to the question posted at https://ask.sagemath.org/question/81610/test-if-a-graph-has-a-claw-decomposition/

INPUT:

  • G – undirected graph

  • certificate – boolean

OUTPUT:

a boolean or 2-tuple (boolean, solution) if certificate is True

EXAMPLES:

sage: from slabbe.graph import has_claw_decomposition
sage: G1 = Graph( [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3),
....: (1, 5), (2, 3), (2, 4), (3, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 8),
....: (6, 10), (7, 9), (7, 11), (8, 9), (8, 10), (9, 11), (10, 11)])
sage: has_claw_decomposition(G1)
False
sage: has_claw_decomposition(G1, certificate=True)
(False, None)
sage: G2 = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
....:    (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)])
sage: has_claw_decomposition(G2)
True
sage: has_claw_decomposition(G2, certificate=True)     # random
(True,
 [[(0, 1), (1, 2), (1, 5)],
  [(0, 3), (1, 3), (3, 5)],
  [(0, 2), (2, 4), (2, 5)],
  [(0, 4), (1, 4), (4, 5)]])
slabbe.graph.has_graph_decomposition(self, G, induced=False, certificate=False)

Return whether a graph has a decomposition into isometric copies of another graph.

This is an answer to the question posted at https://ask.sagemath.org/question/81610/test-if-a-graph-has-a-claw-decomposition/

INPUT:

  • self – undirected graph

  • G – undirected graph

  • induced – boolean (default: False); whether or not to consider only the induced copies of G in self

  • certificate – boolean

OUTPUT:

A boolean or 2-tuple (boolean, solution) if certificate is True

In the latter case, solution is a list of lists of edges.

EXAMPLES:

sage: from slabbe.graph import has_graph_decomposition
sage: G1 = Graph( [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3),
....: (1, 5), (2, 3), (2, 4), (3, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 8),
....: (6, 10), (7, 9), (7, 11), (8, 9), (8, 10), (9, 11), (10, 11)])
sage: claw = graphs.ClawGraph()
sage: has_graph_decomposition(G1, claw)
False
sage: has_graph_decomposition(G1, claw, certificate=True)
(False, None)
sage: G2 = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
....:    (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)])
sage: has_graph_decomposition(G2, claw)
True
sage: has_graph_decomposition(G2, claw, certificate=True)     # random
(True,
 [[(0, 1), (1, 2), (1, 3)],
  [(0, 2), (0, 3), (0, 4)],
  [(1, 4), (2, 4), (4, 5)],
  [(1, 5), (2, 5), (3, 5)]])
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(sort=True)[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: G.add_edge(0,1,'one')
sage: G.add_edge(0,1,'two')
sage: G.add_edge(0,1,'alpha')
sage: GG = merge_multiedges(G)
sage: GG
Digraph on 2 vertices
sage: GG.edges(sort=True)
[(0, 1, ('alpha', 'one', 'two'))]

A graph:

sage: G = Graph(multiedges=True)
sage: G.add_edge(0,1,'one')
sage: G.add_edge(0,1,'two')
sage: G.add_edge(0,1,'alpha')
sage: GG = merge_multiedges(G)
sage: GG
Graph on 2 vertices
sage: GG.edges(sort=True)
[(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(sort=True)
[(0, 1, alpha,one,two)]
slabbe.graph.minimal_eulerian_paths(G, cost=None)

Return a sequence of paths covering all edges of the graph exactly once and minimizing the distance between the end and start of the next path.

INPUT:

  • G – undirected graph

  • cost – function (vertices x vertices -> R) or None. If None, it computes the Euclidean distance between points.

ALGORITHM:

Euler’s Theorem says that (https://en.wikipedia.org/wiki/Eulerian_path):

A connected graph has an Euler cycle if and only if every vertex has even degree.

We add edges between vertices of odd degree (a matching of minimal Euclidean distance). We compute a Euler cycle. We decompose the cycle.

EXAMPLES:

The following graph has two vertices of odd degree. Thus, it has no Eulerian circuit, but it has an Eulerian path:

sage: G = Graph([(0,1), (1,2), (0,3), (3,2), (0,4), (4,2)])
sage: G
Graph on 5 vertices
sage: G.degree()
[3, 2, 3, 2, 2]
sage: G.eulerian_circuit()
False
sage: G.eulerian_circuit(path=True)
[(2, 4, None),
 (4, 0, None),
 (0, 3, None),
 (3, 2, None),
 (2, 1, None),
 (1, 0, None)]
sage: from slabbe.graph import minimal_eulerian_paths
sage: cost = lambda u,v : abs(v-u)
sage: minimal_eulerian_paths(G, cost)
[[(2, 1), (1, 0), (0, 4), (4, 2), (2, 3), (3, 0)]]

The following has four odd degree vertices. Thus, it has no Eulerian circuit nor Eulerian paths. But we can cover all the edges with two paths:

sage: G = Graph([(0,1), (1,2), (0,3), (3,2), (0,4), (4,2), (1,4)])
sage: G.eulerian_circuit()
False
sage: G.eulerian_circuit(path=True)
False
sage: cost = lambda u,v : abs(v-u)
sage: minimal_eulerian_paths(G, cost)       # known bug
[[(4, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 2)], [(1, 0)]]

TODO:

  • the matchings should not be part of the edges of the graph!!

slabbe.graph.minimal_perfect_matching(vertices, cost=None, solver=None, verbose=False)

Return a perfect matching of points minimizing the sum of the cost of all pairs.

INPUT:

  • vertices – list of vertices

  • cost – function (vertices x vertices -> R) or None. If None, it computes the Euclidean distance between points.

  • solver – string (default:None), name of a MILP solver, default is default_mip_solver()

  • verbose – bool (default:False)

OUTPUT:

list of pairs of vertices

EXAMPLES:

sage: from slabbe.graph import minimal_perfect_matching
sage: minimal_perfect_matching([(0,0), (10,0), (0,1), (10,1)])
[((0, 0), (0, 1)), ((10, 0), (10, 1))]
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(sort=True)
[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(sort=False))
[('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(sort=True)
['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(sort=True)
['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(sort=True)
[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(sort=False))
[('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(sort=False))
[('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
slabbe.graph.vertices_in_a_cycle(G, verbose=False)

Return the set of vertices belonging to a cycle.

INPUT:

  • G – digraph

  • verbose – bool (default:False)

OUTPUT:

list or set of vertices

EXAMPLES:

sage: from slabbe.graph import vertices_in_a_cycle
sage: G = DiGraph()
sage: G.add_vertex(0)
sage: vertices_in_a_cycle(G)
[]
sage: vertices_in_a_cycle(G, verbose=True)
ignoring vertex 0 because it has no loop
[]
sage: G = DiGraph(loops=True)
sage: G.add_edge(0, 0)
sage: vertices_in_a_cycle(G)
[0]
sage: D = DiGraph({0:[1, 3], 1:[2], 2:[0,3], 4:[5, 6], 5:[6]})
sage: D.strongly_connected_components()
[[3], [0, 1, 2], [6], [5], [4]]
sage: vertices_in_a_cycle(D)
[0, 1, 2]