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)

60
votes
3answers
2k 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 ...
47
votes
2answers
9k views

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

Boggle is a word game played with 16 dice and a 4x4 tray. This question is inspired by a Stack Overflow question about Boggle that I decided to solve using Mathematica. In addition to Mathematica, I ...
30
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, ...
30
votes
5answers
7k 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 ...
30
votes
1answer
1k 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
4answers
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 ...
25
votes
3answers
4k 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
606 views

Reduce distances between vertices of graph to minimum possible?

This simple graph has vertex shapes of different sizes: ...
23
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.
22
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 ...
22
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 ...
22
votes
1answer
761 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 ...
21
votes
3answers
926 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
981 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
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 ...
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
614 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 ...
20
votes
1answer
914 views

Graph vs GraphPlot

What is the difference (in purpose) between Graph and GraphPlot? Which function is bested suited to which tasks? Background: I ...
19
votes
2answers
1k views

Drawing pairs (planar 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 ...
19
votes
5answers
987 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 ...
19
votes
2answers
382 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 ...
19
votes
2answers
810 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 ...
19
votes
1answer
441 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
18
votes
1answer
280 views

Visual representation of a Ranking over time (image provided)

[Disclaimer: I initially posted this question on stackOverflow 2 months ago and think it might be better suited for this forum (link to original question)] The graph below shows a ranking of ...
18
votes
1answer
197 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. ...
18
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 ...
17
votes
5answers
565 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 ...
17
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 ...
16
votes
3answers
470 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
2answers
701 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: ...
16
votes
1answer
712 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 ...
16
votes
1answer
375 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
6answers
449 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 ...
15
votes
3answers
250 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
1answer
423 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
848 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
492 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
2answers
631 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: ...
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
3answers
552 views

How can I construct and visualize a hypergraph?

A hypergraph is a generalization of a graph, in which an edge can connect more than two vertices. Thus you can think of an edge in an hypergraph as a subset of nodes. Since version 8, Mathematica has ...
14
votes
3answers
522 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
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 ...
14
votes
1answer
515 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 ...
14
votes
2answers
597 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
392 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
3answers
669 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
6answers
507 views

Finding all paths of certain length between vertices in path graph, non-simple ones too

First I will tell you what my ultimate goal is, because maybe there's another way of doing it other than what I am trying. I need a list of all $(a_1, a_2, \ldots, a_N)$ tuples that satisfy certain ...
13
votes
2answers
334 views

How to build a 3D graph from a 3D matrix?

Following this and that question and the corresponding answers, Mathematica can build 2D graph from 2D matrices. Question How to make the corresponding 3D graphs from 3D cubes? Attempt ...
13
votes
1answer
717 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?