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.
2,267 questions
4
votes
1
answer
127
views
Is there any efficient way to find cycle matroid of a graph?
Is there any efficient way to find cycle matroid of a graph?
A cycle matroid is basically all sets of edges in a graph that does not form a cycle.
The code below works pretty well for small graphs, ...
- 1,407
3
votes
1
answer
79
views
How to generate all graphs that decompose into a given list of subgraphs at articulation points?
Given a list of directed edge-tagged graphs gList like this:
...
- 1,407
1
vote
0
answers
77
views
VertexContract cannot handle tagged edges when vertices are lists
VertexContract works with EdgeTaggedGraphs:
...
- 701
3
votes
1
answer
125
views
Why Graph and EdgeShapeFunction do not respect order of vertices of edges?
Switching between {1, 5} and {5, 1} has no effect on produced graphs even though EdgeList-s ...
- 32.5k
0
votes
1
answer
135
views
Accelerate Mathematica code computing visibility polynomial of one graph
Let $G$ be a graph of order $n$. Then the visibility polynomial, $\mathcal{V}(G)$, of $G$ is defined as
$$
\\
\mathcal{V}(G)=\sum_{i\geq 0} r_i x^{i}
\\
$$
where $r_i$ denote the number of mutual-...
- 2,294
0
votes
0
answers
76
views
How to solve the all-terminal network reliability problem in Mathematica?
I like to reproduce the algorithm(s) provided in https://arxiv.org/abs/1709.08561 to solve the all-terminal network reliability problem:
Given an undirected connected graph $G$, suppose each edge is ...
- 2,294
2
votes
1
answer
103
views
How to determine the direction of edges through a cutset in a graph?
I have the following directed graph and a cutset:
...
- 1,407
0
votes
0
answers
36
views
Mathematica: Factor a sum of graph terms by splitting disjoint diagrams and combining like factors
I have an expression that is a sum of graph terms. Each term is a pair {graph, coeff}, where graph is a list of edges. A single <...
- 101
5
votes
3
answers
275
views
How to find fundamental cycles of a directed graph?
I am trying to find the fundamental cycles of a directed graph in Mathematica. I defined my graph as follows:
...
- 1,407
2
votes
2
answers
207
views
Nice planar layout of graphs
What can be done when GraphLayout -> "TutteEmbedding" produces ugly graphs?
...
- 32.5k
5
votes
1
answer
103
views
Restricting GraphLayout of vertices in GraphPlot3D to discrete planes along the z-axis
GraphLayout can do a lot of cool things like when we set the option to SpringElectricalEmbedding and other embeddings for ...
- 687
2
votes
3
answers
370
views
Why does importing a .dot graph file cause \l and \r to become \n?
When I import a DOT file (or a string in that format) with labels containing the exact characters \\l or \\r, they are displayed ...
- 1,143
3
votes
2
answers
155
views
How can I efficiently find all cutsets of a graph based on the definition of cutset?
I want to find all cutsets of a graph based on the following definition:
A cutset is a set of edges of a connected graph G such that the removal of these edges from G reduces the rank of G by one, ...
- 2,151
1
vote
0
answers
71
views
Efficient calculation of Hosoya Index
The Hosoya Index is the number of independent edge sets (i.e., matchings) in a graph.
I have implemented it in Mathematica (based on the source code provided in ...
- 1
1
vote
1
answer
151
views
Rectangle counting in large bipartite graphs
For a bipartite graph, the local clustering coefficient of a node $v$ is the number of rectangles containing $v$ as a fraction of (something like, depending on the definition) the total number of ...
- 2,303
2
votes
1
answer
130
views
Generate only certain number of graphs because of limited RAM
I am using the code provided in the answer for this other question. It is shown below:
...
- 51
3
votes
1
answer
135
views
Important clarification about PlanarGraphQ
By definition, a planar graph is a graph that can be represented on a plane without intersecting edges.
...
- 2,665
2
votes
2
answers
254
views
How can we choose the numbers as shown in the figure to obtain the smallest possible final sum?
I have a graph
I have
When I go A-> B -> C->D->E->A I get the sum 23,
and
How can I find the numbers like the graph. I tried
...
- 167
0
votes
0
answers
94
views
How can I efficiently list non-cyclic edge combinations in a graph?
I'm trying to find all subsets of edges in a graph that do not form a cycle.
Currently, my approach is to generate all subsets of the edge set and use AcyclicGraphQ ...
- 1,407
1
vote
1
answer
114
views
GraphUnion not working correctly with multiedges
GraphUnion doesn't seem to produce the correct result. The output should be four blocks connected in a chain, but it's not. This appears to be another bug in ...
- 1,407
2
votes
1
answer
173
views
EdgeContract in multigraph
In the following code, I expected that only the edge between vertices 0 and 1 would be removed.
...
- 1,407
4
votes
0
answers
220
views
Generating random Hamiltonian cycle
I need random Hamiltonian cycles in directed graphs. I guess for me it would be OK to mean by that choosing uniformly randomly from the set of all Hamiltonian cycles. ...
- 2,459
1
vote
2
answers
112
views
How to copy edge directions from one graph to another with different labels?
I have two graphs, g1 and g2, defined as follows:
...
- 1,407
5
votes
1
answer
244
views
How to split a graph at two cut vertices?
How can I split a graph into two subgraphs, as shown in the image below, given a pair of cut vertices?
(Let's assume the user ensures that a valid pair of cut vertices is provided.)
The possible cut ...
- 1,407
3
votes
0
answers
114
views
I wrote one simple demonstration of Shannon Capacity of one graph. How to accelerate it?
I wrote one simple demonstration of Shannon Capacity of one graph. How to accelerate it?
$\Theta(G)=\sup \limits_{k }\left[\alpha(\underbrace{G ⊠ \cdots ⊠G)}_k \right] ^{1 / k}$
where $⊠$ denotes ...
- 1