Network Graphic Objects in SageMath

See here for how to install SageMath:
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)

The above code will print out a description of the Graph/Network connectivity, in case you want the students to draw a network from a description.

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()

The above will create an image of the graph that you can copy and paste into a document. Unfortunately the options dictionary needs to be this long as 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)

finds the minimal weighted path between two nodes, using the edge labels as distances.

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

finds the maximum flow between two nodes using the edge labels for capacity, and also shows the flow network. Now the frustrating thing is, that my school's Maths A textbooks does vertex-limited flow problems, when everyone else in the world (including SageMath) uses edge-limited flow problems. :(

A.degree('C')

finds the degree of vertex/node 'C'

A.degree_histogram()

returns a list of numbers that represents the number of vertex/nodes with
[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"

The second line of this code uses a nice feature of python called list comprehensions. Basically the range(1,len(degrees),2) returns a list of odd numbers (1,3,5,etc).
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()

generates the minimal spanning tree, prints out it's total length and plots it.

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.