Package 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

Method Summary
Modifier and TypeMethodDescriptionvoid
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()
Breadthfirst search connected components of graph.void
BFS search on graph and performs some operation defined in visitor on each vertex during traveling.int[][]
dfs()
Depthfirst search connected components of graph.void
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.getEdge
(int source, int target) Returns an edge connecting source vertex to target vertex if such edge exist in this graph.getEdges()
Returns the edges in this graph.getEdges
(int vertex) Returns the edges from the specified vertex.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 indegree of the specified vertex.int
Returns the number of vertices.int
getOutdegree
(int vertex) Returns the outdegree 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
(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.setWeight
(int source, int target, double weight) Sets the weight assigned to a given edge.int[]
sortbfs()
Topological sort digraph by breadthfirst search of graph.int[]
sortdfs()
Reverse topological sort digraph by depthfirst search of graph.subgraph
(int[] vertices) Returns a subgraph containing all given vertices.toMatrix()
Returns the (dense or sparse) matrix representation of the graph.

Method Details

getNumVertices
int getNumVertices()Returns the number of vertices. Returns:
 the number of 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 multigraph, the return value is illdefined. Parameters:
source
 the id of source vertex of the edge.target
 the id of target vertex of the edge. Returns:
 the edge weight

setWeight
Sets the weight assigned to a given edge. For multigraph, the operation is illdefined. 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
Collection<Graph.Edge> getEdges()Returns the edges in this graph. Returns:
 the edges.

getEdges
Returns the 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:
 the edges touching the specified vertex.

getEdges
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.
 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
Returns an edge connecting source vertex to target vertex if such edge exist in this graph. Otherwise, returnsnull
.In undirected graphs, the returned edge may have its source and target vertices in the opposite order.
For multigraph, the return value is illdefined.
 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.weight
 the weight of edge.

removeEdges
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
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 indegree of the specified vertex. An indegree of a vertex in a 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 outdegree of the specified vertex. An outdegree of a vertex in a 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 depthfirst search of graph. Returns:
 an array of vertex IDs in the reverse topological order.

dfs
int[][] dfs()Depthfirst search connected components of graph. Returns:
 a twodimensional array of which each row is the vertices in the same connected component.

dfs
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 breadthfirst search of graph. Returns:
 an array of vertex IDs in the topological order.

bfs
int[][] bfs()Breadthfirst search connected components of graph. Returns:
 a twodimensional array of which each row is the vertices in the same connected component.

bfs
BFS search on graph and performs some operation defined in visitor on each vertex during traveling. Parameters:
vistor
 the visitor functor.

subgraph
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
IMatrix toMatrix()Returns the (dense or sparse) matrix representation of the graph. Returns:
 the matrix representation of the graph.
