Sharedsage_worksheets / ADS_graphs.sagewsOpen in CoCalc
Author: Ken Levasseur
Description: Worksheets related to Applied Discrete Structures
g=Graph({1:[3,5],2:[4,5],3:[4,5],4:[5],6:[2,4,7]}) g
Graph on 7 vertices
g.plot()
g.degree_sequence()
[4, 4, 3, 3, 3, 2, 1]
g.diameter()
4
g.chromatic_number()
3
g.adjacency_matrix()
[0 0 1 0 1 0 0] [0 0 0 1 1 1 0] [1 0 0 1 1 0 0] [0 1 1 0 1 1 0] [1 1 1 1 0 0 0] [0 1 0 1 0 0 1] [0 0 0 0 0 1 0]
h=graphs.CubeGraph(3) h.plot(layout="spring")

There are two basic search algorithms for graphs, the breadth-first and depth-first searches. Here, we demonstrate the use of both of them. We start with a small, relatively sparse graph after seeding the random number generator.

set_random_seed(1000) r=graphs.RandomGNP(20,0.2) r
RandomGNP(20,0.200000000000000): Graph on 20 vertices
bfs=r.breadth_first_search(0,report_distance="True") list(bfs)
[(0, 0), (2, 1), (13, 1), (7, 2), (15, 2), (3, 3), (19, 3), (8, 3), (14, 3), (5, 3), (11, 3), (6, 4), (9, 4), (1, 4), (16, 4), (4, 4), (10, 4), (18, 4), (12, 5), (17, 5)]

The maximum depth in a breadth-first search will be a lower bound on the diameter of the graph, which is the length of the longest "shortest path" between all vertices.

r.diameter()
5
r.depth_first_search?
File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : r.depth_first_search(self, start, ignore_direction=False, distance=None, neighbors=None) Docstring : Return an iterator over the vertices in a depth-first ordering. INPUT: * "start" - vertex or list of vertices from which to start the traversal * "ignore_direction" - (default False) only applies to directed graphs. If True, searches across edges in either direction. * "distance" - Deprecated. Broken, do not use. * "neighbors" - a function giving the neighbors of a vertex. The function should take a vertex and return a list of vertices. For a graph, "neighbors" is by default the "neighbors()" function of the graph. For a digraph, the "neighbors" function defaults to the "neighbor_out_iterator()" function of the graph. See also: * "breadth_first_search()" * "breadth_first_search" -- breadth-first search for fast compiled graphs. * "depth_first_search" -- depth-first search for fast compiled graphs. EXAMPLES: sage: G = Graph( { 0: [1], 1: [2], 2: [3], 3: [4], 4: [0]} ) sage: list(G.depth_first_search(0)) [0, 4, 3, 2, 1] By default, the edge direction of a digraph is respected, but this can be overridden by the "ignore_direction" parameter: sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.depth_first_search(0)) [0, 3, 6, 7, 2, 5, 1, 4] sage: list(D.depth_first_search(0, ignore_direction=True)) [0, 7, 6, 3, 5, 2, 1, 4] Multiple starting vertices can be specified in a list: sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.depth_first_search([0])) [0, 3, 6, 7, 2, 5, 1, 4] sage: list(D.depth_first_search([0,6])) [0, 3, 6, 7, 2, 5, 1, 4] More generally, you can specify a "neighbors" function. For example, you can traverse the graph backwards by setting "neighbors" to be the "neighbors_in()" function of the graph: sage: D = digraphs.Path(10) sage: D.add_path([22,23,24,5]) sage: D.add_path([5,33,34,35]) sage: list(D.depth_first_search(5, neighbors=D.neighbors_in)) [5, 4, 3, 2, 1, 0, 24, 23, 22] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_in)) [5, 24, 4, 23, 3, 22, 2, 1, 0] sage: list(D.depth_first_search(5, neighbors=D.neighbors_out)) [5, 6, 7, 8, 9, 33, 34, 35] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_out)) [5, 33, 6, 34, 7, 35, 8, 9]
dfs=r.depth_first_search(start=0)
for v in dfs: print v
0 13 7 14 11 15 5 6 12 4 8 10 18 1 9 3 19 16 17 2
r.plot()

How many sequences of n nonnegative integers are graphic?

How many different degree sequences are there for an n vertex undirected graph? Does a degree sequence uniquely determine an undirected graph. For example, is there one graph with four vertices and degree sequence (3,1,1,1)?

