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)

14
votes
1answer
408 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?
13
votes
2answers
2k 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 ...
13
votes
6answers
681 views

Finding all paths of certain length between vertices in path graph, non-simple ones too

First I will tell you what my ultimate goal is, because maybe there's another way of doing it other than what I am trying. I need a list of all $(a_1, a_2, \ldots, a_N)$ tuples that satisfy certain ...
13
votes
2answers
409 views

How to build a 3D graph from a 3D matrix?

Following this and that question and the corresponding answers, Mathematica can build 2D graph from 2D matrices. Question How to make the corresponding 3D graphs from 3D cubes? Attempt ...
13
votes
4answers
521 views

How to recompute the layout of a Graph?

I asked a question about changing Graph properties in a similar way to how Show can change ...
13
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 ...
13
votes
2answers
426 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 ...
13
votes
1answer
447 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. ...
12
votes
4answers
2k views

Finding elementary cycles of (directed) graphs

I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...
12
votes
2answers
538 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
387 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
218 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
1k 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
2answers
963 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 ...
12
votes
1answer
709 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
0answers
104 views

A question about weighted graphs

Bug introduced in 8.0 or earlier and persisting through 10.2 or later I need create a weighted graph with given data. Number of nodes: $53$ $\quad$ Number of edges: $91$ ...
11
votes
4answers
763 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 ...
11
votes
1answer
433 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
313 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 ...
11
votes
2answers
317 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, ...
11
votes
1answer
382 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
216 views

Graph smoothing keeping vertices fixed?

Context Given a Graph like this one: ...
11
votes
2answers
560 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. ...
11
votes
2answers
558 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 ...
11
votes
1answer
176 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 ...
11
votes
1answer
520 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: ...
11
votes
1answer
85 views

Question about TransitiveReductionGraph

Bug introduced in 10.0 and persisting through 10.2.0. Note: TransitiveReductionGraph is new in 10.0. In Mathematica 10.0 and 10.1, according to the ...
10
votes
2answers
315 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
3answers
731 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 ...
10
votes
2answers
206 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
537 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
1answer
174 views

Algorithm used by IsomorphicGraphQ

I'd like to know which algorithm is used to test if two graphs are isomorphic?
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
3answers
899 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
578 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
1answer
89 views

IsomorphicGraphQ fails to recognize that two empty graphs are identical

Bug introduced in 9.0.1 or earlier and persisting through 10.2.0 Consider the following two graphs: ...
10
votes
1answer
964 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 ...
10
votes
1answer
778 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
2answers
306 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 ...
10
votes
2answers
196 views

Finding the minimum vertex cut of a graph

Bug introduced in 9.0.1 or earlier and fixed in 10.2.0 Note: FindVertexCut is new in 9.0. It seems that Mathematica is not correctly finding the smallest set of ...
10
votes
2answers
1k 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, ...
10
votes
1answer
188 views

Issue with PathGraph

I am having a strange issue with PathGraph. Executing PathGraph[{a, b, c}] or ...
10
votes
1answer
417 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 ...
10
votes
1answer
292 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
496 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
4answers
274 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
654 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 ...
9
votes
3answers
337 views

Label multiple edges between same vertices

I have a simple graph with multiple edges between two vertices, say: Graph[{ Labeled[a -> b, "A"], Labeled[a -> b, "B"] }] Unfortunately, Mathematica ...
9
votes
3answers
444 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
213 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.2.0 Problem is due to a BezierCurve bug. I don't understand why the following does not work: ...