Sharedsage_worksheets / pythongsage_appendix.sagewsOpen in CoCalc
Author: Ken Levasseur
Views : 9
Description: Worksheets related to Applied Discrete Structures

Some basic features of Python

Looping over an iterable object

Suppose we want to count the number of subsets of {0,1,2,...,9}\{0,1,2,...,9\} that contain no adjacent elements. First, we will define our universe and its power set. The plan will be to define a function that determines whether a subset is "valid" in the sense that it contains no adjacent elements. Then we will iterate over the subsets, counting the valid ones.

U=Set(range(10)) power_set=U.subsets()
%md We know that the number of subsets will be 2 raised to the number of elements in $U$, which would be $2^{10}=1024$, but let's check.

We know that the number of subsets will be 2 raised to the number of elements in UU, which would be 210=10242^{10}=1024, but let's check.

len(power_set)
1024

The validity check in this case is very simple. For each element, kk, of a set, BB, we ask whether its successor, k+1k+1, is also in the set. If we never get an answer of "True" then we consider the set valid. This function could be edited to define validity in other ways to answer different counting questions.

def valid(B): v=true for k in B: if k+1 in B: v=false break return v

It's always a good idea to test your functions, so here is a list of two tests, one of a valid set and one of an invalid one.

[valid(Set([1,3,5,9])),valid(Set([1,2,4,7,9]))]
[True, False]

Finally we do the counting over our power set, incrementing the count variable with each valid set.

count=0 for B in power_set: if valid(B): count+=1 count
144
%html <h2>Dictionaries</h2>

Dictionaries

Consider the following

fruit_color={} fruit_color['Red']=['apple','pomegranate','blood orange'] fruit_color['Yellow']=['banana','apple','lemon'] fruit_color['Green']=['apple','pear','grape','lime'] fruit_color['Purple']=['plum','grape'] fruit_color['Orange']=['orange','pineapple']
fruit_color
{'Purple': ['plum', 'grape'], 'Orange': ['orange', 'pineapple'], 'Green': ['apple', 'pear', 'grape', 'lime'], 'Yellow': ['banana', 'apple', 'lemon'], 'Red': ['apple', 'pomegranate', 'blood orange']}
fruit_color.keys()
['Purple', 'Orange', 'Green', 'Yellow', 'Red']
if 'Red' in fruit_color: fruit_color['Red']=fruit_color['Red']+['raspberry'] else: fruit_color['Red']=['raspberry'] fruit_color['Red']
['apple', 'pomegranate', 'blood orange', 'raspberry']
fruit_color.values()
[['plum', 'grape'], ['orange', 'pineapple'], ['apple', 'pear', 'grape', 'lime'], ['banana', 'apple', 'lemon'], ['apple', 'pomegranate', 'blood orange', 'raspberry']]
fruit_color.items()
[('Purple', ['plum', 'grape']), ('Orange', ['orange', 'pineapple']), ('Green', ['apple', 'pear', 'grape', 'lime']), ('Yellow', ['banana', 'apple', 'lemon']), ('Red', ['apple', 'pomegranate', 'blood orange', 'raspberry'])]

As an afterthough, we might add the information that a raspberry is red as follows. You have to be careful in that if 'Red' isn't already in the dictionary, it doesn't have a value. This is why we need an if statement.

