背景

前一陣項目中引用了Material Design依賴庫中的一個控件BottomSheetDialog巫糙，主要是用來上下滑動操作界面的show()&hide()事件（解決界面需要跟手操作問題）足画，過程中碰到了一些問題垮兑，于是花時間研究了一下其具體實現(xiàn)。其核心源碼是CoordinatorLayout些侍，內(nèi)部還包括了另一個重要內(nèi)部類Behavior执泰，本篇文章內(nèi)容如標題所示暫不去分析其整體的運行機制，而是打算抽出其中一個點——CoordinatorLayout中View之間的依賴關系是如何確定的造挽，這一個點來分析。

這里先給出結論：View之間的依賴關系恰好是有向圖（child指向dependency的一條有向無權邊）的一個具體應用（具體還要檢測是否有環(huán)）惊窖，CoordinatorLayout采用鄰接表（SimpleArrayMap<T, ArrayList<T>>）的數(shù)據(jù)結構構建有向圖的依賴關系刽宪，并將圖的拓撲排序結果作為View的處理（measure、layout等）順序界酒。因此這里也剛好有助于我們復習一下大學學過的核心課程《數(shù)據(jù)結構》中關于圖的相關內(nèi)容圣拄。

圖相關概念

圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V, E)毁欣，其中庇谆，G表示一個圖，V是圖G中頂點的集合凭疮，E是圖G中邊的集合饭耳。

圖按照邊的有無方向性分為無向圖和有向圖。

圖中某個節(jié)點與其他節(jié)點的直連邊條數(shù)稱為該節(jié)點的度执解。有向圖中寞肖，指向其他節(jié)點的邊成為出度，被其他節(jié)點指向的邊稱為入度衰腌。

如果在有向圖中新蟆，無法從某個頂點出發(fā)經(jīng)過若干條邊回到該點，則這個圖是一個有向無環(huán)圖（DAG圖）右蕊。

拓撲排序是將圖中所有頂點排成一個線性序列琼稻，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)饶囚，則u在線性序列中出現(xiàn)在v之前帕翻。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列萝风，簡稱拓撲序列嘀掸。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序规惰，這個操作稱之為拓撲排序睬塌。

Behavior功能簡介

我們來看看CoordinatorLayout和Behavior這一套機制主要是為了實現(xiàn)什么功能。個人理解是谷歌弄的這個機制為了簡化開發(fā)者在通過自定義View實現(xiàn)比以往更復雜的交互時的工作量（抽象）和工作難度（僅需實現(xiàn)自己關注的功能）。比如：如果自定義一個能解決父-子View之間的事件沖突的View結構時衫仑，必須要重寫父View和子View的onInterceptTouchEvent()和onTouchEvent()接口以及其他必要接口，然后分別處理事件攔截堕花，且這個自定義View很難重用起來（必須兩個View配合行動）文狱。但是當Behavior出現(xiàn)后，觸摸事件缘挽、滑動沖突瞄崇、依賴關系等工作都被CoordinatorLayout進行抽象完成了，僅拋出一個Behavior的接口讓開發(fā)者自定義感興趣的部分即可壕曼。Behavior機制通常用來實現(xiàn)如下三種功能：

• 事件的攔截：需重寫方法onInterceptTouchEvent() + onTouchEvent()苏研。
• View變化的攔截(本章的重點)：需重寫layoutDependsOn() + onDependentViewChanged() + onDependentViewRemoved()。
• 嵌套滑動的攔截：需重寫方法onStartNestedScroll() + onNestedScrollAccepted() + onStopNestedScroll() + onNestedScroll() + onNestedPreScroll() + onNestedFling() + onNestedPreFling()腮郊。

為什么要實現(xiàn)View之間的依賴關系及需要重寫哪些方法

如果要實現(xiàn)這樣一個效果：滑動A-View時摹蘑，讓另一個B-View也能跟著滑動。按照傳統(tǒng)的做法轧飞，首先我們需要重新自定義一個父View來處理滑動事件來衅鹿，然后在滑動A-View時，根據(jù)A-View的位置來設置B-View的translation值實現(xiàn)（實現(xiàn)較繁瑣）过咬，如果滑動的View是一個列表呢大渤，比如RecyclerView，這里的操作又該如何進行掸绞。但是有了Behavior之后泵三，僅需要非常簡單的實現(xiàn)的兩個接口就能達到這個效果了，如下所示：

/**
 *
 * @param parent： 父容器
 * @param child: Behavior作用的View
 * @param dependency： 是child的依賴對象衔掸，同時也是Behavior對child進行操作的根據(jù)
 * @return child是否依賴dependency
 */
@Override
public boolean layoutDependsOn(CoordinatorLayout parent, View child, View dependency) {
    if (dependency != null && dependency.getId() == R.id.view_header) { //找到依賴變化的A-View
        return true;
    }
    return false;
}

@Override
public boolean onDependentViewChanged(CoordinatorLayout parent, View child, View dependency) {
    child.setTranslationY(dependency.getTranslationY()); //B-View的位置跟著A-View的位置變化
    return true;
}

