@Test public void testToMatrix() { System.out.println("toMatrix 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); SparseMatrix matrix = graph.toMatrix(); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { System.out.print(matrix.get(i, j) + " "); } System.out.println(); } assertEquals(1.0, matrix.get(0, 2), 1E-10); assertEquals(1.0, matrix.get(1, 7), 1E-10); assertEquals(1.0, matrix.get(2, 6), 1E-10); assertEquals(1.0, matrix.get(7, 4), 1E-10); assertEquals(1.0, matrix.get(3, 4), 1E-10); assertEquals(1.0, matrix.get(3, 5), 1E-10); assertEquals(1.0, matrix.get(5, 4), 1E-10); assertEquals(1.0, matrix.get(2, 0), 1E-10); assertEquals(1.0, matrix.get(7, 1), 1E-10); assertEquals(1.0, matrix.get(6, 2), 1E-10); assertEquals(1.0, matrix.get(4, 7), 1E-10); assertEquals(1.0, matrix.get(4, 3), 1E-10); assertEquals(1.0, matrix.get(5, 3), 1E-10); assertEquals(1.0, matrix.get(4, 5), 1E-10); }
@Override public SparseMatrix toMatrix() { int size = 0; int[] colSize = new int[n]; int[] colIndex = new int[n + 1]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; size += edges.size(); colSize[i] = edges.size(); } for (int i = 0; i < n; i++) { colIndex[i + 1] = colIndex[i] + colSize[i]; } int[] rowIndex = new int[size]; double[] x = new double[size]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; int ni = edges.size(); int[] index = new int[ni]; double[] w = new double[ni]; int j = 0; for (Edge edge : edges) { index[j] = edge.v1 == i ? edge.v2 : edge.v1; w[j++] = edge.weight; } QuickSort.sort(index, w); int k = colIndex[i]; for (j = 0; j < ni; j++, k++) { rowIndex[k] = index[j]; x[k] = w[j]; } } return new SparseMatrix(n, n, x, rowIndex, colIndex).transpose(); }
AdjacencyList implements Graph { @Override public SparseMatrix toMatrix() { int size = 0; int[] colSize = new int[n]; int[] colIndex = new int[n + 1]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; size += edges.size(); colSize[i] = edges.size(); } for (int i = 0; i < n; i++) { colIndex[i + 1] = colIndex[i] + colSize[i]; } int[] rowIndex = new int[size]; double[] x = new double[size]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; int ni = edges.size(); int[] index = new int[ni]; double[] w = new double[ni]; int j = 0; for (Edge edge : edges) { index[j] = edge.v1 == i ? edge.v2 : edge.v1; w[j++] = edge.weight; } QuickSort.sort(index, w); int k = colIndex[i]; for (j = 0; j < ni; j++, k++) { rowIndex[k] = index[j]; x[k] = w[j]; } } return new SparseMatrix(n, n, x, rowIndex, colIndex).transpose(); } }
AdjacencyList implements Graph { @Override public SparseMatrix toMatrix() { int size = 0; int[] colSize = new int[n]; int[] colIndex = new int[n + 1]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; size += edges.size(); colSize[i] = edges.size(); } for (int i = 0; i < n; i++) { colIndex[i + 1] = colIndex[i] + colSize[i]; } int[] rowIndex = new int[size]; double[] x = new double[size]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; int ni = edges.size(); int[] index = new int[ni]; double[] w = new double[ni]; int j = 0; for (Edge edge : edges) { index[j] = edge.v1 == i ? edge.v2 : edge.v1; w[j++] = edge.weight; } QuickSort.sort(index, w); int k = colIndex[i]; for (j = 0; j < ni; j++, k++) { rowIndex[k] = index[j]; x[k] = w[j]; } } return new SparseMatrix(n, n, x, rowIndex, colIndex).transpose(); } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); }
AdjacencyList implements Graph { @Override public SparseMatrix toMatrix() { int size = 0; int[] colSize = new int[n]; int[] colIndex = new int[n + 1]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; size += edges.size(); colSize[i] = edges.size(); } for (int i = 0; i < n; i++) { colIndex[i + 1] = colIndex[i] + colSize[i]; } int[] rowIndex = new int[size]; double[] x = new double[size]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; int ni = edges.size(); int[] index = new int[ni]; double[] w = new double[ni]; int j = 0; for (Edge edge : edges) { index[j] = edge.v1 == i ? edge.v2 : edge.v1; w[j++] = edge.weight; } QuickSort.sort(index, w); int k = colIndex[i]; for (j = 0; j < ni; j++, k++) { rowIndex[k] = index[j]; x[k] = w[j]; } } return new SparseMatrix(n, n, x, rowIndex, colIndex).transpose(); } 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 SparseMatrix toMatrix() { int size = 0; int[] colSize = new int[n]; int[] colIndex = new int[n + 1]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; size += edges.size(); colSize[i] = edges.size(); } for (int i = 0; i < n; i++) { colIndex[i + 1] = colIndex[i] + colSize[i]; } int[] rowIndex = new int[size]; double[] x = new double[size]; for (int i = 0; i < n; i++) { LinkedList<Edge> edges = graph[i]; int ni = edges.size(); int[] index = new int[ni]; double[] w = new double[ni]; int j = 0; for (Edge edge : edges) { index[j] = edge.v1 == i ? edge.v2 : edge.v1; w[j++] = edge.weight; } QuickSort.sort(index, w); int k = colIndex[i]; for (j = 0; j < ni; j++, k++) { rowIndex[k] = index[j]; x[k] = w[j]; } } return new SparseMatrix(n, n, x, rowIndex, colIndex).transpose(); } 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);  }