Sage in Graph TheoryNathann Cohen nathann (this round thing) cohen (the weird 'a') gmail (same round thing) com
Sage will not solve your graph problems in polynomial time. But everything that is already written, YOU do not have to write it again !
Sage is a free opensource
mathematics software system licensed under the GPL. It combines the
power of many existing opensource packages into a
common Pythonbased interface.
Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and
Matlab.
Motto : Build the car without reinventing the wheel
Sage is based upon Python and uses a plethora of other softwares specialized in mathematics.
http://www.sagemath.org/linkscomponents.html
Practically, it means that Sage is an attempt to unite many dedicated pieces of code, developped independantly by researchers or engineers around the world, into a common library. It also means, for example, that each one of these pieces of code is independently debugged, improved, and developped by their respective authors and the communities around them, Sage always benefiting from this huge amount of work. Conversely, the best way to add new features to Sage can be to directly participate to the development of these others softwares. It also helps to find bugs in those modules, which are reported back to the respective projects to improve them further.
Quickly :
 Sage runs under Linux, Mac and Windows
 You can use Sage for both numerical and symbolic computations
 Sage is Open Source
 You can read any piece of code you may be interested in
 You can modify any piece of code if you think you can do better
 You can add any function you think could be useful
 You can use Sage through Python
 You do not need to learn a new one if you know it already
 If you do not, well.. You will be learning two tools at the same time !
And best of all, Sage is FULL of Graph Theoretic functions you can use, along with combinatorics, number theory, algebra, etc ...
If you do not know Python yet, you will find interesting things to read at this address.
Sage behaves exactly as a Shell on Linux or Mac would. You can use the arrows to walk through the commands you type, and even search through them with Ctrl+R. Most importantly, you can use tab completion
Type in Sage:
sage: graphs.
Then hit two times the Tabulation key on your keyboard. What you get is the list of Graphs that Sage knows how to build :
    
graphs.BalancedTree   graphs.FlowerSnark   graphs.OddGraph 
graphs.BarbellGraph   graphs.FruchtGraph   graphs.PappusGraph 
graphs.BubbleSortGraph   graphs.GeneralizedPetersenGraph   graphs.PathGraph 
graphs.BullGraph   graphs.Grid2dGraph   graphs.PetersenGraph 
graphs.ChvatalGraph   graphs.GridGraph   graphs.RandomBarabasiAlbert 
graphs.CirculantGraph   graphs.HanoiTowerGraph   graphs.RandomBipartite 
graphs.CircularLadderGraph   graphs.HeawoodGraph   graphs.RandomGNM 
graphs.ClawGraph   graphs.HexahedralGraph   graphs.RandomGNP 
graphs.CompleteBipartiteGraph   graphs.HigmanSimsGraph   graphs.RandomHolmeKim 
graphs.CompleteGraph   graphs.HoffmanSingletonGraph   graphs.RandomInterval 
graphs.CubeGraph   graphs.HouseGraph   graphs.RandomLobster 
graphs.CycleGraph   graphs.HouseXGraph   graphs.RandomNewmanWattsStrogatz 
graphs.DegreeSequence   graphs.HyperStarGraph   graphs.RandomRegular 
graphs.DegreeSequenceBipartite   graphs.IcosahedralGraph   graphs.RandomShell 
graphs.DegreeSequenceConfigurationModel   graphs.KneserGraph   graphs.RandomTreePowerlaw 
graphs.DegreeSequenceExpected   graphs.KrackhardtKiteGraph   graphs.StarGraph 
graphs.DegreeSequenceTree   graphs.LCFGraph   graphs.TetrahedralGraph 
graphs.DesarguesGraph   graphs.LadderGraph   graphs.ThomsenGraph 
graphs.DiamondGraph   graphs.LollipopGraph   graphs.ToroidalGrid2dGraph 
graphs.DodecahedralGraph   graphs.MoebiusKantorGraph   graphs.WheelGraph 
graphs.DorogovtsevGoltsevMendesGraph   graphs.NKStarGraph   graphs.WorldMap 
graphs.EmptyGraph   graphs.NStarGraph   graphs.nauty_geng 
graphs.FibonacciTree   graphs.OctahedralGraph   graphs.trees 
To learn how to generate, for example, a random graph on 10 vertices with edge probability 0.5, you can just add a question mark at the end of the function's name :
sage: graphs.RandomGNP?
Definition: graphs.RandomGNP(self, n, p, seed=None, fast=True)
Docstring:
Returns a Random graph on `n` nodes. Each edge is inserted
independently with probability `p`.
IMPLEMENTATION: This function calls the NetworkX function
``fast_gnp_random_graph``, unless fast==False, then
``gnp_random_graph``.
REFERENCES:
 [1] P. Erdos and A. Renyi, On Random Graphs, Publ.
