@Test public void testSubgraph() { System.out.println("subgraph digraph = false"); AdjacencyList graph = new AdjacencyList(8, false); graph.addEdge(0, 2); graph.addEdge(1, 7); graph.addEdge(2, 6); graph.addEdge(7, 4); graph.addEdge(3, 4); graph.addEdge(3, 5); graph.addEdge(5, 4); int[] v = {1, 3, 7}; AdjacencyList sub = graph.subgraph(v); for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { System.out.print(sub.getWeight(i, j) + " "); } System.out.println(); } assertEquals(1.0, sub.getWeight(0, 2), 1E-10); assertEquals(1.0, sub.getWeight(2, 0), 1E-10); }
@Override public AdjacencyList subgraph(int[] vertices) { int[] v = vertices.clone(); Arrays.sort(v); AdjacencyList g = new AdjacencyList(v.length, digraph); for (int i = 0; i < v.length; i++) { Collection<Edge> edges = getEdges(v[i]); for (Edge edge : edges) { int j = edge.v1 == v[i] ? edge.v2 : edge.v1; j = Arrays.binarySearch(v, j); if (j >= 0) { g.addEdge(i, j, edge.weight); } } } return g; }
AdjacencyList implements Graph { @Override public AdjacencyList subgraph(int[] vertices) { int[] v = vertices.clone(); Arrays.sort(v); AdjacencyList g = new AdjacencyList(v.length, digraph); for (int i = 0; i < v.length; i++) { Collection<Edge> edges = getEdges(v[i]); for (Edge edge : edges) { int j = edge.v1 == v[i] ? edge.v2 : edge.v1; j = Arrays.binarySearch(v, j); if (j >= 0) { g.addEdge(i, j, edge.weight); } } } return g; } }
AdjacencyList implements Graph { @Override public AdjacencyList subgraph(int[] vertices) { int[] v = vertices.clone(); Arrays.sort(v); AdjacencyList g = new AdjacencyList(v.length, digraph); for (int i = 0; i < v.length; i++) { Collection<Edge> edges = getEdges(v[i]); for (Edge edge : edges) { int j = edge.v1 == v[i] ? edge.v2 : edge.v1; j = Arrays.binarySearch(v, j); if (j >= 0) { g.addEdge(i, j, edge.weight); } } } return g; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); }
AdjacencyList implements Graph { @Override public AdjacencyList subgraph(int[] vertices) { int[] v = vertices.clone(); Arrays.sort(v); AdjacencyList g = new AdjacencyList(v.length, digraph); for (int i = 0; i < v.length; i++) { Collection<Edge> edges = getEdges(v[i]); for (Edge edge : edges) { int j = edge.v1 == v[i] ? edge.v2 : edge.v1; j = Arrays.binarySearch(v, j); if (j >= 0) { g.addEdge(i, j, edge.weight); } } } return g; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyList setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); @Override AdjacencyList subgraph(int[] vertices); @Override SparseMatrix toMatrix(); static AdjacencyList of(SparseMatrix matrix); }
AdjacencyList implements Graph { @Override public AdjacencyList subgraph(int[] vertices) { int[] v = vertices.clone(); Arrays.sort(v); AdjacencyList g = new AdjacencyList(v.length, digraph); for (int i = 0; i < v.length; i++) { Collection<Edge> edges = getEdges(v[i]); for (Edge edge : edges) { int j = edge.v1 == v[i] ? edge.v2 : edge.v1; j = Arrays.binarySearch(v, j); if (j >= 0) { g.addEdge(i, j, edge.weight); } } } return g; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyList setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); @Override AdjacencyList subgraph(int[] vertices); @Override SparseMatrix toMatrix(); static AdjacencyList of(SparseMatrix matrix);  }