Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.

learn more… | top users | synonyms (2)

58
votes
3answers
1k views

Automatically generating a dependency graph of an arbitrary Mathematica function?

Has anyone written a function to pull the function dependencies of a function? That is, it would be nice to have a function that returns a list of function dependencies as a set of rules, terminating ...
42
votes
2answers
9k views

How can I use Mathematica's graph functions to cheat at Boggle?

This question is inspired by a Stack Overflow question that I decided to solve using Mathematica. In addition to Mathematica, I thought I'd use some of the new version's graph-related functionality, ...
29
votes
5answers
6k views

Custom arrow shaft

Inspired by Sjoerd C. de Vries' nice answer to this question, and the desire to pimp a Graph I did with Mathematica recently I would like to know if there are ways to customize the arrow's shaft ...
28
votes
8answers
2k views

Longest path in 0/1 matrix

I have a matrix of 0's and 1's forming a number of disjoint paths:   I would like to find the lengths of the paths, and from that "spectrum," the longest length (in the above example: 27, ...
25
votes
1answer
905 views

Finding the likeliest path in a Markov process

With Mathematica 9, we have the addition of various processes, among which the discrete Markov process. Given a transition probability matrix m, such a process is ...
25
votes
3answers
3k views

Finding all shortest paths between two vertices

The built-in FindShortestPath and GraphDistance functions find the shortest path between two particular vertices in a graph. I ...
24
votes
1answer
555 views

Reduce distances between vertices of graph to minimum possible?

This simple graph has vertex shapes of different sizes: ...
22
votes
2answers
3k views

How to play with Facebook data inside Mathematica?

I saw this post from Wolfram here and I would like to know how to import facebook data into Mathematica.
21
votes
3answers
2k views

How to generate a random tree?

Is it possible to generate a random tree without explicitly constructing a random adjacency matrix that satisfies tree properties? How about a random directed tree? Edit: incredible answer by ...
21
votes
3answers
1k views

Generating graphs interactively (GUI)

I want to create graphs interactively using a GUI. I thought of using a ClickPane[] environment. The code I have (in part borrowed from the Documentation) works ...
21
votes
1answer
905 views

How to create regular (planar) graphs?

How to programmatically create and plot regular planar graphs with $k = 3, 4$ or $6$ (not hypercubes) and regular nonplanar graphs of $k = 8$ (see figure)? Note that what matters is the average ...
21
votes
3answers
823 views

Finding a “not-shortest” path between two vertices

In designing a routine for making a simple three dimensional (5x5x5) labyrinth, I realized that my solutions (a solution is a labyrinth includes a single path from {1, 1, 1} to {5, 5, 5} in a 5 x5x5 ...
21
votes
1answer
1k views

Is there a way to convert an image into a Graph?

I'm trying to convert an image with several overlapping dots into a Graph. The goal is to be able to derive the Kirchhoff matrix for the randomly created "network ...
21
votes
2answers
2k views

How to plot planar graphs as such?

A planar graph is a graph that can be drawn in the plane such that no two edges cross. For example, the graph ...
21
votes
1answer
569 views

Strategies for solving problems involving searches

As an example of a search-oriented problem, consider finding all constrained $n$-colorings of a graph. An "$n$-coloring" associates one of $n \ge 1$ colors to each vertex in such a way that no edge ...
21
votes
1answer
705 views

Visualizing Rubik's Graph

After the August 2010 discovery that the diameter of the Rubik graph is 20, I wanted to make a way to visualize Rubik's graph. Since there are about $4.3 \times 10^{19}$ vertices in this graph, it is ...
20
votes
2answers
2k views

Cycles of length N in a graph

If I have an undirected graph represented with an adjacency matrix, how can I find all the subgraphs which are a cycle of length N? I don't really know the math nor the programming language well, so ...
20
votes
1answer
830 views

Graph vs GraphPlot

What is the difference (in purpose) between Graph and GraphPlot? Which function is bested suited to which tasks? Background: I ...
18
votes
5answers
913 views

How can I replace bi-directional DirectedEdge pairs in a Graph with a single UndirectedEdge?

The Cayley graphs produced by Mathematica 8.0's CayleyGraph function represent actions that are their own inverses in an unconventional way: rather than using a ...
18
votes
2answers
755 views

Graph layout on a grid

Is it possible for Mathematica to layout a graph so that the connections lie on a grid? Furthermore, for graphs with multiple edges per vertex, is it possible to specify the location on the vertex ...
18
votes
1answer
398 views

How to visualize large graphs with directed edge bundling

I'm wondering if anyone has implemented edge bundled graph plotting? http://www.win.tue.nl/~dholten/papers/forcebundles_eurovis.pdf
17
votes
1answer
190 views

Is UndirectedEdge[a,b] the same edge as UndirectedEdge[b,a]?

Is UndirectedEdge[a,b] the same edge as UndirectedEdge[b,a]? Then please consider this. ...
17
votes
2answers
359 views

Packed Graph or GraphPlot output with non-square layout?

Graph or GraphPlot produce square layouts for disconnected graphs: Graph[Table[i -> Mod[i^3, 100], {i, 1, 100}]] I´d like to get a rectangular layout with ...
17
votes
3answers
2k views

How to get graph layout that reflects edge weights?

My heart soared to discover that Mathematica 8 offers support for specifying a weighted adjacency matrix in WeightedAdjacencyGraph. But it seems that, regardless of the weights between edges, the ...
16
votes
3answers
442 views

How to get complete Documentation Center graph of guide pages?

On the very last image below you can see a typical path of walking through Documentation Center guide pages. What is the best way to get the graph data and visualize the whole structure of these ...
16
votes
1answer
343 views

Convert GraphPlot[]s with many nodes into something that's human-understandable

This is more of an abstract/creative problem. I think everyone who has played around with GraphPlot, ended up with an image that looks like this, at least once in ...
15
votes
3answers
229 views

What is the most convenient way to change options for Graph[] objects?

What is the most convenient way to change options such as VertexLabels in existing Graph objects? (Version 7 users note: ...
15
votes
2answers
3k views

Solving the Travelling Salesman Problem

I've been trying to find some kind of mathematical computer software to solve the Travelling Salesman Problem. The Excel Solver is able to do it, but I've noticed there is a built-in function in ...
15
votes
2answers
614 views

How to measure segment length and branch angle

I am trying to measure segment length and branch angle or bifurcation angle between each pair of segments. My image after thinning looks like this: ...
15
votes
1answer
404 views

Need tips on improving this directed graph

First we define a function that returns the least odd prime factor. lopf[n_] := FactorInteger[n][[2, 1]] Then we craft a routine that performs the 3x+1 steps ...
15
votes
1answer
769 views

How to export and import Graphs with additional data?

I'm trying to export and then later import graphs with additional data added such as VertexLabels and EdgeLabels. When I export ...
14
votes
4answers
459 views

Can TreeForm be displayed “sideways”?

One recurrent problem I'm having with displays generated with TreeForm is that the expressions to be so displayed often at least one level with many (> 20) nodes ...
14
votes
3answers
1k views

Creating diagrams for category theory

Lately I've been doing algebra and I have found myself drawing a bunch of diagrams when I attempt to solve a problem. Most of the diagrams are very simple so I thought, I bet I can do this in ...
14
votes
3answers
3k views

How to generate random directed acyclic graphs?

How to programmatically build random directed acyclic graphs (DAG)? I know about the AcyclicGraphQ predicate and the ...
14
votes
2answers
794 views

Drawing pairs (graph, circle packing)

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. How to use Mathematica to draw examples ...
14
votes
3answers
494 views

Determining all possible traversals of a tree

I have a list: B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}}; This list can be visualized as a tree using ...
14
votes
2answers
540 views

How can I speed up the classic GA for graph coloring?

I'm trying to compute the chromatic number of this graph (which is 28): g = Import@"http://www.info.univ-angers.fr/pub/porumbel/graphs/dsjc250.5.col"; My genetic ...
14
votes
1answer
385 views

When to use built-in Graph/GraphPlot vs. Combinatorica

What are the pros and cons of using built-in Graph/GraphPlot (and related) types vs. types in the Combinatorica package?
13
votes
4answers
373 views

How can I remove B -> A from a list if A -> B is in the list?

I have a list of transformations like this: list = {"A" -> "B", "B" -> "A", "C" -> "D"} As this is used to plot an undirected graph with ...
13
votes
5answers
454 views

Graph from binary matrix (not adjacency) respecting the original matrix positions

I have a binary matrix. My objective is to connect every close (without "jump") elements with value equal to 1, but I must keep the point positions, just like it's shown at the image. Can somebody ...
13
votes
2answers
557 views

Animating transition between all graph representations obtained from curated data

Pappus graph is one of many graphs whose various data is contained within Mathematica. Mathematica typically keeps several ways of representing such graphs: ...
13
votes
3answers
613 views

How to find all vertices reachable from a start vertex following directed edges?

How to find all vertices reachable from a given start vertex following directed edges, in a cyclic directed graph given as ...
13
votes
2answers
1k views

Creating a graph with variable size of vertices and variable thickness of edges

I'm trying to create a graph to represent transitions between different states of a system. I would like to represent the time the systems spent in a state with the size of the vertex and the ...
13
votes
1answer
626 views

How can I conveniently call igraph through RLink?

Mathematica has lots of functions for working with graphs, but this functionality is not yet as mature as the igraph library. It is useful to have access to igraph from Mathematica, both for ...
13
votes
1answer
460 views

Visiting nodes in a tree bottom up

I have a problem that can be reduced to this one: Suppose I have an unbalanced (almost random) tree. The leaves of the tree have one property already set, and all vertex (including the leaves) have ...
13
votes
4answers
434 views

How to recompute the layout of a Graph?

I asked a question about changing Graph properties in a similar way to how Show can change ...
13
votes
1answer
618 views

Use Mathematica to do a network analysis of Mathematica.SE

Recently Wolfram|Alpha announced that you could use it to analyze your Facebook site. How could I do a network analysis of questioners and answers here on Mathematica.SE?
13
votes
1answer
361 views

Transform an expression into a graph that can be plotted with TreeGraph (not TreeForm)

I would like to plot an expression (like TreeForm does), but using the new TreeGraph functionality. ...
12
votes
2answers
1k views

How to convert an image to a graph and get the positions of the edges?

I am trying to convert an image to a graph. My image is already skeletonized and looks pretty much like this: What I need to do is identify all vertices and edges, and in particular get a list of ...
12
votes
4answers
1k views

Finding elementary cycles of (directed) graphs

I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...