Package smile.graph

java.lang.Object
All Implemented Interfaces:
`Serializable`, `Graph`

public class AdjacencyMatrix extends Object implements Graph, Serializable
An adjacency matrix representation of a graph. Only simple graph is supported.

## Nested classes/interfaces inherited from interface smile.graph.Graph

`Graph.Edge`
• ## Constructor Summary

Constructors
Constructor
Description
`AdjacencyMatrix(int n)`
Constructor.
```AdjacencyMatrix(int n, boolean digraph)```
Constructor.
• ## Method Summary

Modifier and Type
Method
Description
`void`
```addEdge(int source, int target)```
Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
`void`
```addEdge(int source, int target, double weight)```
Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
`int[][]`
`bfs()`
Breadth-first search connected components of graph.
`void`
`bfs(Visitor visitor)`
BFS search on graph and performs some operation defined in visitor on each vertex during traveling.
`int[][]`
`dfs()`
Depth-first search connected components of graph.
`void`
`dfs(Visitor visitor)`
DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
`double[]`
`dijkstra(int s)`
Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
`double[]`
```dijkstra(int s, boolean weighted)```
Calculates the shortest path by Dijkstra algorithm.
`int`
`getDegree(int vertex)`
Returns the degree of the specified vertex.
`Graph.Edge`
```getEdge(int source, int target)```
Returns an edge connecting source vertex to target vertex if such edge exist in this graph.
`Collection<Graph.Edge>`
`getEdges()`
Returns the edges in this graph.
`Collection<Graph.Edge>`
`getEdges(int vertex)`
Returns the edges from the specified vertex.
`Collection<Graph.Edge>`
```getEdges(int source, int target)```
Returns the edges connecting source vertex to target vertex if such vertices exist in this graph.
`int`
`getIndegree(int vertex)`
Returns the in-degree of the specified vertex.
`int`
`getNumVertices()`
Returns the number of vertices.
`int`
`getOutdegree(int vertex)`
Returns the out-degree of the specified vertex.
`double`
```getWeight(int source, int target)```
Returns the weight assigned to a given edge.
`boolean`
```hasEdge(int source, int target)```
Returns true if and only if this graph contains an edge going from the source vertex to the target vertex.
`double`
```pushRelabel(double[][] flow, int source, int sink)```
Push-relabel algorithm for maximum flow.
`void`
```removeEdge(int source, int target)```
In a simple graph, removes and returns the edge going from the specified source vertex to the specified target vertex.
`void`
`removeEdge(Graph.Edge edge)`
Removes the specified edge from the graph.
`void`
`removeEdges(Collection<Graph.Edge> edges)`
Removes a set of edges from the graph.
`AdjacencyMatrix`
```setWeight(int source, int target, double weight)```
Sets the weight assigned to a given edge.
`int[]`
`sortbfs()`
Topological sort digraph by breadth-first search of graph.
`int[]`
`sortdfs()`
Reverse topological sort digraph by depth-first search of graph.
`AdjacencyMatrix`
`subgraph(int[] vertices)`
Returns a subgraph containing all given vertices.
`double[][]`
`toArray()`
`Matrix`
`toMatrix()`
Returns the (dense or sparse) matrix representation of the graph.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### Methods inherited from interface smile.graph.Graph

`dijkstra`
• ## Constructor Details

Constructor.
Parameters:
`n` - the number of vertices.

Constructor.
Parameters:
`n` - the number of vertices.
`digraph` - true if this is a directed graph.
• ## Method Details

• ### getNumVertices

public int getNumVertices()
Description copied from interface: `Graph`
Returns the number of vertices.
Specified by:
`getNumVertices` in interface `Graph`
Returns:
the number of vertices.
• ### hasEdge

public boolean hasEdge(int source, int target)
Description copied from interface: `Graph`
Returns true if and only if this graph contains an edge going from the source vertex to the target vertex. In undirected graphs the same result is obtained when source and target are inverted.
Specified by:
`hasEdge` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
Returns:
true if this graph contains the specified edge.
• ### getWeight

public double getWeight(int source, int target)
Description copied from interface: `Graph`
Returns the weight assigned to a given edge. Unweighted graphs always return 1.0. For multi-graph, the return value is ill-defined.
Specified by:
`getWeight` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
Returns:
the edge weight
• ### setWeight

public AdjacencyMatrix setWeight(int source, int target, double weight)
Description copied from interface: `Graph`
Sets the weight assigned to a given edge. For multi-graph, the operation is ill-defined.
Specified by:
`setWeight` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
`weight` - the edge weight
Returns:
this graph.
• ### getEdges

public  getEdges()
Description copied from interface: `Graph`
Returns the edges in this graph.
Specified by:
`getEdges` in interface `Graph`
Returns:
the edges.
• ### getEdges

public  getEdges(int vertex)
Description copied from interface: `Graph`
Returns the edges from the specified vertex. If no edges are touching the specified vertex returns an empty set.
Specified by:
`getEdges` in interface `Graph`
Parameters:
`vertex` - the id of vertex for which a set of touching edges is to be returned.
Returns:
the edges touching the specified vertex.
• ### getEdges

public  getEdges(int source, int target)
Description copied from interface: `Graph`
Returns the edges connecting source vertex to target vertex if such vertices exist in this graph. If both vertices exist but no edges found, returns an empty set.

