圖論：有向無環(huán)圖的定義及應(yīng)用

1、圖論（1）:有向無環(huán)圖的定義及應(yīng)用=1匕豆.冃景刖一陣項(xiàng)目中引用了MaterialDesign依賴庫中的控件BottomSheetDialog，主要是用來上下滑動操作界面的show（）&hide（）事件（解決界面需要跟手操作問題），過程中碰到了一些問題，于是花時(shí)間研究了一下其具體實(shí)現(xiàn)。其核心源碼是CoordinatorLayout，內(nèi)部還包括了另一個(gè)重要內(nèi)部類Behavior，本篇文章內(nèi)容如標(biāo)題所示暫不去分析其整體的運(yùn)行機(jī)制，而是打算抽出其中一個(gè)點(diǎn)一一CoordinatorLayout中View之間的依賴關(guān)系是如何確定的，這一個(gè)點(diǎn)來分析。這里先給出結(jié)論：View之間的依賴關(guān)系恰好是有向圖（ch

2、ild指向dependency的一條有向無權(quán)邊）的一個(gè)具體應(yīng)用（具體還要檢測是否有環(huán)），CoordinatorLayout采用鄰接表（SimpleArrayMapT,ArrayList）的數(shù)據(jù)結(jié)構(gòu)構(gòu)建有向圖的依賴關(guān)系，并將圖的拓?fù)渑判蚪Y(jié)果作為View的處理（measurelayout等）順序。因此這里也剛好有助于我們復(fù)習(xí)一下大學(xué)學(xué)過的核心課程數(shù)據(jù)結(jié)構(gòu)中關(guān)于圖的相關(guān)內(nèi)容。圖相關(guān)概念圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V,E）,其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合中邊的集合。圖按照邊的有無方向性分為無向圖和有向圖。圖中某個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的直連邊條數(shù)稱為

3、該節(jié)點(diǎn)的度。有向圖中，指向其他節(jié)點(diǎn)的邊成為出度，被其他節(jié)點(diǎn)指向的邊稱為入度。如果在有向圖中，無法從某個(gè)頂點(diǎn)出發(fā)經(jīng)過若干條邊回到該點(diǎn)，則這個(gè)圖是一個(gè)有向無環(huán)圖（DAG圖）。拓?fù)渑判蚴菍D中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對頂點(diǎn)u和v，若邊（u,v）E（G），貝Uu在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡颍═opologicalOrder）的序列，簡稱拓?fù)湫蛄?。簡單的說，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判?。Behavior功能簡介我們來看看CoordinatorLayout和Behavior這一套機(jī)制主要是為了實(shí)現(xiàn)什么功能。個(gè)人理解是

4、谷歌弄的這個(gè)機(jī)制為了簡化開發(fā)者在通過自定義View實(shí)現(xiàn)比以往更復(fù)雜的交互時(shí)的工作量（抽象）和工作難度（僅需實(shí)現(xiàn)自己關(guān)注的功能）。比如：如果自定義一個(gè)能解決父-子View之間的事件沖突的View結(jié)構(gòu)時(shí)，必須要重與父View和子View的onlnterceptTouchEvent（）和onTouchEvent（）接口以及其他必要接口，然后分別處理事件攔截，且這個(gè)自定義View很難重用起來（必須兩個(gè)View配合行動）。但是behavior出現(xiàn)后，觸摸事件、滑動沖突、依賴關(guān)系等工作都被CoordinatorLayout進(jìn)行抽象完成了，僅拋出一個(gè)Behavior的接口讓開發(fā)者自定義感興趣的部分即可。Be

5、havior機(jī)制通常用來實(shí)現(xiàn)如下三種功能:事件的攔截：需重與方法onInterceptTouchEvent()+onTouchEvent()。+onDependentViewRemoved()。View變化的攔截(本章的重點(diǎn))：需重與layoutDependsOn()+onDependentViewChanged()嵌套滑動的攔截：需重與方法onStartNestedScroll()+onNestedScrollAccepted()+onStopNestedScroll()+onNestedScroll()+onNestedPreScroll()+onNestedFling()+onNeste

