Find border edges of the graph

Question

NA 2020-5-12

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/524963-find-border-edges-of-the-graph

评论： Christine Tobler 2020-5-14

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]

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Christine Tobler 2020-5-12

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/524963-find-border-edges-of-the-graph#answer_432085

在 MATLAB Online 中打开

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.

4 个评论
显示 2更早的评论隐藏 2更早的评论

NA 2020-5-13

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

yes. I want this border (1,8), (8,7), (7,6), (6,1), (1,5), (5,4), (4,1)

Christine Tobler 2020-5-14

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.

请先登录，再进行评论。