In undirected graphs, some of the returned edges may have their source and target vertices in the opposite order.

Specified by:
`getEdges` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
Returns:
the edges connecting source vertex to target vertex.
• ### getEdge

public Graph.Edge getEdge(int source, int target)
Description copied from interface: `Graph`
Returns an edge connecting source vertex to target vertex if such edge exist in this graph. Otherwise, returns ` null`.

In undirected graphs, the returned edge may have its source and target vertices in the opposite order.

For multi-graph, the return value is ill-defined.

Specified by:
`getEdge` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
Returns:
an edge connecting source vertex to target vertex if there are connected. Otherwise, null.

public void addEdge(int source, int target)
Description copied from interface: `Graph`
Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
Specified by:
`addEdge` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.

public void addEdge(int source, int target, double weight)
Description copied from interface: `Graph`
Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
Specified by:
`addEdge` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
`weight` - the weight of edge.
• ### removeEdges

public void removeEdges(Collection<Graph.Edge> edges)
Description copied from interface: `Graph`
Removes a set of edges from the graph.
Specified by:
`removeEdges` in interface `Graph`
Parameters:
`edges` - edges to be removed from this graph.
• ### removeEdge

public void removeEdge(int source, int target)
Description copied from interface: `Graph`
In a simple graph, removes and returns the edge going from the specified source vertex to the specified target vertex.
Specified by:
`removeEdge` in interface `Graph`
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
• ### removeEdge

public void removeEdge(Graph.Edge edge)
Description copied from interface: `Graph`
Removes the specified edge from the graph. Returns true if the graph contained the specified edge.
Specified by:
`removeEdge` in interface `Graph`
Parameters:
`edge` - edge to be removed from this graph, if present.
• ### getDegree

public int getDegree(int vertex)
Description copied from interface: `Graph`
Returns the degree of the specified vertex. A degree of a vertex in an undirected graph is the number of edges touching that vertex.
Specified by:
`getDegree` in interface `Graph`
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• ### getIndegree

public int getIndegree(int vertex)
Description copied from interface: `Graph`
Returns the in-degree of the specified vertex. An in-degree of a vertex in a directed graph is the number of edges head to that vertex.
Specified by:
`getIndegree` in interface `Graph`
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• ### getOutdegree

public int getOutdegree(int vertex)
Description copied from interface: `Graph`
Returns the out-degree of the specified vertex. An out-degree of a vertex in a directed graph is the number of edges from that vertex.
Specified by:
`getOutdegree` in interface `Graph`
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• ### sortdfs

public int[] sortdfs()
Description copied from interface: `Graph`
Reverse topological sort digraph by depth-first search of graph.
Specified by:
`sortdfs` in interface `Graph`
Returns:
an array of vertex IDs in the reverse topological order.
• ### dfs

public int[][] dfs()
Description copied from interface: `Graph`
Depth-first search connected components of graph.
Specified by:
`dfs` in interface `Graph`
Returns:
a two-dimensional array of which each row is the vertices in the same connected component.
• ### dfs

public void dfs(Visitor visitor)
Description copied from interface: `Graph`
DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
Specified by:
`dfs` in interface `Graph`
Parameters:
`visitor` - the visitor functor.
• ### sortbfs

public int[] sortbfs()
Description copied from interface: `Graph`
Topological sort digraph by breadth-first search of graph.
Specified by:
`sortbfs` in interface `Graph`
Returns:
an array of vertex IDs in the topological order.
• ### bfs

public int[][] bfs()
Description copied from interface: `Graph`
Breadth-first search connected components of graph.
Specified by:
`bfs` in interface `Graph`
Returns:
a two-dimensional array of which each row is the vertices in the same connected component.
• ### bfs

public void bfs(Visitor visitor)
Description copied from interface: `Graph`
BFS search on graph and performs some operation defined in visitor on each vertex during traveling.
Specified by:
`bfs` in interface `Graph`
Parameters:
`visitor` - the visitor functor.
• ### dijkstra

public double[] dijkstra(int s)
Description copied from interface: `Graph`
Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.
Specified by:
`dijkstra` in interface `Graph`
Parameters:
`s` - the source vertex.
Returns:
the length of shortest path to other vertices.
• ### dijkstra

public double[] dijkstra(int s, boolean weighted)
Calculates the shortest path by Dijkstra algorithm.
Parameters:
`s` - The source vertex.
`weighted` - True to calculate weighted path. Otherwise, the edge weights will be ignored.
Returns:
The distance to all vertices from the source.
• ### subgraph

Description copied from interface: `Graph`
Returns a subgraph containing all given vertices.
Specified by:
`subgraph` in interface `Graph`
Parameters:
`vertices` - the vertices to be included in subgraph.
Returns:
a subgraph containing all given vertices
• ### toArray

public double[][] toArray()
Returns:
• ### pushRelabel

public double pushRelabel(double[][] flow, int source, int sink)
Push-relabel algorithm for maximum flow.
Parameters:
`flow` - the flow network.
`source` - the source vertex.
`sink` - the sink vertex.
Returns:
the maximum flow between source and sink.
• ### toMatrix

public Matrix toMatrix()
Description copied from interface: `Graph`
Returns the (dense or sparse) matrix representation of the graph.
Specified by:
`toMatrix` in interface `Graph`
Returns:
the matrix representation of the graph.