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
butG.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 labelloops
– 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
– integerconnected
– bool (defaut:None
), ifTrue
, 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
butG.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
butG.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
butG.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 graphcertificate
– 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 graphG
– undirected graphinduced
– boolean (default:False
); whether or not to consider only the induced copies ofG
inself
certificate
– boolean
OUTPUT:
A boolean or 2-tuple
(boolean, solution)
if certificate isTrue
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
– graphfilter
– 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
– graphlabel_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 graphcost
– function (vertices x vertices -> R) orNone
. IfNone
, 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 verticescost
– function (vertices x vertices -> R) orNone
. IfNone
, it computes the Euclidean distance between points.solver
– string (default:None
), name of a MILP solver, default isdefault_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
– graphproj_fn
– functionfilename
– integer (default:None
), save the graph to this pdf filename if filename is not Noneverbose
– 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
usingmerge_function(u,v)
to create the new vertex. Only edges such thatfilter(u,v)
is True are kept.INPUT:
G
– digraphmerge_function
– function taking two vertices as input and returning a new vertexfilter
– function from pair of vertices to boolean (default:None
), Only creates edges(u,v)
such thatfilter(u,v) is True
are kept. IfNone
, thenfilter = 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
– digraphmerge_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
usingmerge_function(u,v)
to create the new vertex.INPUT:
G
– digraphmerge_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
usingmerge_function(u,v)
to create the new vertex.INPUT:
G
– digraphmerge_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
– digraphverbose
– 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]