6、dPreFling()。為什么要實(shí)現(xiàn)View之間的依賴關(guān)系及需要重寫哪些方法如果要實(shí)現(xiàn)這樣一個(gè)效果：滑動A-View時(shí)，讓另一個(gè)B-View也能跟著滑動。按照傳統(tǒng)的做法，首先我們需要重新自定義一個(gè)父View來處理滑動事件來，然后在滑動A-View時(shí)，根據(jù)A-View的位置來設(shè)置B-View的translation值實(shí)現(xiàn)（實(shí)現(xiàn)較繁瑣），如果滑動的View是一個(gè)列表呢，比如RecyclerView，這里的操作又該如何進(jìn)行。但是有了Behavior之后，僅需要非常簡單的實(shí)現(xiàn)的兩個(gè)接口就能達(dá)到這個(gè)效果了，如下所示：/*paramparent:父容器paramchild:Behavior作用的Viewp

7、aramdependency:是child的依賴對象，同時(shí)也是Behavior對child進(jìn)行操作的根據(jù)returnchild是否依賴dependency*/OverridepublicbooleanlayoutDependsOn(CoordinatorLayoutparent,Viewchild,Viewdependency)if(dependency!=null&dependency.getId()=R.id.view_header)/找到依賴變化的A-Viewreturntrue;returnfalse;OverridepublicbooleanonDependentViewChange

8、d(CoordinatorLayoutparent,Viewchild,Viewdependency)child.setTranslationY(dependency.getTranslationY();B-View的位置跟著A-View的位置變化returntrue;具體的原理就是CoordinatorLayout在滑動之初(onMeasure()函數(shù)中)就通過layoutDependsOn()回調(diào)確定了View兩兩之間的依賴關(guān)系(通過雙重for循環(huán)遍歷，因此|ayoutDependsOn中最好不要寫復(fù)雜邏輯，僅需簡單確定是否是依賴View)，所以當(dāng)依賴View發(fā)生變化時(shí)，自然就能再回調(diào)回來

9、告訴被依賴View發(fā)生了變化。依賴關(guān)系的具體實(shí)現(xiàn)經(jīng)查看CoordinatorLayout的源碼，可以看到在onMeasure()開始就調(diào)用了函數(shù)prepareChildren()(有向圖的拓?fù)渑判?來確疋View的依賴關(guān)系:依賴關(guān)系的排序結(jié)果列表(有向圖的拓?fù)渑判?privatefinalListmDependencySortedChildren=newArrayList();/mChildDag是構(gòu)建有向無環(huán)圖的數(shù)據(jù)結(jié)構(gòu)(DAG)privatefinalDirectedAcyclicGraphmChildDag=newDirectedAcyclicGraph();Overrideprotec

10、tedvoidonMeasure(intwidthMeasureSpec,intheightMeasureSpec)prepareChildren();/通過回調(diào)函數(shù)layoutDependsOn()確定view兩兩之間的依賴關(guān)系ensurePreDrawListener();/注冊重繪監(jiān)聽，在dependency發(fā)生變化時(shí)由onDependentViewChanged()回調(diào)出來privatevoidprepareChildren()mDependencySortedChildren.clear();mChildDag.clear();這里的雙重循環(huán)進(jìn)行了兩兩比較for(inti=0,cou

11、nt=getChildCount();icount;i+)finalViewview=getChildAt(i);省略mChildDag.addNode(view);/將節(jié)點(diǎn)加入有向圖中，view相當(dāng)與圖的節(jié)點(diǎn)/Nowiterateagainovertheotherchildren,addinganydependenciestothegraphfor(intj=0;jcount;j+)if(j=i)不可能出現(xiàn)自環(huán)(self-loop)，直接過濾continue;finalViewother=getChildAt(j);finalCoordinatorLayout.LayoutParamsoth

12、erLp=getResolvedLayoutParams(other);if(otherLp.dependsOn(this,other,view)/這里就是調(diào)用Behavior的layoutDependsOn()-重點(diǎn)if(!mChildDag.contains(other)/MakesurethattheothernodeisaddedmChildDag.addNode(other);/NowaddthedependencytothegraphmChildDag.addEdge(view,other);將一條有向邊加入有向圖中：source:view,target:other/Finally

13、addthesortedgraphlisttoourlist/保存有向圖的拓?fù)渑判蚪Y(jié)果(依賴節(jié)點(diǎn)排在列表的最后)mDependencySortedChildren.addAll(mChildDag.getSortedList();/Wealsoneedtoreversetheresultsincewewantthestartofthelisttocontain/Viewswhichhavenodependencies,thendependentviewsafterthatCollections.reverse(mDependencySortedChildren);反轉(zhuǎn)結(jié)果的目的主要是為了效率優(yōu)

14、化，因?yàn)殛P(guān)注的焦點(diǎn)是依賴節(jié)點(diǎn)，如果它能排在靠前的位置，便能更及時(shí)的處理他的操作。這里的mDependencySortedChildren存放的就是有向圖的拓?fù)渑判蚪Y(jié)果（依賴的節(jié)點(diǎn)排在列表前面，被依賴的節(jié)點(diǎn)排在列表后面）；mChildDag是整個(gè)有向圖數(shù)據(jù)結(jié)構(gòu)，觸發(fā)onDependentViewChanged（）回調(diào)時(shí)就是通過mChildDag非常簡單找到被依賴View列表的（時(shí)間復(fù)雜度為O）。這么做是為了在dependency發(fā)生變化時(shí)，只需通知它的被依賴view即可，而其他與之無關(guān)的view則不應(yīng)該回調(diào)（因?yàn)闆]有依賴關(guān)系），后面還列出了類中定義的獲取依賴view列表和被依賴view列表的接口

