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 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()[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
– graphfilter
– 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
– graphlabel_function
– function (default:tuple
), a function to apply to each list of labels
OUTPUT:
(looped) (di)graphEXAMPLES:
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() [(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() [(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
– 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() [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