Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [graphs-and-networks]

Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.

161 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
17
votes
0answers
234 views

GridGraph[{6,6,6}] crashes—can you reproduce this?

Bug introduced in 11.3 and fixed in 12.0 Occasionally, I see a kernel crash with GridGraph[{6,6,6}]. It is not easy to trigger. Sometimes it may require as many ...
13
votes
0answers
440 views

Issues adding properties to multigraph

Bug persisting through 12.0 Unsupported Functionality (loosely, a bug) Mathematica (as of 11.0.1 for Mac OS X x86 (64-bit) (September 21, 2016)) does not support multi-graph where edge properties ...
10
votes
0answers
164 views

FindVertexCut & FindEdgeCut

Bug introduced in 9.0 and persisting through 12.0 FindVertexCut is new in 9.0. Note: Before 10.3, the bug can be reproduced by wrapping the first argument in <...
10
votes
0answers
609 views

How to generate a random flow graph?

A flow graph is a rooted directed graph that the root reaches all other vertices. I need to generate a random flow graph in Mathematica. My idea is to use ...
9
votes
0answers
109 views

How to implement graph neural networks in Mathematica?

Graph neural networks are useful for prediction tasks like predicting walks. In python I use DeepGraph typically, but I'm wondering what can be done in the new Version 12. Here's a nice introduction ...
9
votes
0answers
268 views

FindMaximumFlow generates a weird result

Bug introduced in 10.0 and persisting through 12.0 Try the following program: ...
9
votes
0answers
165 views

More efficient way to generate lattice graph with edges between visible vertices?

Given a nXn lattice, I need to generate the graph such that there is an edge between two vertices iff they are directly "visible" to each other, i.e., there is no vertex between them. I'm using <...
9
votes
0answers
113 views

Graph: PropertyValue changes and Dynamic

I almost never work with Graph in Mathematica but lately I helped someone with it. For this, I tried to make an animation using ...
8
votes
0answers
54 views

Probable bug in EdgeAdd when adding edges to multigraphs

Bug introduced in 10.0 or earlier and persisting through 12.0 M10.0.2 and M10.3 return a wrong result without errors. M11.0 and M12.0 issue a flood of messages and sometimes crash. I am using ...
8
votes
0answers
117 views

StableMarriage vs. FindIndependendEdgeSet: How to use the procedure FindIndependendEdgeSet as a Gale-Shapley algorithm?

From Help, the procedure StableMarriage was an element of the Combinatorica, but it is available in the built-in ...
7
votes
0answers
48 views

Is it possible to extend the graph layout framework with our own methods?

The GraphLayout specification can take complex forms, where we can specify separate vertex layouts, edge layout and packing layouts. Often each of these takes more ...
7
votes
0answers
100 views

Functionality of FindMaximumFlow

