http://australianteacher.blogspot.com.au/2012/12/installing-sage-mathematics-on-windows.html

At the end of this year, my school set our Year 10's some network theory as their last topic for assessment. I quickly needed a way to generate weighted networks for worksheets. Yes, hand-drawn would have worked, but like all things, once you put the effort into making a program, it's only a couple of edits and clicks to make multiple diagrams. Plus this way, I can also use the same SageMath worksheet to generate the answers as well.

*Warning 1: graph objects don't work well in SageMath with typesetting enabled.*

*Warning 2: if you copy and paste the code below into a Sage worksheet, keep in mind that whitespace (tabs and spaces) are important in python.*

The code is as follows:

Firstly, creating the Graph/Network object. This creates bidirectional graphs with letter codes for the nodes/vertices, and a numerical label/weight for each of the edges.

from sage.graphs.graph_plot import GraphPlot set_random_seed(17) A = graphs.RandomGNM(8,14) nodestr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" edges = [] for u,v,l in A.edges(): edges.append((nodestr[u],nodestr[v],randint(1,20))) A = Graph(edges,vertex_labels=True,multiedges=False,weighted=True); A |

The

**set_random_seed**function (note the underscore characters in the code above) enables you to write up a worksheet that will

**reliably**create the same graphs each time you run the worksheet. However, you can get a different graph by changing the 17 inside the brackets to another integer.

The

**graphs.RandomGNM**takes two options. The first sets the number of nodes/vertices (in this case, 8), and the number of edges (in this case 14).

In the second last line, there is a call to

**randint(1,20)**. This will create a random integer between 1 and 20, inclusive. This random integer will be applied as the

**edge label**, which can be used for distance, weight, cost, capacity or any property that you would put on a edge in order to calculate something. Changing the two numbers inside the brackets will result in edges with different ranges of lengths. However, it's usually a good idea to avoid randint(0,something) as this

**will**create some 0 length edges.

If you want decimals for your lengths, the best way is to replace the randint(1,20) with the following: randint(0*10+1,20*10)/10.0. This will create values from 0.1 to 20.0 to one decimal place.

Note that the divide by 10

**.0**is important. Python/SageMath assumes that if you divide an integer by an integer, you want your

**answer**as an

**integer.**This might seem unusual, but python is a professional programming language, and there are plenty of cases where you want to control what type of number a calculation returns.

Changing these values enables you to create a series of networks that you can use for worksheets.

for u,v,l in A.edges(): print "Edge from %s to %s: has a length = %skm" % (u,v,l) |

options = { 'vertex_size':200, 'vertex_labels':True, 'layout':'spring', 'edge_style':'solid', 'edge_color':'grey', 'edge_colors':None, 'edge_labels':True, 'iterations':50, 'tree_orientation':'down', 'heights':None, 'graph_border':False, 'talk':False, 'color_by_label':False, 'partition':None, 'dist':.075, 'max_dist':1.5, 'loop_size':.075} GraphPlot(A,options).show() |

**all**options have to be set if you use this method. However, it has the advantage that once the options dictionary is created, you can use them for all graphs, leading to a consistent set of diagrams.

**Applications**

Here are some things that can be done with the Graph object A.

A.distance('F','H',by_weight=True) |

flow = A.flow('F','H',value_only=False) print "Maximum flow between F and H is %s" % flow[0] GraphPlot(flow[1],options).show() |

A.degree('C') |

A.degree_histogram() |

[0 degree, 1 degree, 2 degree, etc...]. Note that python starts counting from 0. This is because again, python is a professional programming language, and most modern languages have found it causes less problems overall to start from 0, rather than 1.

This and some python programming, can be used to test for traversability:

degrees = A.degree_histogram() odds = sum([degrees[val] for val in range(1,len(degrees),2)]) if (odds == 0) or (odds == 2): print "Network is traversable" else: print "Network is non-traversable" |

Then the [degrees[val] for val in _______] makes another list of the odd-numbered entries in the degrees list, (Number of vertices with 1 degree, 3 degree, 5 degree, etc.).

This list is passed to the sum function and the sum is stored in the variable odds.

If the number of odd-degree vertices equals 0 or 2, the network is traversable. (It's impossible to get 1 odd degree vertex). If not, the network is non-traversable.

Finally, the following:

tree = A.min_spanning_tree() print "Total length of minimum spanning tree is %s" % (sum([val[-1] for val in tree])) GraphPlot(Graph(tree),options).show() |

There are figuratively tons of calculations that Sage can do on Graphs.

Just type in A. (A followed by a dot) then press TAB to get a list of all the functions (Well, technically in this context they're called methods, not functions.)

Then type in A.

*functionname*( then TAB to get a description of the function. Note that the left bracket is important for this to work.

E.g. A.degree( TAB to read a description of the Graph.degree method.

## No comments:

## Post a Comment