12 views (last 30 days)

I have a graph like this, how I can find border edges.

M = [1 8; 7 8; 1 7; 7 6; 1 6; 1 5; 4 5; 1 3; 2 3; 1 2; 1 4];

Layout = [3 2; 5 2; 5 4; 6 1; 6 6; 4 6; 2 4; 1 1];

g = graph(M(:, 1), M(:, 2));

h = plot(g);

h.XData=Layout(:,1);

h.YData=Layout(:,2);

The border edges in this graph is (1,8), (8,7), (7,6), (6,1), (1,5), (5,4), (4,1)

result should be:

border_edges = [1,8; 8,7; 7,6; 6,1; 1,5; 5,4; 4,1]

The other question is that, how I can find nodes with 2 edges?

node_with_two_edges =[8; 6; 5; 4; 2; 3]

Christine Tobler
on 12 May 2020

The graph class doesn't have any functions based on coordinates of the points - it just knows about their connections. Use convex hull to find the nodes that lie on the border:

>> K = convhull(Layout(:, 1), Layout(:, 2));

>> plot(Layout(:, 1), Layout(:, 2), 'x'); hold on; plot(Layout(K, 1), Layout(K, 2), 'o-')

For finding all nodes with 2 edges, use degree(g) == 2.

Christine Tobler
on 13 May 2020

Vertex 1 is located in the center of the points, I had assumed you wanted the border to contain the vertices on the outside of the region defined by the set of vertices.

Do you want the border to be defined such that all vertices except 2 and 3 are part of it?

Christine Tobler
on 14 May 2020

Okay, so the problem that I'm not sure how to define this in general. We could say that each simple cycle in the graph represents a polygon, and a vertex is not on the border only if it's inside one or more of these polygons. Here a simple cycle is a list of nodes where each consecutive pair is connected by an edge, with no repeating nodes and where the last node connects back to the first.

But it's possible to have a cycle which does not form a simple polygon, because the lines intersect. Here's an example of that:

Is there something about the data you're looking at that makes sure this couldn't happen? Or if not, how would you want to treat this case?

You might have a look at the polyshape class, which feels like it could be more relevant to the kind of data you're working with.

Opportunities for recent engineering grads.

Apply TodayFind the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 0 Comments

Sign in to comment.