CoCalc -- Collaborative Calculation in the Cloud
Sharedsage_worksheets / pythongsage_appendix.sagewsOpen in CoCalc

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.

%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.


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):
    for k in B:
        if k+1 in B:
    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.

[True, False]

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

for B in power_set:
    if valid(B):


%html <h2>Dictionaries</h2>


Consider the following

fruit_color['Red']=['apple','pomegranate','blood orange']

{'Purple': ['plum', 'grape'], 'Orange': ['orange', 'pineapple'], 'Green': ['apple', 'pear', 'grape', 'lime'], 'Yellow': ['banana', 'apple', 'lemon'], 'Red': ['apple', 'pomegranate', 'blood orange']}
['Purple', 'Orange', 'Green', 'Yellow', 'Red']
if 'Red' in fruit_color:
['apple', 'pomegranate', 'blood orange', 'raspberry']
[['plum', 'grape'], ['orange', 'pineapple'], ['apple', 'pear', 'grape', 'lime'], ['banana', 'apple', 'lemon'], ['apple', 'pomegranate', 'blood orange', 'raspberry']]
[('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:

['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']]
for c in fruit_color.keys():
{'Purple': (-5, 0), 'Orange': (-5, 1), 'Green': (-5, 2), 'Red': (-5, 4), 'Yellow': (-5, 3)}
for v in fruit_color.values():
for f in fruits:
{'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)}

from sage.plot.colors import rainbow

for hue in mlibcolor:
    e_colors[hue]=filter(lambda ed:ed[0]==mlibcolor[hue],eds)
{'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)]}
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/", 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/", line 3594, in displayhook show(obj) File "/cocalc/lib/python2.7/site-packages/smc_sagews/", line 2678, in show s = show0(objs, combine_all=True) File "/cocalc/lib/python2.7/site-packages/smc_sagews/", line 2639, in show0 b = show0(a) File "/cocalc/lib/python2.7/site-packages/smc_sagews/", line 2606, in show0 show_2d_plot_using_matplotlib(obj, svg=svg, **kwds) File "/cocalc/lib/python2.7/site-packages/smc_sagews/", line 2434, in show_2d_plot_using_matplotlib, **kwds) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/misc/", line 483, in wrapper return func(*args, **kwds) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/", line 3147, in save figure = self.matplotlib(**options) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/", line 2598, in matplotlib g._render_on_subplot(subplot) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/plot/", 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/", line 349, in rgbcolor raise ValueError("unknown color '%s'" % c) ValueError: unknown color 'R(0)'
File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/misc/
Signature : DiGraph(fruit_color).plot(self, **kwds)
Docstring :
Returns a graphics object representing the (di)graph.


* "pos" - an optional positioning dictionary

* "layout" - what kind of layout to use, takes precedence over

     * '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

* "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 (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

* "edge_colors" - a dictionary specifying edge colors: each key
  is a color recognized by matplotlib, and each entry is a list of

* "partition" - a partition of the vertex set. if specified, plot
  will show each cell in a different color. vertex_colors takes

* "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


  * This method supports any parameter accepted by

  * 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.


   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: C = graphs.CubeGraph(8)
   sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True)

   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: G = graphs.PetersenGraph()
   sage: G.allow_loops(True)
   sage: G.add_edge(0,0)

   sage: D = DiGraph({0:[0,1], 1:[2], 2:[3]}, loops=True)

   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()
   sage: G = DiGraph()
   sage: P = G.plot()
   sage: P.axes()

   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)
%html <h2>
    Truth Tables