Package ons.util

Class WeightedGraph

java.lang.Object
ons.util.WeightedGraph
All Implemented Interfaces:
java.io.Serializable
Direct Known Subclasses:
WeightedGraphLPCandidates
public class WeightedGraph
extends java.lang.Object
implements java.io.Serializable
A weighted graph associates a label (weight) with every edge in the graph. If a pair of nodes has weight equal to zero, it means the edge between them doesn't exist.
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected double[][] edges  
    protected int numNodes  

  • Constructor Summary

    Constructors 
    Constructor Description
    WeightedGraph​(int n)
    Creates a new WeightedGraph object with no edges,
    WeightedGraph​(WeightedGraph g)
    Creates a new WeightedGraph object, based on an already existing weighted graph.

  • Method Summary

    Modifier and Type Method Description
    void addEdge​(int source, int target, double w)
    Creates a new edge within the graph, which requires its two vertexes and its weight.
    void addNode()
    Creates a new node in graph.
    double getAverageClusteringCoefficient()
    Retrieves the average clustering coefficient of this graph.
    double getAveragePathLength()
    Retrieves the Average path length of this graph.
    double getClusteringCoefficient​(int node)
    Retrieves the clustering coefficient of this node.
    double getGlobalClusteringCoefficient()
    Retrieves the global clustering coefficient of this graph.
    double getGraphDiameter()
    Retrieves the diameter of this graph.
    double getGraphDiameter_mod​(int k)
    Retornas a maior rota das k-5 menores
    double getMaxClusteringCoefficient()
    Retrieves the max local clustering coefficient in this graph.
    double getMaxPossiblePathWeight​(int k)
    Retrieves the max possible wheight by 'k' hops
    double getSumClusteringCoefficient()
    Retrieves the sum of all local clustering coefficient in this graph.
    double getWeight​(int source, int target)
    Retrieves the weight of a given edge on the graph.
    boolean isEdge​(int source, int target)
    Says whether or not a given pair of nodes has an edge between them.
    int[] neighbors​(int vertex)
    Retrieves the neighbors of a given vertex.
    int[] neighbors2​(int vertex)
    Retrieves the neighbors of a given vertex.
    void removeEdge​(int source, int target)
    Removes a given edge from the graph by simply attributing zero to its source and target coordinates within the matrix of edges.
    void removeNode​(int node)
    Remove node in graph
    void removeNodeEdge​(int node)
    Remode all edges node
    void setWeight​(int source, int target, double w)
    Sets a determined weight to a given edge on the graph.
    int size()
    Retrieves the size of the graph, i.e., the amount of vertexes it has.
    java.lang.String toString()
    Prints all information related to the weighted graph.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • numNodes

      protected int numNodes

    • edges

      protected double[][] edges

  • Constructor Details

    • WeightedGraph

      public WeightedGraph​(int n)
      Creates a new WeightedGraph object with no edges,
      Parameters:
      n - number of nodes the new graph will have

    • WeightedGraph

      public WeightedGraph​(WeightedGraph g)
      Creates a new WeightedGraph object, based on an already existing weighted graph.
      Parameters:
      g - the graph that will be copied into the new one

  • Method Details

    • size

      public int size()
      Retrieves the size of the graph, i.e., the amount of vertexes it has.
      Returns:
      integer with the quantity of nodes in the graph

    • addEdge

      public void addEdge​(int source, int target, double w)
      Creates a new edge within the graph, which requires its two vertexes and its weight.
      Parameters:
      source - the edge's source node
      target - the edge's destination node
      w - the value of the edge's weight

    • isEdge

      public boolean isEdge​(int source, int target)
      Says whether or not a given pair of nodes has an edge between them.
      Parameters:
      source - the source node
      target - the destination node
      Returns:
      true if the edge exists, or false otherwise

    • removeEdge

      public void removeEdge​(int source, int target)
      Removes a given edge from the graph by simply attributing zero to its source and target coordinates within the matrix of edges.
      Parameters:
      source - the edge's source node
      target - the edge's destination node

    • getWeight

      public double getWeight​(int source, int target)
      Retrieves the weight of a given edge on the graph.
      Parameters:
      source - the edge's source node
      target - the edge's destination node
      Returns:
      the value of the edge's weight

    • setWeight

      public void setWeight​(int source, int target, double w)
      Sets a determined weight to a given edge on the graph.
      Parameters:
      source - the edge's source node
      target - the edge's destination node
      w - the value of the weight

    • neighbors

      public int[] neighbors​(int vertex)
      Retrieves the neighbors of a given vertex. The vertices that are reachable by this vertex
      Parameters:
      vertex - index of the vertex within the matrix of edges
      Returns:
      list with indexes of the vertex's neighbors

    • neighbors2

      public int[] neighbors2​(int vertex)
      Retrieves the neighbors of a given vertex. The vertices that reach this vertex
      Parameters:
      vertex - index of the vertex within the matrix of edges
      Returns:
      list with indexes of the vertex's neighbors

    • toString

      public java.lang.String toString()
      Prints all information related to the weighted graph. For each vertex, shows the vertexes is is adjacent to and the weight of each edge.
      Overrides:
      toString in class java.lang.Object
      Returns:
      string containing the edges of each vertex

    • removeNodeEdge

      public void removeNodeEdge​(int node)
      Remode all edges node
      Parameters:
      node - the node

    • removeNode

      public void removeNode​(int node)
      Remove node in graph
      Parameters:
      node - the node

    • addNode

      public void addNode()
      Creates a new node in graph.

    • getGraphDiameter

      public double getGraphDiameter()
      Retrieves the diameter of this graph.
      Returns:
      the longest of all the calculated shortest paths in a network

    • getGraphDiameter_mod

      public double getGraphDiameter_mod​(int k)
      Retornas a maior rota das k-5 menores
      Returns:
      a maior rota das k-5 menores

    • getClusteringCoefficient

      public double getClusteringCoefficient​(int node)
      Retrieves the clustering coefficient of this node. The clustering coefficient of a node is the ratio of existing links connecting a node's neighbors to each other to the maximum possible number of such links.
      Parameters:
      node - the node
      Returns:
      the clustering coefficient

    • getMaxClusteringCoefficient

      public double getMaxClusteringCoefficient()
      Retrieves the max local clustering coefficient in this graph.
      Returns:
      the max local clustering coefficient

    • getSumClusteringCoefficient

      public double getSumClusteringCoefficient()
      Retrieves the sum of all local clustering coefficient in this graph.
      Returns:
      the sum of all local clustering coefficient

    • getAverageClusteringCoefficient

      public double getAverageClusteringCoefficient()
      Retrieves the average clustering coefficient of this graph.
      Returns:
      the average clustering coefficient

    • getGlobalClusteringCoefficient

      public double getGlobalClusteringCoefficient()
      Retrieves the global clustering coefficient of this graph.
      Returns:
      the global clustering coefficient

    • getAveragePathLength

      public double getAveragePathLength()
      Retrieves the Average path length of this graph. Average path length is calculated by finding the shortest path between all pairs of nodes, adding them up, and then dividing by the total number of pairs.
      Returns:
      the average path length of this graph

    • getMaxPossiblePathWeight

      public double getMaxPossiblePathWeight​(int k)
      Retrieves the max possible wheight by 'k' hops
      Parameters:
      k - the k of YensKSP algorithm
      Returns:
      the max possible weight