% Sage Graph Theory Quick Reference
% (c) 2011 by Steven Rafael Turner
% Licensed with the GNU Free Documentation License (GFDL)
%   http://www.gnu.org/copyleft/fdl.html
%
%  History
%
%    2011-28-07  Initial version based on Sage 4.7
%    2011-28-07  Spelling Mistakes 
%    2011-06-08  New sections: Common Invariants, Boolean Queries, Common Invariants, NP-Complete 

%    2012-03-30  Modified. (use quickrefcard.sty, a4paper and dvipdfmx.)
%
\documentclass[a4paper]{article}
\usepackage[dvipdfm]{graphicx}  
\usepackage[dvipdfm]{color}

\usepackage{quickrefcard}

\usepackage{multicol}
\usepackage{amsmath}
\usepackage{amsfonts}

\begin{document}
\begin{multicols*}{3}
\begin{center}
\textbf{Sage Quick Reference: Graph Theory}\\
Steven Rafael Turner(w/mod. by nu)\\
Sage Version 4.7\\
\url{http://wiki.sagemath.org/quickref}\\
GNU Free Document License, extend for your own use
\end{center}
% backup over center environment gap
\vspace{-2ex}
%*********************************************
\sect{Constructing}

%%--%%
\subsect{Adjacency Mapping}

\EX{G=Graph([GF(13), lambda i,j: }\EXVAR{conditions on i,j}\EX{ ])}
\BreakLineAndIndent
  Input is a list whose first item are vertices and the other is some adjacency function: 
\sagecommand{[}\sagevar{list of vertices}\sagecommand{,} \sagevar{function}\sagecommand{]}

%%--%%
\subsect{Adjacency Lists}

\EX{G=Graph({0:[1,2,3], 2:[4]})} 

\EX{G=Graph({0:{1:"x",2:"z",3:"a"}, 2:{5:"out"}})}
\BreakLineAndIndent
  \sagecommand{x}, \sagecommand{z}, \sagecommand{a}, and out 
  are labels for edges and be used as weights.

%%--%%
\subsect{Adjacency Matrix} 

\EX{A = numpy.array([[0,1,1],[1,0,1],[1,1,0]])}
\BreakLineAndIndent
  Don't forget to import numpy for the NumPy matrix or ndarray. 

\EX{M = Matrix([(....), (....), . . . ])} 

%%--%%
\subsect{Edge List with or without labels} 

\EX{G = Graph([(1,3,"Label"),(3,8,"Or"),(5,2)])} 

%%--%%
\subsect{Incidence Matrix}

\EX{M = Matrix(2, [-1,0,0,0,1, 1,-1,0,0,0])}

%%--%%
\subsect{Graph6 Or Sparse6 string} 

\EX{G=':IgMoqoCUOqeb\n:I`EDOAEQ?PccSsge\N\n'}\\
\EX{graphs_list.from_sparse6(G)} 
\BreakLineAndIndent
  Above is a list of graphs using sparse6 strings.

%%--%%
\subsect{NetworkX Graph} 

\EX{g = networkx.Graph({0:[1,2,3], 2:[4]})}\\
\EX{DiGraph(g)} \\
\EX{g_2 = networkx.MultiGraph({0:[1,2,3], 2:[4]})}
\EX{Graph(g_2)}
\BreakLineAndIndent
   Don't forget to import networkx

%*********************************************
\sect{Centrality Measures}

\EX{G.centrality_betweenness(normalized=False)} \\
\EX{G.centrality_closeness(v=1)} \\
\EX{G.centrality_degree()} 

%*********************************************
\sect{Graph Deletions and Additions}

\EX{G.add_cycle([}\EXVAR{vertices}\EX{])}\\ 
\EX{G.add_edge(}\EXVAR{edge}\EX{)}\\
\EX{G.add_edges(}\EXVAR{iterable of edges}{)}\\
\EX{G.add_path}\\ 
\EX{G.add_vertex(}\EXVAR{Name of isolated vertex}\EX{)}\\ 
\EX{G.add_vertices(}\EXVAR{iterable of vertices}\EX{)}\\ 
\EX{G.delete_edge( v_1, v_2, 'label')}\\ 
\EX{G.delete_edges(}\EXVAR{iterable of edges}\EX{)}\\ 
\EX{G.delete_multiedge(v_1, v_2)}\\ 
\EX{G.delete_vertex(v_1)}\\ 
\EX{G.delete_vertices(}\EXVAR{iterable of vertices}\EX{)}\\ 
\EX{G.merge_vertices([}\EXVAR{vertices}\EX{])}

%*********************************************
\sect{Connectivity and Cuts}


\EX{G.is_connected()}

\EX{G.edge_connectivity()}

\EX{G.edge_cut(source, sink)}

\EX{G.blocks_and_cut_vertices()}

\EX{G.max_cut()}
 
\EX{G.edge_disjoint_paths(v1,v2, method='LP')} \BreakLineAndIndent
  This \sagecommand{method} can use \sagecommand{LP} (Linear Programming) or \sagecommand{FF} (Ford-Fulkerson)

\EX{vertex_disjoint_paths(v1,v2)} 

\EX{G.flow(1,2)} \BreakLineAndIndent
  There are many options to this function please check the documentation.

%*********************************************
\sect{Conversions}

\EX{G.to_directed()}\\ 
\EX{G.to_undirected()}\\ 
\EX{G.sparse6_string()}\\ 
\EX{G.graph6_string()}

%*********************************************
\sect{Products}

\EX{G.strong_product(H)}

\EX{G.tensor_product(H)}\\
\EX{G.categorical_product(H)} \BreakLineAndIndent
  Same as the tensor product. 

\EX{G.disjunctive_product(H)}

\EX{G.lexicographic_product(H)}

\EX{G.cartesian_product(H)}
 
%*********************************************
\sect{Boolean Queries}

\EX{G.is_tree()}\\
\EX{G.is_forest()}\\
\EX{G.is_gallai_tree()}\\
\EX{G.is_interval()}\\
\EX{G.is_regular()}\\
\EX{G.is_chordal()}\\
\EX{G.is_eulerian()}\\
\EX{G.is_hamiltonian()}\\
\EX{G.is_interval()}\\
\EX{G.is_independent_set([}\EXVAR{vertices}\EX{])}\\
\EX{G.is_overfull()}\\
\EX{G.is_regular(k)}\BreakLineAndIndent
  Can test for being \sagecommand{k}-regular, by default \sagecommand{k=None}. 

%*********************************************
\sect{Common Invariants}

\EX{G.diameter()}\\
\EX{G.average_distance()}\\
\EX{G.edge_disjoint_spanning_trees(k)}\\
\EX{G.girth()}\\
\EX{G.size()}\\
\EX{G.order()}\\
\EX{G.radius()}

%*********************************************
\sect{Graph Coloring}

\EX{G.chromatic_polynomial()}

\EX{G.chromatic_number(algorithm="DLX")}
\BreakLineAndIndent
  You can change \sagecommand{DLX} (dancing links) to \sagecommand{CP} (chromatic polynomial coefficients) or \sagecommand{MILP} (mixed integer linear program)

\EX{G.coloring(algorithm="DLX")}
\BreakLineAndIndent
  You can change \sagecommand{DLX} to \sagecommand{MILP}

\EX{G.is_perfect(certificate=False)}

%*********************************************
\sect{Planarity} 

\EX{G.is_planar()}\\ 
\EX{G.is_circular_planar()}\\ 
\EX{G.is_drawn_free_of_edge_crossings()}\\ 
\EX{G.layout_planar(test=True, set_embedding=True}\\ 
\EX{G.set_planar_positions()} 

%*********************************************
\sect{Search and Shortest Path}

\EX{list(G.depth_first_search([}\EXVAR{vertices}\EX{], distance=4)}

\EX{list(G.breadth_first_search([}\EXVAR{vertices}\EX{])}

\EX{dist,pred=graph.shortest_path_all_pairs(by_weight=True, algorithm="auto")} 
\BreakLineAndIndent
  Choice of algorithms: \sagecommand{BFS} or \sagecommand{Floyd-Warshall-Python}

\EX{G.shortest_path_length(v_1,v_2, by_weight=True}

\EX{G.shortest_path_lengths(v_1)}

\EX{G.shortest_path(v_1,v_2)}

%*********************************************
\sect{Spanning Trees} 

\EX{G.steiner_tree(g.vertices()[:10])}

\EX{G.spanning_trees_count()}

\EX{G.edge_disjoint_spanning_trees(2, }\EXVAR{root vertex}\EX{)}

\EX{G.min_spanning_tree(weight_function=somefunction,algorithm='Kruskal',starting_vertex=3)} 
\BreakLineAndIndent
  \sagecommand{Kruskal} can be change to \sagecommand{Prim_fringe}, \sagecommand{Prim_edge}, or \sagecommand{NetworkX}.

%*********************************************
\sect{Linear Algebra}

%%--%%
\subsect{Matrices}

\EX{G.kirchhoff_matrix()}\\
\EX{G.laplacian_matrix()}\BreakLineAndIndent 
  Same as the kirchoff matrix

\EX{G.weighted_adjacency_matrix()}

\EX{G.adjacency_matrix()}

\EX{G.incidence_matrix()}

%%--%%
\subsect{Operations}

\EX{G.characteristic_polynomial()}

\EX{G.cycle_basis()} 

\EX{G.spectrum()}

\EX{G.eigenspaces(laplacian=True)}

\EX{G.eigenvectors(laplacian=True)}

%*********************************************
\sect{Automorphism and Isomorphism Related}

\EX{G.automorphism_group()}\\ 
\EX{G.is_isomorphic(H)}\\ 
\EX{G.is_vertex_transitive()}\\ 
\EX{G.canonical_label()}\\ 
\EX{G.minor(}\EXVAR{graph of minor to find}\EX{)}
 
%*********************************************
\sect{Generic Clustering} 

\EX{G.cluster_transitivity()}\\ 
\EX{G.cluster_triangles()}\\ 
\EX{G.clustering_average()}\\ 
\EX{G..clustering_coeff(nbunch=[0,1,2],weights=True)}

%*********************************************
\sect{Clique Analysis}

\EX{G.is_clique([}\EXVAR{vertices}\EX{])}

\EX{G.cliques_vertex_clique_number(vertices=[(0, 1), (1, 2)],algorithm="networkx")}
\BreakLineAndIndent
  \sagecommand{networkx} can be replaced with \sagecommand{cliquer}.

\EX{G.cliques_number_of()}

\EX{G.cliques_maximum()}

\EX{G.cliques_maximal()}

\EX{G.cliques_get_max_clique_graph()}

\EX{G.cliques_get_clique_bipartite()}

\EX{G.cliques_containing_vertex()}

\EX{G.clique_number(algorithm="cliquer")}
\BreakLineAndIndent
  \sagecommand{cliquer} can be replaced with \sagecommand{networkx}.

\EX{G.clique_maximum()}

\EX{G.clique_complex()}

%*********************************************
\sect{Component Algorithms}

\EX{G.is_connected()}\\
\EX{G.connected_component_containing_vertex(vertex)}\\ 
\EX{G.connected_components_number()}\\ 
\EX{G.connected_components_subgraphs()}\\ 
\EX{G.strong_orientation()}\\ 
\EX{G.strongly_connected_components()}\\ 
\EX{G.strongly_connected_components_digraph()}\\ 
\EX{G.strongly_connected_components_subgraphs()}\\ 
\EX{G.strongly_connected_component_containing_vertex( vertex )}\\
\EX{G.is_strongly_connected()} 

%*********************************************
\sect{NP Problems}

\EX{G.vertex_cover(algorithm='Cliquer')}
\BreakLineAndIndent
  The \sagecommand{algorithm} can be changed to \sagecommand{MILP} (mixed integer linear program). 
  Note that \sagecommand{MILP} requires packages \sagecommand{GLPK} or \sagecommand{CBC}.

\EX{G.hamiltonian_cycle()}

\EX{G.traveling_salesman_problem()}

%*********************************************
\end{multicols*}

\end{document}