if 'Red' in fruit_color: fruit_color['Red']=fruit_color['Red']+['raspberry'] else: fruit_color['Red']=['raspberry'] fruit_color['Red']
['apple', 'pomegranate', 'blood orange', 'raspberry', 'raspberry']
for fruit in fruit_color: print [fruit,fruit_color[fruit]]
['Purple', ['plum', 'grape']] ['Orange', ['orange', 'pineapple']] ['Green', ['apple', 'pear', 'grape', 'lime']] ['Yellow', ['banana', 'apple', 'lemon']] ['Red', ['apple', 'pomegranate', 'blood orange', 'raspberry', 'raspberry']]
DiGraph(fruit_color).plot()
color_pos={} k=0 for c in fruit_color.keys(): color_pos[c]=(-5,k) k+=1 color_pos
{'Purple': (-5, 0), 'Orange': (-5, 1), 'Green': (-5, 2), 'Red': (-5, 4), 'Yellow': (-5, 3)}
fruits=Set([]) for v in fruit_color.values(): fruits=fruits.union(Set(v)) k=0 for f in fruits: color_pos[f]=(5,k) k+=1 color_pos
{'blood orange': (5, 0), 'grape': (5, 1), 'apple': (5, 2), 'Purple': (-5, 0), 'plum': (5, 10), 'pomegranate': (5, 3), 'pear': (5, 4), 'Yellow': (-5, 3), 'orange': (5, 7), 'Green': (-5, 2), 'pineapple': (5, 6), 'Orange': (-5, 1), 'lemon': (5, 8), 'raspberry': (5, 9), 'banana': (5, 5), 'Red': (-5, 4), 'lime': (5, 11)}
DiGraph(fruit_color).plot(pos=color_pos,vertex_size=1,edge_style='dashed')
from sage.plot.colors import rainbow R=rainbow(5) mlibcolor={} mlibcolor['R(0)']='Red' mlibcolor['R(1)']='Green' mlibcolor['R(2)']='Yellow' mlibcolor['R(3)']='Orange' mlibcolor['R(4)']='Purple'
fr=DiGraph(fruit_color) eds=fr.edges() e_colors={} for hue in mlibcolor: e_colors[hue]=filter(lambda ed:ed[0]==mlibcolor[hue],eds) e_colors
{'R(0)': [('Red', 'apple', None), ('Red', 'blood orange', None), ('Red', 'pomegranate', None), ('Red', 'raspberry', None), ('Red', 'raspberry', None)], 'R(1)': [('Green', 'apple', None), ('Green', 'grape', None), ('Green', 'lime', None), ('Green', 'pear', None)], 'R(2)': [('Yellow', 'apple', None), ('Yellow', 'banana', None), ('Yellow', 'lemon', None)], 'R(3)': [('Orange', 'orange', None), ('Orange', 'pineapple', None)], 'R(4)': [('Purple', 'grape', None), ('Purple', 'plum', None)]}
DiGraph(fruit_color).plot(pos=color_pos,vertex_size=1,edge_colors=e_colors)
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 3594, in displayhook show(obj) File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 2678, in show s = show0(objs, combine_all=True) File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 2639, in show0 b = show0(a) File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 2606, in show0 show_2d_plot_using_matplotlib(obj, svg=svg, **kwds) File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 2434, in show_2d_plot_using_matplotlib obj.save(t, **kwds) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/misc/decorators.py", line 483, in wrapper return func(*args, **kwds) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/graphics.py", line 3147, in save figure = self.matplotlib(**options) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/graphics.py", line 2598, in matplotlib g._render_on_subplot(subplot) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/arrow.py", line 144, in _render_on_subplot color = to_mpl_color(options['rgbcolor']) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/colors.py", line 349, in rgbcolor raise ValueError("unknown color '%s'" % c) ValueError: unknown color 'R(0)'
DiGraph(fruit_color).plot?
File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/misc/decorators.py Signature : DiGraph(fruit_color).plot(self, **kwds) Docstring : Returns a graphics object representing the (di)graph. INPUT: * "pos" - an optional positioning dictionary * "layout" - what kind of layout to use, takes precedence over pos * 'circular' -- plots the graph with vertices evenly distributed on a circle * 'spring' - uses the traditional spring layout, using the graph's current positions as initial positions * 'tree' - the (di)graph must be a tree. One can specify the root of the tree using the keyword tree_root, otherwise a root will be selected at random. Then the tree will be plotted in levels, depending on minimum distance for the root. * "vertex_labels" - whether to print vertex labels * "edge_labels" - whether to print edge labels. By default, False, but if True, the result of str(l) is printed on the edge for each label l. Labels equal to None are not printed (to set edge labels, see set_edge_label). * "edge_labels_background" - The color of the edge labels background. The default is "white". To achieve a transparent background use "transparent". * "vertex_size" - size of vertices displayed * "vertex_shape" - the shape to draw the vertices, for example ""o"" for circle or ""s"" for square. Whole list is available at http://matplotlib.org/api/markers_api.html. (Not available for multiedge digraphs.) * "graph_border" - whether to include a box around the graph * "vertex_colors" - optional dictionary to specify vertex colors: each key is a color recognizable by matplotlib, and each corresponding entry is a list of vertices. If a vertex is not listed, it looks invisible on the resulting plot (it doesn't get drawn). * "edge_colors" - a dictionary specifying edge colors: each key is a color recognized by matplotlib, and each entry is a list of edges. * "partition" - a partition of the vertex set. if specified, plot will show each cell in a different color. vertex_colors takes precedence. * "talk" - if true, prints large vertices with white backgrounds so that labels are legible on slides * "iterations" - how many iterations of the spring layout algorithm to go through, if applicable * "color_by_label" - a boolean or dictionary or function (default: False) whether to color each edge with a different color according to its label; the colors are chosen along a rainbow, unless they are specified by a function or dictionary mapping labels to colors; this option is incompatible with "edge_color" and "edge_colors". * "heights" - if specified, this is a dictionary from a set of floating point heights to a set of vertices * "edge_style" - keyword arguments passed into the edge-drawing routine. This currently only works for directed graphs, since we pass off the undirected graph to networkx * "tree_root" - a vertex of the tree to be used as the root for the layout="tree" option. If no root is specified, then one is chosen at random. Ignored unless layout='tree'. * "tree_orientation" - "up" or "down" (default is "down"). If "up" (resp., "down"), then the root of the tree will appear on the bottom (resp., top) and the tree will grow upwards (resp. downwards). Ignored unless layout='tree'. * "save_pos" - save position computed during plotting Note: * This method supports any parameter accepted by "sage.plot.graphics.Graphics.show()". * See the documentation of the "sage.graphs.graph_plot" module for information and examples of how to define parameters that will be applied to **all** graph plots. * Default parameters for this method *and a specific graph* can also be set through the "options" mechanism. For more information on this different way to set default parameters, see the help of the "options decorator". * See also the "sage.graphs.graph_latex" module for ways to use LaTeX to produce an image of a graph. EXAMPLES: sage: from sage.graphs.graph_plot import graphplot_options sage: list(sorted(graphplot_options.items())) [...] sage: from math import sin, cos, pi sage: P = graphs.PetersenGraph() sage: d = {'#FF0000':[0,5], '#FF9900':[1,6], '#FFFF00':[2,7], '#00FF00':[3,8], '#0000FF':[4,9]} sage: pos_dict = {} sage: for i in range(5): ....: x = float(cos(pi/2 + ((2*pi)/5)*i)) ....: y = float(sin(pi/2 + ((2*pi)/5)*i)) ....: pos_dict[i] = [x,y] ... sage: for i in range(5, 10): ....: x = float(0.5*cos(pi/2 + ((2*pi)/5)*i)) ....: y = float(0.5*sin(pi/2 + ((2*pi)/5)*i)) ....: pos_dict[i] = [x,y] ... sage: pl = P.plot(pos=pos_dict, vertex_colors=d) sage: pl.show() sage: C = graphs.CubeGraph(8) sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True) sage: P.show() sage: G = graphs.HeawoodGraph() sage: for u,v,l in G.edges(): ....: G.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')') sage: G.plot(edge_labels=True).show() sage: D = DiGraph( { 0: [1, 10, 19], 1: [8, 2], 2: [3, 6], 3: [19, 4], 4: [17, 5], 5: [6, 15], 6: [7], 7: [8, 14], 8: [9], 9: [10, 13], 10: [11], 11: [12, 18], 12: [16, 13], 13: [14], 14: [15], 15: [16], 16: [17], 17: [18], 18: [19], 19: []} , sparse=True) sage: for u,v,l in D.edges(): ....: D.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')') sage: D.plot(edge_labels=True, layout='circular').show() sage: from sage.plot.colors import rainbow sage: C = graphs.CubeGraph(5) sage: R = rainbow(5) sage: edge_colors = {} sage: for i in range(5): ....: edge_colors[R[i]] = [] sage: for u,v,l in C.edges(): ....: for i in range(5): ....: if u[i] != v[i]: ....: edge_colors[R[i]].append((u,v,l)) sage: C.plot(vertex_labels=False, vertex_size=0, edge_colors=edge_colors).show() sage: D = graphs.DodecahedralGraph() sage: Pi = [[6,5,15,14,7],[16,13,8,2,4],[12,17,9,3,1],[0,19,18,10,11]] sage: D.show(partition=Pi) sage: G = graphs.PetersenGraph() sage: G.allow_loops(True) sage: G.add_edge(0,0) sage: G.show() sage: D = DiGraph({0:[0,1], 1:[2], 2:[3]}, loops=True) sage: D.show() sage: D.show(edge_colors={(0,1,0):[(0,1,None),(1,2,None)],(0,0,0):[(2,3,None)]}) sage: pos = {0:[0.0, 1.5], 1:[-0.8, 0.3], 2:[-0.6, -0.8], 3:[0.6, -0.8], 4:[0.8, 0.3]} sage: g = Graph({0:[1], 1:[2], 2:[3], 3:[4], 4:[0]}) sage: g.plot(pos=pos, layout='spring', iterations=0) Graphics object consisting of 11 graphics primitives sage: G = Graph() sage: P = G.plot() sage: P.axes() False sage: G = DiGraph() sage: P = G.plot() sage: P.axes() False sage: G = graphs.PetersenGraph() sage: G.get_pos() {0: (6.12..., 1.0...), 1: (-0.95..., 0.30...), 2: (-0.58..., -0.80...), 3: (0.58..., -0.80...), 4: (0.95..., 0.30...), 5: (1.53..., 0.5...), 6: (-0.47..., 0.15...), 7: (-0.29..., -0.40...), 8: (0.29..., -0.40...), 9: (0.47..., 0.15...)} sage: P = G.plot(save_pos=True, layout='spring') The following illustrates the format of a position dictionary. sage: G.get_pos() # currently random across platforms, see #9593 {0: [1.17..., -0.855...], 1: [1.81..., -0.0990...], 2: [1.35..., 0.184...], 3: [1.51..., 0.644...], 4: [2.00..., -0.507...], 5: [0.597..., -0.236...], 6: [2.04..., 0.687...], 7: [1.46..., -0.473...], 8: [0.902..., 0.773...], 9: [2.48..., -0.119...]} sage: T = list(graphs.trees(7)) sage: t = T[3] sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]}) Graphics object consisting of 14 graphics primitives sage: T = list(graphs.trees(7)) sage: t = T[3] sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]}) Graphics object consisting of 14 graphics primitives sage: t.set_edge_label(0,1,-7) sage: t.set_edge_label(0,5,3) sage: t.set_edge_label(0,5,99) sage: t.set_edge_label(1,2,1000) sage: t.set_edge_label(3,2,'spam') sage: t.set_edge_label(2,6,3/2) sage: t.set_edge_label(0,4,66) sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]}, edge_labels=True) Graphics object consisting of 20 graphics primitives sage: T = list(graphs.trees(7)) sage: t = T[3] sage: t.plot(layout='tree') Graphics object consisting of 14 graphics primitives sage: t = DiGraph('[email protected]??GO??CO??GO??') sage: t.plot(layout='tree', tree_root=0, tree_orientation="up") Graphics object consisting of 22 graphics primitives sage: D = DiGraph({0:[1,2,3], 2:[1,4], 3:[0]}) sage: D.plot() Graphics object consisting of 16 graphics primitives sage: D = DiGraph(multiedges=True,sparse=True) sage: for i in range(5): ....: D.add_edge((i,i+1,'a')) ....: D.add_edge((i,i-1,'b')) sage: D.plot(edge_labels=True,edge_colors=D._color_by_label()) Graphics object consisting of 34 graphics primitives sage: D.plot(edge_labels=True, color_by_label={'a':'blue', 'b':'red'}, edge_style='dashed') Graphics object consisting of 34 graphics primitives sage: g = Graph({}, loops=True, multiedges=True,sparse=True) sage: g.add_edges([(0,0,'a'),(0,0,'b'),(0,1,'c'),(0,1,'d'), ....: (0,1,'e'),(0,1,'f'),(0,1,'f'),(2,1,'g'),(2,2,'h')]) sage: g.plot(edge_labels=True, color_by_label=True, edge_style='dashed') Graphics object consisting of 26 graphics primitives sage: S = SupersingularModule(389) sage: H = S.hecke_matrix(2) sage: D = DiGraph(H,sparse=True) sage: P = D.plot() sage: G=Graph({'a':['a','b','b','b','e'],'b':['c','d','e'],'c':['c','d','d','d'],'d':['e']},sparse=True) sage: G.show(pos={'a':[0,1],'b':[1,1],'c':[2,0],'d':[1,0],'e':[0,0]})
%html <h2> Truth Tables </h2>
bool=['False','True']
cases=tuples(bool,2)