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)

12
votes
2answers
479 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 ...
12
votes
2answers
329 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
186 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 ...
12
votes
1answer
825 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: ...
12
votes
1answer
546 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
292 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 ...
11
votes
1answer
314 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 ...
11
votes
1answer
311 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
2answers
1k 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 ...
10
votes
4answers
551 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 ...
10
votes
2answers
270 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 ...
10
votes
4answers
8k views

Finding all simple paths between two vertices in a graph

There are built-in methods to find a shortest path between two vertices in a graph, and the question on finding all shortest paths between two vertices has gathered quite a bit of attention. A path ...
10
votes
2answers
187 views

NumberOfSpanningTrees command not working correctly

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a ...
10
votes
2answers
419 views

Proper way to add vertices to an adjacency matrix

I'm looking for a robust way to add vertices to a graph by modifying its AdjacencyMatrix. Here's what I have so far: ...
10
votes
2answers
730 views

Combinatorica package and graph-theoretical issues

I've searched for a solution to my problem a couple of days, and I didn't find one. Hope you guys can help me. I'm currently trying to solve some graph-theoretical problems. One of them is to find ...
10
votes
3answers
705 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. ...
10
votes
2answers
265 views

Why is NeighborhoodGraph so slow?

To get neighboring vertices I first tried: gg = GridGraph[{10, 10, 10, 10}]; VertexList[NeighborhoodGraph[gg, 1, 1]] // AbsoluteTiming {5.539308, {1, 2, 11, ...
10
votes
2answers
468 views

Dynamic graphics are less responsive inside a Manipulate

I have some code which displays a GraphPlot and allows the user to click on any vertex in the graph to display some information about that vertex in a popup window. ...
10
votes
1answer
509 views

Roads network visualization by thickness and color intensity by population from GIS files

We can have road networks of the countries in GIS shape file.For exmple from here. Normally traffic flows are proportionate to populations of the cities. I wonder how we can have the same in ...
10
votes
1answer
183 views

Issue with PathGraph

I am having a strange issue with PathGraph. Executing PathGraph[{a, b, c}] or ...
10
votes
2answers
424 views

Select a directed SubGraph without sinks and sources

Consider the following problem: Assume you have a large list of directed edges, that constitute a large graph. I would like to provide an initial subset of vertices and I need to know which additional ...
10
votes
1answer
150 views

Figuring out how AbsoluteOptions works with Graphs

I am puzzled by how AbsoluteOptions works with Graph objects. I would have expected that one could use it to obtain all the ...
10
votes
1answer
433 views

Drawing dessins d'enfants (bipartite graphs subject to certain conditions)

I want to write a function which constructs all possible dessins d'enfants (bipartite graphs fulfilling certain criteria, given below) from a collection of data presented in the following form: ...
9
votes
4answers
452 views

Show path with arrows in a matrix

I have a matrix, for example, 5x5 matrix Partition[Range[25], 5]. And I am given a list, for example: ...
9
votes
3answers
372 views

FindShortestTour for charity (or: How can I optimize meal delivery with FindShortestTour?)

I've been wondering about this for a while - but never got around to asking - until I saw faleichik's incredible answer to Mathematica Minecraft. I did some work at a not-for-profit a little while ...
9
votes
3answers
390 views

Remove redundant dependencies from a directed acyclic graph

Given a directed acyclic graph, I want to remove all the edges $v_i \rightarrow v_j$ if $v_j$ is reachable from $v_i$ by some other path. Given the rich set of graph algorithms in Mathematica, what is ...
9
votes
1answer
142 views

Algorithm used by IsomorphicGraphQ

I'd like to know which algorithm is used to test if two graphs are isomorphic?
9
votes
2answers
300 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 ...
9
votes
2answers
245 views

VertexSize doesn't scale with Graph layout?

I wonder about how I could make a Graph scale automatically when I vary the size of the vertices. I would like to visualize information with a ...
9
votes
2answers
242 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 ...
9
votes
1answer
646 views

