Package smile.graph
Class Graph
java.lang.Object
smile.graph.Graph
- Direct Known Subclasses:
AdjacencyList
,AdjacencyMatrix
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
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionaddEdge
(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.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.addEdges
(Collection<Graph.Edge> edges) Adds a set of edges to the graph.int[]
Returns the approximate solution to TSP with the arbitrary insertion heuristic.int[][]
bfcc()
Returns the connected components by breadth-first search.void
bfs
(VertexVisitor visitor) BFS search on graph and performs some operation defined in visitor on each vertex during traveling.int[]
bfsort()
Topological sort digraph by breadth-first search of graph.int[]
Returns the approximate solution to TSP with Christofides algorithm.int[][]
dfcc()
Returns the connected components by depth-first search.void
dfs
(VertexVisitor visitor) DFS search on graph and performs some operation defined in visitor on each vertex during traveling.int[]
dfsort()
Reverse topological sort digraph by depth-first search of graph.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.double[]
dijkstra
(int s, boolean weighted) Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.dot()
Returns the graphic representation in Graphviz dot format.Returns the graphic representation in Graphviz dot format.int[]
Returns the approximate solution to TSP with the farthest insertion heuristic.abstract void
forEachEdge
(int vertex, ArrayElementConsumer action) Performs an action for each edge of a vertex.int
getDegree
(int vertex) Returns the degree of the specified vertex.double
getDistance
(int source, int target) Returns the distance between two vertices.abstract List
<Graph.Edge> getEdges
(int vertex) Returns the edges from the specified vertex.abstract int
getInDegree
(int vertex) Returns the in-degree of the specified vertex.abstract int
getOutDegree
(int vertex) Returns the out-degree of the specified vertex.double
getPathDistance
(int[] path) Returns the distance of path.abstract int
Returns the number of vertices.abstract double
getWeight
(int source, int target) Returns the weight assigned to a given edge.abstract 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.int[]
heldKarp()
Returns the optimal TSP tour with Held-Karp algorithm.boolean
Return true if the graph is directed.abstract DoubleStream
mapEdges
(int vertex, ArrayElementFunction mapper) Returns a stream consisting of the results of applying the given function to the edge weights of a vertex.int[]
Returns the approximate solution to TSP with the nearest insertion heuristic.double
opt2
(int[] tour, int maxIter) Improves an existing TSP tour with the 2-opt heuristic.double
prim
(List<Graph.Edge> mst) Returns the minimum spanning tree (MST) for a weighted undirected graph by Prim's algorithm.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.removeEdges
(Collection<Graph.Edge> edges) Removes a set of edges from the graph.abstract Graph
setWeight
(int source, int target, double weight) Sets the weight assigned to a given edge.abstract Graph
subgraph
(int[] vertices) Returns a subgraph containing all given vertices.abstract IMatrix
toMatrix()
Returns the (dense or sparse) matrix representation of the graph.int[]
tsp()
Returns the optimal travelling salesman problem (TSP) tour with branch and bound algorithm.abstract void
updateEdges
(int vertex, ArrayElementFunction mapper) Updates the edge weights of a vertex.
-
Constructor Details
-
Graph
public Graph(boolean digraph) Constructor.- Parameters:
digraph
- true if this is a directed graph.
-
-
Method Details
-
isDigraph
public boolean isDigraph()Return true if the graph is directed.- Returns:
- true if the graph is directed.
-
dot
Returns the graphic representation in Graphviz dot format. Try http://viz-js.com/ to visualize the returned string.- Returns:
- the graphic representation in Graphviz dot format.
-
dot
Returns the graphic representation in Graphviz dot format. Try http://viz-js.com/ to visualize the returned string.- Parameters:
name
- the graph name.label
- the label of nodes.- Returns:
- the graphic representation in Graphviz dot format.
-
toMatrix
Returns the (dense or sparse) matrix representation of the graph.- Returns:
- the matrix representation of the graph.
-
subgraph
Returns a subgraph containing all given vertices.- Parameters:
vertices
- the vertices to be included in subgraph.- Returns:
- a subgraph containing all given vertices
-
getVertexCount
public abstract int getVertexCount()Returns the number of vertices.- Returns:
- the number of vertices.
-
hasEdge
public abstract 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
public abstract double getWeight(int source, int target) Returns the weight assigned to a given edge. Unweighted graphs always return 1.0. If the edge doesn't exist, it returns zero. For minimization problems such as TSP, use getDistance as it will return infinity instead.- Parameters:
source
- the id of source vertex of the edge.target
- the id of target vertex of the edge.- Returns:
- the edge weight
-
getDistance
public double getDistance(int source, int target) Returns the distance between two vertices.- Parameters:
source
- the id of source vertex of the edge.target
- the id of target vertex of the edge.- Returns:
- the distance between two vertices.
-
setWeight
Sets the weight assigned to a given edge.- 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
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.
-
forEachEdge
Performs an action for each edge of a vertex.- Parameters:
vertex
- the vertex id.action
- a non-interfering action to perform on the edges.
-
mapEdges
Returns a stream consisting of the results of applying the given function to the edge weights of a vertex.- Parameters:
vertex
- the vertex id.mapper
- a non-interfering, stateless function to map each edge weight of a vertex.- Returns:
- the stream of the new values of edge weights.
-
updateEdges
Updates the edge weights of a vertex.- Parameters:
vertex
- the vertex id.mapper
- a function to map each edge weight to new value.
-
addEdge
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
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.
-
addEdges
Adds a set of edges to the graph.- Parameters:
edges
- edges to be added to this graph.
-
removeEdges
Removes a set of edges from the graph.- Parameters:
edges
- edges to be removed from this graph.
-
removeEdge
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.
-
getDegree
public 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
public abstract int getInDegree(int vertex) 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.- Parameters:
vertex
- the id of vertex.- Returns:
- the degree of the specified vertex.
-
getOutDegree
public abstract int getOutDegree(int vertex) 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.- Parameters:
vertex
- the id of vertex.- Returns:
- the degree of the specified vertex.
-
dfsort
public int[] dfsort()Reverse topological sort digraph by depth-first search of graph.- Returns:
- the vertices in the reverse topological order.
-
dfcc
public int[][] dfcc()Returns the connected components by depth-first search.- Returns:
- a two-dimensional 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:
visitor
- the visitor functor.
-
bfsort
public int[] bfsort()Topological sort digraph by breadth-first search of graph.- Returns:
- the vertices in the topological order.
-
bfcc
public int[][] bfcc()Returns the connected components by breadth-first search.- Returns:
- a two-dimensional 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:
visitor
- the visitor functor.
-
dijkstra
public 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 distance to all vertices from the source.
-
dijkstra
public double[] dijkstra(int s, boolean weighted) Calculate the shortest path from a source to all other vertices in the graph by Dijkstra algorithm.- Parameters:
s
- The source vertex.weighted
- Ignore edge weights if false.- Returns:
- The distance to all vertices from the source. If weighted is false, it is the length of the shortest path to other vertices.
-
dijkstra
public double[][] dijkstra()Calculates the all pair shortest-path by Dijkstra algorithm.- Returns:
- the length of shortest-path between vertices.
-
prim
Returns the minimum spanning tree (MST) for a weighted undirected graph by Prim's algorithm. MST is a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.- Parameters:
mst
- an output container to hold edges in the MST.- Returns:
- the cost of minimum spanning tree.
-
getPathDistance
public double getPathDistance(int[] path) Returns the distance of path.- Parameters:
path
- the path.- Returns:
- the distance.
-
tsp
public int[] tsp()Returns the optimal travelling salesman problem (TSP) tour with branch and bound algorithm.- Returns:
- the optimal TSP tour.
-
heldKarp
public int[] heldKarp()Returns the optimal TSP tour with Held-Karp algorithm. It works on graph up to 31 vertices.- Returns:
- the optimal TSP tour.
-
nearestInsertion
public int[] nearestInsertion()Returns the approximate solution to TSP with the nearest insertion heuristic.- Returns:
- the approximate solution to TSP.
-
farthestInsertion
public int[] farthestInsertion()Returns the approximate solution to TSP with the farthest insertion heuristic.- Returns:
- the approximate solution to TSP.
-
arbitraryInsertion
public int[] arbitraryInsertion()Returns the approximate solution to TSP with the arbitrary insertion heuristic.- Returns:
- the approximate solution to TSP.
-
opt2
public double opt2(int[] tour, int maxIter) Improves an existing TSP tour with the 2-opt heuristic. The method reconnects pairs of non-adjacent edges until no more pairs can be swapped to further improve the solution.- Parameters:
tour
- an existing TSP tour. It may be revised with a better tour of lower cost.maxIter
- the maximum number of iterations of the outer loop.- Returns:
- the improved tour cost.
-
christofides
public int[] christofides()Returns the approximate solution to TSP with Christofides algorithm.- Returns:
- the approximate solution to TSP.
-