Class AdjacencyListGraph

java.lang.Object
jdg.graph.AdjacencyListGraph
public class AdjacencyListGraph extends Object
Pointer based implementation of an Adjacency List Representation of a graph. The graph is assumed to be undirected (with no multiple edges and loops).
Author:
Luca Castelli Aleardi (Ecole Polytechnique, INF562)

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    HashMap<Edge,Integer>
    edges
    the edges of the graph, stored in a hash map as pairs of nodes
    ArrayList<Node>
    neighbors
    for each node, store the list of neighbors

  • Constructor Summary

    Constructors
    Constructor
    Description
    AdjacencyListGraph()
    Initialize an empty graph

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(Node a, Node b)
    Add an edge between two nodes
    void
    addNode(Node v)
    Add a new node to the graph.
    boolean
    adjacent(Node a, Node b)
    Check whether two nodes are adjacent (slow implementation, without hash maps)
    int
    degree(Node v)
    Return the degree of a node
    List<Node>
    findConnectedComponent(Node v)
    Compute and return the connected component containing the vertex v It performs a DFS visit of the graph starting from vertex v
    int
    getEdgeIndex(Node a, Node b)
    Return the index of the edge having extremities (a, b) if any.
    int[]
    getIndices()
    Return an array storing all vertex indices, according to the order of vertices
    Collection<Node>
    getNeighbors(Node v)
     
    Node
    getNode(int index)
    Return the node given its index (between [0..n-1])
    String
    info()
    Return a string containing informations and parameters of the graph
    boolean
    isConnected()
    Check whether the graph is connected Remark: the graph is assumed to be undirected
    int
    maxVertexIndex()
    Compute the maximum vertex index of the graph (a non negative number) Remark: vertices are allowed to have indices between 0..infty This is required when graphs are dynamic: vertices can be removed
    int
    minVertexIndex()
    Compute the minimum vertex index of the graph (a non negative number) Remark: vertices are allowed to have indices between 0..infty This is required when graphs are dynamic: vertices can be removed
    void
    removeEdge(Node a, Node b)
    Remove the edge between two nodes
    void
    removeNode(Node v)
     
    int
    sizeEdges()
    Return the number of arcs Remark: arcs are not counted twice
    int
    sizeVertices()
    Return the number of nodes

    Methods inherited from class java.lang.Object

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

  • Field Details

    • neighbors

      public ArrayList<Node> neighbors
      for each node, store the list of neighbors

    • edges

      public HashMap<Edge,Integer> edges
      the edges of the graph, stored in a hash map as pairs of nodes

  • Constructor Details

    • AdjacencyListGraph

      public AdjacencyListGraph()
      Initialize an empty graph

  • Method Details

    • addNode

      public void addNode(Node v)
      Add a new node to the graph.
      Remark:
      -) if the label of 'v' is not defined, add the node (without any check)
      -) otherwise, before adding the node the function check whether it already exists (expensive test).

    • getEdgeIndex

      public int getEdgeIndex(Node a, Node b)
      Return the index of the edge having extremities (a, b) if any.
      Returns:
      the index of edge (a, b).
      Return -1 if the edge (a, b) does not exist in the graph.

    • getNode

      public Node getNode(int index)
      Return the node given its index (between [0..n-1])

    • removeNode

      public void removeNode(Node v)

    • addEdge

      public void addEdge(Node a, Node b)
      Add an edge between two nodes

    • removeEdge

      public void removeEdge(Node a, Node b)
      Remove the edge between two nodes

    • adjacent

      public boolean adjacent(Node a, Node b)
      Check whether two nodes are adjacent (slow implementation, without hash maps)

    • degree

      public int degree(Node v)
      Return the degree of a node
      Returns:
      the degree (number of neighbors) of the input node. If the node is not defined (null) return 0.

    • getNeighbors

      public Collection<Node> getNeighbors(Node v)

    • sizeVertices

      public int sizeVertices()
      Return the number of nodes

    • sizeEdges

      public int sizeEdges()
      Return the number of arcs Remark: arcs are not counted twice

    • getIndices

      public int[] getIndices()
      Return an array storing all vertex indices, according to the order of vertices

    • findConnectedComponent

      public List<Node> findConnectedComponent(Node v)
      Compute and return the connected component containing the vertex v It performs a DFS visit of the graph starting from vertex v

      Remark: the graph is assumed to be undirected

      Parameters:
      v - the starting node
      Returns:
      the list of nodes lying in the same connected component of v

    • isConnected

      public boolean isConnected()
      Check whether the graph is connected Remark: the graph is assumed to be undirected

    • minVertexIndex

      public int minVertexIndex()
      Compute the minimum vertex index of the graph (a non negative number) Remark: vertices are allowed to have indices between 0..infty This is required when graphs are dynamic: vertices can be removed

    • maxVertexIndex

      public int maxVertexIndex()
      Compute the maximum vertex index of the graph (a non negative number) Remark: vertices are allowed to have indices between 0..infty This is required when graphs are dynamic: vertices can be removed

    • info

      public String info()
      Return a string containing informations and parameters of the graph