5
$\begingroup$

For the following image:

enter image description here

The attached code produces a graph.

img = Import["https://i.sstatic.net/Yj6npagx.png"]
g = img // ColorNegate // Binarize // 
  MorphologicalGraph[#, VertexLabels -> "Name"] &

enter image description here

How do I obtain the list of outermost nodes as follows?

{1, 2, 7, 12, 14, 13, 4}
Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$ 
img = Import["https://i.sstatic.net/Yj6npagx.png"]
g = img // ColorNegate // Binarize // 
  MorphologicalGraph[#, VertexLabels -> "Name"] &

enter image description here

ge = GraphEmbedding[g];
lut = Thread[ge -> VertexList[g]];
pts = ConvexHullMesh[ge] // MeshCoordinates;
fst = FindShortestTour[pts];
outermost = Lookup[lut, pts[[Most@Last@fst]]];

{1, 2, 7, 12, 14, 13, 4}

HighlightGraph[g, outermost, VertexSize -> Large
 ]

enter image description here

Improve this answer
$\endgroup$
5
$\begingroup$ 
Clear["Global`*"];
im = Import["https://i.sstatic.net/Yj6npagx.png"];
g0 = MorphologicalGraph[Binarize@ColorNegate@im, 
   VertexLabels -> Automatic];
coords = GraphEmbedding[g0];
m = AdjacencyMatrix[g0];
g = AdjacencyGraph[coords, m, VertexCoordinates -> coords];
reg = ConvexHullMesh[coords];
pts = MeshPrimitives[RegionBoundary@ConvexHullMesh[coords], 1][[;; , 
     1]][[;; , 1]];
indexs = VertexList[g0][[Flatten[Position[coords, #] & /@ pts]]];
{HighlightGraph[g, pts, VertexSize -> .2, VertexLabels -> Automatic], 
 HighlightGraph[g0, indexs, VertexSize -> .2, 
  VertexLabels -> Automatic]}
indexs

{1, 2, 7, 12, 14, 13, 4}.

enter image description here

Improve this answer
$\endgroup$
5
$\begingroup$

Since you did not really specify what you mean by the "outermost graph nodes", and the approaches by @Syed and @cvgmt only work for convex graphs, here is an approach that works also for non-convex graphs, and where the "outermost graph nodes" are defined as the nodes of the "outer face". The key function used is PlanarFaceList.

pts = AssociationThread[VertexList[g] -> GraphEmbedding[g]];
outer = Select[PlanarFaceList[g], 
  And @@ (RegionMember[Polygon[Values@KeyTake[pts, #]]] /@ Values@pts) &]
(* {{1, 4, 13, 14, 12, 7, 2}} *)

An example of a non-convex graphs:

g = Graph[{{1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 5}, {5, 6}, {6, 4}}]
HighlightGraph[g, outer]

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Before I post my answer, I also test the graph g = HypercubeGraph[3]; That is why I use ConvexHullMesh. $\endgroup$
    – cvgmt
    Commented Apr 29 at 10:48
  • $\begingroup$ @cvgmt, well, I somehow assumed that the input graph should be in a planar embedding ... But mainly I just wanted to emphasize that the initial problem posed by the OP is not really well-defined. $\endgroup$
    – Domen
    Commented Apr 29 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.