@Test public void testBroadFirstSearch() { clearAndTest(); graph.addEdge(1, 2, null, true); graph.addEdge(2, 3, null, true); graph.addEdge(3, 4, null, true); graph.addEdge(4, 5, null, true); graph.addEdge(1, 6, null, true); List<Integer> visit = null; try { visit = graph.broadFirstSearch(); assertEquals(visit.size(), 6); assertTrue(visit.get(0) == 1); assertTrue(visit.get(1) == 2); assertTrue(visit.get(2) == 6); assertTrue(visit.get(3) == 3); assertTrue(visit.get(4) == 4); assertTrue(visit.get(5) == 5); } catch (Exception e) { assertTrue(false); } graph.addEdge(7, 8, null, true); try { visit = graph.broadFirstSearch(); assertEquals(visit.size(), 8); assertTrue(visit.get(0) == 1); assertTrue(visit.get(1) == 7); assertTrue(visit.get(2) == 2); assertTrue(visit.get(3) == 6); assertTrue(visit.get(4) == 8); assertTrue(visit.get(5) == 3); assertTrue(visit.get(6) == 4); assertTrue(visit.get(7) == 5); } catch (Exception e) { assertTrue(false); } graph.addEdge(8, 7, null, true); try { visit = graph.broadFirstSearch(); assertTrue(false); } catch (Exception e) { assertTrue(true); } }
public List<VK> broadFirstSearch() throws Exception { List<VK> visit = new ArrayList<>(); Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); synchronized (this) { for (VK key : getStartVertex()) { q.add(key); hasVisited.add(key); visit.add(key); } while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); visit.add(postKey); } } } if (visit.size() != getVertexNumber()) { throw new Exception("Broad first search can't search complete."); } } return visit; }
Graph { public List<VK> broadFirstSearch() throws Exception { List<VK> visit = new ArrayList<>(); Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); synchronized (this) { for (VK key : getStartVertex()) { q.add(key); hasVisited.add(key); visit.add(key); } while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); visit.add(postKey); } } } if (visit.size() != getVertexNumber()) { throw new Exception("Broad first search can't search complete."); } } return visit; } }
Graph { public List<VK> broadFirstSearch() throws Exception { List<VK> visit = new ArrayList<>(); Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); synchronized (this) { for (VK key : getStartVertex()) { q.add(key); hasVisited.add(key); visit.add(key); } while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); visit.add(postKey); } } } if (visit.size() != getVertexNumber()) { throw new Exception("Broad first search can't search complete."); } } return visit; } Graph(); }
Graph { public List<VK> broadFirstSearch() throws Exception { List<VK> visit = new ArrayList<>(); Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); synchronized (this) { for (VK key : getStartVertex()) { q.add(key); hasVisited.add(key); visit.add(key); } while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); visit.add(postKey); } } } if (visit.size() != getVertexNumber()) { throw new Exception("Broad first search can't search complete."); } } return visit; } 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 List<VK> broadFirstSearch() throws Exception { List<VK> visit = new ArrayList<>(); Queue<VK> q = new LinkedList<>(); Set<VK> hasVisited = new HashSet<>(); synchronized (this) { for (VK key : getStartVertex()) { q.add(key); hasVisited.add(key); visit.add(key); } while (!q.isEmpty()) { VK key = q.poll(); for (VK postKey : getPostNode(key)) { if (!hasVisited.contains(postKey)) { q.add(postKey); hasVisited.add(postKey); visit.add(postKey); } } } if (visit.size() != getVertexNumber()) { throw new Exception("Broad first search can't search complete."); } } return visit; } 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();  }