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)

6
votes
5answers
414 views

Building graph based on the cities connection?

I built a Graph based on the permutations of city's connections from : ...
7
votes
3answers
343 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}}] ...
2
votes
1answer
149 views

How to set FindGraphCommunities Modularity's method option

It is possible to set 2 options for one of FindGraphCommunities's methods "Modularity". They are "Weighted" and "StopTest". The question is how can one use the second option "StopTest"? What ...
6
votes
1answer
152 views

Graph rendering not working as expected

I'm running the older Mathematica v6 which seems to go through the edges of graphs twice. Is this a bug? Is it fixed on the latest version? Please just try this command: ...
1
vote
1answer
417 views

Adding an image background to a graph that uses vertexposition

Hello Mathematica stackexchange community! I need your help on a research project. I'm looking to create a graph g with vertices in specifies places and then use an image I have as the background of ...
5
votes
2answers
1k views

How to find the Shortest Path, visiting ALL vertices, without coming back to the start (Hamiltonian Path, minimum distance)

A car has to pick up each person and take them to their destination. I am trying to find the shortest tour that will do this. How can I find the shortest path between any s and t.... visiting all ...
2
votes
2answers
153 views

Adding Dynamic functionality to a Graph

I would like to make the edges and vertices of a Graph interactive, a simple demonstration is to change their colors: ...
4
votes
2answers
212 views

Efficiently determining the largest minimum cost to travel from a fixed source to an arbitrary sink in a weighted graph

Let $v_i$ be a vertex in a graph $G$ with vertices $(v_1,...,v_N) \in V$ and edges $(e_1,...,e_M) \in E$ with associated weights $(w_1,...,w_M)$. Let $v_s \in V$ be specified vertex in the graph. In ...
1
vote
0answers
144 views

Get path to end nodes in directed (partially cyclic) graph

I have a large directed graph containing small loops. I would like to extract all paths to all end nodes (no VertexOutComponent) with a given path length $n$. I ...
9
votes
3answers
355 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 ...
4
votes
0answers
100 views

Efficient Generation of Subgraphs (or, unfriend a friend a day)

NB: If you're not interested in the back-story, you could simply jump forward to the code which I'm seeking to optimize. Also, I believe this code would only work for MMA 8.0 and above. My friends ...
1
vote
1answer
356 views

Plotting a network or a graph with given coordinates for vertices

I'm new to Mathematica yet have coded a lot in MATLAB. Currently I'm working on a network simulation. My model is implemented in MATLAB, but I need to port it to Mathematica. Here is my question: ...
6
votes
1answer
120 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 ...
2
votes
1answer
97 views

PermuteSubgraph not working? (Combinatorica)

I am trying to write a code to perform the QAP partialling analysis (here's a paper to know more) but the part in which I "scramble" the graph with PermuteSubgraph does nothing, I am actually not ...
0
votes
2answers
107 views
1
vote
1answer
94 views

How do I change the Head of Graph into List?

I am trying to change the Head of b (a NeighborhoodGraph) from Graph into List but Apply seems to fail. I start with a list of connected vertices: ...
8
votes
1answer
202 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: ...
6
votes
0answers
105 views

Is there a function to generate a minimal clique cover?

This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and ...
1
vote
1answer
121 views

How can I preserve the properties of edges of the original graph $g$ in a subgraph that doesn't include every edge of $g$?

The closest question to the following I could find was Preserving labels when using graph functions, but it doesn't seem to cover this. Consider a graph g where ...
1
vote
1answer
2k views

I want to draw a graph using a weighted Adjacency matrix

I have a weighted adjacency matrix as follows: ...
1
vote
1answer
117 views

How can I get precisely the subgraph corresponding to a set of edges?

Consider the complete graph on 3 vertices. Then, a method gives me a list of interesting edges, say $\{(1,2),(2,3)\}$. I want to get a subgraph of $g$ that corresponds to precisely the given ...
1
vote
2answers
126 views

Converting polygon to graph in V7

I've unsuccessfully tried many ways of converting polygon points into a graph using Mathematica 7, and I am frustrated. I looked at this post, but it doesn't work: ...
7
votes
0answers
249 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 ...
8
votes
2answers
880 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 ...
5
votes
1answer
414 views

How can I draw a polygon from a set of angles?

In recreational mathematics, polytans are polygons formed by edge-connecting isosceles right triangles. Order-n polytans are those constructed from n such triangles. My question is this: Given a ...
1
vote
1answer
129 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 ...
0
votes
2answers
223 views

How can I give graph required data with GUI?

Consider that I have the simple graph of ...
4
votes
2answers
219 views

Convert Graph to Graphics

In Mathematica 9, a graph is returned as an object with head Graph: In[8]:= CompleteGraph[8] // Head Out[8]= Graph ...
13
votes
1answer
494 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 ...
9
votes
2answers
231 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 ...
2
votes
1answer
253 views

Isomorphisms for graphs with loops and multiple edges

I am working with graphs with multiple edges and loops, and I want to eliminate all isomorphic graphs from a long list I've generated. The FindGraphIsomorphism ...
12
votes
2answers
254 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 ...
5
votes
2answers
260 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$ ...
5
votes
2answers
180 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 ...
1
vote
1answer
247 views
25
votes
1answer
750 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 ...
3
votes
0answers
90 views

shortest paths in probabilistically weighted edges? [duplicate]

I understand Mathematica can find shortest paths. However, is it also able to find the most probable paths? I mean this is a case where edges are given probabilistic wights (from 0 to 1) and the most ...
1
vote
1answer
115 views

How can I stop DiscreteMarkovProcess[] from relabeling vertices?

I'm attempting to calculate the mean first passage time between two vertices, $v_1$ and $v_2$, provided some undirected graph $G$. However, I noticed that running the following script: ...
1
vote
0answers
74 views

What algorithm is Mathematica using for FirstPassageTimeDistribution[]?

What algorithm is Mathematica 9 using for FirstPassageTimeDistribution[]? Is it attempting to use PseudoInverse[] on the ...
2
votes
2answers
326 views

Create a planar graph from a set of random points

A planar graph is a graph embedded in the plane in such a way that the edges intersect at vertices. This is an example of a planar graph: g = GridGraph[{3, 3}] ...
5
votes
3answers
582 views

Random Geometric Graphs

I'm trying to implement an application which uses random geometric graphs in Mathematica, but it seems Mathematica lacks the functionality. I need the following functionalities: Generate a set of ...
0
votes
2answers
92 views

How can I efficiently and uniformly sample the set of vertices a fixed edge-wise distance away from a chosen vertex?

I have a large graph $G$, which may be either directed or undirected. How would I use DepthFirstScan[] or BreadthFirstScan[] to ...
0
votes
1answer
121 views
0
votes
2answers
239 views

Draw network graph and get the coordinates of each node

I would like to draw an undirected graph by specifying the nodes and the edges among them. This is currently done by, for example: ...
2
votes
3answers
228 views

Drawing a complete graph of an ego network

I have an ego network (a network of a person (ego) and his friends). It is drawn with the ego at the center surrounded by the friends. It might be possible that all the friends are connected to each ...
2
votes
0answers
121 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 ...
4
votes
0answers
205 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 ...
6
votes
3answers
208 views

Converting Mesh in Density Plots to a Graph

Consider the following line of code: ...