图论（3）：Guava中Graph使用入门及原理介绍
2018-01-01 本文已影响1125人
JarryWell
关于guava中图数据结构的基本情况官方介绍请先查看上一篇wiki文档翻译：图论（2）：Guava中Graph模块(wiki翻译)，这一节我们使用具体的示例图来测试各个接口的功能并以此查看对应源码的具体实现。
由于Graph模块中绝大部分的具体实现类都是private类型的（仅对本包可见）而仅暴露相关的interface(如：Graph、Network等)，因此在实际使用过程中，我们并不会接触到太多的具体实现类。这里为了理清Guava的实现原理，打算在用例中顺带梳理一下其实现。
测试用例准备
节点定义: {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"}.(边名称上数字表示其起点和终点)
预期节点数: NODE_COUNT=20.
预期边数: EDGE_COUNT=20.
Graph功能介绍
特性：
a)顶点唯一; b)支持有向边和无向边; c)边只能通过两个顶点隐式定义; d)不支持并行边。
示例图如下：
Graph测试用例图
- 使用对应构建类
GraphBuilder来构建Graph实例：
MutableGraph<Integer> graph1 = GraphBuilder.directed() //指定为有向图
.nodeOrder(ElementOrder.<Integer>insertion()) //节点按插入顺序输出
//(还可以取值无序unordered()、节点类型的自然顺序natural())
.expectedNodeCount(NODE_COUNT) //预期节点数
.allowsSelfLoops(true) //允许自环
.build();
Log.d(TAG, "initlized graph1: " + graph1);
输出：
initlized graph1:isDirected: true, allowsSelfLoops: true, nodes: [], edges: []
在Builder中并没有包含复杂的构造逻辑，而只是简单设置了几个全局属性而已（如输出所示：是否允许自环、是否有向等）；build()接口为最终的构建接口，返回一个MutableGraph接口类型的返回值，此处返回的是其实现子类ConfigurableMutableGraph，内部通过一个ConfigurableMutableValueGraph实例来实现（所有的方法都调用该实例的方法实现）的，因为ValueGraph包含了Graph的全部功能，可以猜测到设计者也因此复用了同一套实现方案(ConfigurableMutableValueGraph)。
注：使用Builder类构建的实例都是Mutable类型的，表示这个Graph可以增删节点和边，与之对应的是Immutable类型，一般通过copyOf()的静态函数实现，表示该类型是不可变类型（不能增加/删除节点和边）。
- 增加节点以及连接边：
//插入边(默认会将节点加入graph中)
graph1.putEdge(N2, N3);
graph1.putEdge(N1, N3);
graph1.putEdge(N1, N2);
graph1.putEdge(N2, N2);
graph1.addNode(N4);
//返回图中所有的节点(顺序依赖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} //按节点的插入先后顺序
graph1 edge count:4, edges value:{<2 -> 2>,<2 -> 3>,<1 -> 2>,<1 -> 3>}
示例中的修改接口addNode()、putEdge()，以及removeNode()、removeEdge()，最终操作的数据结构是ConfigurableMutableValueGraph中的属性nodeConnections，它是一个Map<N, GraphConnections>类型，保存每一个节点的连接关系（它的前趋有哪些节点、后继有哪些节点、连接边的权值是什么），其具体实现子类是DirectedGraphConnections（有向图）或UndirectedGraphConnections（无向图）。
注：此处节点的顺序如果指定为无序unordered()或者自然顺序natural()时将会影响节点的输出顺序：
//无序：节点的输出顺序
nodes value:{3,4,1,2}
//自然顺序：节点输出顺序
nodes value:{1,2,3,4}
另外，Graph(ValueGraph)要求节点在图中唯一（作为Map<N, GraphConnections>的Key值），因此如果添加重复的节点会自动覆盖已有的同名节点。
由于节点和边在添加进来时就已经按照其逻辑关系保存在GraphConnections中了，因此下面示例在求其前趋、后继、邻接点、出度、入度等操作时，只要查询该数据结构就能获取相关信息了，下面为添加逻辑：
对于无向图的UndirectedGraphConnections而言，由于不需要区分前趋和后继，因此只要将其指定为邻节点即可。如下源码所示：
//UndirectedGraphConnections
public void addPredecessor(N node, V value) { //添加前趋
V unused = addSuccessor(node, value); //直接调用了添加后继方法
}
public V addSuccessor(N node, V value) { //添加后继
return adjacentNodeValues.put(node, value); //直接将node和value的映射关系添加到Map中
}
对于有向图DirectedGraphConnections而言，则情况复杂一点，关键点在于在同一个Map中如何区分相关节点是前趋还是后继。
代码中是这样定义的：
// 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（仅仅是前趋节点）、要么是V类型的实例（仅仅是后继节点）。
添加前趋
public void addPredecessor(N node, V unused) {
Object previousValue = adjacentNodeValues.put(node, PRED); //首先直接添加PRED，标识是前趋
if (previousValue == null) { //表示是首次添加该节点
checkPositive(++predecessorCount); //前趋+1
} else if (previousValue instanceof PredAndSucc) {
// Restore previous PredAndSucc object.
adjacentNodeValues.put(node, previousValue); //表示该节点已经包含了前趋和后继关系，则恢复原来的值
} else if (previousValue != PRED) { // successor //到这里已经有一个具体的V类型的值了，表示已经添加了后继
// Do NOT use method parameter value 'unused'. In directed graphs, successors store the value.
adjacentNodeValues.put(node, new PredAndSucc(previousValue)); //则构造一个既是前趋也是后继的数据
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) { //已经加入过，且标识为既是前趋也是后继
adjacentNodeValues.put(node, new PredAndSucc(value)); //覆盖其旧值
return (V) ((PredAndSucc) previousValue).successorValue; //返回旧值
} else if (previousValue == PRED) { //已经加入为前趋节点
adjacentNodeValues.put(node, new PredAndSucc(value)); //则构造一个既是前趋也是后继的数据
checkPositive(++successorCount); //后继+1
return null;
} else { // successor //已经是value类型的值，
return (V) previousValue; //已经在第一行覆盖了，返回其旧值即可。
}
}
判断当前节点是前趋还是后继方法：
private static boolean isPredecessor(@Nullable Object value) {
//是PRED或者是PredAndSucc类型就表示该节点是前趋节点（在添加时就是按这个规则加入的）
return (value == PRED) || (value instanceof PredAndSucc);
}
private static boolean isSuccessor(@Nullable Object value) {
//要么是具体的value类型值，要么是`PredAndSucc`类型，则表示是后继节点
return (value != PRED) && (value != null);
}
删除前趋节点和删除后继节点也按上述类型规则执行，此处省略其实现。
3.获取节点的前趋列表：
Set<Integer> predecessors = graph1.predecessors(N2); //获取N2的前趋
Log.d(TAG, "graph1 node:" + N2 + " predecessors:" + format(predecessors));
输出：
graph1 node:2 predecessors:{1,2}
注：对于允许自环的图allowsSelfLoops(true)中，一条自环边在有向图中既是前趋也是后继，既是入度也是出度。
- 获取节点的后继列表：
graph1.putEdge(N2, N4); //图上面示例图中红色边所示，动态增加了一条边
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} //如图所示
- 获取节点的邻接点列表(包括前趋和后继)：
Set<Integer> adjacents = graph1.adjacentNodes(N2); //获取N2的邻接点
Log.d(TAG, "graph1 node: " + N2 + ", adjacents: " + format(adjacents));
输出：
graph1 node: 2, adjacents: {4,1,2,3}
- 获取节点的度(入度和出度)：
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 //自环既是入度也是出度
- 判断顶点连通性(是否有直连边)：
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之间无边
判断连通性，只需要后面那个节点是否是前一个节点的后继即可，AbstractBaseGraph中实现：
public boolean hasEdgeConnecting(N nodeU, N nodeV) {
checkNotNull(nodeU);
checkNotNull(nodeV);
return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
}
- 转换成不可变graph(
Immutable**类型)
ImmutableGraph<Integer> immutableGraph = ImmutableGraph.copyOf(graph1);
nodes = immutableGraph.nodes(); //返回图中所有的节点(顺序依赖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的实现方式实际上就是将Mutable**类型的数据原样复制到没有实现Mutable**接口的类ForwardingGraph中。
- 判断是否存在环(第一个顶点和最后一个顶点相同的路径称为环)
final boolean cycle = Graphs.hasCycle(graph1);
Log.d(TAG, "graph1 has cycle: " + cycle);
输出：
graph1 has cycle: true //因为N2节点存在一条自环，如果去掉则不存在环
- 获取仅包含指定节点的生成子图：
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>]
- 获取节点的可到达列表(获取能访问到的节点结合，不单指直连边)：
Set<Integer> reachNodes = Graphs.reachableNodes(graph1, N2); //N2的可达列表
Log.d(TAG, "graph1 node: " + N2 + ", reachNodes: " + format(reachNodes));
输出：
graph1 node: 2, reachNodes: {2,4,3} //N2不存在能访问到N1的边
这里是通过从起始点N开始进行BFS遍历的结果。
- 获取图的传递闭包(如果节点A的可达列表
reachableNodes(A)包含节点B，则在节点A和节点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>]
- 获取有向图的的反转图：
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>]
- 图的遍历
//深度优先-后序
Iterable<Integer> dfs = Traverser.forGraph(graph1).depthFirstPostOrder(N1);
Log.d(TAG, "dfs traverser: " + format(dfs));
//深度优先-前序
Iterable<Integer> dfsPre =Traverser.forGraph(graph1).depthFirstPreOrder(N1);
Log.d(TAG, "dfs pre traverser: " + format(dfsPre));
//广度优先
Iterable<Integer> bfs =Traverser.forGraph(graph1).breadthFirst(N1);
Log.d(TAG, "bfs traverser: " + format(bfs));
输出：
dfs traverser: {4,3,2,1} //深度优先-后序
dfs pre traverser: {1,2,4,3} //深度优先-前序
bfs traverser: {1,2,3,4} //广度优先
- 删除节点(对应的连接边也将删除)
删除节点，或者删除边时，需要将对应的连接关系也要删除，因此又涉及到了关系结构GraphConnections，此处也重点分析一下：
//ConfigurableMutableValueGraph
//删除节点
public boolean removeNode(N node) {
checkNotNull(node, "node");
GraphConnections<N, V> connections = nodeConnections.get(node);
if (connections == null) { //查看是否有邻接点
return false;
}
//先删除自环（简单，因为不涉及其他节点）
if (allowsSelfLoops()) {
// Remove self-loop (if any) first, so we don't get CME while removing incident edges.
if (connections.removeSuccessor(node) != null) { //删除它的后继，不为null表示存在此环
connections.removePredecessor(node); //再次删除其前趋，存放的数据不一样
--edgeCount; //边数-1
}
}
//遍历其后继节点列表，并分别删除它的前趋关系
for (N successor : connections.successors()) {
nodeConnections.getWithoutCaching(successor).removePredecessor(node);
--edgeCount;
}
//因为在无向图中不区分前趋和后继，因此这里只有是有向图时才需要删除后继关系
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); //连接关系中彻底删除该节点
checkNonNegative(edgeCount);
return true;
}
//删除边
public V removeEdge(N nodeU, N nodeV) {
checkNotNull(nodeU, "nodeU");
checkNotNull(nodeV, "nodeV");
//分别获取节点U和V的连接结构
GraphConnections<N, V> connectionsU = nodeConnections.get(nodeU);
GraphConnections<N, V> connectionsV = nodeConnections.get(nodeV);
if (connectionsU == null || connectionsV == null) { //校验其连通性，有一个为null，表示结构已不成立
return null;
}
//删除U的后继
V previousValue = connectionsU.removeSuccessor(nodeV);
if (previousValue != null) { //不为null表示有连接关系
connectionsV.removePredecessor(nodeU); //则还需要删除节点V到U的前趋关系
checkNonNegative(--edgeCount);
}
return previousValue;
}
删除节点：
graph1.removeNode(N2); //删除一个节点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>}
- 构建类
Builder的from()接口只能复制其属性值，而并不会复制相应的节点和边：
//build of from()仅仅复制其属性，节点和边不会复制过来
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是一套实现方案，都是实现类ConfigurableMutableValueGraph来操作的，因此这里不再详细描述其实现。
特性：
a)顶点必须唯一,边可以不唯一; b)支持有向和无向边; c)边的定义支持权值指定; d)不支持并行边.
示例图如下:
ValueGraph测试用例图
注：ValueGraph支持Graph的全部功能，因此下面仅介绍其差异功能：
- 使用对应构建类
ValueGraphBuilder来构建ValueGraph实例：
//节点类型为Integer,边类型为String
MutableValueGraph<Integer, String> graph1 = ValueGraphBuilder.directed() //有向
.allowsSelfLoops(true) //允许自环
.expectedNodeCount(NODE_COUNT) //期望节点数
.nodeOrder(ElementOrder.<Integer>insertion()) //节点顺序
.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);
//返回图中所有的节点(顺序依赖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}
//节点顺序
graph1 nodes count:4, nodes value:{3,1,4,2}
- 获取两个节点之间的连接边：
其内部实现为：
public V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
checkNotNull(nodeU);
checkNotNull(nodeV);
//得到节点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()转换为Graph视图
asGraph()实际上是重新new了一个AbstractGraph，只是它的接口实现是调用了Graph本身的接口，因此如果修改asGraph()返回的视图的数据，其变化也会反映在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中允许并行边（即两个节点间可以有多条同向边，如：节点A和节点B可以有两条同向边：A->B: a-b-1，a-b-2），这就导致了前面介绍的使用节点作为Map的key的数据结构GraphConnections的逻辑走不下去了，因为节点不唯一了。使得设计者重新设计了另一套使用边为Key的机制来实现节点的连接关系。
为什么需要Network加入到Guava中？通过上面描述的不同点可知，Graph(ValueGraph)是通过顶点来定义边的，即两个顶点只能有一条（有向）边连接；但是在某些图中，在两个顶点之间需要有多条边连接的场景出现。比如，两个机场（对应两个节点）之间存在多趟固定航班，而这里用ValueGraph是无法描述的。
Network相对于Graphe(ValueGraph)，由于功能的差异，其接口也发生了些变化，增加了如下特殊接口：
Set<E> inEdges(N node); //node的入度边集合（不同于predecessors()，它返回的入度节点非边）
Set<E> outEdges(N node); //node的出度边集合（不同于successors()，它返回的是出度节点非边）
EndpointPair<N> incidentNodes(E edge); //边对应的两个端点
Set<E> adjacentEdges(E edge); //边的邻接边
Set<E> edgesConnecting(N nodeU, N nodeV); //两个节点的连接边集
其主要区别在于NetworkConnections的实现不同：
取消了前趋和后继的操作接口，因为操作节点已不能满足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)构建Network实例时使用）的源码，其内部相对于GraphConnections已经将出度边和入度边集合分开存放了：
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，因为前趋和后继允许有并行边，存在多个相同节点
//内部缓存了节点对应的前趋节点集
private transient Reference<Multiset<N>> predecessorsReference;
//内部缓存了节点对应的后继节点集
private transient Reference<Multiset<N>> successorsReference;
//这里使用缓存的目的是减少inEdgeMap.values()的遍历操作，在函数predecessors()中可以直接返回predecessorsReference。
private Multiset<N> predecessorsMultiset() {
Multiset<N> predecessors = getReference(predecessorsReference);
if (predecessors == null) {
//前趋就是节点入度边Map的value集合，可重复
predecessors = HashMultiset.create(inEdgeMap.values());
predecessorsReference = new SoftReference<>(predecessors);
}
return predecessors;
}
private Multiset<N> successorsMultiset() {
//...同上
}
特性：
a)边必须唯一（因为两个相同顶点间可以同时存在多条边）; b)支持有向和无向边; c)边的定义支持权值指定; d)支持并行边.
示例图如下:
NetWork测试用例图
注：Network也支持Graph的全部功能，因此下面仅介绍其差异功能：
- 使用对应构建类
NetworkBuilder来构建Network实例：
MutableNetwork<Integer, String> network1 = NetworkBuilder.directed() //有向网
.allowsParallelEdges(true) //允许并行边
.allowsSelfLoops(true) //允许自环
.nodeOrder(ElementOrder.<Integer>insertion()) //节点顺序
.edgeOrder(ElementOrder.<String>insertion()) //边顺序
.expectedNodeCount(NODE_COUNT) //期望节点数
.expectedEdgeCount(EDGE_COUNT) //期望边数
.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不同的是，它可以通过一条边来定义两个顶点，如输出所示。
- 获取边的邻接边(即边对应两个端点的邻接边集合)
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
- 获取节点的邻接边(所有包含该节点的边集合)
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}
- 获取边的邻接点(边对应的两个顶点)
EndpointPair<Integer> incidentNodes = network1.incidentNodes(E12_A);
Log.d(TAG, "network1 edge " + E12_A + " incidentNodes: " + incidentNodes);
输出：
network1 edge 1-2a incidentNodes: <1 -> 2>
示例代码中组装Iterable的元素信息的函数如下：
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用法及原理到这里基本介绍完了。后续，我们将使用上面的这些基本接口来实现《数据结构》中关于图的具体算法应用。
