Package org.tweetyproject.graphs.util

Class GraphUtil

java.lang.Object
org.tweetyproject.graphs.util.GraphUtil
public abstract class GraphUtil extends Object
This abstract class contains some auxiliary methods for working with graphs.
Author:
Matthias Thimm

  • Constructor Details

    • GraphUtil

      public GraphUtil()

  • Method Details

    • pageRank

      public static Double pageRank(Graph<? extends Node> g, Node n, double dampingFactor, double precision)
      Computes the PageRank of the given node in the given graph.
      Parameters:
      g - a graph
      n - a node
      dampingFactor - the damping factor for PageRank
      precision - the precision (smaller values mean higher precision)
      Returns:
      the PageRank of the given node in the given graph.

    • hitsRank

      public static Double hitsRank(Graph<? extends Node> g, Node n, double precision, boolean getAuth)
      Computes the HITS rank of the given node in the given graph.
      Parameters:
      g - a graph
      n - a node
      precision - the precision (smaller values mean higher precision)
      getAuth - whether to use Auth (instead of Hub)
      Returns:
      the HITS rank of the given node in the given graph.

    • eigenvalues

      public static ComplexNumber[] eigenvalues(Graph<? extends Node> g)
      Computes the (real parts of the) Eigenvalues of the given graph.
      Parameters:
      g - some graph
      Returns:
      an array of double (the real parts of the Eigenvalues).

    • isIsomorphic

      public static boolean isIsomorphic(Graph<? extends Node> g1, Graph<? extends Node> g2)
      Checks whether the two graphs are isomorphic.
      Parameters:
      g1 - some graph.
      g2 - some graph.
      Returns:
      "true" iff the two graphs are isomorphic.

    • undirecteddiameter

      public static <T extends Node> int undirecteddiameter(Graph<T> g)
      * Returns the (undirected) diameter of the graph, i.e. the longest shortest path in the undirected version of the graph.
      Type Parameters:
      T - a Node
      Parameters:
      g - some graph
      Returns:
      the (undirected) diameter of the graph

    • globalclusteringcoefficient

      public static <T extends Node> double globalclusteringcoefficient(Graph<T> g)
      Returns the global clustering coefficient of the graph (if it is directed it is interpreted as an undirected version).
      Type Parameters:
      T - a Node
      Parameters:
      g - some graph
      Returns:
      the clustering coefficient

    • enumerateChordlessCircuits

      public static <T extends Node> Collection<List<T>> enumerateChordlessCircuits(Graph<T> g)
      Enumerates all chordless circuits of the given graph, i.e. all circuits a1,...,an where there is no edge connecting any ak with aj unless k=j+1 or k=j-1. The algorithm of this method is adapted from [Bisdorff, On enumerating chordless circuits in directed graphs, 2010].
      Type Parameters:
      T - a Node
      Parameters:
      g - some graph
      Returns:
      the set of chordless circuits

    • betweennessCentralityNormalised

      public static <T extends Node> Map<T,Double> betweennessCentralityNormalised(Graph<T> graph)
      Computes the normalised betweenness centrality of all nodes, i.e. the number of shortest paths going through each node. The value is normalised by subtracting the minimum number (min) of such shortest paths and dividing by (max-min).
      Type Parameters:
      T - a Node
      Parameters:
      graph - some graph
      Returns:
      a map mapping each node to its betweenness centrality.

    • isConnected

      public static <T extends Node> boolean isConnected(Graph<T> g)
      Returns "true" if the graph is (simply) connected, i.e. if there is a path from every node to each other node (ignoring edge directions).
      Type Parameters:
      T - a Node
      Parameters:
      g - some graph
      Returns:
      "true" if the graph is (simply) connected