關(guān)于guava中圖數(shù)據(jù)結(jié)構(gòu)的基本情況官方介紹請先查看上一篇wiki文檔翻譯：圖論（2）：Guava中Graph模塊(wiki翻譯)蟆技，這一節(jié)我們使用具體的示例圖來測試各個接口的功能并以此查看對應(yīng)源碼的具體實現(xiàn)捣鲸。
由于Graph模塊中絕大部分的具體實現(xiàn)類都是private類型的（僅對本包可見）而僅暴露相關(guān)的interface(如：Graph宠页、Network等)乓诽，因此在實際使用過程中，我們并不會接觸到太多的具體實現(xiàn)類遂庄。這里為了理清Guava的實現(xiàn)原理古戴，打算在用例中順帶梳理一下其實現(xiàn)。
測試用例準(zhǔn)備
節(jié)點定義: {N1=1, N2=2, N3=3, N4=4}.
邊集定義: {E11="1-1", E11_A="1-1a", E12="1-2", E12_A="1-2a", E12_B = "1-2b", E21 = "2-1", E13 = "1-3", E31 = "3-1", E34 = "3-4", E44 = "4-4", E42 = "4-2"}.(邊名稱上數(shù)字表示其起點和終點)
預(yù)期節(jié)點數(shù): NODE_COUNT=20.
預(yù)期邊數(shù): EDGE_COUNT=20.
Graph功能介紹
特性：
a)頂點唯一; b)支持有向邊和無向邊; c)邊只能通過兩個頂點隱式定義; d)不支持并行邊摄悯。
示例圖如下：
Graph測試用例圖
- 使用對應(yīng)構(gòu)建類
GraphBuilder來構(gòu)建Graph實例：
MutableGraph<Integer> graph1 = GraphBuilder.directed() //指定為有向圖
.nodeOrder(ElementOrder.<Integer>insertion()) //節(jié)點按插入順序輸出
//(還可以取值無序unordered()赞季、節(jié)點類型的自然順序natural())
.expectedNodeCount(NODE_COUNT) //預(yù)期節(jié)點數(shù)
.allowsSelfLoops(true) //允許自環(huán)
.build();
Log.d(TAG, "initlized graph1: " + graph1);
輸出：
initlized graph1:isDirected: true, allowsSelfLoops: true, nodes: [], edges: []
在Builder中并沒有包含復(fù)雜的構(gòu)造邏輯，而只是簡單設(shè)置了幾個全局屬性而已（如輸出所示：是否允許自環(huán)奢驯、是否有向等）碟摆；build()接口為最終的構(gòu)建接口，返回一個MutableGraph接口類型的返回值叨橱，此處返回的是其實現(xiàn)子類ConfigurableMutableGraph典蜕，內(nèi)部通過一個ConfigurableMutableValueGraph實例來實現(xiàn)（所有的方法都調(diào)用該實例的方法實現(xiàn)）的，因為ValueGraph包含了Graph的全部功能罗洗，可以猜測到設(shè)計者也因此復(fù)用了同一套實現(xiàn)方案(ConfigurableMutableValueGraph)饵沧。
注：使用Builder類構(gòu)建的實例都是Mutable類型的坊夫，表示這個Graph可以增刪節(jié)點和邊，與之對應(yīng)的是Immutable類型，一般通過copyOf()的靜態(tài)函數(shù)實現(xiàn)扬蕊，表示該類型是不可變類型（不能增加/刪除節(jié)點和邊）膳凝。
- 增加節(jié)點以及連接邊：
//插入邊(默認(rèn)會將節(jié)點加入graph中)
graph1.putEdge(N2, N3);
graph1.putEdge(N1, N3);
graph1.putEdge(N1, N2);
graph1.putEdge(N2, N2);
graph1.addNode(N4);
//返回圖中所有的節(jié)點(順序依賴nodeOrder)
Set<Integer> nodes = graph1.nodes();
Log.d(TAG, "graph1 nodes count:" + nodes.size() + ", nodes value:"
+ format(nodes));
//返回圖中所有的邊集合
Set<EndpointPair<Integer>> edges = graph1.edges();
Log.d(TAG, "graph1 edge count:" + edges.size() + ", edges value:"
+ format(edges));
輸出：
graph1 nodes count:4, nodes value:{2,3,1,4} //按節(jié)點的插入先后順序
graph1 edge count:4, edges value:{<2 -> 2>,<2 -> 3>,<1 -> 2>,<1 -> 3>}
示例中的修改接口addNode()艳汽、putEdge()赠法，以及removeNode()、removeEdge()淑倾，最終操作的數(shù)據(jù)結(jié)構(gòu)是ConfigurableMutableValueGraph中的屬性nodeConnections馏鹤，它是一個Map<N, GraphConnections>類型，保存每一個節(jié)點的連接關(guān)系（它的前趨有哪些節(jié)點娇哆、后繼有哪些節(jié)點湃累、連接邊的權(quán)值是什么），其具體實現(xiàn)子類是DirectedGraphConnections（有向圖）或UndirectedGraphConnections（無向圖）碍讨。
注：此處節(jié)點的順序如果指定為無序unordered()或者自然順序natural()時將會影響節(jié)點的輸出順序：
//無序：節(jié)點的輸出順序
nodes value:{3,4,1,2}
//自然順序：節(jié)點輸出順序
nodes value:{1,2,3,4}
另外治力，Graph(ValueGraph)要求節(jié)點在圖中唯一（作為Map<N, GraphConnections>的Key值），因此如果添加重復(fù)的節(jié)點會自動覆蓋已有的同名節(jié)點勃黍。
由于節(jié)點和邊在添加進(jìn)來時就已經(jīng)按照其邏輯關(guān)系保存在GraphConnections中了宵统，因此下面示例在求其前趨、后繼覆获、鄰接點马澈、出度益兄、入度等操作時，只要查詢該數(shù)據(jù)結(jié)構(gòu)就能獲取相關(guān)信息了箭券，下面為添加邏輯：
對于無向圖的UndirectedGraphConnections而言，由于不需要區(qū)分前趨和后繼疑枯，因此只要將其指定為鄰節(jié)點即可辩块。如下源碼所示：
//UndirectedGraphConnections
public void addPredecessor(N node, V value) { //添加前趨
V unused = addSuccessor(node, value); //直接調(diào)用了添加后繼方法
}
public V addSuccessor(N node, V value) { //添加后繼
return adjacentNodeValues.put(node, value); //直接將node和value的映射關(guān)系添加到Map中
}
對于有向圖DirectedGraphConnections而言，則情況復(fù)雜一點荆永，關(guān)鍵點在于在同一個Map中如何區(qū)分相關(guān)節(jié)點是前趨還是后繼废亭。
代碼中是這樣定義的：
// Every value in this map must either be an instance of PredAndSucc with a successorValue of
// type V, PRED (representing predecessor), or an instance of type V (representing successor).
private final Map<N, Object> adjacentNodeValues;
其意思是：Map中的value值要么是一個PredAndSucc（這里表示既是前趨也是后繼）、要么是PRED（僅僅是前趨節(jié)點）具钥、要么是V類型的實例（僅僅是后繼節(jié)點）豆村。
添加前趨
public void addPredecessor(N node, V unused) {
Object previousValue = adjacentNodeValues.put(node, PRED); //首先直接添加PRED，標(biāo)識是前趨
if (previousValue == null) { //表示是首次添加該節(jié)點
checkPositive(++predecessorCount); //前趨+1
} else if (previousValue instanceof PredAndSucc) {
// Restore previous PredAndSucc object.
adjacentNodeValues.put(node, previousValue); //表示該節(jié)點已經(jīng)包含了前趨和后繼關(guān)系骂删，則恢復(fù)原來的值
} else if (previousValue != PRED) { // successor //到這里已經(jīng)有一個具體的V類型的值了掌动，表示已經(jīng)添加了后繼
// Do NOT use method parameter value 'unused'. In directed graphs, successors store the value.
adjacentNodeValues.put(node, new PredAndSucc(previousValue)); //則構(gòu)造一個既是前趨也是后繼的數(shù)據(jù)
checkPositive(++predecessorCount); //前趨+1
}
}
添加后繼
public V addSuccessor(N node, V value) {
Object previousValue = adjacentNodeValues.put(node, value); //首先直接添加value，表示是一個后繼
if (previousValue == null) { //首次添加
checkPositive(++successorCount); //后繼+1
return null;
} else if (previousValue instanceof PredAndSucc) { //已經(jīng)加入過宁玫，且標(biāo)識為既是前趨也是后繼
adjacentNodeValues.put(node, new PredAndSucc(value)); //覆蓋其舊值
return (V) ((PredAndSucc) previousValue).successorValue; //返回舊值
} else if (previousValue == PRED) { //已經(jīng)加入為前趨節(jié)點
adjacentNodeValues.put(node, new PredAndSucc(value)); //則構(gòu)造一個既是前趨也是后繼的數(shù)據(jù)
checkPositive(++successorCount); //后繼+1
return null;
} else { // successor //已經(jīng)是value類型的值粗恢，
return (V) previousValue; //已經(jīng)在第一行覆蓋了，返回其舊值即可欧瘪。
}
}
判斷當(dāng)前節(jié)點是前趨還是后繼方法：
private static boolean isPredecessor(@Nullable Object value) {
//是PRED或者是PredAndSucc類型就表示該節(jié)點是前趨節(jié)點（在添加時就是按這個規(guī)則加入的）
return (value == PRED) || (value instanceof PredAndSucc);
}
private static boolean isSuccessor(@Nullable Object value) {
//要么是具體的value類型值眷射，要么是`PredAndSucc`類型，則表示是后繼節(jié)點
return (value != PRED) && (value != null);
}
刪除前趨節(jié)點和刪除后繼節(jié)點也按上述類型規(guī)則執(zhí)行佛掖，此處省略其實現(xiàn)妖碉。
3.獲取節(jié)點的前趨列表：
Set<Integer> predecessors = graph1.predecessors(N2); //獲取N2的前趨
Log.d(TAG, "graph1 node:" + N2 + " predecessors:" + format(predecessors));
輸出：
graph1 node:2 predecessors:{1,2}
注：對于允許自環(huán)的圖allowsSelfLoops(true)中，一條自環(huán)邊在有向圖中既是前趨也是后繼芥被，既是入度也是出度欧宜。
- 獲取節(jié)點的后繼列表：
graph1.putEdge(N2, N4); //圖上面示例圖中紅色邊所示，動態(tài)增加了一條邊
Set<Integer> successors = graph1.successors(N2); //獲取N2的后繼
Log.d(TAG, "add edge of (" + N2 + "->" + N4 + ") after graph1 node:"
+ N2 + " successors:" + format(successors));
輸出：
add edge of (2->4) after graph1 node:2 successors:{4,2,3} //如圖所示
- 獲取節(jié)點的鄰接點列表(包括前趨和后繼)：
Set<Integer> adjacents = graph1.adjacentNodes(N2); //獲取N2的鄰接點
Log.d(TAG, "graph1 node: " + N2 + ", adjacents: " + format(adjacents));
輸出：
graph1 node: 2, adjacents: {4,1,2,3}
- 獲取節(jié)點的度(入度和出度)：
Log.d(TAG, "graph1 node: " + N2 + ", degree: " + graph1.degree(N2)
+ ", indegree: " + graph1.inDegree(N2)
+ ", outdegree: " + graph1.outDegree(N2)); //N2的度拴魄、入度鱼鸠、出度
輸出：
graph1 node: 2, degree: 5, indegree: 2, outdegree: 3 //自環(huán)既是入度也是出度
- 判斷頂點連通性(是否有直連邊)：
final boolean connecting23 = graph1.hasEdgeConnecting(N2, N3); //N2&N3是否連通
final boolean connecting14 = graph1.hasEdgeConnecting(N1, N4); //N1&N4是否連通
Log.d(TAG, "graph1 node " + N2 + " & " + N3 + " connecting: " + connecting23
+ ", node " + N1 + " & " + N4 + " connecting: " + connecting14);
輸出：
graph1 node 2 & 3 connecting: true, node 1 & 4 connecting: false //N1&N4之間無邊
判斷連通性，只需要后面那個節(jié)點是否是前一個節(jié)點的后繼即可羹铅，AbstractBaseGraph中實現(xiàn)：
public boolean hasEdgeConnecting(N nodeU, N nodeV) {
checkNotNull(nodeU);
checkNotNull(nodeV);
return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
}
- 轉(zhuǎn)換成不可變graph(
Immutable**類型)
ImmutableGraph<Integer> immutableGraph = ImmutableGraph.copyOf(graph1);
nodes = immutableGraph.nodes(); //返回圖中所有的節(jié)點(順序依賴nodeOrder)
Log.d(TAG, "immutable graph nodes count:" + nodes.size()
+ ", nodes value:" + format(nodes));
輸出：
immutable graph nodes count:4, nodes value:{2,3,1,4} //同被拷貝圖順序
ImmutableGraph的實現(xiàn)方式實際上就是將Mutable**類型的數(shù)據(jù)原樣復(fù)制到?jīng)]有實現(xiàn)Mutable**接口的類ForwardingGraph中蚀狰。
- 判斷是否存在環(huán)(第一個頂點和最后一個頂點相同的路徑稱為環(huán))
final boolean cycle = Graphs.hasCycle(graph1);
Log.d(TAG, "graph1 has cycle: " + cycle);
輸出：
graph1 has cycle: true //因為N2節(jié)點存在一條自環(huán)，如果去掉則不存在環(huán)
- 獲取僅包含指定節(jié)點的生成子圖：
Set<Integer> subNodes = new HashSet<>();
subNodes.add(N1);
subNodes.add(N2); //獲取只包含N1和N2的生成子圖
MutableGraph<Integer> subgraph = Graphs.inducedSubgraph(graph1, subNodes);
Log.d(TAG, "subgraph: " + subgraph);
輸出：
subgraph: isDirected: true, allowsSelfLoops: true, nodes: [1, 2],
edges: [<1 -> 2>, <2 -> 2>]
- 獲取節(jié)點的可到達(dá)列表(獲取能訪問到的節(jié)點結(jié)合职员，不單指直連邊)：
Set<Integer> reachNodes = Graphs.reachableNodes(graph1, N2); //N2的可達(dá)列表
Log.d(TAG, "graph1 node: " + N2 + ", reachNodes: " + format(reachNodes));
輸出：
graph1 node: 2, reachNodes: {2,4,3} //N2不存在能訪問到N1的邊
這里是通過從起始點N開始進(jìn)行BFS遍歷的結(jié)果麻蹋。
- 獲取圖的傳遞閉包(如果節(jié)點A的可達(dá)列表
reachableNodes(A)包含節(jié)點B，則在節(jié)點A和節(jié)點B之間增加一條直連邊)焊切，具體參考有向圖的傳遞閉包概念扮授。
Graph<Integer> graph2 = Graphs.transitiveClosure(graph1);
Log.d(TAG, "transitiveClosure graph2: " + graph2);
輸出：
transitiveClosure graph2: isDirected: true, allowsSelfLoops: true,
nodes: [2, 4, 3, 1], edges: [<2 -> 4>, <2 -> 3>, <2 -> 2>, <4 -> 4>,
<3 -> 3>, <1 -> 4>, <1 -> 1>, <1 -> 3>, <1 -> 2>]
- 獲取有向圖的的反轉(zhuǎn)圖：
Graph<Integer> graph3 = Graphs.transpose(graph1);
Log.d(TAG, "transpose graph3: " + graph3);
輸出：
transpose graph3: isDirected: true, allowsSelfLoops: true,
nodes: [2, 3, 1, 4], edges: [<2 -> 1>, <2 -> 2>, <3 -> 1>, <3 -> 2>, <4 -> 2>]
- 圖的遍歷
//深度優(yōu)先-后序
Iterable<Integer> dfs = Traverser.forGraph(graph1).depthFirstPostOrder(N1);
Log.d(TAG, "dfs traverser: " + format(dfs));
//深度優(yōu)先-前序
Iterable<Integer> dfsPre =Traverser.forGraph(graph1).depthFirstPreOrder(N1);
Log.d(TAG, "dfs pre traverser: " + format(dfsPre));
//廣度優(yōu)先
Iterable<Integer> bfs =Traverser.forGraph(graph1).breadthFirst(N1);
Log.d(TAG, "bfs traverser: " + format(bfs));
輸出：
dfs traverser: {4,3,2,1} //深度優(yōu)先-后序
dfs pre traverser: {1,2,4,3} //深度優(yōu)先-前序
bfs traverser: {1,2,3,4} //廣度優(yōu)先
- 刪除節(jié)點(對應(yīng)的連接邊也將刪除)
刪除節(jié)點芳室，或者刪除邊時，需要將對應(yīng)的連接關(guān)系也要刪除刹勃，因此又涉及到了關(guān)系結(jié)構(gòu)GraphConnections堪侯，此處也重點分析一下：
//ConfigurableMutableValueGraph
//刪除節(jié)點
public boolean removeNode(N node) {
checkNotNull(node, "node");
GraphConnections<N, V> connections = nodeConnections.get(node);
if (connections == null) { //查看是否有鄰接點
return false;
}
//先刪除自環(huán)（簡單，因為不涉及其他節(jié)點）
if (allowsSelfLoops()) {
// Remove self-loop (if any) first, so we don't get CME while removing incident edges.
if (connections.removeSuccessor(node) != null) { //刪除它的后繼荔仁，不為null表示存在此環(huán)
connections.removePredecessor(node); //再次刪除其前趨伍宦，存放的數(shù)據(jù)不一樣
--edgeCount; //邊數(shù)-1
}
}
//遍歷其后繼節(jié)點列表，并分別刪除它的前趨關(guān)系
for (N successor : connections.successors()) {
nodeConnections.getWithoutCaching(successor).removePredecessor(node);
--edgeCount;
}
//因為在無向圖中不區(qū)分前趨和后繼乏梁，因此這里只有是有向圖時才需要刪除后繼關(guān)系
if (isDirected()) { // In undirected graphs, the successor and predecessor sets are equal.
for (N predecessor : connections.predecessors()) { //類似刪除前趨
checkState(nodeConnections.getWithoutCaching(predecessor).removeSuccessor(node) != null);
--edgeCount;
}
}
nodeConnections.remove(node); //連接關(guān)系中徹底刪除該節(jié)點
checkNonNegative(edgeCount);
return true;
}
//刪除邊
public V removeEdge(N nodeU, N nodeV) {
checkNotNull(nodeU, "nodeU");
checkNotNull(nodeV, "nodeV");
//分別獲取節(jié)點U和V的連接結(jié)構(gòu)
GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
GraphConnections<N, V> connectionsV = nodeConnections.get(nodeV);
if (connectionsU == null || connectionsV == null) { //校驗其連通性次洼，有一個為null，表示結(jié)構(gòu)已不成立
return null;
}
//刪除U的后繼
V previousValue = connectionsU.removeSuccessor(nodeV);
if (previousValue != null) { //不為null表示有連接關(guān)系
connectionsV.removePredecessor(nodeU); //則還需要刪除節(jié)點V到U的前趨關(guān)系
checkNonNegative(--edgeCount);
}
return previousValue;
}
刪除節(jié)點：
graph1.removeNode(N2); //刪除一個節(jié)點N2
edges = graph1.edges();
Log.d(TAG, "graph1 remove node of (" + N2 + ") after graph1 edge
count:" + edges.size() + ", edges value:" + format(edges));
輸出：
graph1 remove node of (2) after graph1 edge count:1, edges value:{<1 -> 3>}
- 構(gòu)建類
Builder的from()接口只能復(fù)制其屬性值遇骑，而并不會復(fù)制相應(yīng)的節(jié)點和邊：
//build of from()僅僅復(fù)制其屬性卖毁，節(jié)點和邊不會復(fù)制過來
MutableGraph<Integer> graph4 = GraphBuilder.from(graph1).build();
Set<EndpointPair<Integer>> edges4 = graph4.edges();
Log.d(TAG, "graph4 edge count:" + edges4.size()
+ ", edges value:" + format(edges4));
輸出：
graph4 edge count:0, edges value:{}
ValueGraph
ValueGraph由于和Graph是一套實現(xiàn)方案，都是實現(xiàn)類ConfigurableMutableValueGraph來操作的落萎，因此這里不再詳細(xì)描述其實現(xiàn)亥啦。
特性：
a)頂點必須唯一,邊可以不唯一; b)支持有向和無向邊; c)邊的定義支持權(quán)值指定; d)不支持并行邊.
示例圖如下:
ValueGraph測試用例圖
注：ValueGraph支持Graph的全部功能，因此下面僅介紹其差異功能：
- 使用對應(yīng)構(gòu)建類
ValueGraphBuilder來構(gòu)建ValueGraph實例：
//節(jié)點類型為Integer,邊類型為String
MutableValueGraph<Integer, String> graph1 = ValueGraphBuilder.directed() //有向
.allowsSelfLoops(true) //允許自環(huán)
.expectedNodeCount(NODE_COUNT) //期望節(jié)點數(shù)
.nodeOrder(ElementOrder.<Integer>insertion()) //節(jié)點順序
.build();
Log.d(TAG, "initlized graph1: " + graph1);
輸出：
initlized graph1:isDirected: true,allowsSelfLoops:true,nodes:[], edges:{}
- 增加頂點和邊
graph1.putEdgeValue(N3, N1, E31);
graph1.putEdgeValue(N3, N4, E34);
graph1.putEdgeValue(N4, N4, E44);
graph1.putEdgeValue(N1, N1, E11);
graph1.putEdgeValue(N1, N2, E12);
graph1.putEdgeValue(N2, N1, E21);
graph1.putEdgeValue(N1, N3, E13);
Log.d(TAG, "put edges after graph1: " + graph1);
//返回圖中所有的節(jié)點(順序依賴nodeOrder)
Set<Integer> nodes = graph1.nodes();
Log.d(TAG, "graph1 nodes count:" + nodes.size() + ", nodes value:"
+ format(nodes));
輸出：
put edges after graph1: isDirected: true, allowsSelfLoops: true,
nodes: [3, 1, 4, 2], edges: {<3 -> 4>=3-4, <3 -> 1>=3-1,
<1 -> 1>=1-1, <1 -> 2>=1-2, <1 -> 3>=1-3, <4 -> 4>=4-4, <2 -> 1>=2-1}
//節(jié)點順序
graph1 nodes count:4, nodes value:{3,1,4,2}
- 獲取兩個節(jié)點之間的連接邊：
其內(nèi)部實現(xiàn)為：
public V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
checkNotNull(nodeU);
checkNotNull(nodeV);
//得到節(jié)點U的連接連接結(jié)構(gòu)
GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
V value = (connectionsU == null) ? null : connectionsU.value(nodeV); //拿到其連接值
return value == null ? defaultValue : value;
}
獲取連接邊：
String edge = graph1.edgeValueOrDefault(N1, N2, "@null");
Log.d(TAG, "graph1 node " + N1 + " & " + N2 + " edge: " + edge);
輸出：
graph1 node 1 & 2 edge: 1-2
-
asGraph()轉(zhuǎn)換為Graph視圖
asGraph()實際上是重新new了一個AbstractGraph练链，只是它的接口實現(xiàn)是調(diào)用了Graph本身的接口禁悠，因此如果修改asGraph()返回的視圖的數(shù)據(jù)，其變化也會反映在Graph本身上兑宇，反之亦然碍侦。
Graph<Integer> graph5 = graph1.asGraph();
Log.d(TAG, "asGraph:" + graph5);
輸出：
asGraph:isDirected: true, allowsSelfLoops: true, nodes: [3, 1, 4],
edges: [<3 -> 4>, <3 -> 1>, <1 -> 1>, <1 -> 3>, <4 -> 4>] //注意此處不包含邊信息
Network
由于Network與Graph以及ValueGraph有很大的不同性，最大的不同點是Network中允許并行邊（即兩個節(jié)點間可以有多條同向邊隶糕，如：節(jié)點A和節(jié)點B可以有兩條同向邊：A->B: a-b-1瓷产，a-b-2），這就導(dǎo)致了前面介紹的使用節(jié)點作為Map的key的數(shù)據(jù)結(jié)構(gòu)GraphConnections的邏輯走不下去了枚驻，因為節(jié)點不唯一了濒旦。使得設(shè)計者重新設(shè)計了另一套使用邊為Key的機(jī)制來實現(xiàn)節(jié)點的連接關(guān)系。
為什么需要Network加入到Guava中再登？通過上面描述的不同點可知尔邓，Graph(ValueGraph)是通過頂點來定義邊的，即兩個頂點只能有一條（有向）邊連接锉矢；但是在某些圖中梯嗽，在兩個頂點之間需要有多條邊連接的場景出現(xiàn)。比如沽损，兩個機(jī)場（對應(yīng)兩個節(jié)點）之間存在多趟固定航班灯节，而這里用ValueGraph是無法描述的。
Network相對于Graphe(ValueGraph)，由于功能的差異炎疆，其接口也發(fā)生了些變化卡骂，增加了如下特殊接口：
Set<E> inEdges(N node); //node的入度邊集合（不同于predecessors()，它返回的入度節(jié)點非邊）
Set<E> outEdges(N node); //node的出度邊集合（不同于successors()形入，它返回的是出度節(jié)點非邊）
EndpointPair<N> incidentNodes(E edge); //邊對應(yīng)的兩個端點
Set<E> adjacentEdges(E edge); //邊的鄰接邊
Set<E> edgesConnecting(N nodeU, N nodeV); //兩個節(jié)點的連接邊集
其主要區(qū)別在于NetworkConnections的實現(xiàn)不同：
取消了前趨和后繼的操作接口全跨，因為操作節(jié)點已不能滿足Network的場景：
void addPredecessor(N node, V value);
void removePredecessor(N node);
V addSuccessor(N node, V value);
V removeSuccessor(N node);
增加了對出度邊和入度邊的操作接口：
void addInEdge(E edge, N node, boolean isSelfLoop);
void addOutEdge(E edge, N node);
N removeInEdge(E edge, boolean isSelfLoop);
N removeOutEdge(E edge);
重點查看DirectedMultiNetworkConnections（使用allowsParallelEdges(true)構(gòu)建Network實例時使用）的源碼，其內(nèi)部相對于GraphConnections已經(jīng)將出度邊和入度邊集合分開存放了：
AbstractDirectedNetworkConnections --是NetworkConnections的子類
/** Keys are edges incoming to the origin node, values are the source node. */
protected final Map<E, N> inEdgeMap; //入度邊集合亿遂，邊是key
/** Keys are edges outgoing from the origin node, values are the target node. */
protected final Map<E, N> outEdgeMap; //出度邊集合浓若，邊是key
//addInEdge(), addOutEdge, removeInEdge(), removeOutEdge()操作的對象都是上述兩個Map
DirectedMultiNetworkConnections --是AbstractDirectedNetworkConnections的子類
//注意，下面的前趨集合和后繼集合使用了Multiset崩掘，因為前趨和后繼允許有并行邊，存在多個相同節(jié)點
//內(nèi)部緩存了節(jié)點對應(yīng)的前趨節(jié)點集
private transient Reference<Multiset<N>> predecessorsReference;
//內(nèi)部緩存了節(jié)點對應(yīng)的后繼節(jié)點集
private transient Reference<Multiset<N>> successorsReference;
//這里使用緩存的目的是減少inEdgeMap.values()的遍歷操作少办，在函數(shù)predecessors()中可以直接返回predecessorsReference苞慢。
private Multiset<N> predecessorsMultiset() {
Multiset<N> predecessors = getReference(predecessorsReference);
if (predecessors == null) {
//前趨就是節(jié)點入度邊Map的value集合，可重復(fù)
predecessors = HashMultiset.create(inEdgeMap.values());
predecessorsReference = new SoftReference<>(predecessors);
}
return predecessors;
}
private Multiset<N> successorsMultiset() {
//...同上
}
特性：
a)邊必須唯一（因為兩個相同頂點間可以同時存在多條邊）; b)支持有向和無向邊; c)邊的定義支持權(quán)值指定; d)支持并行邊.
示例圖如下:
NetWork測試用例圖
注：Network也支持Graph的全部功能英妓，因此下面僅介紹其差異功能：
- 使用對應(yīng)構(gòu)建類
NetworkBuilder來構(gòu)建Network實例：
MutableNetwork<Integer, String> network1 = NetworkBuilder.directed() //有向網(wǎng)
.allowsParallelEdges(true) //允許并行邊
.allowsSelfLoops(true) //允許自環(huán)
.nodeOrder(ElementOrder.<Integer>insertion()) //節(jié)點順序
.edgeOrder(ElementOrder.<String>insertion()) //邊順序
.expectedNodeCount(NODE_COUNT) //期望節(jié)點數(shù)
.expectedEdgeCount(EDGE_COUNT) //期望邊數(shù)
.build();
network1.addEdge(N1, N3, E13);
network1.addEdge(N3, N1, E31);
network1.addEdge(N3, N4, E34);
network1.addEdge(N4, N4, E44);
network1.addEdge(N1, N1, E11);
network1.addEdge(N1, N1, E11_A);
network1.addEdge(N1, N2, E12);
network1.addEdge(N1, N2, E12_A);
network1.addEdge(N1, N2, E12_B);
network1.addEdge(N2, N1, E21);
Log.d(TAG, "add edges after network1: " + network1);
輸出：
add edges after network1: isDirected: true, allowsParallelEdges: true,
allowsSelfLoops: true, nodes: [1, 3, 4, 2], edges: {1-3=<1 -> 3>,
3-1=<3 -> 1>, 3-4=<3 -> 4>, 4-4=<4 -> 4>, 1-1=<1 -> 1>,
1-1a=<1 -> 1>, 1-2=<1 -> 2>, 1-2a=<1 -> 2>, 1-2b=<1 -> 2>, 2-1=<2 -> 1>}
注：Network和Graph不同的是挽放，它可以通過一條邊來定義兩個頂點，如輸出所示蔓纠。
- 獲取邊的鄰接邊(即邊對應(yīng)兩個端點的鄰接邊集合)
Set<String> adjacentEdges = network1.adjacentEdges(E12_A);
Log.d(TAG, "network1 edge: " + E12_A + ", adjacentEdges: "
+ format(adjacentEdges));
輸出：
network1 edge: 1-2a, adjacentEdges: {1-1,1-1a,2-1,3-1,1-2b,1-2,1-3,4-2}
- 獲取兩個頂點之間的邊集(network中由于頂點間存在平行邊辑畦，因此兩個頂點之間存在多條邊)：
Set<String> networkEdges = network1.edgesConnecting(N1, N2);
Log.d(TAG, "network1 node " + N1 + " & " + N2 + " edges: "
+ format(networkEdges));
輸出：
network1 node 1 & 2 edges: {1-2a,1-2b,1-2} //存在3條邊
- 返回兩個頂點之間的一條邊（如果該兩個頂點間存在多條邊則會拋出異常）：
String edge = network1.edgeConnectingOrNull(N1, N3);//如果是N1和N2則會拋異常
Log.d(TAG, "network1 node " + N1 + " & " + N3 + " edge: " + edge);
輸出：
network1 node 1 & 3 edge: 1-3
- 獲取節(jié)點的鄰接邊(所有包含該節(jié)點的邊集合)
Set<String> incidentEdges = network1.incidentEdges(N1);
Log.d(TAG, "network1 node " + N1 + " incidents: " + format(incidentEdges));
輸出：
network1 node 1 incidents: {1-1,1-1a,2-1,3-1,1-2a,1-2b,1-2,1-3}
- 獲取邊的鄰接點(邊對應(yīng)的兩個頂點)
EndpointPair<Integer> incidentNodes = network1.incidentNodes(E12_A);
Log.d(TAG, "network1 edge " + E12_A + " incidentNodes: " + incidentNodes);
輸出：
network1 edge 1-2a incidentNodes: <1 -> 2>
示例代碼中組裝Iterable的元素信息的函數(shù)如下：
private static <T> String format(Iterable<T> iterable) {
StringBuilder builder = new StringBuilder();
builder.append("{");
for (T obj : iterable) {
builder.append(obj).append(",");
}
if (builder.length() > 1) {
builder.deleteCharAt(builder.length() - 1);
}
builder.append("}");
return builder.toString();
}
最后
Guava中的Graph的基本API用法及原理到這里基本介紹完了。后續(xù)腿倚，我們將使用上面的這些基本接口來實現(xiàn)《數(shù)據(jù)結(jié)構(gòu)》中關(guān)于圖的具體算法應(yīng)用纯出。