rg=graphs.RandomGNP(10,0.5) rg.degree_sequence()
[5, 5, 5, 4, 4, 3, 3, 2, 2, 1]
rg.is_eulerian()
False
set_random_seed(33) rg=graphs.RandomGNP(35,0.2) rg.is_connected()
True
rg.plot()
rg.is_hamiltonian()
True

A spanning subgraph is one for which V(H)=V(G)

g=Graph({1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]}) g.plot(save_pos=True)
posit=g.get_pos() posit
{1: [1.1398183902683194, 0.6323995278931902], 2: [0.7856541282386849, -0.60184354419796], 3: [0.6563870407458304, 0.7114396135611625], 4: [1.2180603090400683, -0.04241945033695333], 5: [0.4220724685685111, 0.16082730175516477], 6: [1.4559346510382543, -0.8604034486746043]}
posit_r={1: [1.1398183902683194, 0.6323995278931902], 2: [0.7856541282386849, -0.60184354419796], 3: [0.6563870407458304, 0.7114396135611625], 4: [1.2180603090400683, -0.04241945033695333], 6: [1.4559346510382543, -0.8604034486746043]}
h1=Graph({1:[3],2:[4],3:[4],6:[2,4]}) p2=h1.show(pos=posit)
h2=Graph({1:[3,5],2:[4,5],3:[4],6:[2]}) h2.plot()
h3=g.spanning_trees()[9] h3.show(pos=posit)
g.spanning_trees()
[Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices]
g=Graph({1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]}) p1=g.plot(save_pos=True) posit=g.get_pos() p1a=g.plot(pos=posit) posit_r=posit posit_r.pop(5) print posit_r h1=Graph({1:[3],2:[4],3:[4],6:[2,4]}) p2=h1.plot(pos=posit_r) h2=Graph({1:[3,5],2:[4,5],3:[4],6:[2]}) p3=h2.plot(pos=posit) h3=g.spanning_trees()[9] p4=h3.plot(pos=posit) fig=graphics_array(((p1a,p2),(p3,p4))) fig
[2.036750636271431, -0.4416564025709533] {1: [2.2499028811170922, 0.4446082077560374], 2: [1.2046076653900806, -0.3894460982436145], 3: [2.4397923296347277, -0.017138018767639592], 4: [1.541880540145284, 0.2585074549460352], 6: [0.7072907912653226, 0.14512485688013455]}
File: /usr/local/sage/sage-6.5/local/lib/python2.7/site-packages/sage/combinat/posets/lattices.py Signature : LatticePoset(*args, **kwds) Docstring : Construct a lattice from various forms of input data. INPUT: * "data", "*args", "**options" -- data and options that will be passed down to "Poset()" to construct a poset that is also a lattice. OUTPUT: FiniteLatticePoset -- an instance of "FiniteLatticePoset" See also: "Posets", "FiniteLatticePosets", "JoinSemiLattice()", "MeetSemiLattice()" EXAMPLES: Using data that defines a poset: sage: LatticePoset([[1,2],[3],[3]]) Finite lattice containing 4 elements sage: LatticePoset([[1,2],[3],[3]], cover_relations = True) Finite lattice containing 4 elements Using a previously constructed poset: sage: P = Poset([[1,2],[3],[3]]) sage: L = LatticePoset(P); L Finite lattice containing 4 elements sage: type(L) <class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'> If the data is not a lattice, then an error is raised: sage: elms = [1,2,3,4,5,6,7] sage: rels = [[1,2],[3,4],[4,5],[2,5]] sage: LatticePoset((elms, rels)) Traceback (most recent call last): ... ValueError: Not a lattice. Creating a facade lattice: sage: L = LatticePoset([[1,2],[3],[3]], facade = True) sage: L.category() Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets sage: parent(L[0]) Integer Ring sage: TestSuite(L).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented
save?
File: /projects/sage/sage-7.3/src/sage/structure/sage_object.pyx Signature : save(obj, filename=None, compress=True, **kwds) Docstring : Save "obj" to the file with name "filename", which will have an ".sobj" extension added if it doesn't have one and if "obj" doesn't have its own "save()" method, like e.g. Python tuples. For image objects and the like (which have their own "save()" method), you may have to specify a specific extension, e.g. ".png", if you don't want the object to be saved as a Sage object (or likewise, if "filename" could be interpreted as already having some extension). Warning: This will *replace* the contents of the file if it already exists. EXAMPLES: sage: a = matrix(2, [1,2,3,-5/2]) sage: objfile = os.path.join(SAGE_TMP, 'test.sobj') sage: objfile_short = os.path.join(SAGE_TMP, 'test') sage: save(a, objfile) sage: load(objfile_short) [ 1 2] [ 3 -5/2] sage: E = EllipticCurve([-1,0]) sage: P = plot(E) sage: save(P, objfile_short) # saves the plot to "test.sobj" sage: save(P, filename=os.path.join(SAGE_TMP, "sage.png"), xmin=-2) sage: save(P, os.path.join(SAGE_TMP, "filename.with.some.wrong.ext")) Traceback (most recent call last): ... ValueError: allowed file extensions for images are '.eps', '.pdf', '.pgf', '.png', '.ps', '.sobj', '.svg'! sage: print(load(objfile)) Graphics object consisting of 2 graphics primitives sage: save("A python string", os.path.join(SAGE_TMP, 'test')) sage: load(objfile) 'A python string' sage: load(objfile_short) 'A python string'
H=matrix(ZZ,[[1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0], [0,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,1]]) T=matrix(ZZ,[[0,0,1,1],[0,1,1,0],[1,1,0,0],[1,0,0,1]]) L=matrix(ZZ,[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1], [1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]) L*(T.transpose())*H
[]
Traceback (most recent call last): File "/projects/sage/sage-7.3/local/lib/python2.7/site-packages/smc_sagews/sage_parsing.py", line 423, in introspect O = eval(obj if not preparse else preparse_code(obj), namespace) File "<string>", line 1, in <module> NameError: name 'export' is not defined
[0 0 1 1 0 0 1 1] [0 1 1 0 0 1 1 0] [1 1 0 0 1 1 0 0] [1 0 0 1 1 0 0 1] [0 0 1 1 0 0 1 1] [0 1 1 0 0 1 1 0] [1 1 0 0 1 1 0 0] [1 0 0 1 1 0 0 1]
H=matrix(ZZ,[[1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0], [0,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,1]])
H
[1 0 0 0 1 0 0 0] [0 1 0 0 0 1 0 0] [0 0 1 0 0 0 1 0] [0 0 0 1 0 0 0 1]
L
[1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]
T
[0 0 1 1] [0 1 1 0] [1 0 0 1]
L*(T.transpose())
[0 0 1] [0 1 0] [1 1 0] [1 0 1] [0 0 1] [0 1 0] [1 1 0] [1 0 1]
T.transpose()*H
Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 947, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "sage/structure/element.pyx", line 2900, in sage.structure.element.Matrix.__mul__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/element.c:22510) return coercion_model.bin_op(left, right, mul) File "sage/structure/coerce.pyx", line 1069, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/coerce.c:9736) raise TypeError(arith_error_message(x,y,op)) TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 4 by 3 dense matrices over Integer Ring' and 'Full MatrixSpace of 4 by 8 dense matrices over Integer Ring'
C = Matrix(RR,[[5,1,2,1,2],[3,1,-2,0,5],[1,1,3,-1,-1]]) C.echelon_form()
[ 1.00000000000000 0.000000000000000 0.000000000000000 0.500000000000000 0.500000000000000] [ 0.000000000000000 1.00000000000000 0.000000000000000 -1.50000000000000 1.50000000000000] [ 0.000000000000000 0.000000000000000 1.00000000000000 4.93432455388958e-17 -1.00000000000000]
seq=[5,5,4,3,2,1]
graphs.DegreeSequence([5,3,2,2,2,2]).show()
graphs.CubeGraph(3).show(layout="spring",vertex_size=0)
g=graphs.CubeGraph(3)
g.show?
File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.show(self, method='matplotlib', **kwds) Docstring : Shows the (di)graph. INPUT: * "method" -- set to ""matplotlib"" (default) to display the graph using matplotlib, or to ""js"" to visualize it in a browser using d3.js. * Any other argument supported by the drawing functions: * ""matplotlib"" -- see "GenericGraph.plot" and "sage.plot.graphics.Graphics.show()". * ""js"" -- see "gen_html_code()". EXAMPLES: sage: C = graphs.CubeGraph(8) sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True) sage: P.show() # long time (3s on sage.math, 2011)