Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.
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, ...
44
votes
3answers
642 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 ...
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 ...
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 ...
12
votes
1answer
119 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
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 ...
13
votes
4answers
325 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 ...
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 ...
18
votes
2answers
748 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 ...
5
votes
3answers
244 views
Centrality measures for single nodes
I am producing a graph, generated by a list of adjacent nodes. (The list looks like {1 ->583, 1->2977, 2->14, 4->1293, 5->221, ...}. Each node of my ...
13
votes
3answers
337 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 ...
23
votes
1answer
371 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 ...
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 ...
10
votes
1answer
180 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.
...
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 ...
15
votes
3answers
747 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 ...
18
votes
3answers
440 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 ...
8
votes
2answers
176 views
Cases[data,Colon[key,_]] vs. Cases[data,key:_] toward XPath, XQuery
Exploring methods to index and search tree-structured key:value pairs via named-entity index (key paths) as opposed to Position-based indexing.
Using Rule as ...
7
votes
1answer
409 views
How to speed up Minimum Spanning Tree algorithm?
How to speed up MST algorithm? I work with graphs and I have adopted Prim's algorithm for my needs, from here.
The graphs which I use are very dense (number of vertexes: $V=500$ and every vertex is ...
6
votes
1answer
363 views
Mathematica Package for Bayesian Networks
Are there any packages that allow the simulation of Bayesian Networks with Mathematica? I found what seemed to be a promising package (Dynamics) on a Brown University URL,
...
6
votes
3answers
505 views
Find cycles of graphs with both directed and undirected edges
I need to enumerate all the simple cycles of a graph which has both directed and undirected edges, where we can treat the undirected edges as doubly directed. (Specifically, I am looking at the Cayley ...
6
votes
2answers
402 views
Is it possible to export a graph as graphic to Excel?
It is straightforward to export lists to Excel with Export. Can I export a graphic image, too? This does not work:
...
4
votes
2answers
295 views
Finding face vertices from the face adjacency graph
I have a question about face adjacency graphs.
Suppose that I have an adjacency matrix
...
1
vote
1answer
69 views
How can I change the Graph required data such as EdgeWeight,VertexWeight,EdgeCapacity,VertexCapacity in the Graph?
I asked this question in different form and because I couldn't receive the proper answer so I have to change my question.I know that was my fault sorry.I need to change the Matrix Data of nodes and ...
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 ...
7
votes
3answers
144 views
Preserving labels when using graph functions
I am finding that some functions that accept a graph and return a transformed graph lose all the vertex and edge labels of the graph being transformed. For example, when I define a graph like this:
...
7
votes
2answers
240 views
HighlightGraph with different styles
I want to highlight two different directed paths on a graph with two different style. I am using the following two code snippets:
...
5
votes
2answers
123 views
Is there something wrong with VertexConnectivity
As I noticed in the documentation VertexConnectivity is defined as the following
The vertex connectivity of a graph $g$ is the smallest number of vertices whose ...
2
votes
3answers
226 views
How to find all graph isomorphisms in FindGraphIsomorphism
I found the second definition of the function FindGraphIsomorphism not working.
Here's the definition Mathematica 8 gives:
...
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.
11
votes
2answers
696 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 ...
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 ...
14
votes
2answers
379 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
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 ...
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
...
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 ...
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
...
10
votes
1answer
186 views
Dynamic visualization of Graph[] on a webpage
How can we embed a dynamic version of a Graph object on a web page, similar to the one showcased on the networkx home page?
This sort of dynamic visualization can ...
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
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 ...
5
votes
2answers
203 views
Is there something akin to “SubgraphIsomorphismQ” in Mathematica 9?
Provided two unlabeled graphs, $G$ and $H$, I would like to test where $H$ is a subgraph of $G$. In other words, I'd like to test whether we can prune some fixed number of vertices or edges from $G$ ...
16
votes
2answers
243 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 ...
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?
10
votes
2answers
210 views
Using Gather to rearrange my data
I have a list of elements:
{{1, 2}, {1, 5}, {2, 6}, {3, 7}, {4, 8}, {5, 6},
{5, 9}, {9, 13}, {10,11}, {11, 12}, {11, 15}, {15, 16}}
I have to divide it into ...
9
votes
2answers
156 views
Determining whether two $k$-chromatic graphs are isomorphic (respecting vertex coloration)
Consider the case where I have two $k$-chromatic graphs $G_1$ and $G_2$, i.e. two graphs where individual vertices can be colored with one of a set of $k$ total colors, and I would like to determine ...
8
votes
2answers
216 views
Transition between graphs
I want to visually demonstrate the manipulations made to a graph. For instance, I have a graph g where using the command ...
12
votes
2answers
124 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: ...
8
votes
1answer
121 views
Algorithm used by IsomorphicGraphQ
I'd like to know which algorithm is used to test if two graphs are isomorphic?
8
votes
3answers
442 views
How to plot layered graphs?
Given a directed acyclic graph, there is always a possibility to plot the graph as layers, where nodes always send edges into one direction (usually down), to successive layers, and never backwards. ...
6
votes
1answer
102 views
Property assignment on a graph vertex using PropertyValue does not work inside a function
I created this function:
AddStone[board_Graph, v_, s : white | black | empty] :=
PropertyValue[{board, v}, VertexState] = s
This function should change the ...