15、也是如此，它的實(shí)現(xiàn)如下實(shí)現(xiàn)如下：publicvoiddispatchDependentViewsChanged(Viewview)finalListdependents=mChildDag.getlncomingEdges(view);/view的入度邊就是被依賴對象if(dependents!=null&!dependents.isEmpty()/依次回調(diào)給相應(yīng)childfor(inti=0;idependents.size();i+)finalViewchild=dependents.get(i);省略if(b!=null)b.onDependentViewChanged(this,chi

16、ld,view);即我們實(shí)現(xiàn)Behavior的對應(yīng)回調(diào)獲取child的依賴列表publicListgetDependencies(NonNullViewchild)finalListdependencies=mChildDag.getOutgoingEdges(child);/獲取出度邊View省略returndependencies;獲取child的被依賴列表publicListgetDependents(NonNullViewchild)finalListedges=mChildDag.getIncomingEdges(child);/獲取入度邊View省略returnedges;到這里，

17、有向圖的一個(gè)實(shí)際應(yīng)用場景就介紹完了。接下來我們來看看源碼中有向無環(huán)圖DirectedAcyclicGraph)的具體實(shí)現(xiàn)，總體來講就是圍繞下面這一個(gè)鄰接表的操作：privatefinalSimpleArrayMapT,ArrayListmGraph=newSimpleArrayMap();SimpieArrayMap是個(gè)android自己實(shí)現(xiàn)的一個(gè)Map，它的key(T)為圖中的每一個(gè)節(jié)點(diǎn)對象，value(ArrayList)是指向key節(jié)點(diǎn)的節(jié)點(diǎn)，卩key節(jié)點(diǎn)的入度邊。它的方法addNode()、addEdge()就是將這些關(guān)系存入到這個(gè)鄰接表中，然后再通過它獲取其入度和出度(出度需要遍歷整

18、個(gè)鄰接表才能獲取)；函數(shù)getSortedList()調(diào)用深度優(yōu)先的遞歸函數(shù)dfs()實(shí)現(xiàn)其拓?fù)渑判?。下面來看一個(gè)測試?yán)觼眚?yàn)證運(yùn)行結(jié)果，有如下示例有向無環(huán)圖：有向無環(huán)圖測試實(shí)例圖中標(biāo)有A、B、C、D、E、F、G、H、T、J、K這11個(gè)節(jié)點(diǎn)。由于SimpleArrayMap中key的最終順序會自動按升序排列（非插入的順序），為了結(jié)果比較明顯特意將圖中的節(jié)點(diǎn)打亂。測試用例:DirectedAcyclicGraphDAG=newDirectedAcyclicGraph();/定義有向無環(huán)圖/將節(jié)點(diǎn)加入有向圖中DAG.addNode(A);DAG.addNode(T);DAG.addNode(C);