I know that the superseeded function NetworkFlow (needs Combinatorica) uses Goldberg-Tarjan's Push-Relabel-Algorithm but i cant find any information on Mathematica's built-in-function (...
7
votes
0answers
88 views

VertexDelete not working on graph with VertexWeight

Bug introduced in 10.0 and fixed in 10.3 Good afternoon, I have observed an "unexpected behaviour" with VertexDelete and a graph with vertex weights. This is a minimal working example: OK ...
7
votes
0answers
238 views

Using Graph to cull correlated lists

I have a set of lists that represent molecular descriptors. I need to identify which descriptors are highly correlated and eliminate the correlated pairs. I can represent the connectivity by ...
6
votes
0answers
179 views

Does DegreeGraphDistribution sample uniformly?

Bug introduced in 10.0 or earlier and persisting through 12.0 The first symptom (histogram below) is gone in 12.0. The second (fraction of connected graphs) persists, showing that the sampling is ...
6
votes
0answers
58 views

What method does FindGraphCommunities use with Method -> “Centrality”?

Cross-posted to W Community I would like to know what method FindGraphCommunities uses with the option Method -> "Centrality"...
6
votes
0answers
76 views

Querying vertex properties on graphs whose vertices are lists

Bug introduced in 10.0 or earlier and fixed in 11.3 Cross-posted on Wolfram Community Consider the following graph with the vertex property "foo". ...
6
votes
0answers
123 views

how to efficiently generate all directed graphs with 6 vertices

I am attempting to generate all non-isomorphic directed graphs with 6 vertices using command ListGraphs[6, Directed].But it does not work efficiently and takes a ...
6
votes
0answers
181 views

What's the meaning of FindVertexCut?

Bug introduced in 9.0 or earlier and persisting through 11.1 Is there a conflict in these two places in the documentation? In the Basic Examples: Then the Properties & Relations But actually:
6
votes
0answers
611 views

Finding quasi-cliques

What is the best way to identify quasi-cliques in a graph in Mathematica? I don't think it has been implemented, so are there any solutions to do this? Or do I have to export the graph data somehow ...
5
votes
0answers
87 views

Graph problem with IGraphM package

Consider the graph: ...
5
votes
0answers
98 views

Generating random mixed multigraph with random edge weights

The following function generates a random mixed unweighted multigraph: ...
5
votes
0answers
284 views

How to do a Sankey Diagram with multiple notes in Mathematica

I want to create a Sankey Diagram that looks like this: I read the post on How to Make a Sankey Diagram, but I can't seem to make the right adjustments to get the diagram I want. Is there a way to do ...
5
votes
0answers
152 views

Number of 4-colorings of Johnson solids

I want to know the number of 4-colorings for all Johnson solids. This is equivalent to evaluating the flow polynomial for the corresponding polyhedral graphs at $k=4$. I tried the following to get ...
5
votes
0answers
192 views

FindGraphCommunities method options?

FindGraphCommunitites has a couple of method options: "Modularity", "Hierarchical", ...
5
votes
0answers
637 views

Finding a Graph Shortest Path with Custom Graph Distance Function

What is the best way to find a shortest path by using a custom distance function? I'm trying to play a little bit with the concept of using distributions instead of a deterministic weight value for ...
4
votes
0answers
62 views

Graph Partition

Consider a graph 'g': ...
4
votes
0answers
40 views

Weird behaviour when importing a mixed graph from GraphML file

Consider a mixed graph G1 stored in GraphML file: ...
4
votes
0answers
170 views

Loopy Belief Propagation

I look for an efficient way to implement a Belief Propagation in Pairwise Markov Random Field. Each node is a binary random variable, and the unary potential function is ...
4
votes
0answers
902 views

How to find the a minimum cost perfect matching

Crossposted on Wolfram Community A a minimum cost perfect matching is very useful tool.This three links about this demand just related me,let alone all MMA.SE. How to get some pairing with smallest ...
4
votes
0answers
208 views

Finding all Minimal Cut Sets for Site Percolation?

Bug introduced in 9.0 and persisting through 11.3.0 FindVertexCut and FindMinimumCut are new in 9.0. I want to disconnect the ...
4
votes
0answers
61 views

Why NearestNeighborGraph gives different result for numerical List and exact List

In mathematica 10.3 there is a function called NearestNeighborGraph. I found some behavior of it that I don't understand. First I generate a 2D list like this <...
4
votes
0answers
211 views

Better control of vertex positions in GraphPlot?

I am trying to graphically visualize a sort of a transformation network. My program generates a list of vertices and edges and I want to turn that into a visually clear graph fulfilling a few ...
4
votes
0answers
182 views

Graph plotting: specify layers for layered drawing

Mathematica can do layered graph drawing with LayeredGraphPlot or GraphLayout -> "LayeredEmbedding". Is it possible to ...
4
votes
0answers
546 views

Understanding performance: graph connected components

I need to analyze directed graphs with 10M edges, 1M vertices, and 300K strongly connected components, so that the largest one contains 400K vertices. I read some explanations of Leonid Shifrin here, ...
4
votes
0answers
91 views

Can BreadthFirstScan be modified?

I would like to obtain a "slick" implementation of A*-search algorithm on Graph objects, using the built-in BreadthFirstScan (if that is possible at all). I noticed that BreadthFirstScan is static in ...
4
votes
0answers
1k views

A* algorithm for finding shortest path in a graph

FindShortestPath finds the shortest path between two vertices in an edge-weighted graph, allowing a choice between the Dijkstra and Bellman-Ford algorithms. In my (limited) understanding, both of ...
4
votes
0answers
150 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 ...
3
votes
0answers
60 views

Steiner Tree Approximation

I am wondering about the existence of Mathematica code to find (approximate) Steiner trees in graphs. I know there are a number of algorithms to do so --- just curious if anyone has implemented any ...
3
votes
0answers
50 views

IncidentGraph not showing edge weights correctly

I am performing the following commands: ...
3
votes
0answers
113 views

Hopcroft's Algorithm for Minimization of Deterministic Finite State Automaton

Background Given a deterministic finite state automaton, Hopcroft's algorithm is a $O(n \log(n))$ algorithm for finding an automaton that generates the same language with a minimal number of vertices....
3
votes
0answers
63 views

FindPath: adding one's own heuristic?

Mathematica is incredibly powerful. More often than not, for whatever it is one wishes to do all the supporting functions already exist in Mathematica. This makes development incredibly quick and ...
3
votes
0answers
61 views

HighlightGraph without redrawing the underlying graph?

I have an animation that generates a graph, then highlights different points on it over time. I use HighlightGraph. The graph is very big, and this seems to bog ...
3
votes
0answers
167 views

Power law fitting package that optimizes fitting parameters based off of the KolmogorovSmirnov MC method

I'm exploring power law fitting and would like to get to a point of making a power law package like what was discussed in this post, where OP references the R poweRlaw package. As per the comments/...
3
votes
0answers
86 views

Automorphism group and its order for a multigraph with loops using IGraph/M (or anything else)

I found this post: How to compute the automorphisms of graphs with multiple edges? about how to compute the automorphism group order for a multigraph (labeled and undirected). Even ...
3
votes
0answers
131 views

How to deal with these source vertices?

This is uncompleted answer for this post based on NearestNeighborGraph.I'm lost in how to deal with that source vertices(whose vertex in-degree is 0.) in ...
3
votes
0answers
110 views

Want to improve Career Lattice Graph

I'm attempting to improve the following Graph: ...
3
votes
0answers
80 views

Generating All Regular Multigraphs — Issue with Solve and/or FindInstance

I'm looking to generate all regular multi-graphs over $n$ vertexes and of degree $d$ in mathematica (side note: $n,d$ are fairly small, this problem gets unmanagable very fast). So here $n,d$ are my ...
3
votes
0answers
481 views

Min Weight Perfect Matching on General Graphs

I'm looking for a minimum weight perfect matching algorithm in Mathematica. Ideally, it should be able to handle arbitrary weighted graphs (e.g. not just bipartite, as that case is easy), although I ...
3
votes
0answers
45 views

WeightedAdjacencyMatrix does not complete for Connected Graph

Please see code snippet below - I have a weighted, connected graph that models a software process using a DiscreteMarkovProcess. I set some of the edge weights to ...