49
$\begingroup$

The context:

I'm going to start working on a project that involves running predefined algorithms (and defining my own) for very big graphs (thousands of nodes). Visualization would also be welcome if possible.

This is a research project and the goal is to produce a prototype that generates/handles biological reaction networks.

Also, I would like to stick to these kind of platforms with "everything but the kitchen-sink" for scientific computing. The reason is, we will need other features like differentiation (symbolic and numeric) during the project.

The question:

So my question is, how complete is sage for graph theory algorithms, when compared to Mathematica (Combinatorica) and Matlab.

  • 7
    @J.D.: Note that the [faq] says: *We welcome questions about: [...] Software that mathematicians use*, so I don't think this is off-topic.2012-03-13

1 Answers 1

43

Try asking on http://ask.sagemath.org/questions/

In fact, there was already a general question asked there about Sage versus other software, and the top answer said, "If you are doing graph theory or serious number theory, you shouldn't even be asking the question of which package to use." That is, if you're doing graph theory, or serious number theory, Sage is the winner by far. This was comparing Sage to all other computer algebra systems. So, I believe the answer is Sage is the best graph theory program that exists. And, it is getting better all the time.

http://ask.sagemath.org/question/1010/reliability-of-sage-vs-commercial-software

Sage combines together many open source graph theory tools that exist (nauty generator, networkx which contains tons of stuff by itself, cliquer, and more) and also all the things that have been programmed by Sage developers. And, if there is anything you want to be able to do that isn't already programmed, you can program it in Python (or if you need it to be really fast, in cython).

