Friday, March 25, 2011

Graph utilities I use

There's a number of graph utilities and tricks I use when working with graphs in Mathematica 8, I've summarized them in notebook graphUsage.nb. You can get this notebook and all required packages here.

Brief overview:

Fixing annoyances
programmatically changing style of existing graph, modifying graphs without forgetting vertex coordinates, using GraphPlot's layout for Graph objects, aligning adjacency matrix with vertex labels in index graphs

Listing graph structures
cliques, independent sets, maximal cliques, maximal independent sets, hamiltonian circuits

Visualizing graphs
Showing all graphs that miss particular properties, visualizing graphs with intensity attached to vertices -- pieGraph and fadedGraph. Showing graph with several types of vertices.

3 comments:

  1. Thansk for posting! Looking forward to look at your graph magic!

    ReplyDelete
  2. Cool.

    I'm a big fan of Mathematica (actually I work there), but one of my annoyances is how hard it is to do decent customization of the graph viz functionality. For example, I want to provide an arbitrary Hamiltonian for the energy minimizing graph layout solver because I know something about the structure of the graph. Or I want to draw certain vertices larger than others without them overlapping, but M- doesn't "know" about VertexRenderingFunction before it does layout. Etc.

    I'm just going to *write* this new GraphPlot, so let me know if you have any of your own bugbears you want fixed or talk about how it GraphPlot2 should look (I'll open source it).

    ReplyDelete
  3. Well, I think GraphPlot is pretty good for quick graph plots, but it would be cool to have smarter layout for specialized graph types. Here are some examples

    1. clique intersection graphs like here http://mathematica-bits.blogspot.com/2011/01/independence-polynomials-with-tree.html

    In those cases I minimized my own energy function, and plugged in coordinates into GraphPlot (http://yaroslavvb.com/upload/save/clusterVisualize.nb
    ), but it would be cool to have something like that packaged nicely for reuse

    2. Graphs with low tree width can be nicely visualized with VLSI type graph plot (nodes are drawn as long strips, edges are points) -- http://yaroslavvb.blogspot.com/2010/11/visualizing-tree-decompositions.html .

    3. Graphs with substantial symmetry. You can see that layouts for highly symmetrical graphs in GraphData graphs are usually pretty good, often much better than GraphPlot's default layout. There are various techniques for discovering those layouts, for example of linear algebra-based approach see page 21 in Lovasz "Semidefinite programs and combinatorial optimization"

    ReplyDelete