smile.graph

## Interface Graph

• All Known Implementing Classes:
AdjacencyList, AdjacencyMatrix

`public interface Graph`
A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. The edges may be directed (asymmetric) or undirected (symmetric). A graph is a weighted graph if a number (weight) is assigned to each edge. Such weights might represent, for example, costs, lengths or capacities, etc. depending on the problem.
• ### Nested Class Summary

Nested Classes
Modifier and Type Interface and Description
`static class ` `Graph.Edge`
Graph edge.
• ### Method Summary

All Methods
Modifier and Type Method and 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 vistor)`
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 vistor)`
DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
`default double[][]` `dijkstra()`
Calculates the all pair shortest path by Dijkstra algorithm.
`double[]` `dijkstra(int s)`
Calculate the shortest path from a source to all other vertices in the graph 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.
`java.util.Collection<Graph.Edge>` `getEdges()`
Returns a set of the edges contained in this graph.
`java.util.Collection<Graph.Edge>` `getEdges(int vertex)`
Returns a set of all edges from the specified vertex.
`java.util.Collection<Graph.Edge>` ```getEdges(int source, int target)```
Returns a set of all 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 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.
`void` `removeEdge(Graph.Edge edge)`
Removes the specified edge from the graph.* Returns true if the graph contained the specified edge.
`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` `removeEdges(java.util.Collection<Graph.Edge> edges)`
Removes a set of edges from the graph.
`Graph` ```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.
`Graph` `subgraph(int[] vertices)`
Returns a subgraph containing all given vertices.
`DMatrix` `toMatrix()`
Returns the (dense or sparse) matrix representation of the graph.
• ### Method Detail

• #### getNumVertices

`int getNumVertices()`
Returns the number vertices.
• #### hasEdge

```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. In undirected graphs the same result is obtained when source and target are inverted.
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

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

```Graph setWeight(int source,
int target,
double weight)```
Sets the weight assigned to a given edge. For multi-graph, the operation is ill-defined.
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
`weight` - the edge weight
• #### getEdges

`java.util.Collection<Graph.Edge> getEdges()`
Returns a set of the edges contained in this graph.
• #### getEdges

`java.util.Collection<Graph.Edge> getEdges(int vertex)`
Returns a set of all edges from the specified vertex. If no edges are touching the specified vertex returns an empty set.
Parameters:
`vertex` - the id of vertex for which a set of touching edges is to be returned.
Returns:
a set of all edges touching the specified vertex.
• #### getEdges

```java.util.Collection<Graph.Edge> getEdges(int source,
int target)```
Returns a set of all 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.

Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
Returns:
a set of all edges connecting source vertex to target vertex.
• #### getEdge

```Graph.Edge getEdge(int source,
int target)```
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.

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.
• #### addEdge

```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.
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
• #### addEdge

```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.
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
• #### removeEdges

`void removeEdges(java.util.Collection<Graph.Edge> edges)`
Removes a set of edges from the graph.
Parameters:
`edges` - edges to be removed from this graph.
• #### removeEdge

```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.
Parameters:
`source` - the id of source vertex of the edge.
`target` - the id of target vertex of the edge.
• #### removeEdge

`void removeEdge(Graph.Edge edge)`
Removes the specified edge from the graph.* Returns true if the graph contained the specified edge.
Parameters:
`edge` - edge to be removed from this graph, if present.
• #### getDegree

`int getDegree(int vertex)`
Returns the degree of the specified vertex. A degree of a vertex in an undirected graph is the number of edges touching that vertex.
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• #### getIndegree

`int getIndegree(int vertex)`
Returns the in-degree of the specified vertex. A in-degree of a vertex in an directed graph is the number of edges head to that vertex.
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• #### getOutdegree

`int getOutdegree(int vertex)`
Returns the out-degree of the specified vertex. A out-degree of a vertex in an directed graph is the number of edges from that vertex.
Parameters:
`vertex` - the id of vertex.
Returns:
the degree of the specified vertex.
• #### sortdfs

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

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

`void dfs(Visitor vistor)`
DFS search on graph and performs some operation defined in visitor on each vertex during traveling.
Parameters:
`vistor` - the visitor functor.
• #### sortbfs

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

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

`void bfs(Visitor vistor)`
BFS search on graph and performs some operation defined in visitor on each vertex during traveling.
Parameters:
`vistor` - the visitor functor.
• #### subgraph

`Graph subgraph(int[] vertices)`
Returns a subgraph containing all given vertices.
Parameters:
`vertices` - the vertices to be included in subgraph.
Returns:
a subgraph containing all given vertices
• #### dijkstra

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

`default double[][] dijkstra()`
Calculates the all pair shortest path by Dijkstra algorithm.
Returns:
the length of shortest path between vertices.
• #### toMatrix

`DMatrix toMatrix()`
Returns the (dense or sparse) matrix representation of the graph.