具體的原理就是CoordinatorLayout在滑動之初(onMeasure()函數(shù)中)就通過layoutDependsOn()回調(diào)確定了View兩兩之間的依賴關系（通過雙重for循環(huán)遍歷烫幕，因此layoutDependsOn中最好不要寫復雜邏輯，僅需簡單確定是否是依賴View）具篇，所以當依賴View發(fā)生變化時纬霞，自然就能再回調(diào)回來告訴被依賴View發(fā)生了變化。

依賴關系的具體實現(xiàn)

經(jīng)查看CoordinatorLayout的源碼驱显，可以看到在onMeasure()一開始就調(diào)用了函數(shù)prepareChildren()(有向圖的拓撲排序)來確定View的依賴關系：

//依賴關系的排序結果列表（有向圖的拓撲排序）
private final List<View> mDependencySortedChildren = new ArrayList<>();

//mChildDag是構建有向無環(huán)圖的數(shù)據(jù)結構（DAG）
private final DirectedAcyclicGraph<View> mChildDag = new DirectedAcyclicGraph<>();

@Override
protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    prepareChildren(); //通過回調(diào)函數(shù)layoutDependsOn()確定view兩兩之間的依賴關系
    ensurePreDrawListener(); //注冊重繪監(jiān)聽诗芜，在dependency發(fā)生變化時由onDependentViewChanged()回調(diào)出來
}


private void prepareChildren() {
    mDependencySortedChildren.clear();
    mChildDag.clear();

    //這里的雙重循環(huán)進行了兩兩比較
    for (int i = 0, count = getChildCount(); i < count; i++) {
        final View view = getChildAt(i);
        //...省略
        mChildDag.addNode(view); //將節(jié)點加入有向圖中，view相當與圖的節(jié)點

        // Now iterate again over the other children, adding any dependencies to the graph
        for (int j = 0; j < count; j++) {
            if (j == i) {  //不可能出現(xiàn)自環(huán)（self-loop）埃疫，直接過濾
                continue;
            }
            final View other = getChildAt(j);
            final CoordinatorLayout.LayoutParams otherLp = getResolvedLayoutParams(other);
            if (otherLp.dependsOn(this, other, view)) { //這里就是調(diào)用Behavior的layoutDependsOn()--重點
                if (!mChildDag.contains(other)) {
                    // Make sure that the other node is added
                    mChildDag.addNode(other);
                }
                // Now add the dependency to the graph
                mChildDag.addEdge(view, other); //將一條有向邊加入有向圖中：source:view, target:other
            }
        }
    }

    // Finally add the sorted graph list to our list
    //保存有向圖的拓撲排序結果（依賴節(jié)點排在列表的最后）
    mDependencySortedChildren.addAll(mChildDag.getSortedList()); 

    // We also need to reverse the result since we want the start of the list to contain
    // Views which have no dependencies, then dependent views after that
    Collections.reverse(mDependencySortedChildren); 
    //反轉(zhuǎn)結果的目的主要是為了效率優(yōu)化伏恐，因為關注的焦點是依賴節(jié)點，如果它能排在靠前的位置栓霜，
    //便能更及時的處理他的操作翠桦。
}

這里的mDependencySortedChildren存放的就是有向圖的拓撲排序結果（依賴的節(jié)點排在列表前面，被依賴的節(jié)點排在列表后面）；mChildDag是整個有向圖數(shù)據(jù)結構销凑，觸發(fā)onDependentViewChanged()回調(diào)時就是通過mChildDag非常簡單找到被依賴View列表的（時間復雜度為O(1)）丛晌。這么做是為了在dependency發(fā)生變化時，只需通知它的被依賴view即可斗幼，而其他與之無關的view則不應該回調(diào)（因為沒有依賴關系）澎蛛，后面還列出了類中定義的獲取依賴view列表和被依賴view列表的接口也是如此，它的實現(xiàn)如下實現(xiàn)如下：

public void dispatchDependentViewsChanged(View view) {
    final List<View> dependents = mChildDag.getIncomingEdges(view); //view的入度邊就是被依賴對象!!!
    if (dependents != null && !dependents.isEmpty()) { //依次回調(diào)給相應child
        for (int i = 0; i < dependents.size(); i++) {
            final View child = dependents.get(i);
            //...省略
            if (b != null) {
                b.onDependentViewChanged(this, child, view);  //即我們實現(xiàn)Behavior的對應回調(diào)
            }
        }
    }
}

//獲取child的依賴列表
public List<View> getDependencies(@NonNull View child) {
    final List<View> dependencies = mChildDag.getOutgoingEdges(child); //獲取出度邊View
    //...省略
    return dependencies;
}

//獲取child的被依賴列表
public List<View> getDependents(@NonNull View child) {
    final List<View> edges = mChildDag.getIncomingEdges(child); //獲取入度邊View
    //...省略
    return edges;
}

到這里蜕窿，有向圖的一個實際應用場景就介紹完了谋逻。接下來我們來看看源碼中有向無環(huán)圖（DirectedAcyclicGraph<T>）的具體實現(xiàn)，總體來講就是圍繞下面這一個鄰接表的操作：