When using GraphPlot with an adjacency matrix, how can I make Mathematica draw exactly one self loop for any non-zero weight?

I have tried using the option MultiedgeStyle->None, but apparently Mathematica doesn't treat self loops in the same way it treats edges. For example, I find ...
9
votes
1answer
347 views

Drawing Zonotopes from Adjacency Matrix

This is crossposted in cs.stackexchange.com, but I have been trying to use Mathematica do this and figured it might be more appropriate to ask here. Define a "simple zonotope" to be a regular ...
9
votes
1answer
119 views

How to get control over DepthFirstScan?

Is there a way to conditionally take control the flow during a depth-first scan against a TreeGraph? I have a tree graph whose nodes are constructed as object, and there's a method ...
9
votes
1answer
105 views

FindHamiltonianCycle is not invariant to edge permutation

Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the vertices in canonical order, ...
8
votes
2answers
1k views

Dynamic graph visualisation using JLink/Java and GraphStream

Visualising the addition of new nodes and edges to a graph to 'watch it grow' is to something Mathematica is not suited to by default. However this type of animation really helps convey the emergence ...
8
votes
2answers
437 views

Extracting vertex coordinates from an automatically laid out graph

Given a Graph with an automatically computed layout (i.e. not explicitly given VertexCoordinates, but using a ...
8
votes
3answers
241 views

Pairwise distances of points and classification using GraphDistanceMatrix

The challenge Given $n$ points in $\mathbf{R}^3$ and a cutoff distance, $d$, I would like to determine all pairs of points that are separated by less than the given cutoff distance, $d$, and all ...
8
votes
2answers
233 views

Organise a graph's vertices into levels

I would like to organise a graph's vertices in levels. Consider ...
8
votes
2answers
271 views

Graphing a network with state transition flows (of varying size)

In one of Stephen Wolfram's recent blog posts (http://blog.stephenwolfram.com/2013/04/data-science-of-the-facebook-world/#more-5350) he provides the network plot below. The size of the arrows that ...
8
votes
2answers
289 views

How do I convert this Nicomachus's Triangle to one with edges?

I want to put edges on this Nicomachus's Triangle r = 7; t = Table[2^(n - k) 3^k, {n, 0, r}, {k, 0, n}]; ColumnForm[t, Center] Is there an easy way to do this? ...
8
votes
2answers
227 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 ...
8
votes
1answer
160 views

Dual graph of an arbitrary (planar) graph

Every planar graph has a dual. How can I obtain it with Mathematica? I know that GraphData provides the DualGraph property for ...
8
votes
1answer
738 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 ...
8
votes
1answer
207 views

How can I sequentially apply different graph embeddings?

Imagine I have some graph G, and I perform a graph embedding using a command like: ...
8
votes
3answers
405 views

TreePlot with centered vertexes

I want to draw a tree plot for Euler totient function for this question like the following: I generate the EulerPhi for first 20 numbers into a list: ...
8
votes
1answer
166 views

Using GraphHighlight interactively

I want to build a small GUI, where the user can select either a single edge or a single node of a graph. I got to this point: ...
8
votes
1answer
597 views

How to add vertex/edge labels to existing graph

If I have already created a graph using Graph. Later, I want to add to the graph some vertex and/or edge labels, how can I do that? Thank you.
8
votes
1answer
444 views

Why does SocialMediaData return such a small FollowerNetwork?

I have hooked up my Twitter account to Mathematica and I have 1468 followers myfollowers = Length[SocialMediaData["Twitter", "Followers"]] 1468 I wondered what ...
7
votes
3answers
238 views

Converting Mesh in Density Plots to a Graph

Consider the following line of code: ...
7
votes
3answers
366 views

I can't understand FindShortest Tour

I can't understand the function FindShortestTour because of the result: FindShortestTour[{ {0, 1}, {5, 1}, {2, 1}, {10, 1}}] ...