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)

10
votes
1answer
1k 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 ...
10
votes
1answer
183 views

Algorithm used by IsomorphicGraphQ

I'd like to know which algorithm is used to test if two graphs are isomorphic?
10
votes
3answers
309 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: ...
10
votes
2answers
638 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: ...
10
votes
3answers
989 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
1answer
70 views

Arrows from GraphicsComplex not converted to Normal form correctly

Bug introduced in 7.0 or earlier and persisting through 10.3.1 or later Show @ Graph[{1 -> 2, 2 -> 3}, Frame -> True] Normal @ % Is this a pure bug, ...
10
votes
1answer
888 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
763 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 ...
10
votes
2answers
427 views

Removing edge weights from a Graph

How can I remove EdgeWeights from a Graph without affecting any other properties of the graph? Let's construct a graph with ...
10
votes
1answer
192 views

Issue with PathGraph

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

How can I efficiently check if a graph is unit distance?

A unit distance graph is a graph that is embeddable in the plane so that every edge has length 1. ...
10
votes
1answer
388 views

Shortest tour with vertex priority

I changed the title of my question and tried to simplify formulation of the problem. I solve a very big vehicle routing problem. I divided this one big problem on many small sub-problems. Each small ...
10
votes
1answer
325 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 ...
9
votes
4answers
505 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
2answers
469 views

Sierpinski carpet with GraphData

Is this graph in the list among the so-called "standard" structures used in GraphData? However, I have not found, yet, anything like "Carpet" or "Sponge" in the ...
9
votes
4answers
303 views

Multiple Forms of Transportation Between Cities

I want to be able to show different connections between cities based on modes of transportation. For instance, you could walk to any city, but it would take a long time, you could take a train, but ...
9
votes
2answers
219 views

Graph subtree with respect to the flow

So let's say we have a TreeGraph: ...
9
votes
2answers
507 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 ...
9
votes
3answers
478 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
2answers
249 views

Self-loops in Graph may not display correctly or export correctly to PDF (due to BezierCurve problem)

Bug introduced in 10.0 and persisting through 10.3 Problem is due to a BezierCurve bug. I don't understand why the following does not work: ...
9
votes
2answers
354 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
325 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
1answer
230 views

Possible improvements to this Syracuse (3x+1)/2 graph?

This algorithm produces the Syracuse disjoint tree graph without any duplicates. No need for Union, For, and ...
9
votes
2answers
1k views
9
votes
1answer
950 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.
9
votes
2answers
274 views

Relaxation of Mass-Spring System with Pinned Masses

Problem Assume that four masses are connected to each other by springs while two of them are pinned down at their initial positions. Find the position of masses when system is at its minimum ...
9
votes
1answer
345 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 ...
9
votes
1answer
65 views

Cannot set VertexCoordinates twice in a Graph. Workaround?

Versions 10.0-10.2 seem to have a bug when trying to set VertexCoordinates twice on a graph (version 9.0 is fine). Can you confirm it? What is a good workaround ...
9
votes
1answer
137 views

FindHamiltonianCycle is not invariant to edge permutation

Bug introduced in 9.0.1 or earlier and fixed in 10.0 Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the ...
9
votes
1answer
679 views

How can I display a multigraph with different colored edges?

I'm new to Mathematica(version 9) and I'm trying to display a multigraph with different colored edges. Here's my code so far: ...
9
votes
1answer
139 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
0answers
82 views

Set new edge capacity

Bug introduced in 9.0 or earlier and persisting through 10.3.1 I am trying to add a new edge to an existing graph and set its capacity, but for some reason the ...
8
votes
5answers
433 views

Is there a neat way to generate the odd set constraints matrix?

Given a undirected graph $G=(V,E)$, I am trying to generate a related matrix $M$, where columns are indexed by $E(G)$ and rows are indexed by all odd subsets of $V(G)$. I can finish this task using ...
8
votes
3answers
644 views

How can one draw a network with nodes and links in a grid shape?

I'd like to be able to use MMa's graphics to make something like this which I know must absolutely be possible (and probably easy) with MMa. I don't actually even need different colors (though ...
8
votes
2answers
651 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 ...
8
votes
3answers
445 views

How to remove all dead ends from a undirected graph?

so what I want to do is take an undirected graph, and remove all the "dead ends" (that is, vertices that are attached to only one other vertex), but do it in such a way that it does it until reaches ...
8
votes
2answers
2k 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
3answers
355 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
4answers
361 views

Can I stop edges in graphs from drawing on top of the vertices?

Consider the following testadj = RandomVariate[BernoulliDistribution[0.15], {50, 50}]; AdjacencyGraph[testadj, VertexSize -> Large] The nodes are almost ...
8
votes
3answers
824 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 ...
8
votes
2answers
353 views

Is there a bug in FindClique?

If h is a graph, FindClique[g, {n}] should return a clique on exactly $n$ vertices if one exists in ...
8
votes
2answers
329 views

Organise a graph's vertices into levels

I would like to organise a graph's vertices in levels. Consider ...
8
votes
2answers
379 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
1answer
402 views

Coloring edges of a graph according to their weight?

What's the simplest way to plot a graph with weighted edges, such that the color of the edge corresponds to the weight of the edge?
8
votes
2answers
295 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
2answers
187 views

Efficient solution for a discrete assignment problem with pairwise costs

Let's consider a simple graph with N vertices, and a corresponding set of N items. The goal of the problem is to assign every item to a vertex on the graph so that sum of a per-edge (that is ...
8
votes
2answers
363 views

Creating a hyperlink graph from Wikipedia

This goes out to all the Mathematica experts - I'm hoping to get some helpful comments, ideas or code for that matter. In my attempts to maximize learning efficiency I had the idea to create an ...
8
votes
2answers
3k 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 ...
8
votes
4answers
4k views

How to generate and draw simple bipartite graphs?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets. Given two lists: {1, 2, 3} and {x, y, z}, ...
8
votes
1answer
179 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: ...