As far as visualization, yes, Sage graphs are extremely good graphics. If you save them to a PDF, you can zoom in as much as you want (I'm not exaggerating) and they will still be crisp, clean graphics. And, there is a graph editor that allows you to draw graphs and move the vertices around and add vertices and edges and things like that. Not to mention, there are many built in graphs.

Oh, and by the way, if Mathematica (or one of many other programs) is installed on the same computer as Sage, you can use the functions from those other programs and get the results in Sage.

Here's a video tutorial on graph theory (second video from top). It gives a lot of detail, and includes all the info on graphics such as saving pdfs and using the graph editor to make nice looking graphs.

http://www.sagemath.org/help-video.html

Here's a real quick tutorial on graph theory in Sage:

http://steinertriples.fr/ncohen/tut/Graphs/

Here are the functions available:

    g.add_cycle     g.add_edge     g.add_edges     g.add_path     g.add_vertex     g.add_vertices     g.adjacency_matrix     g.all_paths     g.allow_loops     g.allow_multiple_edges     g.allows_loops     g.allows_multiple_edges     g.am     g.antisymmetric     g.automorphism_group     g.average_degree     g.average_distance     g.bipartite_color     g.bipartite_sets     g.blocks_and_cut_vertices     g.bounded_outdegree_orientation     g.breadth_first_search     g.canonical_label     g.cartesian_product     g.categorical_product     g.category     g.center     g.centrality_betweenness     g.centrality_closeness     g.centrality_degree     g.characteristic_polynomial     g.charpoly     g.check_embedding_validity     g.check_pos_validity     g.chromatic_number     g.chromatic_polynomial     g.clear     g.clique_complex     g.clique_maximum     g.clique_number     g.cliques     g.cliques_containing_vertex     g.cliques_get_clique_bipartite     g.cliques_get_max_clique_graph     g.cliques_maximal     g.cliques_maximum     g.cliques_number_of     g.cliques_vertex_clique_number     g.cluster_transitivity     g.cluster_triangles     g.clustering_average     g.clustering_coeff     g.coarsest_equitable_refinement     g.coloring     g.complement     g.connected_component_containing_vertex     g.connected_components     g.connected_components_number     g.connected_components_subgraphs     g.convexity_properties     g.copy     g.cores     g.cycle_basis     g.db     g.degree     g.degree_constrained_subgraph     g.degree_histogram     g.degree_iterator     g.degree_sequence     g.degree_to_cell     g.delete_edge     g.delete_edges     g.delete_multiedge     g.delete_vertex     g.delete_vertices     g.density     g.depth_first_search     g.diameter     g.disjoint_routed_paths     g.disjoint_union     g.disjunctive_product     g.distance     g.distance_all_pairs     g.distance_graph     g.dominating_set     g.dump     g.dumps     g.eccentricity     g.edge_boundary     g.edge_connectivity     g.edge_cut     g.edge_disjoint_paths     g.edge_disjoint_spanning_trees     g.edge_iterator     g.edge_label     g.edge_labels     g.edges     g.edges_incident     g.eigenspaces     g.eigenvectors     g.eulerian_circuit     g.eulerian_orientation     g.flow     g.fractional_chromatic_index     g.genus     g.get_boundary     g.get_embedding     g.get_pos     g.get_vertex     g.get_vertices     g.girth     g.gomory_hu_tree     g.graph6_string     g.graphics_array_defaults     g.graphplot     g.graphviz_string     g.graphviz_to_file_named     g.hamiltonian_cycle     g.has_edge     g.has_loops     g.has_multiple_edges     g.has_vertex     g.incidence_matrix     g.independent_set     g.independent_set_of_representatives     g.interior_paths     g.is_bipartite     g.is_chordal     g.is_circular_planar     g.is_clique     g.is_connected     g.is_directed     g.is_drawn_free_of_edge_crossings     g.is_equitable     g.is_eulerian     g.is_even_hole_free     g.is_forest     g.is_gallai_tree     g.is_hamiltonian     g.is_independent_set     g.is_interval     g.is_isomorphic     g.is_line_graph     g.is_odd_hole_free     g.is_overfull     g.is_perfect     g.is_planar     g.is_prime     g.is_regular     g.is_split     g.is_subgraph     g.is_transitively_reduced     g.is_tree     g.is_triangle_free     g.is_vertex_transitive     g.kirchhoff_matrix     g.laplacian_matrix     g.latex_options     g.layout     g.layout_circular     g.layout_default     g.layout_extend_randomly     g.layout_graphviz     g.layout_planar     g.layout_ranked     g.layout_spring     g.layout_tree     g.lex_BFS     g.lexicographic_product     g.line_graph     g.longest_path     g.loop_edges     g.loop_vertices     g.loops     g.matching     g.matching_polynomial     g.max_cut     g.maximum_average_degree     g.merge_vertices     g.min_spanning_tree     g.minimum_outdegree_orientation     g.minor     g.modular_decomposition     g.multicommodity_flow     g.multiple_edges     g.multiway_cut     g.name     g.neighbor_iterator     g.neighbors     g.networkx_graph     g.num_edges     g.num_verts     g.number_of_loops     g.order     g.periphery     g.plot     g.plot3d     g.radius     g.random_edge     g.random_subgraph     g.random_vertex     g.relabel     g.remove_loops     g.remove_multiple_edges     g.rename     g.reset_name     g.save     g.set_boundary     g.set_edge_label     g.set_embedding     g.set_latex_options     g.set_planar_positions     g.set_pos     g.set_vertex     g.set_vertices     g.shortest_path     g.shortest_path_all_pairs     g.shortest_path_length     g.shortest_path_lengths     g.shortest_paths     g.show     g.show3d     g.size     g.spanning_trees_count     g.sparse6_string     g.spectrum     g.steiner_tree     g.strong_orientation     g.strong_product     g.subdivide_edge     g.subdivide_edges     g.subgraph     g.subgraph_search     g.subgraph_search_count     g.subgraph_search_iterator     g.szeged_index     g.tensor_product     g.to_directed     g.to_simple     g.to_undirected     g.topological_minor     g.trace_faces     g.transitive_closure     g.transitive_reduction     g.traveling_salesman_problem     g.two_factor_petersen     g.union     g.version     g.vertex_boundary     g.vertex_connectivity     g.vertex_cover     g.vertex_cut     g.vertex_disjoint_paths     g.vertex_iterator     g.vertices     g.weighted     g.weighted_adjacency_matrix     g.wiener_index     g.write_to_eps 

And here are some graphs you can easily generate:

graphs.BalancedTree graphs.BarbellGraph graphs.BidiakisCube graphs.BrinkmannGraph graphs.BubbleSortGraph graphs.BuckyBall graphs.BullGraph graphs.ButterflyGraph graphs.ChvatalGraph graphs.CirculantGraph graphs.CircularLadderGraph graphs.ClawGraph graphs.CompleteBipartiteGraph graphs.CompleteGraph graphs.CompleteMultipartiteGraph graphs.CubeGraph graphs.CycleGraph graphs.DegreeSequence graphs.DegreeSequenceBipartite graphs.DegreeSequenceConfigurationModel graphs.DegreeSequenceExpected graphs.DegreeSequenceTree graphs.DesarguesGraph graphs.DiamondGraph graphs.DodecahedralGraph graphs.DorogovtsevGoltsevMendesGraph graphs.DurerGraph graphs.DyckGraph graphs.EmptyGraph graphs.ErreraGraph graphs.FibonacciTree graphs.FlowerSnark graphs.FranklinGraph graphs.FriendshipGraph graphs.FruchtGraph graphs.FuzzyBallGraph graphs.GeneralizedPetersenGraph graphs.GoldnerHararyGraph graphs.Grid2dGraph graphs.GridGraph graphs.GrotzschGraph graphs.HanoiTowerGraph graphs.HeawoodGraph graphs.HerschelGraph graphs.HexahedralGraph graphs.HigmanSimsGraph graphs.HoffmanSingletonGraph graphs.HouseGraph graphs.HouseXGraph graphs.HyperStarGraph graphs.IcosahedralGraph graphs.IntervalGraph graphs.KneserGraph graphs.KrackhardtKiteGraph graphs.LCFGraph graphs.LadderGraph graphs.LollipopGraph graphs.MoebiusKantorGraph graphs.MoserSpindle graphs.MycielskiGraph graphs.MycielskiStep graphs.NKStarGraph graphs.NStarGraph graphs.OctahedralGraph graphs.OddGraph graphs.PappusGraph graphs.PathGraph graphs.PetersenGraph graphs.RandomBarabasiAlbert graphs.RandomBipartite graphs.RandomGNM graphs.RandomGNP graphs.RandomHolmeKim graphs.RandomInterval graphs.RandomLobster graphs.RandomNewmanWattsStrogatz graphs.RandomRegular graphs.RandomShell graphs.RandomTree graphs.RandomTreePowerlaw graphs.ShrikhandeGraph graphs.StarGraph graphs.TetrahedralGraph graphs.ThomsenGraph graphs.ToroidalGrid2dGraph graphs.WheelGraph graphs.WorldMap graphs.cospectral_graphs graphs.line_graph_forbidden_subgraphs graphs.nauty_geng graphs.trees             
  • 3
    Thanks for the "to the point " answer. I actually looked for something in ask.sagemath.org but missed the question you linked to. And, loved the nickname. ;)2012-03-12