New answers tagged graphs-and-networks
5
If you are determined to work from the way the graph has been drawn, then you need to modify the input image to get it into a form MorphologicalGraph can work with. This is one way of doing it - the idea is to fill in the circles where the vertices are then use Thinning:
img=
Then (the value of 'r' arrived at from experiment):
With[{r = 12}, TopHatTransform[...
5
img = Import["https://i.stack.imgur.com/g4Z5W.png"]
We can identify the circles representing vertices and remove them and fill the spaces of removed vertices to get an image to pass to MorphologicalGraph:
img2 = Colorize @ DeleteBorderComponents @ MorphologicalComponents @ Binarize @ img
img3 = DeleteSmallComponents[img2, 500]
img4 = Binarize @ ...
3
The circles in your drawing are recognized as branch point. Therefore, do not draw circles.
Here is an example picture:
With this pictures stored in im:
im = ColorNegate[im]
MorphologicalGraph[im]
We get the following graph:
3
As per the "Applications" section of the documentation, you can use ColorNegate:
As per your comment: if you want to get Daniel Huber's graph from your image, try
MorphologicalGraph[ColorNegate@Binarize@Erosion[i, DiskMatrix[20]]] where i is the image.
1
A one-liner:
Length@Select[Graph /@ Subsets[EdgeList[CompleteGraph[4]]],
Sort@VertexDegree[#] == {1, 1, 2, 2} &]
EdgeList[CompleteGraph[4]] will give us all the possible edges on four vertices, Subsets will give us all the possible subsets of those edges, and Graph will turn those into graphs. (When a vertex is isolated, it will not be included in the ...
10
I had an old program lying around that will generate all realizations of a degree sequence. The first vertex will have degree equal to the first element in the input list, the 2nd degree equal to the 2nd element, and so on.
The program requires my IGraph/M package for graphicality testing.
For details on how it works, see http://bolyai.cs.elte.hu/egres/tr/...
5
4X4 adjacency matrices:
am = Tuples[{0, 1}, {4, 4}];
4X4 adjacency matrices with no self-loops:
simpleam = DeleteDuplicates[(1 - IdentityMatrix[4]) # & /@ am];
Adjacency matrices for undirected graphs on 4 nodes:
undirectedam = Select[# == Transpose@# &]@simpleam;
Adjacency matrices for graphs with vertex degree sequence {1,1,2,2}:
vdegree1122am = ...
1
I should indicate from the outset that this is not an answer to the question but an option to the OP for exploring different versions of his/her question. I should further indicate that the main function in the following code belongs to @kglr, who has developed it a few years ago. I could not find the link to share with you. Therefore, I give a small example....
2
We can use VertexComponent and FindPath to find all paths from a starting node as follows:
ClearAll[f]
f[g_, v_, l_] := Join @@ (FindPath[g, v, #, {l-1}, All] & /@ VertexComponent[g, v, l-1])
Example:
g = GridGraph[{10, 10}, VertexStyle -> White,
VertexLabels -> Placed["Name", Center], VertexSize -> Large];
Multicolumn[f[g, 36, ...
2
To simplify calculations, we introduce an x/y coordinate system x=1..10/y=1..10. The root: 36 reads then: {4,6}.
To change from x/y to linear coordinates, we define:
Clear[testwalked, step, tolin];
tolin[pos_] := (pos[[2]] + 10 (pos[[1]] - 1));
We further need a routine that checks if a move is acceptable:
testwalked[walked_List, dir_] := Module[{pos = Last@...
7
EDIT 01:
Found some time to package these in a function (see end of post for code).
It accepts an association as input, with the following key-value pairs:
"nodes": Association with integer keys (one per column of nodes) and a list of nodes for that column
"ribbons": List of ribbons to plot of the form source->target, given as a two ...
3
I am using the IGraph/M package for this answer.
Approach 1:
Generate Prüfer sequences, convert to trees, filter duplicates based on canonical labelling.
In[17]:= Needs["IGraphM`"]
In[18]:= n = 7;
In[19]:= DeleteDuplicatesBy[
IGFromPrufer /@ Tuples[Range[n], n - 2],
CanonicalGraph
] // Length // AbsoluteTiming
Out[19]= {2.0961, 11}
...
1
edges = {a -> c, b -> c};
TransitiveReductionGraph[Graph[#, edges],
VertexLabels -> Placed[{"Name", "Index"}, {Before, After}],
GraphLayout -> {"LayeredEmbedding", "Orientation" -> Top},
PlotLabel -> Row[{"VertexList: ", #}]] & /@
Permutations[{a, b, c}] // ...
1
1. Replace 5 in the table iterator with VertexList[g]:
g = labeling[relations, {1, 2, 3, 4, 5}];
g = SetProperty[g, {VertexLabels ->
Table[i -> Placed[{i, PropertyValue[{g, i}, VertexWeight]}, {Above, Below}],
{i, VertexList[g]}]}]
Using
g = labeling[relations, {1, 2, 3, 4, 5}];
g = SetProperty[g, {VertexLabels ->
Table[Placed[{i, ...
2
The thing that makes v_ a pattern is the _, which matches any single expression by itself. Indeed, f[_] := expr is sometimes seen, and f will return expr regardless of input. v_ is just a way of naming the thing that _ matches, so you can keep track of it on the right hand side of :> or :=!
v, on the other hand, is a literal pattern that only matches the ...
2
From SetProperty >> Details
That is, SetProperty[obj,...] does not modify properties in place. We need to do obj = SetProperty[obj, ...] to modify the properties of obj.
Illustration using a simple example:
g0 = Graph[{1 -> 2, 2 -> 3}];
PropertyValue[g0, EdgeStyle]
Automatic
SetProperty[g0, EdgeStyle -> {(1 -> 2) -> Red, (2 -> 3) -&...
3
Here is a very quick and dirty solution which takes advantage of the new molecule editor just recently added in 12.2
MoleculeGraph[MoleculeDraw[]]
To make a graph, you can simply make a "molecule" where all of the atoms are vertices and all of the bonds are edges. And then use the built in MoleculeGraph function to convert it into a graph. Here's ...
7
graph2 = SetProperty[graph1,
VertexCoordinates -> ReflectionTransform[{0, -1}] @ GraphEmbedding[graph1]]
Show[graph1, graph2, Axes -> {True, False}, Ticks -> False]
Alternatively, you can use the built-in graph layout "LayeredDigraphEmbedding" with the option "Orientation" -> Top or "Orientation" -> Bottom:
...
3
Update 2: Using EdgeStyle
NearestNeighborGraph[data, 1, VertexSize -> Large,
DirectedEdges -> True,
EdgeStyle ->
{e_ :> Arrowheads[{{If[EuclideanDistance @@ List @@ e < 28, .02, .04], .75}}]}]
Update: "need all arrows, with the exceptions of the ones which are too close, to have the same size"
1. Identify the $k$ shortest ...
1
swapLabel[g_, v_] := Module[{vo = Rest @ VertexOutComponent[g, v, 1]},
If[vo === {}, {v -> PropertyValue[{g, v}, VertexLabels]},
{v -> Placed[Min[vo], Center], Min[vo] -> Placed[v, Center]}]]
SetProperty[h, VertexLabels -> swapLabel[h, 2]]
7
It seems to me that what the vector contains is a probability vector of resetting a random walk onto the corresponding vertex?
Yes, an un-normalized probability vector.
Introduction to PageRank
The PageRank score is based on the idea of a web surfer randomly clicking through links, i.e. a random walk on the directed graph of webpages and links.
After each ...
1
In versions 10.2+, you can use FindHamiltonianPath:
"HamiltonianPath[g] finds a Hamiltonian path in the graph g with the smallest total length."
hpath = FindHamiltonianPath[graph]
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
HighlightGraph[graph, PathGraph @ hpath, GraphHighlightStyle -> "Thick"]
3
In versions prior to 12.+, due to a bug in VertexDelete, (among other things) EdgeWeights are not properly updated:
PropertyValue[vdwag, EdgeWeight] == PropertyValue[wag, EdgeWeight]
True
$Version
"11.3.0 for Microsoft Windows (64-bit) (March 7, 2018)"
A work-around: use EdgeDelete + VertexDelete:
edwag = VertexDelete[EdgeDelete[wag, ...
2
Parts 1 & 2
ClearAll[waMs]
waMs[matrix_, indexlists_] := Module[{exclst = Flatten @ indexlists,
ll = Length @ indexlists, lengths = Length /@ indexlists, m2},
m2 = multiplierB[matrix, Length[exclst]][[exclst, exclst]](* Part 1 *);
Prepend[m2][ArrayFlatten[MapAt[0 &, TakeList[m2, lengths, lengths], #]] & /@
Tuples[Range @ ll, 2]](*...
2
dsn = ExampleData[{"NetworkGraph", "DolphinSocialNetwork"}];
1. The edges between each pair of communities:
ClearAll[cToCedges, edgesBetweenCommunities]
cToCedges = Module[{vToC = Association[
Join @@ MapIndexed[Thread[# -> #2[[1]]] &]@ FindGraphCommunities[#]]},
KeySort@GroupBy[EdgeList@#, Sort[vToC /@ VertexList[{#}]] &...
Top 50 recent answers are included
