************ Graph theory ************ See the Sage wiki page http://wiki.sagemath.org/graph_survey for an excellent survey of exisiting graph theory software. Networkx ======== Networkx (http://networkx.lanl.gov) "is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks". More details can also be found on http://wiki.sagemath.org/graph_survey or in Robert Miller's SageDays 3 talk. :: sage: C = graphs.CubeGraph(4) Now type C.show(vertex_labels=False, vertex_size=60, graph_border=True, figsize=[9,8]) to view this with some of the options. The digraph below is a :math:3-cycle with vertices :math:\{0,1,2\} and edges :math:0\rightarrow 1, :math:1\rightarrow 2, :math:2\rightarrow 0: :: sage: D = DiGraph( { 0: [1], 1: [2], 2: [0]} ) Type D.show() to view this. .. _section-cayley: Cayley graphs ============= includes wrappers to many NetworkX commands, written mainly by Emily Kirkman and Robert Miller. The implementation of Cayley graphs was written by Bobby Moretti and Robert Miller. :: sage: G = DihedralGroup(5) sage: C = G.cayley_graph(); C Digraph on 10 vertices sage: C.diameter() 3 sage: C.girth() 2 sage: C.automorphism_group().order() 10 sage: len(C.edges()) 20 .. index:: pair: graph; adjacency matrix .. section_adjacency: Graphs from adjacency matrices ============================== To construct the graph G with :math:n \times n adjacency matrix :math:A, you want a graph :math:X so that the vertex-set of G is :math:\{1,..., n\}, and :math:[i,j] is an edge of G if and only if :math:A[i][j] = 1. Here is an example of the syntax in (copied from Robert Miller's SageDays 3 talk): Define the distance :math:d(x,y) from :math:x to :math:y to be the minimum length of a (directed) path in Gamma joining a vertex :math:x to a vertex :math:y if such a path exists, and :math:-1 otherwise. A diameter of :math:-1 is returned if G is not (strongly) connected. Otherwise, the diameter of G is equal to the maximum (directed) distance :math:d(x,y) in G (as :math:x and :math:y range over all the vertices of G). :: sage: M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ]) sage: # (the order is the number of edges) sage: G = Graph(M); G.order() 3 sage: G.distance(0,2) 1 sage: G.diameter() 1