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 graph in shape.
Some useful links to GraphPlot, circular graph and EdgeRenderingFunction for edge thickness from Mathematica.StackExchange and StackOverflow:
- Ordering vertices in
GraphPlot - Removing edge weights from a graph
- Label edges with their weights
- Graph layout that reflects edge weights
Mathematica code:
(*vertex shape function with labels*)
options =
Sequence[Method -> "CircularEmbedding", VertexLabeling -> True,
EdgeLabeling -> False,
EdgeRenderingFunction -> ({Text[Style[#3, 15], Mean[#1]],
Blue, AbsoluteThickness[0.8 + #3/5],
Arrowheads[0.02 + #3/170],
Arrow[#1, 0.075]} &), ImageSize -> 200];
Default Mathematica circular graph arranges vertices differently.
(*default mathematica circular graph*)
connections = {{1 -> 5, 1}, {4 -> 3, 3.6}, {6 -> 8, 1}, {2 -> 4,
2}, {2 -> 5, 2.5}, {5 -> 4, 0.9}, {7 -> 8, 2}, {3 -> 8,
1}, {8 -> 2, 1}};
gp1 = GraphPlot[connections, options];
So, we need to sort circular graph vertices to start calculating minumum cut (intersecting edges).
(*sorted mathematica circular graph*)
Needs["Combinatorica`"];
sortedVertices =
Sort[Union[
Flatten[{connections[[All, 1, 1]], connections[[All, 1, 2]]}]]];
sortedConnections = Table[
sortedVertices[[i]] ->
Partition[Flatten[CircularEmbedding[Length[sortedVertices]]], 2][[i]],
{i, Length[sortedVertices]}];
gp2 = GraphPlot[connections, options,
VertexCoordinateRules -> sortedConnections];
(*show two graphs*)
Row[{gp1, gp2}]
The question is how the above code can be rearranged in such a way that GraphPlot has minimum cuts (intersection of edges) while keeping the circular graph in shape. The vertex points order may be changed but not the number of connections or directions.
