Package net.sf.tweety.graphs.util

Class GraphUtil

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

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>> archiveHITSAuthRank
      For archiving HITS rank values.
      private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>> archiveHITSHubRank  
      private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>>> archivePageRank
      For archiving page rank values.

    • Constructor Summary

      Constructors 
      Constructor Description
      GraphUtil()  

    • Method Summary

      Modifier and Type Method Description
      static <T extends Node>
      java.util.Map<T,​java.lang.Double>      		 betweennessCentralityNormalised​(Graph<T> graph)
      Computes the normalised betweenness centrality of all nodes, i.e.
      static ComplexNumber[] eigenvalues​(Graph<? extends Node> g)
      Computes the (real parts of the) Eigenvalues of the given graph.
      static <T extends Node>
      java.util.Collection<java.util.List<T>>      		 enumerateChordlessCircuits​(Graph<T> g)
      Enumerates all chordless circuits of the given graph, i.e.
      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).
      static java.lang.Double hitsRank​(Graph<? extends Node> g, Node n, double precision, boolean getAuth)
      Computes the HITS rank of the given node in the given graph.
      static boolean isIsomorphic​(Graph<? extends Node> g1, Graph<? extends Node> g2)
      Checks whether the two graphs are isomorphic.
      static java.lang.Double pageRank​(Graph<? extends Node> g, Node n, double dampingFactor, double precision)
      Computes the PageRank of the given node in the given graph.
      static <T extends Node>
      int      		 undirecteddiameter​(Graph<T> g)
      Returns the (undirected) diameter of the graph, i.e.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • archivePageRank

        private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>>> archivePageRank
        For archiving page rank values.

      • archiveHITSAuthRank

        private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>> archiveHITSAuthRank
        For archiving HITS rank values.

      • archiveHITSHubRank

        private static java.util.Map<Graph<? extends Node>,​java.util.Map<java.lang.Double,​java.util.Map<Node,​java.lang.Double>>> archiveHITSHubRank

    • Constructor Detail

      • GraphUtil

        public GraphUtil()

    • Method Detail

      • pageRank

        public static java.lang.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 java.lang.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.
        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).
        Parameters:
        g - some graph
        Returns:
        the clustering coefficient

      • enumerateChordlessCircuits

        public static <T extends Node> java.util.Collection<java.util.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].
        Parameters:
        g - some graph
        Returns:
        the set of chordless circuits

      • betweennessCentralityNormalised

        public static <T extends Node> java.util.Map<T,​java.lang.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).
        Parameters:
        graph - some graph
        Returns:
        a map mapping each node to its betweenness centrality.