📄 planar_graphs.html
字号:
<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <!--This HTML is auto-generated from an M-file.To make changes, update the M-file and republish this document. --> <title>Planar graphs in MatlabBGL</title> <meta name="generator" content="MATLAB 7.5"> <meta name="date" content="2008-10-22"> <meta name="m-file" content="planar_graphs"> <link rel="stylesheet" type="text/css" href="../site.css"><style>body { background: white; color: black;}p.footer { text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;}pre.codeinput { margin-left: 20px; margin-top: 10px; margin-bottom: 10px; background-color: #bbbbbb; border: solid 1px; font-size: 10pt; width: 620px;}p{ margin: 10px;}hr{ color: #bbbbbb; height: 4;}.main{ border-left-style: solid; margin-left: 100px; width: 650px;}.upwhitesq{ position: relative; left: -5px; top: -8px; background: white; }.downwhitesq{ position: relative; left: 95px; bottom: 10px; background: white; }img{ text-align: center;}span.keyword {color: #0000FF}span.comment {color: #228B22}span.string {color: #A020F0}span.untermstring {color: #B20000}span.syscmd {color: #B28C00}pre.showbuttons { margin-left: 30px; border: solid black 2px; padding: 4px; background: #EBEFF3;}pre.codeoutput { margin-left: 20px; margin-top: 10px; margin-bottom: 10px; font-size: 10pt; width: 520px;}pre.error { color: red;}.intro { width: 650px;} </style></head> <body> <h1>Planar graphs in MatlabBGL</h1> <introduction> <div class="intro"> <p>In version 1.35.0, the Boost Graph Library added a large suite of planar graph algorithms.</p> </div> </introduction> <h2>Contents</h2> <div> <ul> <li><a href="#1">Planarity testing</a></li> <li><a href="#4">A (planar?) road network</a></li> <li><a href="#14">Planar embeddings</a></li> <li><a href="#18">Conclusion</a></li> </ul> </div> <div class="main"> <h2>Planarity testing<a name="1"></a></h2> <p>Two functions help test if a graph is planar. The algorithm is the Boyer-Myrvold planarity tester.</p><pre class="codeinput">K5 = clique_graph(5);test_planar_graph(K5)</pre><pre class="codeoutput">ans = 0</pre><p>Of course K_5 isn't a planar graph. To get more information about why it isn't planar, we use the boyer_myrvold_planarity_test function. When a graph isn't planar, this function will isolate a Kuratowski subgraph. </p><pre class="codeinput">[is_planar K] = boyer_myrvold_planarity_test(K5);is_planarfull(K)</pre><pre class="codeoutput">is_planar = 0ans = 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0</pre><p>A Kuratowski subgraph is a certificate that a graph isn't planar. A Kuratowski subgraph must contract to either K_5 or K_3,3 (a bipartite clique). In this case, the graph was K_5, and so K was the entire graph. </p> <hr> <div class="upwhitesq"> </div> <h2>A (planar?) road network<a name="4"></a></h2> <p>Let's have some fun! Let's look at a road network.</p><pre class="codeinput">load(<span class="string">'../graphs/minnesota.mat'</span>);gplot(A,xy,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_01.png"> <pre class="codeinput">test_planar_graph(A)</pre><pre class="codeoutput">ans = 0</pre><p>What? The road network isn't planar? Let's see what is going on here.</p><pre class="codeinput">[is_planar K] = boyer_myrvold_planarity_test(A);gplot(K,xy,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_02.png"> <p>It looks like there are a lot of tree-like portions. Those shouldn't be the problem, let's remove them.</p><pre class="codeinput">cn = core_numbers(K);K2 = K;K2(cn<2,cn<2) = 0;gplot(K2,xy,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_03.png"> <p>We'd better check the graph is still Kuratowski. There's a function called is_kuratowski_graph that does just this task.</p><pre class="codeinput">is_kuratowski_graph(K2)</pre><pre class="codeoutput">ans = 1</pre><p>Well, that looks more helpful, but I don't see the planarity problem. Now, let's try contracting edges. What the following code does is to look for vertices of degree 2 (pieces of a line) and remove the intermediate vertex. In Matlab it isn't very efficent code, but this graph only has a few edges (~1000) at this point, so it'll be fast enough. </p><pre class="codeinput">Kcur = K2;rand(<span class="string">'state'</span>,0); <span class="comment">% reset for deterministic results</span><span class="keyword">for</span> ntimes=1:20 <span class="comment">% compute the degree of all edges</span> d = sum(Kcur,2); <span class="comment">% pick an independent set of vertices with degree 2</span> s = d==2; s = s.*round(rand(size(s))); <span class="comment">% randomly pick entries</span> a = Kcur*s; <span class="comment">% follow one edge</span> s = s&~a; <span class="comment">% remove dependent edges</span> a = Kcur*double(s); fprintf(<span class="string">'check for is: %i\n'</span>, full(sum(a&s))==0); <span class="comment">% verify indep set.</span> <span class="comment">% contract the edges</span> <span class="keyword">for</span> k=find(s)' ns = find(Kcur(:,k)); Kcur(ns(1),ns(2)) = 1; Kcur(:,k) = 0; Kcur(k,:) = 0; <span class="keyword">end</span> Kcur = Kcur|Kcur';<span class="keyword">end</span><span class="comment">% plot the graph after contraction in red</span>gplot(K2,xy,<span class="string">'.-'</span>); hold <span class="string">on</span>; gplot(Kcur,xy,<span class="string">'r.-'</span>); hold <span class="string">off</span>;</pre><pre class="codeoutput">check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1check for is: 1</pre><img vspace="5" hspace="5" src="planar_graphs_04.png"> <p>Ahah, now we see the problem. (Try to untangle the red graph!)</p> <p>Now that we see the problem, I think it's clear what we should have done from the beginning...</p><pre class="codeinput">d = sum(K);max(d)</pre><pre class="codeoutput">ans = (1,1) 3</pre><p>The maximum degree is 3, so the subgraph must be isomorphic to K_3,3.</p><pre class="codeinput">d3= d==3;sum(d3);</pre><p>That is the problem with the graph, but why doesn't the display show it? Well, it does.</p><pre class="codeinput">gplot(K2,xy,<span class="string">'.-'</span>); hold <span class="string">on</span>; gplot(Kcur,xy,<span class="string">'r.-'</span>); hold <span class="string">off</span>;xlim([-95.2092 -94.5842]);ylim([ 43.5903 43.7778]);</pre><img vspace="5" hspace="5" src="planar_graphs_05.png"> <p>It looks like there is a vertex of degree 4 in the middle. Unfortunately, that is just 2 paths crossing. Zooming in further, there are actually two vertices there! That's the problem! </p> <p>And so, here is a problem for you:</p> <p>Problem, automatically identify the following pairs of vertices as problematic for the planar embedding [2546,2547] [1971,1975] [1663,1666] Find another pair that prevents a planar embedding of the graph. </p> <hr> <div class="upwhitesq"> </div> <h2>Planar embeddings<a name="14"></a></h2> <p>To investigate planar embeddings, let's start with the road network again.</p><pre class="codeinput">load(<span class="string">'../graphs/minnesota.mat'</span>);test_planar_graph(A(1:500,1:500))</pre><pre class="codeoutput">ans = 1</pre><p>Good, we found a planar region!</p><pre class="codeinput">A = A(1:500,1:500);xy = xy(1:500,:);gplot(A,xy,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_06.png"> <p>Let's compute it's planar embedding</p><pre class="codeinput">X = chrobak_payne_straight_line_drawing(A);gplot(A,X,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_07.png"> <p>Well, that isn't quite as helpful, but now you know how to compute a straight line drawing. The straight line drawing is computed from a maximal planar graph. A maximal planar graph cannot have any additional edges and still be planar. </p><pre class="codeinput">M = make_maximal_planar(A);gplot(M,X,<span class="string">'.-'</span>);</pre><img vspace="5" hspace="5" src="planar_graphs_08.png"> <hr> <div class="upwhitesq"> </div> <h2>Conclusion<a name="18"></a></h2> <p>That's it for our brief tour of planar graph algorithms in MatlabBGL. See the BGL documentation pages on planar graph algorithms for more information. </p> <p><a href="http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/planar_graphs.html"> Planar Graphs in the Boost Graph Library</a></p> <hr> <div class="upwhitesq"> </div> </div> <div class="downwhitesq"> </div> <!--##### SOURCE BEGIN #####%% Planar graphs in MatlabBGL% In version 1.35.0, the Boost Graph Library added a large suite of planar% graph algorithms.%% Planarity testing% Two functions help test if a graph is planar. The algorithm is the% Boyer-Myrvold planarity tester.K5 = clique_graph(5);test_planar_graph(K5)%% % Of course K_5 isn't a planar graph. To get more information about why it% isn't planar, we use the boyer_myrvold_planarity_test function. When a% graph isn't planar, this function will isolate a Kuratowski subgraph.[is_planar K] = boyer_myrvold_planarity_test(K5);is_planarfull(K)%%% A Kuratowski subgraph is a certificate that a graph isn't planar. A% Kuratowski subgraph must contract to either K_5 or K_3,3 (a bipartite% clique). In this case, the graph was K_5, and so K was the entire graph.%% A (planar?) road network% Let's have some fun! Let's look at a road network.load('../graphs/minnesota.mat');gplot(A,xy,'.-');%%test_planar_graph(A)%%% What? The road network isn't planar? Let's see what is going on here.[is_planar K] = boyer_myrvold_planarity_test(A);gplot(K,xy,'.-');%%% It looks like there are a lot of tree-like portions. Those shouldn't be% the problem, let's remove them.cn = core_numbers(K);K2 = K;K2(cn<2,cn<2) = 0;gplot(K2,xy,'.-');%%% We'd better check the graph is still Kuratowski. There's a function% called is_kuratowski_graph that does just this task.is_kuratowski_graph(K2)%%% Well, that looks more helpful, but I don't see the planarity problem.% Now, let's try contracting edges. What the following code does is to% look for vertices of degree 2 (pieces of a line) and remove the% intermediate vertex. In Matlab it isn't very efficent code, but this% graph only has a few edges (~1000) at this point, so it'll be fast% enough.Kcur = K2;rand('state',0); % reset for deterministic resultsfor ntimes=1:20 % compute the degree of all edges d = sum(Kcur,2); % pick an independent set of vertices with degree 2 s = d==2; s = s.*round(rand(size(s))); % randomly pick entries a = Kcur*s; % follow one edge s = s&~a; % remove dependent edges a = Kcur*double(s); fprintf('check for is: %i\n', full(sum(a&s))==0); % verify indep set. % contract the edges for k=find(s)' ns = find(Kcur(:,k)); Kcur(ns(1),ns(2)) = 1; Kcur(:,k) = 0; Kcur(k,:) = 0; end Kcur = Kcur|Kcur';end% plot the graph after contraction in redgplot(K2,xy,'.-'); hold on; gplot(Kcur,xy,'r.-'); hold off;%%% Ahah, now we see the problem. (Try to untangle the red graph!)%% Now that we see the problem, I think it's clear what we should have done% from the beginning... d = sum(K);max(d)%%% The maximum degree is 3, so the subgraph must be isomorphic to K_3,3.d3= d==3;sum(d3);%%% That is the problem with the graph, but why doesn't the display show it?% Well, it does. gplot(K2,xy,'.-'); hold on; gplot(Kcur,xy,'r.-'); hold off;xlim([-95.2092 -94.5842]);ylim([ 43.5903 43.7778]);%%% It looks like there is a vertex of degree 4 in the middle.% Unfortunately, that is just 2 paths crossing. Zooming in further, there% are actually two vertices there! That's the problem!%% And so, here is a problem for you:%% Problem, automatically identify the following pairs of vertices as% problematic for the planar embedding% [2546,2547]% [1971,1975]% [1663,1666]% Find another pair that prevents a planar embedding of the graph.%% Planar embeddings% To investigate planar embeddings, let's start with the road network again.load('../graphs/minnesota.mat');test_planar_graph(A(1:500,1:500))%%% Good, we found a planar region!A = A(1:500,1:500);xy = xy(1:500,:);gplot(A,xy,'.-');%%% Let's compute it's planar embeddingX = chrobak_payne_straight_line_drawing(A);gplot(A,X,'.-');%%% Well, that isn't quite as helpful, but now you know how to compute a% straight line drawing. The straight line drawing is computed from a% maximal planar graph. A maximal planar graph cannot have any additional% edges and still be planar.M = make_maximal_planar(A);gplot(M,X,'.-');%% Conclusion% That's it for our brief tour of planar graph algorithms in MatlabBGL.% See the BGL documentation pages on planar graph algorithms for more% information.%% <http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/planar_graphs.html% Planar Graphs in the Boost Graph Library>##### SOURCE END #####--> </body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -