Tagged Questions

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)

2
votes
0answers
168 views

Fast calculation of commute distances on large graphs (i.e. fast computation of the pseudo-inverse of a large Laplacian / Kirchhoff matrix)

I have a large, locally connected and undirected graph $G$ with $\approx 10^4$ vertices and $\approx 10^5$ to $\approx 10^6$ edges. Moreover I can bound the maximum vertex degree as $Q_{max}$. I ...
9
votes
1answer
321 views

Caching of Graph Graphics

In this answer, Simon Woods concludes that when you display an expression with head graph more than once, something is getting stored somewhere. I looked into it too and found out this only happens if ...
7
votes
3answers
246 views

Converting Mesh in Density Plots to a Graph

Consider the following line of code: ...
4
votes
0answers
262 views

Counting paths of a certain length between a source and sink vertex

I have a graph $G$, which may be directed or not, and I was wondering if there was an efficient way of using, say, BreadthFirstScan[] and FindShortestPath[] to count the number of paths between some ...
1
vote
1answer
182 views

How do I create a graph with randomly directed edges starting from a undirected graph?

I have an undirected graph $G$. How would I randomly assign directions to some fraction $p$ of the edges? How might I do this efficiently / quickly provided I have a large graph structure? For ...
0
votes
2answers
273 views

How to specify VertexCoordinates as geographic coordinates of cities?

I have been very busy these days with giving the VertexCoordinates of the cities the geographic coordinates from ...
2
votes
1answer
130 views

How to get a list of 3-connected graphs?

I'd like to use GraphData to get a list of graphs with vertex connectivity at least 3. I know GraphData["Nonplanar", 6] gives ...
2
votes
1answer
100 views

What is the best way to save a large graph object, allowing it to be reloaded quickly in a new kernel?

I generated a very large graph, too large to simply display and manipulate with copy/paste operations. How can I somehow save the graph to a file to allow it to be rapidly reloaded after I quit out ...
5
votes
1answer
154 views

Why do vertex labels disappear when I edit with drawing tools?

I'm trying to change the text and arrow style in GraphPlot using the drawing tool, but the the vertex labels disappear when I do that: ...
2
votes
1answer
137 views

double arrow in GraphPlot

Is it possible to combine two edges into one with a double arrow? For example: ...
7
votes
2answers
105 views

How can I recover a graph from a graphical output in a notebook after resetting the kernel?

I have an old Mathematica notebook with an output for a graph structure $G$ I would like to recover. However, the routine for building up the graph is stochastic, so I can't simply rerun the code. ...
7
votes
1answer
220 views

Making FindShortestPath a little bit sloppy [duplicate]

I have a dense graph, and I'd like to find multiple "almost shortest" paths from a source vertex, $v_s$, to a sink vertex, $v_s$, on an undirected graph $G$. How can I repeatedly run ...
5
votes
2answers
269 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$ ...
11
votes
1answer
329 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 ...
5
votes
2answers
226 views

Graph does not evaluate some options when not displayed

How can I force Graph to evaluate all its options without actually displaying the graph itself? Evaluating the following code ignores the ...
1
vote
1answer
208 views

Weighted Kirchhoff Matrix?

I have a weighted graph and I want its graph Laplacian matrix (what Mathematica calls the Kirchhoff matrix in the unweighted case). Is there an easy way to get this? For example, the command: ...
2
votes
1answer
119 views

Is it possible for me to explicitly specify a point list for SpatialGraphDistribution?

The function RandomGraph[SpatialGraphDistribution[n, r]] generates a random geometric graph over $[0,1]^2$ where vertices are connected if they are within a ...
2
votes
1answer
135 views

Determining whether two k-chromatic graphs are equivalent (not simply isomorphic) using IsomorphicGraphQ?

In a previous question of mine, I asked whether Mathematica's built-in routines could determine an isomorphism for two $k$-chromatic graphs, Determining whether two $k$-chromatic graphs are isomorphic ...
9
votes
2answers
263 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 ...
4
votes
3answers
465 views

How to create a planar graph from a set of random points

Question Given a set of points in the plane, how can you create a planar graph in the standard graph representation of Mathematica (version 9 or higher), from these points? Background A planar ...
0
votes
1answer
100 views

How does SocialMediaData determine vertex size

How does SocialMediaData determine the size of graph vertices, e.g. on what does the vertex size depend in, say, a Facebook friend network graph?
4
votes
2answers
169 views

HighlightGraph with style

In this picture you see a graph. The shortest path between vertex 5 and vertex 3 is highlighted in red. Instead I want blue highlighted edges of thickness 10. ...
6
votes
1answer
127 views

Tooltip not working in web deployed cdf

I deployed a CDF file in a web page. I used both Mouseover and Tooltip functions. They both work in the raw CDF file. The ...
1
vote
2answers
589 views

How do I divide the columns of a matrix by the sum of its elements?

I am trying to create a transition matrix for a network. In order to do this, I need to sum down the column (the out degree), and then divide the column by the out degree in order to normalize it. ...
5
votes
2answers
215 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 ...
4
votes
1answer
1k views

How can I draw the transition diagram of a Markov chain?