Math. 6, 290 (1959).
 [2] E. N. Gilbert, Random Graphs, Ann. Math.
Stat., 30, 1141 (1959).
PLOTTING: When plotting, this graph will use the default
springlayout algorithm, unless a position dictionary is
specified.
EXAMPLES: We show the edge list of a random graph on 6 nodes with
probability `p = .4`::
sage: graphs.RandomGNP(6, .4).edges(labels=False)
[(0, 1), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5)]
We plot a random graph on 12 nodes with probability
`p = .71`::
sage: gnp = graphs.RandomGNP(12,.71)
sage: gnp.show() # long time
Without exceptions, all the commands you will find in Sage are documented ( you but have to type '?' to read it ), and contain examples of how to use them !
We can now create our random graph with the following command :
sage: # Let G be a Graph !
sage: G = graphs.RandomGNP(10,.5)
Python being an ObjectOriented programming language, you will access all of your graph's methods with the famous ".". As previously, by hitting Tabulation two times in a row, you can list Sage's most standard graph functions :
sage: # Let G be a Graph !
sage: G = graphs.RandomGNP(10,.5)
sage: # We can now list its methods ( functions ) with the Tabulation key
sage: G.
And here is what you get :
    
g.add_cycle   g.distance_all_pairs   g.loop_edges 
g.add_edge   g.distance_graph   g.loop_vertices 
g.add_edges   g.dominating_set   g.loops 
g.add_path   g.dump   g.matching 
g.add_vertex   g.dumps   g.max_cut 
g.add_vertices   g.eccentricity   g.max_weight_matching 
g.adjacency_matrix   g.edge_boundary   g.merge_vertices 
g.all_paths   g.edge_connectivity   g.min_spanning_tree 
g.allow_loops   g.edge_cut   g.minimum_outdegree_orientation 
g.allow_multiple_edges   g.edge_disjoint_paths   g.minor 
g.allows_loops   g.edge_iterator   g.multiple_edges 
g.allows_multiple_edges   g.edge_label   g.name 
g.am   g.edge_labels   g.neighbor_iterator 
g.antisymmetric   g.edges   g.neighbors 
g.automorphism_group   g.edges_incident   g.networkx_graph 
g.average_distance   g.eigenspaces   g.num_edges 
g.bipartite_color   g.eigenvectors   g.num_verts 
g.bipartite_sets   g.eulerian_circuit   g.number_of_loops 
g.blocks_and_cut_vertices   g.eulerian_orientation   g.order 
g.breadth_first_search   g.feedback_edge_set   g.periphery 
g.canonical_label   g.feedback_vertex_set   g.plot 
g.cartesian_product   g.flow   g.plot3d 
g.categorical_product   g.genus   g.radius 
g.category   g.get_boundary   g.random_edge 
g.center   g.get_embedding   g.random_subgraph 
g.centrality_betweenness   g.get_pos   g.random_vertex 
g.centrality_closeness   g.get_vertex   g.relabel 
g.centrality_degree   g.get_vertices   g.remove_loops 
g.characteristic_polynomial   g.girth   g.remove_multiple_edges 
g.check_embedding_validity   g.gomory_hu_tree   g.rename 
g.check_pos_validity   g.graph6_string   g.reset_name 
g.chromatic_number   g.graphics_array_defaults   g.save 
g.chromatic_polynomial   g.graphplot   g.set_boundary 
g.clear   g.graphviz_string   g.set_edge_label 
g.clique_complex   g.graphviz_to_file_named   g.set_embedding 
g.clique_maximum   g.has_edge   g.set_latex_options 
g.clique_number   g.has_loops   g.set_planar_positions 
g.cliques   g.has_multiple_edges   g.set_pos 
g.cliques_containing_vertex   g.has_vertex   g.set_vertex 
g.cliques_get_clique_bipartite   g.incidence_matrix   g.set_vertices 
g.cliques_get_max_clique_graph   g.independent_set   g.shortest_path 
g.cliques_maximal   g.independent_set_of_representatives   g.shortest_path_all_pairs 
g.cliques_maximum   g.interior_paths   g.shortest_path_length 
g.cliques_number_of   g.is_bipartite   g.shortest_path_lengths 
g.cliques_vertex_clique_number   g.is_chordal   g.shortest_paths 
g.cluster_transitivity   g.is_circular_planar   g.show 
g.cluster_triangles   g.is_clique   g.show3d 
g.clustering_average   g.is_connected   g.size 
g.clustering_coeff   g.is_directed   g.spanning_trees_count 
g.coarsest_equitable_refinement   g.is_drawn_free_of_edge_crossings   g.sparse6_string 
g.coloring   g.is_equitable   g.spectrum 
g.complement   g.is_eulerian   g.strong_orientation 
g.connected_component_containing_vertex   g.is_forest   g.strong_product 
g.connected_components   g.is_independent_set   g.subgraph 
g.connected_components_number   g.is_isomorphic   g.szeged_index 
g.connected_components_subgraphs   g.is_planar   g.tensor_product 
g.copy   g.is_regular   g.to_directed 
g.cores   g.is_subgraph   g.to_simple 
g.db   g.is_transitively_reduced   g.to_undirected 
g.degree   g.is_tree   g.trace_faces 
g.degree_constrained_subgraph   g.is_vertex_transitive   g.transitive_closure 
g.degree_histogram   g.kirchhoff_matrix   g.transitive_reduction 
g.degree_iterator   g.laplacian_matrix   g.two_factor_petersen 
g.degree_sequence   g.latex_options   g.union 
g.degree_to_cell   g.layout   g.version 
g.delete_edge   g.layout_circular   g.vertex_boundary 
g.delete_edges   g.layout_default   g.vertex_connectivity 
g.delete_multiedge   g.layout_extend_randomly   g.vertex_cover 
g.delete_vertex   g.layout_graphviz   g.vertex_cut 
g.delete_vertices   g.layout_planar   g.vertex_disjoint_paths 
g.density   g.layout_ranked   g.vertex_iterator 
g.depth_first_search   g.layout_spring   g.vertices 
g.diameter   g.layout_tree   g.weighted 
g.disjoint_union   g.lex_BFS   g.weighted_adjacency_matrix 
g.disjunctive_product   g.lexicographic_product   g.wiener_index 
g.distance   g.line_graph   g.write_to_eps 
I discovered Sage when my boss first told me about an enigma he had found in a french newspaper :
What is the maximum size of a set of integers between 1 and 100 such that for any pair (a,b), the difference ab is not a square ?
This problem can be defined as a Graph problem : we create a vertex for each integer, and link two integers if their difference is a square. We but have to find a maximal independent set in this graph !
sage: n=100
sage: g=Graph(n)
sage: carres=[i*i for i in range(sqrt(n))]
sage: edges=[(i,j) for (i,j) in CartesianProduct(range(n),range(n)) if (i!=j and abs(ij) in carres)]
sage: g.add_edges(edges)
sage: g.independent_set()
[2,4,7,9,14,19,21,24,26,31,36,41,48,54,59,69,74,76,81,86,91,93,96,98]
I was really amazed at this point, because I could think of no other way to compute such things so quickly !
The greedy coloring algorithm can be explained in a few words :
 Define a set of colors
 Take each vertex iteratively, and assign to it the smallest color not already taken by one of its neighbors
