背景

前一阵项目中引用了Material Design依赖库中的一个控件BottomSheetDialog，主要是用来上下滑动操作界面的show()&hide()事件（解决界面需要跟手操作问题），过程中碰到了一些问题，于是花时间研究了一下其具体实现。其核心源码是CoordinatorLayout，内部还包括了另一个重要内部类Behavior，本篇文章内容如标题所示暂不去分析其整体的运行机制，而是打算抽出其中一个点——CoordinatorLayout中View之间的依赖关系是如何确定的，这一个点来分析。

这里先给出结论：View之间的依赖关系恰好是有向图（child指向dependency的一条有向无权边）的一个具体应用（具体还要检测是否有环），CoordinatorLayout采用邻接表（SimpleArrayMap<T, ArrayList<T>>）的数据结构构建有向图的依赖关系，并将图的拓扑排序结果作为View的处理（measure、layout等）顺序。因此这里也刚好有助于我们复习一下大学学过的核心课程《数据结构》中关于图的相关内容。

图相关概念

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图按照边的有无方向性分为无向图和有向图。

图中某个节点与其他节点的直连边条数称为该节点的度。有向图中，指向其他节点的边成为出度，被其他节点指向的边称为入度。

如果在有向图中，无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

拓扑排序是将图中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

Behavior功能简介

我们来看看CoordinatorLayout和Behavior这一套机制主要是为了实现什么功能。个人理解是谷歌弄的这个机制为了简化开发者在通过自定义View实现比以往更复杂的交互时的工作量（抽象）和工作难度（仅需实现自己关注的功能）。比如：如果自定义一个能解决父-子View之间的事件冲突的View结构时，必须要重写父View和子View的onInterceptTouchEvent()和onTouchEvent()接口以及其他必要接口，然后分别处理事件拦截，且这个自定义View很难重用起来（必须两个View配合行动）。但是当Behavior出现后，触摸事件、滑动冲突、依赖关系等工作都被CoordinatorLayout进行抽象完成了，仅抛出一个Behavior的接口让开发者自定义感兴趣的部分即可。Behavior机制通常用来实现如下三种功能：

• 事件的拦截：需重写方法onInterceptTouchEvent() + onTouchEvent()。
• View变化的拦截(本章的重点)：需重写layoutDependsOn() + onDependentViewChanged() + onDependentViewRemoved()。
• 嵌套滑动的拦截：需重写方法onStartNestedScroll() + onNestedScrollAccepted() + onStopNestedScroll() + onNestedScroll() + onNestedPreScroll() + onNestedFling() + onNestedPreFling()。

为什么要实现View之间的依赖关系及需要重写哪些方法

如果要实现这样一个效果：滑动A-View时，让另一个B-View也能跟着滑动。按照传统的做法，首先我们需要重新自定义一个父View来处理滑动事件来，然后在滑动A-View时，根据A-View的位置来设置B-View的translation值实现（实现较繁琐），如果滑动的View是一个列表呢，比如RecyclerView，这里的操作又该如何进行。但是有了Behavior之后，仅需要非常简单的实现的两个接口就能达到这个效果了，如下所示：

