@Test public void testIsConnected() { clearAndTest(); assertTrue(graph.isConnected()); graph.addVertex(1, null); assertTrue(graph.isConnected()); graph.addEdge(1, 2, null, true); graph.addEdge(2, 3, null, true); graph.addEdge(3, 4, null, true); assertTrue(graph.isConnected()); graph.addEdge(5, 6, null, true); assertFalse(graph.isConnected()); }
public synchronized boolean isConnected() { Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); Iterator<Map.Entry<VK, VD>> iter = vertices.entrySet().iterator(); if (!iter.hasNext()) { return true; } Map.Entry<VK, VD> entry = iter.next(); VK startKey = entry.getKey(); q.add(startKey); hasVisited.add(startKey); while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); } } for (VK preKey : getPreNode(key)) { if (!hasVisited.contains(preKey)) { q.add(preKey); hasVisited.add(preKey); } } } return hasVisited.size() == getVertexNumber(); }
Graph { public synchronized boolean isConnected() { Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); Iterator<Map.Entry<VK, VD>> iter = vertices.entrySet().iterator(); if (!iter.hasNext()) { return true; } Map.Entry<VK, VD> entry = iter.next(); VK startKey = entry.getKey(); q.add(startKey); hasVisited.add(startKey); while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); } } for (VK preKey : getPreNode(key)) { if (!hasVisited.contains(preKey)) { q.add(preKey); hasVisited.add(preKey); } } } return hasVisited.size() == getVertexNumber(); } }
Graph { public synchronized boolean isConnected() { Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); Iterator<Map.Entry<VK, VD>> iter = vertices.entrySet().iterator(); if (!iter.hasNext()) { return true; } Map.Entry<VK, VD> entry = iter.next(); VK startKey = entry.getKey(); q.add(startKey); hasVisited.add(startKey); while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); } } for (VK preKey : getPreNode(key)) { if (!hasVisited.contains(preKey)) { q.add(preKey); hasVisited.add(preKey); } } } return hasVisited.size() == getVertexNumber(); } Graph(); }
Graph { public synchronized boolean isConnected() { Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); Iterator<Map.Entry<VK, VD>> iter = vertices.entrySet().iterator(); if (!iter.hasNext()) { return true; } Map.Entry<VK, VD> entry = iter.next(); VK startKey = entry.getKey(); q.add(startKey); hasVisited.add(startKey); while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); } } for (VK preKey : getPreNode(key)) { if (!hasVisited.contains(preKey)) { q.add(preKey); hasVisited.add(preKey); } } } return hasVisited.size() == getVertexNumber(); } Graph(); synchronized void addVertex(VK key, VD vertex); synchronized void addVertexIfAbsent(VK key, VD vertex); synchronized void removeVertex(VK key); boolean addEdge(VK start, VK end); boolean addEdge(VK start, VK end, boolean createVertex); boolean addEdge(VK start, VK end, ED edge); synchronized boolean addEdge(VK start, VK end, ED edge, boolean createVertex); synchronized void removeEdge(VK start, VK end); boolean forceRefreshPreEdges(Collection<VK> addStartKeys,
                                      VK endKey); synchronized boolean forceRefreshPreEdges(Collection<VK> addStartKeys,
                                                   VK endKey,
                                                   boolean createVertex); boolean addRemoveMultiEdges(Collection<VK> removeStartKeys,
                                     Collection<VK> addStartKeys,
                                     VK endKey); synchronized boolean addRemoveMultiEdges(Collection<VK> removeStartKeys,
                                                  Collection<VK> addStartKeys,
                                                  VK endKey,
                                                  boolean createVertex); synchronized void clear(); synchronized boolean containsVertex(VK key); synchronized VD getVertex(VK key); Map<VK, VD> getVertices(); synchronized boolean containsEdge(VK startKey, VK endKey); Map<VK, Map<VK, ED>> getEdges(); synchronized ED getEdge(VK startKey, VK endKey); synchronized int getEdgeNumber(); int getVertexNumber(); synchronized Collection<VK> getStartVertex(); synchronized Collection<VK> getEndVertex(); Set<VK> getPreNode(VK key); Map<VK, ED> getPreNodeAttr(VK key); Set<VK> getPostNode(VK key); Map<VK, ED> getPostNodeAttr(VK key); synchronized int getIndegree(VK key); synchronized int getOutdegree(VK key); boolean hasCycle(); List<VK> broadFirstSearch(); List<VK> depthFirstSearch(); List<VK> topologicalSort(); synchronized boolean isConnected(); }
Graph { public synchronized boolean isConnected() { Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); Iterator<Map.Entry<VK, VD>> iter = vertices.entrySet().iterator(); if (!iter.hasNext()) { return true; } Map.Entry<VK, VD> entry = iter.next(); VK startKey = entry.getKey(); q.add(startKey); hasVisited.add(startKey); while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); } } for (VK preKey : getPreNode(key)) { if (!hasVisited.contains(preKey)) { q.add(preKey); hasVisited.add(preKey); } } } return hasVisited.size() == getVertexNumber(); } Graph(); synchronized void addVertex(VK key, VD vertex); synchronized void addVertexIfAbsent(VK key, VD vertex); synchronized void removeVertex(VK key); boolean addEdge(VK start, VK end); boolean addEdge(VK start, VK end, boolean createVertex); boolean addEdge(VK start, VK end, ED edge); synchronized boolean addEdge(VK start, VK end, ED edge, boolean createVertex); synchronized void removeEdge(VK start, VK end); boolean forceRefreshPreEdges(Collection<VK> addStartKeys,
                                      VK endKey); synchronized boolean forceRefreshPreEdges(Collection<VK> addStartKeys,
                                                   VK endKey,
                                                   boolean createVertex); boolean addRemoveMultiEdges(Collection<VK> removeStartKeys,
                                     Collection<VK> addStartKeys,
                                     VK endKey); synchronized boolean addRemoveMultiEdges(Collection<VK> removeStartKeys,
                                                  Collection<VK> addStartKeys,
                                                  VK endKey,
                                                  boolean createVertex); synchronized void clear(); synchronized boolean containsVertex(VK key); synchronized VD getVertex(VK key); Map<VK, VD> getVertices(); synchronized boolean containsEdge(VK startKey, VK endKey); Map<VK, Map<VK, ED>> getEdges(); synchronized ED getEdge(VK startKey, VK endKey); synchronized int getEdgeNumber(); int getVertexNumber(); synchronized Collection<VK> getStartVertex(); synchronized Collection<VK> getEndVertex(); Set<VK> getPreNode(VK key); Map<VK, ED> getPreNodeAttr(VK key); Set<VK> getPostNode(VK key); Map<VK, ED> getPostNodeAttr(VK key); synchronized int getIndegree(VK key); synchronized int getOutdegree(VK key); boolean hasCycle(); List<VK> broadFirstSearch(); List<VK> depthFirstSearch(); List<VK> topologicalSort(); synchronized boolean isConnected();  }