private final SimpleArrayMap<T, ArrayList<T>> mGraph = new SimpleArrayMap<>();

SimpleArrayMap是一個android自己實現(xiàn)的一個Map桐经，它的key(T)為圖中的每一個節(jié)點對象毁兆，value(ArrayList<T>)是指向key節(jié)點的節(jié)點，即key節(jié)點的入度邊阴挣。它的方法addNode()气堕、addEdge()就是將這些關系存入到這個鄰接表中，然后再通過它獲取其入度和出度（出度需要遍歷整個鄰接表才能獲扰线帧）送巡；函數(shù)getSortedList()調(diào)用深度優(yōu)先的遞歸函數(shù)dfs()實現(xiàn)其拓撲排序。

下面來看一個測試例子來驗證運行結果盒卸，有如下示例有向無環(huán)圖：

有向無環(huán)圖測試實例

測試用例：

    DirectedAcyclicGraph<String> DAG = new DirectedAcyclicGraph<>(); //定義有向無環(huán)圖

    //將節(jié)點加入有向圖中
    DAG.addNode("A");
    DAG.addNode("I");
    DAG.addNode("C");
    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ù)示例圖加入有向邊（終點-起點）
    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.addEdge("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é)點個數(shù)）

final int size = DAG.size();
Log.d(TAG, "DAG size: " + size);

結果：DAG size: 11

測試2：輸出節(jié)點‘E’的入度邊

List<String> incomingEdges = DAG.getIncomingEdges("E");
Log.d(TAG, "node E, incomming: " + formatList(incomingEdges));

結果：node E, incomming: D,J,K,F

測試3：輸出節(jié)點'C'的出度邊

List<String> outgoingEdges = DAG.getOutgoingEdges("C");
Log.d(TAG, "node C, outgoings: " + formatList(outgoingEdges));

結果：node C, outgoings: D,F

測試4：輸出圖的拓撲排序結果（拓撲排序的結果不是唯一的炭菌，滿足定義即可）

List<String> sortList = DAG.getSortedList();
Log.d(TAG, "sortList: " + formatList(sortList));

結果：sortList: G,B,A,H,C,D,J,I,F,K,E --滿足“圖中任意一對頂點u和v罪佳，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前”

格式化節(jié)點函數(shù)：

private String formatList(List<String> list) {
    StringBuilder builder = new StringBuilder();
    for (String value : list) {
        builder.append(value);
        builder.append(",");
    }
    return builder.toString();
}

總結

雖然此處圖的數(shù)據(jù)結構使用了泛型黑低，卻并不通用（僅可以用來表示有向赘艳、無權圖，且其他運算操作缺失）。由于JDK的集合類中并沒有提供表示圖數(shù)據(jù)結構的相關類蕾管，以至于圖在開發(fā)人員間其實并不普及枷踏，開發(fā)過程中很少借助圖去實現(xiàn)某些特定功能。于是掰曾，圖就像神話般一樣呕寝，僅僅出現(xiàn)在相關面試寶典里，以及偶爾回憶其概念的程序員心中婴梧。

在網(wǎng)上找了下實現(xiàn)圖通用的數(shù)據(jù)結構的開源庫，也很少看到評星很高的客蹋，最好找到下載了很久沒有瀏覽過的谷歌開源庫guava塞蹭，最近23版本增加了圖數(shù)據(jù)結構，而且實現(xiàn)android版本了讶坯，于是想接下來借助它來梳理圖的相關知識番电。
通過gradle導入guava方式：compile 'com.google.guava:guava:23.5-android'

使用guava的common.graph圖庫實現(xiàn)上述有向無環(huán)圖：

MutableGraph<String> DAG = GraphBuilder.directed().build(); //構建有向圖

//省略添加節(jié)點，添加邊
//DAG.addNode(node);
//DAG.putEdge(nodeU, nodeV);

//獲取節(jié)點數(shù)
final int size = DAG.nodes().size();
Log.d(TAG, "DAG size: " + size);


//獲取‘E’的入度邊
Set<String> incomingEdges = DAG.predecessors("E"); //‘E’的前趨
Log.d(TAG, "node E, incomming: " + formatList(incomingEdges));

//獲取‘C’的出度邊
Set<String> outgoingEdges = DAG.successors("C"); //‘C’的后繼
Log.d(TAG, "node C, outgoings: " + formatList(outgoingEdges));

//深度優(yōu)先遍歷
Iterable<String> dfs = Traverser.forGraph(DAG).depthFirstPostOrder("G");
for (String value : dfs) {
    Log.d(TAG, "value: " + value);
}

輸出結果：

獲取節(jié)點數(shù)：
DAG size: 11

獲取‘E’的入度邊：
node E, incomming: D,J,K,F

獲取‘C’的出度邊：
node C, outgoings: D,F

拓撲排序結果(逆序)：
value: E
value: J
value: D
value: K
value: F
value: C
value: A
value: B
value: I
value: H
value: G

后續(xù)將繼續(xù)梳理圖相關內(nèi)容辆琅。