/**
 *
 * @param parent： 父容器
 * @param child: Behavior作用的View
 * @param dependency： 是child的依赖对象，同时也是Behavior对child进行操作的根据
 * @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()函数中)就通过layoutDependsOn()回调确定了View两两之间的依赖关系（通过双重for循环遍历，因此layoutDependsOn中最好不要写复杂逻辑，仅需简单确定是否是依赖View），所以当依赖View发生变化时，自然就能再回调回来告诉被依赖View发生了变化。

依赖关系的具体实现

经查看CoordinatorLayout的源码，可以看到在onMeasure()一开始就调用了函数prepareChildren()(有向图的拓扑排序)来确定View的依赖关系：

//依赖关系的排序结果列表（有向图的拓扑排序）
private final List<View> mDependencySortedChildren = new ArrayList<>();

//mChildDag是构建有向无环图的数据结构（DAG）
private final DirectedAcyclicGraph<View> mChildDag = new DirectedAcyclicGraph<>();

@Override
protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    prepareChildren(); //通过回调函数layoutDependsOn()确定view两两之间的依赖关系
    ensurePreDrawListener(); //注册重绘监听，在dependency发生变化时由onDependentViewChanged()回调出来
}


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

    //这里的双重循环进行了两两比较
    for (int i = 0, count = getChildCount(); i < count; i++) {
        final View view = getChildAt(i);
        //...省略
        mChildDag.addNode(view); //将节点加入有向图中，view相当与图的节点

        // Now iterate again over the other children, adding any dependencies to the graph
        for (int j = 0; j < count; j++) {
            if (j == i) {  //不可能出现自环（self-loop），直接过滤
                continue;
            }
            final View other = getChildAt(j);
            final CoordinatorLayout.LayoutParams otherLp = getResolvedLayoutParams(other);
            if (otherLp.dependsOn(this, other, view)) { //这里就是调用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
    //保存有向图的拓扑排序结果（依赖节点排在列表的最后）
    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); 
    //反转结果的目的主要是为了效率优化，因为关注的焦点是依赖节点，如果它能排在靠前的位置，
    //便能更及时的处理他的操作。
}

这里的mDependencySortedChildren存放的就是有向图的拓扑排序结果（依赖的节点排在列表前面，被依赖的节点排在列表后面）；mChildDag是整个有向图数据结构，触发onDependentViewChanged()回调时就是通过mChildDag非常简单找到被依赖View列表的（时间复杂度为O(1)）。这么做是为了在dependency发生变化时，只需通知它的被依赖view即可，而其他与之无关的view则不应该回调（因为没有依赖关系），后面还列出了类中定义的获取依赖view列表和被依赖view列表的接口也是如此，它的实现如下实现如下：

public void dispatchDependentViewsChanged(View view) {
    final List<View> dependents = mChildDag.getIncomingEdges(view); //view的入度边就是被依赖对象!!!
    if (dependents != null && !dependents.isEmpty()) { //依次回调给相应child
        for (int i = 0; i < dependents.size(); i++) {
            final View child = dependents.get(i);
            //...省略
            if (b != null) {
                b.onDependentViewChanged(this, child, view);  //即我们实现Behavior的对应回调
            }
        }
    }
}

//获取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;
}

到这里，有向图的一个实际应用场景就介绍完了。接下来我们来看看源码中有向无环图（DirectedAcyclicGraph<T>）的具体实现，总体来讲就是围绕下面这一个邻接表的操作：

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

SimpleArrayMap是一个android自己实现的一个Map，它的key(T)为图中的每一个节点对象，value(ArrayList<T>)是指向key节点的节点，即key节点的入度边。它的方法addNode()、addEdge()就是将这些关系存入到这个邻接表中，然后再通过它获取其入度和出度（出度需要遍历整个邻接表才能获取）；函数getSortedList()调用深度优先的递归函数dfs()实现其拓扑排序。

下面来看一个测试例子来验证运行结果，有如下示例有向无环图：

有向无环图测试实例

测试用例：

    DirectedAcyclicGraph<String> DAG = new DirectedAcyclicGraph<>(); //定义有向无环图

    //将节点加入有向图中
    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");

    //根据示例图加入有向边（终点-起点）
    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"); //这里增加一条环

测试1：输出有向图的大小（节点个数）

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

结果：DAG size: 11

测试2：输出节点‘E’的入度边

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

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

测试3：输出节点'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在线性序列中出现在v之前”

格式化节点函数：

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

总结

虽然此处图的数据结构使用了泛型，却并不通用（仅可以用来表示有向、无权图，且其他运算操作缺失）。由于JDK的集合类中并没有提供表示图数据结构的相关类，以至于图在开发人员间其实并不普及，开发过程中很少借助图去实现某些特定功能。于是，图就像神话般一样，仅仅出现在相关面试宝典里，以及偶尔回忆其概念的程序员心中。

在网上找了下实现图通用的数据结构的开源库，也很少看到评星很高的，最好找到下载了很久没有浏览过的谷歌开源库guava，最近23版本增加了图数据结构，而且实现android版本了，于是想接下来借助它来梳理图的相关知识。
通过gradle导入guava方式：compile 'com.google.guava:guava:23.5-android'

使用guava的common.graph图库实现上述有向无环图：

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

//省略添加节点，添加边
//DAG.addNode(node);
//DAG.putEdge(nodeU, nodeV);

//获取节点数
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));

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

输出结果：

获取节点数：
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

后续将继续梳理图相关内容。