It is not that harder to explain it to Sage... And it may give you an idea of what an exercise during an Algorithms lecture may look like using Sage :
g = graphs.RandomGNP(100,5/100)
C = Set(xrange(100))
color = {}
for u in g:
interdits = Set([color[v] for v in g.neighbors(u) if color.has_key(v)])
color[u] = min(Cinterdits)
Well first, all of the functions ( around 200 for graphs ) are as much time saved. Now, several examples :
  You want a connected sparse graph on 50 vertices ?
 Generate random graphs until you find one !
sage: while True:
... g = graphs.RandomGNP(50,.1)
... if g.is_connected():
... break
...
sage: print g.is_connected()
True
  You can generate large random graphs, but you would like yours to be planar ?
 You can generate random graphs until you find one, but this will not get you very far... The next thing you can try is looking for a bad minors in your graph, and remove one of their edges iteratively ! (This is obviously not a good way to generate large planar graphs, but it does not take 10 lines, and is, anyway, mainly an excuse to show you how to use Sage !)
sage: g = graphs.RandomGNP(200,6/200)
sage: while True:
... [planar, minor] = g.is_planar(kuratowski = True)
... if planar:
... break
... else:
... g.delete_edge(minor.edges()[0])
...
sage: g.is_planar()
True
sage: # Just to check :)
sage: len(g.coloring()) <= 4
True
  You want to create a Star on 5 vertices whose leaves are complete graphs of size 4,8, 13, 27 ?
 3 steps : Create the disjoint union of your cliques
 Pick one vertex in each of the connected components
 Link it to vertex 1.
