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)

1
vote
1answer
92 views

Is there a TwoColoring function of Graph object?

The following code shows the GraphUtilities package makes a problem for Graph object. I want to use a ...
10
votes
1answer
548 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 ...
5
votes
1answer
523 views

All possible topological orderings of a graph

TopologicalSort[] returns one of many unique orderings. From wikipedia: if a topological sort does not form a Hamiltonian path, the DAG will have two or ...
5
votes
1answer
75 views

Setting PropertyValue for VertexWeight is not persistent

g = CompleteGraph[8, VertexSize -> Medium]; PropertyValue[{g, VertexList[g][[1]]}, VertexWeight] = 10; PropertyValue[g, VertexWeight] ...
3
votes
1answer
52 views

Problems with PropertyValue when Graph's vertices are Lists

I create a Graph which vertices are lists (points in n-dimensional space) ...
2
votes
1answer
323 views

GraphPath: *all* shortest paths for 2 vertices, edge lengths negative

Mathematica uses Bellman-Ford to find a shortest path between two vertices when the edge lengths are negative: ...
3
votes
1answer
160 views

How can I highlight and individually color the connected components of a graph?

I have a graph G, and I wish to individually highlight and color the different connected components of a graph. It is simple enough to do this for one component: ...
1
vote
1answer
165 views

Do any users know of methods to capture Twitter feeds and subject them to analysis? [duplicate]

I would like to use the output of about 300 Twitter sources and would probably collect 30 minutes of tweets at a time and subject each collection to analysis; ideally this process would be automatic ...
1
vote
1answer
96 views

FindEdgeCut with weighted graphs

If I want to find a minimum cut between two nodes in a weighted graph, I would use FindEdgeCut as follows: ...
7
votes
1answer
269 views

Adding/deleting weighted edges to a weighted graph

How can I add and delete weighted edges in a weighted graph? Using Graph in Mathematica I want to add a weighted edge to a weighted graph. The problem is ...
1
vote
2answers
121 views

Separating disconnected graph objects without losing vertex coordinate assignments

Say I have a graph Gtest, which has multiple disconnected components. I found that I can isolate individual components while retaining vertex coordinate ...
9
votes
1answer
105 views

FindHamiltonianCycle is not invariant to edge permutation

Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the vertices in canonical order, ...
0
votes
1answer
35 views

Parsing output from FindHamiltonianCycle to recover an ordered list of vertex positions for a discovered path

After applying FindHamiltonianCycle to a graph, one generates output that looks like the following: ...
3
votes
1answer
283 views

Generating a graph object where vertices are pixel coordinates and edges represent two pixels being in the same Moore neighborhood

I have a list of integer pixel positions, pts, and I wish to create one or more graph objects where vertices at these pixel positions share an edge if they are ...
2
votes
2answers
225 views

Manipulate graphs in 3D

Is it possible to Manipulate Graphs (e.g. a ...
3
votes
2answers
126 views

LineGraph Labels

I have a graph with labels on the edges: ...
5
votes
1answer
153 views

Keeping vertexcoordinates after adding a new vertex

I want to add a new vertex to a graph, with fixed VertexCoordinates but when I use VertexAdd, the new graph does not have the VertexCoordinates of the previous one. ...
5
votes
2answers
332 views

How to add new nodes to an existing graph with fixed (coordinates) nodes?

I'm ultimately trying to create a directed graph with some of the nodes in fixed positions and the other nodes placed around them in "acceptable" positions. It's better if I ask the question by ...
6
votes
2answers
341 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 ...
1
vote
1answer
151 views

Find size of vertex image relative to the graph coordinate system

I am trying to define a graph using my own VertexShapeFunction with an ActionMenu button being the vertex and a custom ...
2
votes
2answers
388 views

EdgeRenderingFunction question

Bug introduced in 9.0 and fixed in 10.0.0 (Edit 1 : I added this paragraph after the original post, for context) Some context for this question can be found in another post ...
5
votes
3answers
237 views
2
votes
3answers
182 views

Graph with $\{a,b\}$ as Vertex Instead of Number

I'm trying to create a graph which has $\{a,b\}$ as labels: ...
9
votes
1answer
352 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 ...
3
votes
4answers
473 views

Graph Creation in Mathematica: TSP

I'm trying to create the following graph in Mathematica Where do I start? I'm specifically trying to make a graph so that I can use it in TravelingSalesman[g], ...
7
votes
1answer
194 views

How to scale edge length and keep layout of edge-weighted Graph?

I love using Graph as structure to store and visualize my data in Mathematica. Consider the following simple example for creating a ...
1
vote
0answers
121 views

Network problem of visualization of vertex

I have a question about visualization of network in Mathematica: for example: for this network g = ExampleData[{"NetworkGraph", "Friendship"}]; when we ...
6
votes
5answers
474 views

Building graph based on the cities connection?

I built a Graph based on the permutations of city's connections from : ...
5
votes
2answers
325 views

Colorize and the Four-Color Theorem

We can write: MorphologicalComponents[image] // Colorize To assign a random set of colors to each component in some image. The example used for reference by ...
6
votes
1answer
158 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
511 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 ...
2
votes
1answer
169 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 ...
2
votes
2answers
183 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
252 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
181 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 ...
7
votes
3answers
370 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}}] ...
5
votes
2answers
2k 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 ...
4
votes
0answers
114 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
452 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: ...
9
votes
3answers
380 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 ...
0
votes
1answer
144 views

Subset of edges with a different color

I want to color a subset of the edges of my graph with a different color. My graph currently has a large number of edges, so the following is just a toy example ...
0
votes
2answers
120 views

Basic question on producing non-overlapping graph nodes in a graph

I am plotting a graph which has about 196 nodes. ...
1
vote
1answer
99 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: ...
6
votes
0answers
110 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
145 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
144 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 ...
2
votes
1answer
100 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 ...
3
votes
2answers
205 views

How can I construct “better” block graphs?

A graph is a block graph if it can be constructed from an undirected tree by replacing each edge with a clique. My method of generating "random" block graphs is as follows. The parameters are the ...
11
votes
4answers
9k views

Finding all simple paths between two vertices in a graph

There are built-in methods to find a shortest path between two vertices in a graph, and the question on finding all shortest paths between two vertices has gathered quite a bit of attention. A path ...
7
votes
2answers
651 views