Sage in Graph Theory

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

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

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.

  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 ?

  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.

An example from a newspaper

  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 cartesian_product(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]

The greedy coloring algorithm in 6 lines

• Define a set of colors
• Take each vertex iteratively, and assign to it the smallest color not already taken by one of its neighbors

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

• - 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

• The Sage-support Google group (here)
• Sage's documentation page (here), containing for example :
  • The tutorials (basic explanations on several topics)
  • The reference manual containing help for all of Sage's functions
• Sage's IRC Channel : sage-support@irc.freenode.net
• and .... do not hesitate to send me an email if you have any question ! ;-)