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)

28
votes
1answer
950 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
159 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
232 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
213 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
227 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
575 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
555 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
843 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
399 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 ...
7
votes
1answer
779 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
128 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: ...
3
votes
2answers
198 views

FindShortestPath with negative weights isn't working

I have the following functions defined: ...
5
votes
1answer
219 views

How to view all graphs available in GraphData?

Is there a "gallery" view of all the graphs available in GraphData? I realize that some graphs may not lend themselves to such representation (e.g. some may have ...
8
votes
1answer
477 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: ...
1
vote
1answer
123 views

Is there an easy way to specify an arbitrary two-dimensional Polyomino tiling in Mathematica 8.0?

Is there an easy way to generate an arbitrary two-dimensional Polyomino tiling: http://en.wikipedia.org/wiki/Polyomino? Specifically, I would like to generate an array of integer coordinates, for ...
6
votes
1answer
826 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, ...
2
votes
1answer
238 views

making a TreeGraph VertexLabel that contains a text label and also a Tooltip?

I am trying to make a TreeGraph[] that has as labels for vertices both text and Tooltip. The text displays all the time, when the TreeGraph is plotted, and in ...
4
votes
1answer
128 views

Functional Programming: modify EdgeList based on condition

I have a simple functional programming question: I have a simple EdgeList defined in Mathematica, I would like to modify the value of certain element of the list based on a condition. I see how to ...
3
votes
1answer
310 views

How to assign graph-node label as node value?

I am facing the following problem: I need to work on several already-designed graphs, accessible in ".DOT" format. Mathematica can perfectly read these graphs, however because the nodes of the graphs ...
1
vote
1answer
226 views

How can I create Arguments Maps with Mathematica's graph functions?

I am relatively new to Mathematica, and I would like to know how I could use it to represent an Argument Map, such as those that you generate on online tools such as http://debategraph.org. The ...
7
votes
1answer
826 views

Dynamic Graph visualization

I'm working on a C++ library that will be used to construct and study certain graphs (as in a set of connected vertices, not a function plot). These graphs will be dynamic in nature (and can ...
2
votes
2answers
415 views

Edges and crossing

I want to make a program where I have a collection of labeled vertices and edges between the vertices such that they join up with edges $a_{1} a_{2}, \; a_{2} a_{3}, \ldots ,\; a_{n} a_{1}$, so the ...
3
votes
1answer
136 views

How do I union graph properties?

I have two graphs ...
15
votes
2answers
3k views

Solving the Travelling Salesman Problem

I've been trying to find some kind of mathematical computer software to solve the Travelling Salesman Problem. The Excel Solver is able to do it, but I've noticed there is a built-in function in ...
4
votes
3answers
491 views

Graph generation given number of edges and nodes

I was wondering if it is possible to have Mathematica generate all graphs with a given number of edges and nodes (and possibly restricting the adjacencies) and draw them I know that there are some ...
1
vote
1answer
160 views

How to preserve graph properties under subgraph in MMA9 [duplicate]

Possible Duplicate: Preserving labels when using graph functions I'm using g = SocialMediaData["Twitter", "FriendNetwork"] to get a nice graph with ...
8
votes
3answers
409 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: ...
7
votes
3answers
226 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: ...
2
votes
1answer
140 views

VertexList ordering of a simple graph

Given a simple graph like g=Graph[{b -> c, a -> b}] I would like to have f[g] resulting in ...
8
votes
1answer
457 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 ...
10
votes
2answers
744 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 ...
6
votes
4answers
2k 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}, ...
1
vote
2answers
150 views

Error changing edge thickness in a GraphPlot

I'm having some problems with the Mathematica graphics inspector. I want to make a graph with the following code: ...
4
votes
3answers
617 views

How to find all graph isomorphisms in FindGraphIsomorphism

I found the second definition of the function FindGraphIsomorphism not working. Here's the definition Mathematica 8 gives: ...
8
votes
2answers
456 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 ...
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, ...
24
votes
1answer
558 views

Reduce distances between vertices of graph to minimum possible?

This simple graph has vertex shapes of different sizes: ...
5
votes
1answer
377 views

Accessing the graph Thinning produces without losing all the edges' lengths/slopes

This is a follow up to the OCR question I had earlier. What I want to do is to use Thinning to create "skeletons" of images of characters and then compare their shapes, utilizing such properties ...
9
votes
1answer
147 views

Algorithm used by IsomorphicGraphQ

I'd like to know which algorithm is used to test if two graphs are isomorphic?
2
votes
0answers
198 views

How can I compute the chromatic index and number of a graph?

I saw a recent question from M.R. and realized there is no function to compute the chromatic index and number of a graph, other than a really slow method in the now deprecated Combinatorica. So, how ...
3
votes
2answers
253 views

Deleting a row or column of an adjacency matrix while maintaining the associated label

I am currently working with a weighted adjacency matrix for a directed graph, and it contains several 0 columns and rows. With the unaltered matrix, I am able to monitor the relations between vertices ...
1
vote
1answer
624 views

Using singular value decomposition for graph clustering

I have a fairly large graph (50-60 vertices) with directed, weighted edges, and I am attempting to cluster the vertices. Prior to this, I have only worked with undirected graphs having symmetric ...
3
votes
2answers
227 views

TreePlot EdgeLabeling Style

I am trying to control the style for edge labels in treeplot and have run into a problem. Consider these two graphs: ...
6
votes
1answer
673 views

Ordering vertices with minimum Edge Crossing in Circular Graphs

Weighted and sorted Mathematica circular graphs are shown below. My question is how to reorder the vertices in such a way that they have minimum cuts (intersection of edges) while keeping the circular ...
2
votes
1answer
256 views

Speed up iterated manipulations of a graph / table

I am trying to generate a version of Watts' model of cascading shocks to a network following the discussion on p. 20-25 of this article. The basic premise is to use the ...
14
votes
2answers
543 views

How can I speed up the classic GA for graph coloring?

I'm trying to compute the chromatic number of this graph (which is 28): g = Import@"http://www.info.univ-angers.fr/pub/porumbel/graphs/dsjc250.5.col"; My genetic ...
1
vote
1answer
204 views

Problem setting up edge rendering function

I have a graph, and I want my EdgeRenderingFunction to colour the edges based on the vertex they originate from. In this toy example, I'm trying to get the edge ...
7
votes
2answers
377 views

Can I put tooltips in a Graph?

This doesn't work: Is there a way to do this? My real goal is to identify the second links in the graph below, which shows the results of a webcrawl (using this code). I'm open to another ...
1
vote
1answer
177 views

EdgeRenderingFunction and Graph input output structure

I am trying to create an EdgeRenderingFunction but the more information does not help me at all as far as explaining what the ...