www.pudn.com > matlab_bgl.zip > planar_graphs.html, change:2008-10-22,size:14381b

<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_planar full(K) </pre><pre class="codeoutput"> is_planar = 0 ans = 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: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check for is: 1 check 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_planar full(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 results for 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 red gplot(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 embedding X = 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>