Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.
45
votes
3answers
646 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 ...
32
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, ...
25
votes
5answers
2k 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 ...
23
votes
1answer
372 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 ...
23
votes
1answer
358 views
Reduce distances between vertices of graph to minimum possible?
This simple graph has vertex shapes of different sizes:
...
22
votes
3answers
1k 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 ...
20
votes
1answer
309 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 ...
19
votes
1answer
577 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 ...
19
votes
1answer
915 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 ...
19
votes
1answer
415 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 ...
18
votes
3answers
441 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 ...
18
votes
2answers
943 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 ...
18
votes
2answers
749 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 ...
17
votes
4answers
506 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 ...
17
votes
2answers
1k 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.
17
votes
1answer
177 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.
...
16
votes
3answers
677 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 ...
16
votes
3answers
324 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
3answers
722 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 ...
16
votes
2answers
244 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 ...
15
votes
1answer
414 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 ...
15
votes
3answers
757 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 ...
15
votes
1answer
264 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 ...
14
votes
3answers
1k 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
1answer
413 views
Graph vs GraphPlot
What is the difference (in purpose) between Graph and GraphPlot? Which function is bested suited to which tasks?
Background: I ...
14
votes
1answer
301 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 ...
14
votes
2answers
448 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 ...
14
votes
2answers
380 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
281 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
326 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
3answers
396 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
3answers
515 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 ...
13
votes
3answers
338 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 ...
13
votes
2answers
326 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:
...
13
votes
1answer
260 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 ...
12
votes
2answers
125 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: ...
12
votes
2answers
870 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 ...
12
votes
2answers
702 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
2answers
224 views
Comfortable Edge Labeling of Undirected Graph
I'm working on a program that finds special [called "interval"] edge-colorings for graphs. Output is as follows:
...
12
votes
1answer
123 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 ...
12
votes
1answer
352 views
Drawing Graph Products
I need to draw graphs that are Cartesian products of 2 graphs. I need them to look like this: .
So each copy of the factors can have LinearEmbedding, but the whole ...
12
votes
2answers
772 views
Simple algorithm to find cycles in edge list
I have the edge list of an undirected graph which consists of disjoint "cycles" only. Example:
{{1, 2}, {2, 3}, {3, 4}, {4, 1}, {5, 6}, {6, 7}, {7, 5}}
Each ...
12
votes
3answers
314 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 ...
11
votes
2answers
375 views
Calculating morphometric properties
Is it possible to calculate segment length, segment diameter and branch angles for three dimensional geometry. Geometry contains vertex points and polygon surfaces as
...
11
votes
1answer
129 views
Layout a second graph of the same nodes in the same way
I have a number of graphs with the same nodes.
I would like to be able to somehow save the layout that results from the spring embedded results of one graph (the first image), and have the other ...
11
votes
1answer
382 views
How to divide a graph into connected components?
Suppose I have some edges:
edges = {1 -> 2, 2 -> 3, 3 -> 1, 4 -> 5, 3 -> 6, 7 -> 8, 8 -> 9, 8 -> 10};
And I make a graph:
...
11
votes
1answer
182 views
Ulam's Spiral with Opperman's diagonals (quarter-squares)
First we craft a function to return the quadrant boundary based on Oppermann's Conjecture
a[n_] := (Mod[n, 2] + n^2 + 2 n)/4
Then we create a few lists
...
11
votes
1answer
353 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?
11
votes
2answers
196 views
Listing subgraphs of G isomorphic to SubG
If I have an undirected graph G, how could I write a function in Mathematica to obtain a list of subgraphs of G that are isomorphic to some other undirected graph SubG?
I'd like to learn how to ...
10
votes
4answers
323 views
Ordering vertices in GraphPlot
I'm new here, so forgive me if this question is not well-posed/duplicates an earlier question - although I've searched for similar questions without success.
I'm trying to present a plot of ...
