% 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 and Translate into Japanese. (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{隣接写像を使う}

\EX{G=Graph([GF(13), lambda i,j: }\EXVAR{conditions on i,j}\EX{])}
\BreakLineAndIndent
  入力に使うリストの最初の要素は頂点達, 二番目の要素は隣接関係を表す関数:
  \sagecommand{[}頂点のリスト\sagecommand{,} 関数\sagecommand{]}


%%--%%
\subsect{隣接リストを使う}

\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}などは辺のラベル. 重みとして使われる.

%%--%%
\subsect{隣接行列を使う} 

\EX{A = numpy.array([[0,1,1],[1,0,1],[1,1,0]])}
\BreakLineAndIndent
    NumPyのmatrixやndarrayを使うには
    \sagecommand{numpy}をインポートしなければならない.


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

%%--%%
\subsect{ラベルあり/なしの辺のリストを使う} 

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

%%--%%
\subsect{接続行列を使う}

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

%%--%%
\subsect{Graph6やSparse6の文字列表現を使う} 

\EX{G=':IgMoqoCUOqeb\n:I`EDOAEQ?PccSsge\N\n'}\\
\EX{graphs_list.from_sparse6(G)} 
\BreakLineAndIndent
   上の例はsparse6の書式.

%%--%%
\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
\sagecommand{networkx}をインポートしないといけない.

\begin{original}
\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
\end{original}

%*********************************************
\sect[Centrality Measures]{中心性の指標}

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

%*********************************************
\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{)}\\
\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{])}
\begin{original}
\EX{G.add_cycle([}\EXVAR{vertices}\EX{])}\\ 
\EX{G.add_edge(}\EXVAR{edge}\EX{)}\\
\EX{G.add_edges(}\EXVAR{iterable of edges}\EX{)}\\
\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{])}
\end{original}
%*********************************************
\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
\sagecommand{method}には
\sagecommand{LP} (Linear Programming) もしくは \sagecommand{FF} (Ford-Fulkerson)
というオプションが指定できる.

\EX{vertex_disjoint_paths(v1,v2)} 

\EX{G.flow(1,2)} \BreakLineAndIndent
たくさんのオプションがある(ドキュメントを参照されたい).

\begin{original}
\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.
\end{original}
%*********************************************
\sect[Conversions]{変換}

\EX{G.to_directed()}\\ 
\EX{G.to_undirected()}\\ 
\EX{G.sparse6_string()}\\ 
\EX{G.graph6_string()}
\begin{original}
\EX{G.to_directed()}\\ 
\EX{G.to_undirected()}\\ 
\EX{G.sparse6_string()}\\ 
\EX{G.graph6_string()}
\end{original}
%*********************************************
\sect[Products]{積}

\EX{G.strong_product(H)}

\EX{G.tensor_product(H)}
\EX{G.categorical_product(H)} \BreakLineAndIndent
テンソル積と同じ.

\EX{G.disjunctive_product(H)}

\EX{G.lexicographic_product(H)}

\EX{G.cartesian_product(H)}

\begin{original}
\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)}
\end{original} 
%*********************************************
\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
\sagecommand{k}-regularであるかを調べる. 
デフォルトでは\sagecommand{k=None}. 

\begin{original}
\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}. 
\end{original}

%*********************************************
\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()}
\begin{original}
\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()}
\end{original}
%*********************************************
\sect[Graph Coloring]{彩色}

\EX{G.chromatic_polynomial()}

\EX{G.chromatic_number(algorithm="DLX")}
\BreakLineAndIndent
\sagecommand{DLX} (dancing links)を\sagecommand{CP} (chromatic
 polynomial coefficients)や\sagecommand{MILP} (mixed integer linear program)
に変更可能.

\EX{G.coloring(algorithm="DLX")}
\BreakLineAndIndent
\sagecommand{DLX}ではなく\sagecommand{MILP}も選べる.

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

\begin{original}
\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)}
\end{original}
%*********************************************
\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()} 

\begin{original}
\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()} 
\end{original}
%*********************************************
\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
アルゴリズムを選べる: \sagecommand{BFS}, \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)}

\begin{original}
\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)}
\end{original}
%*********************************************
\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}は\sagecommand{Prim_fringe},
\sagecommand{Prim_edge}, \sagecommand{NetworkX}に変更可
\begin{original}
\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}.
\end{original}
%*********************************************
\sect[Linear Algebra]{線形代数}

\subsect{行列}

\EX{G.kirchhoff_matrix()}\\
\EX{G.laplacian_matrix()}\BreakLineAndIndent 
キルヒホッフ行列に同じ.

\EX{G.weighted_adjacency_matrix()}

\EX{G.adjacency_matrix()}

\EX{G.incidence_matrix()}

%%--%%
\subsect{操作}

\EX{G.characteristic_polynomial()}

\EX{G.cycle_basis()} 

\EX{G.spectrum()}

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

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

\begin{original}
\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)}
\end{original}
%*********************************************
\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}{)}
\begin{original}
\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{)}
\end{original}
%*********************************************
\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)}

\begin{original}
\EX{G.cluster_transitivity()}\\ 
\EX{G.cluster_triangles()}\\ 
\EX{G.clustering_average()}\\ 
\EX{G..clustering_coeff(nbunch=[0,1,2],weights=True)}
\end{original}
%*********************************************
\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}は\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}は\sagecommand{networkx}に変更可能.

\EX{G.clique_maximum()}

\EX{G.clique_complex()}

\begin{original}
\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()}
\end{original}
%*********************************************
\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()} 

\begin{original}
\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()} 
\end{original}
%*********************************************
\sect[NP Problems]{NP問題}

\EX{G.vertex_cover(algorithm='Cliquer')}
\BreakLineAndIndent
\sagecommand{algorithm}は\sagecommand{MILP} (mixed integer linear
 program)に変更可能. 
ただし\sagecommand{MILP}を使うに\sagecommand{GLPK}か\sagecommand{CBC}をインポートしないといけない.

\EX{G.hamiltonian_cycle()}

\EX{G.traveling_salesman_problem()}

\begin{original}
\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{original}
%*********************************************
\end{multicols*}

\end{document}
