|
1 package org.jgrapht.experimental;
2
3 import java.util.*;
4
5 import org.jgrapht.*;
6
7
8 public final class GraphTests<V, E>
9 {
10
11
13 private GraphTests()
14 {
15 }
16
17
19 public static <V, E> boolean isEmpty(Graph<V, E> g)
20 {
21 return g.edgeSet().isEmpty();
22 }
23
24 public static <V, E> boolean isComplete(Graph<V, E> g)
25 {
26 int n = g.vertexSet().size();
27 return g.edgeSet().size()
28 == (n * (n - 1) / 2);
29 }
30
31 public static <V, E> boolean isConnected(Graph<V, E> g)
32 {
33 int numVertices = g.vertexSet().size();
34 int numEdges = g.edgeSet().size();
35
36 if (numEdges < (numVertices - 1)) {
37 return false;
38 }
39 if (
40 (numVertices < 2)
41 || (numEdges > ((numVertices - 1) * (numVertices - 2) / 2))) {
42 return true;
43 }
44
45 Set<V> known = new HashSet<V>();
46 LinkedList<V> queue = new LinkedList<V>();
47 V v = g.vertexSet().iterator().next();
48
49 queue.add(v); known.add(v);
51
52 while (!queue.isEmpty()) {
53 v = queue.removeFirst();
54 for (
55 Iterator<V> it = Graphs.neighborListOf(g, v).iterator();
56 it.hasNext();) {
57 v = it.next();
58 if (!known.contains(v)) {
59 known.add(v);
60 queue.add(v);
61 }
62 }
63 }
64 return known.size() == numVertices;
65 }
66
67 public static <V, E> boolean isTree(Graph<V, E> g)
68 {
69 return
70 isConnected(g)
71 && (g.edgeSet().size() == (g.vertexSet().size() - 1));
72 }
73
74 public static <V, E> boolean isBipartite(Graph<V, E> g)
75 {
76 if (
77 (4 * g.edgeSet().size())
78 > (g.vertexSet().size() * g.vertexSet().size())) {
79 return false;
80 }
81 if (isEmpty(g)) {
82 return true;
83 }
84
85 Set<V> unknown = new HashSet<V>(g.vertexSet());
86 LinkedList<V> queue = new LinkedList<V>();
87 V v = unknown.iterator().next();
88 Set<V> odd = new HashSet<V>();
89
90 queue.add(v);
91
92 while (!unknown.isEmpty()) {
93 if (queue.isEmpty()) {
94 queue.add(unknown.iterator().next());
95 }
96
97 v = queue.removeFirst();
98 unknown.remove(v);
99
100 for (
101 Iterator<V> it = Graphs.neighborListOf(g, v).iterator();
102 it.hasNext();) {
103 V n = it.next();
104 if (unknown.contains(n)) {
105 queue.add(n);
106 if (!odd.contains(v)) {
107 odd.add(n);
108 }
109 } else if (!(odd.contains(v) ^ odd.contains(n))) {
110 return false;
111 }
112 }
113 }
114 return true;
115 }
116 }
117 |
Popular Tags |
Java API By Example, From Geeks To Geeks.