Package net.sf.tweety.graphs.util
Class GraphUtil
- java.lang.Object
-
- net.sf.tweety.graphs.util.GraphUtil
-
public abstract class GraphUtil extends java.lang.Object
This abstract class contains some auxiliary methods for working with graphs.- Author:
- Matthias Thimm
-
-
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>
doubleglobalclusteringcoefficient(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>
intundirecteddiameter(Graph<T> g)
Returns the (undirected) diameter of the graph, i.e.
-
-
-
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 graphn
- a nodedampingFactor
- the damping factor for PageRankprecision
- 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 graphn
- a nodeprecision
- 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.
-
-