Package smile.graph

Class AdjacencyList

java.lang.Object
smile.graph.AdjacencyList
All Implemented Interfaces:
Serializable, Graph
public class AdjacencyList extends Object implements Graph, Serializable
An adjacency list representation of a graph. Multigraph is supported.
See Also:

  • Nested Class Summary

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

    Graph.Edge

  • Constructor Summary

    Constructors
    Constructor
    Description
    AdjacencyList(int n)
    Constructor.
    AdjacencyList(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.
    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.
    static AdjacencyList
    of(SparseMatrix matrix)
    Converts the sparse matrix to a graph.
    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.
    AdjacencyList
    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.
    AdjacencyList
    subgraph(int[] vertices)
    Returns a subgraph containing all given vertices.
    SparseMatrix
    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

    • AdjacencyList

      public AdjacencyList(int n)
      Constructor.
      Parameters:
      n - the number of vertices.

    • AdjacencyList

      public AdjacencyList(int n, boolean digraph)
      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 AdjacencyList 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 Collection<Graph.Edge> getEdges()
      Description copied from interface: Graph
      Returns the edges in this graph.
      Specified by:
      getEdges in interface Graph
      Returns:
      the edges.

    • getEdges

      public Collection<Graph.Edge> 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 Collection<Graph.Edge> 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.

    • addEdge

      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.

    • addEdge

      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.

    • subgraph

      public AdjacencyList subgraph(int[] vertices)
      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

    • toMatrix

      public SparseMatrix 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.

    • of

      public static AdjacencyList of(SparseMatrix matrix)
      Converts the sparse matrix to a graph. If the matrix is structurally symmetric, it is taken as the adjacency matrix of an undirected graph, where two vertices i and j are connected if the (i, j)-th entry of the matrix is nonzero. Rectangular or structurally asymmetric matrices are treated as bipartite graphs.
      Parameters:
      matrix - the matrix representation of the graph.
      Returns:
      a graph