19、DAG.addNode(B);DAG.addNode(G);DAG.addNode(D);DAG.addNode(H);DAG.addNode(E);DAG.addNode(F);DAG.addNode(J);DAG.addNode(K);根據(jù)示例圖加入有向邊(終點(diǎn)-起點(diǎn))DAG.addEdge(A,B);DAG.addEdge(B,G);DAG.addEdge(C,B);DAG.addEdge(C,H);DAG.addEdge(D,A);DAG.addEdge(D,C);DAG.addEdge(E,D);DAG.addEdge(E,J);DAG.addEdge(E,K);DAG.addEdg

20、e(E,F);DAG.addEdge(F,C);DAG.addEdge(F,I);DAG.addEdge(H,G);DAG.addEdge(I,H);DAG.addEdge(J,D);DAG.addEdge(K,F);/DAG.addEdge(C,G);/這里增加一條環(huán)測試1：輸出有向圖的大?。ü?jié)點(diǎn)個(gè)數(shù)）finalintsize=DAG.size();Log.d(TAG,DAGsize:+size);結(jié)果：DAGsize:11測試2:輸出節(jié)點(diǎn)E的入度邊結(jié)果：nodeE,incomming:D,J,K,F測試3:輸出節(jié)點(diǎn)C的出度邊ListoutgoingEdges=DAG.getOutgoing

21、Edges(C);Log.d(TAG,nodeC,outgoings:+formatList(outgoingEdges);nodeC,outgoings:D,F測試4:輸出圖的拓?fù)渑判蚪Y(jié)果（拓?fù)渑判虻慕Y(jié)果不是唯一的，滿足定義即可）結(jié)果：sortList:G,B,A,H,C,D,J,I,F,K,E滿足“圖中任意一對頂點(diǎn)U和V，若邊（U,V）WE（G）,則U在線性序列中出現(xiàn)在V之前”格式化節(jié)點(diǎn)函數(shù):privateStringformatList(Listlist)StringBuilderbuilder=newStringBuilder();for(Stringvalue:list)builde

22、r.append(value);builder.append(,);returnbuilder.toString();總結(jié)雖然此處圖的數(shù)據(jù)結(jié)構(gòu)使用了泛型，卻并不通用（僅可以用來表示有向、無權(quán)圖，且其他運(yùn)算操作缺失）。由于JDK的集合類中并沒有提供表示圖數(shù)據(jù)結(jié)構(gòu)的相關(guān)類，以至于圖在開發(fā)人員間其實(shí)并不普及，開發(fā)過程中很少借助圖去實(shí)現(xiàn)某些特定功能。于是，圖就像神話般一樣，僅僅出現(xiàn)在相關(guān)面試寶典里，以及偶爾回憶其概念的程序員心中。在網(wǎng)上找了下實(shí)現(xiàn)圖通用的數(shù)據(jù)結(jié)構(gòu)的開源庫，也很少看到評星很高的，最好找到下載了很久沒有瀏覽過的谷歌開源庵uava,最近23版本增加了圖數(shù)據(jù)結(jié)構(gòu)，而且實(shí)現(xiàn)android版本了，于是想接下來借助它來梳理圖的相關(guān)知識。通過gradle導(dǎo)入guava方式：compilecom.google.guava:guava:23.5-android使用guava的common.graph圖庫實(shí)現(xiàn)上述有向無環(huán)圖：MutableGraphDAG=GraphBuilder.directed().build();/構(gòu)建有向圖省略添加節(jié)點(diǎn)，添加邊/DAG.addNode(node);DAG.putEdge(nodeU,nodeV);獲取節(jié)點(diǎn)數(shù)finalintsize=DAG.nodes()