Nathann COHEN ALGO Research Group
Laboratoire de Recherche en Informatique
nathann dot cohen 'at' gmail dot com

Sage in Graph Theory

Nathann 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 !


In a few words
Let G be a Graph
What is a Graph good for ?
An example from a newspaper
The greedy coloring algorithm in 6 lines
Some things that you will not need to spend time on

In a few words


Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based 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/links-components.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.




Let G be a Graph


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
            spring-layout 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)





What is a Graph good for ?


Python being an Object-Oriented 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





An example from a newspaper


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 a-b 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(i-j) 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 in 6 lines


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





Some things that you will not need to spend time on


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
    






Get help and documentation


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 Sage-support Google group (here)
  • Sage's documentation page (here), containing for example :
  • Sage's IRC Channel : sage-support@irc.freenode.net
  • and .... do not hesitate to send me an email if you have any question ! ;-)