I apologize for my heaviness as I am a Mathematica novice. Is there a kind soul who can tell me how to draw diagrams like those shown on page 158, 160 and 161 of this document.Chaine de Markov I ...
3
votes
1answer
494 views

Adjacency List representation of a graph

I am looking to draw a graph knowing a simple adjacency representation of the graph like: A = {{1, 3}, {2, 3}, {3, 4, 5}, {4, 5}, {5}} Where ...
5
votes
3answers
1k views

Travelling salesman with start and end points for 30 points

I am doing a route optimisation for delivery vehicles and failing dismally. Please see problem statement below. My current solution uses FindShortestTour, but this does not have defined start and end ...
1
vote
0answers
101 views

Extracting Facebook Managed accounts (pages) in Mathematica? [duplicate]

I want to use Mathematica to explore various relationships on my Facebook pages. I've been able to successfully extract information on my personal Facebook page using the build in Social Media ...
0
votes
1answer
76 views

combining NeighborhoodGraph and RandomGraph

I have Combinatorica` and GraphUtilities` loaded in version 9 of Mathematica. If I then set: ...
3
votes
2answers
119 views

CommunityGraphPlot doesn't size

When I need to plot a 'large' graph with CommunityGraphPlot the output is always sized at the Mathematica default value. The Graph object itself can be resized with ImageSize option. However that ...
6
votes
3answers
313 views

Export Graph to PDF

I know that I exported Graphs to PDFs before but it doesn't seem to work any more. I tried K5 = GraphData[{"Complete", 5}] Export["K5.PDF", K5] And I get a PDF ...
3
votes
2answers
184 views

The same value of VertexSize for vertices in different graphs causes different vertices size

I generated some graphs. The smallest vertices in the 1st graph should be the same size as the smallest vertices in the second graph. The smallest vertices have the same size (...
3
votes
1answer
148 views

How to get VertexDelete to work?

I'm using Mathematica 9 and want to delete a single vertex and all associated edges on a graph but can't seem to get the function VertexDelete function to work. My code is below. I declare a graph ...
10
votes
2answers
486 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. ...
0
votes
2answers
212 views

Number of edges to each polygon of a graph constructed from an image

I have an image which looks like from How to convert an image to a graph and get the positions of the edges? which by using MorphologicalGraph becomes a graph ...
2
votes
0answers
109 views

Strange double evaluation using MorphologicalGraph

(MMA 9.0.0 on Mac OS/X 10.8) Please consider the following snippet (this is as SMALL as I could make it -- my attempts at making a smaller repro-case eliminated the effect that I am investigating) ...
3
votes
1answer
522 views

How to label the Vertex and, or Edge labels with their weight

I noticed that the Mathematica 9.0 documentation only mentions the usage of "Name" to label the vertexlabel or edgelabel in the Graph. Is there an option to use the Weights automatically just as ...
29
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 ...
2
votes
2answers
162 views

Most efficient way to output a cycle starting from an unordered list of graph vertices

I have some graph $G$ and a list of vertices $(v_1, ..., v_N) \in V$. Using graph structures in Mathematica version 9.0, what is the most efficient way to determine whether or not $(v_1, ..., v_N)$ ...
6
votes
1answer
237 views

What algorithm is Mathematica 9 using for “SpectralEmbedding” of graphs?

When I specify that a graph should be realized using the "SpectralEmbedding" procedure, what paper / algorithm for spectral embedding is this based on? I was unable to find any documentation for ...
8
votes
1answer
220 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: ...
5
votes
1answer
231 views

Processing and storing a graph with a large number of vertices s.t. k-hop neighborhoods are efficiently retrievable

I have an unweighted, undirected graph $G$ with $(v_1, ..., v_N) \in V$ vertices, where each vertex in the lattice represents a string of some length ($\leq 200$ characters), and I need to construct ...
21
votes
1answer
588 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 ...
4
votes
2answers
1k views

How do I plot a solution of a differential equation?

I am having trouble generating a plot for a solution to my differential equations. I always end up with just blank axes. ...
3
votes
1answer
567 views

Combinatorica vs Built-in functions: Use of MinimumSpanningTree

What kind of argument is expected by MinimumSpanningTree (from the package Combinatorica`)? Is it possible that I am providing ...
4
votes
2answers
879 views

Finding face vertices from the face adjacency graph

I have a question about face adjacency graphs. Suppose that I have an adjacency matrix ...
2
votes
3answers
407 views

GraphPlot only working when I evaluate twice

I have some code that builds a graph and some vertex coordinates, but when I evaluate it I get a message that the list of coordinates is not valid and the graph is not valid and it shows the output as ...
8
votes
1answer
845 views

Drawing a graph with specified edge lengths

I was wondering if it was possible to ask Mathematica to draw a graph provided some set of vertices: $(v_1, ..., v_N) \in V$ connected by $M$ edges $(e_1, ..., e_M) \in E$, where the length of each ...
4
votes
2answers
130 views

LayeredGraphPlot: two instances of the same label

What I'd like to do is to have the same label more than once in the plot. I.e. I do not want the edges to direct toward the first instance of that label! For example: ...