sage: g = Graph()
sage: for i in [4,8,13,27]:
... g = g + graphs.CompleteGraph(i)
...
sage: for c in g.connected_components():
... g.add_edge(1,c[0])
sage: g.is_chordal()
True
Yes, it is chordal !
  You would like to save the plottings of 10 differents graphs in different files ?
 All you need is a `for` loop
sage: dir = '/tmp/'
sage: L = [graphs.CompleteGraph(i) for i in range(3,3+10)]
sage: for number, G in enumerate(L):
... G.plot().save(dir+'graph'+str(number)+'.png')
...
sage: ls /tmp/graph*
/tmp/graph0.png /tmp/graph1.png /tmp/graph3.png /tmp/graph5.png /tmp/graph7.png /tmp/graph9.png
/tmp/graph12.png /tmp/graph2.png /tmp/graph4.png /tmp/graph6.png /tmp/graph8.png
  You need to send Graphs to your colleagues. Which format should you chose ?
 Sage supports many different formats. You can read/write in Leda, GML, Yaml, and of course any Matrix is good to define a graph. But the best ones are Sparse6 or Graph6 which translate your graph's structure into a string ! Let us give it a try with the hypercube in 4 dimensions :
sage: g = graphs.CubeGraph(4)
sage: g.sparse6_string()
':O`?Xgf_SsRvL@IePUuRhi^PtUNk}~'
Now, you can send this string by email. When your colleagues get it, they but have to type :
sage: g = Graph(':O`?Xgf_SsRvL@IePUuRhi^PtUNk}~')
sage: g.order()
16
sage: g.size()
32
sage: g.is_regular() and g.is_bipartite() and g.is_vertex_transitive()
True
This was just to show you some functions... But actually you can directly try :
sage: g.is_isomorphic(graphs.CubeGraph(4))
True
Short of the two very useful tips discussed in the previous section (the "Tabulation" key and the question mark "?" at the end of a line), there are three ways to obtain help :
 The Sagesupport Google group (here)
 Sage's documentation page (here), containing for example :
 Sage's IRC Channel : sagesupport@irc.freenode.net
 and .... do not hesitate to send me an email if you have any question ! ;)
