org.openimaj.math.graph.algorithm

Class CharikarDensestSubgraph<V,E>

java.lang.Object

org.openimaj.math.graph.algorithm.CharikarDensestSubgraph<V,E>

Type Parameters:

V - type of vertex

E - type of edge

public class CharikarDensestSubgraph<V,E>
extends Object

Implementation of Charikar's greedy Densest-subgraph algorithm for unweighted, undirected graphs.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Field Summary

Fields

Modifier and Type	Field and Description
protected org.jgrapht.graph.UndirectedSubgraph<V,E>	bestSubGraph
protected org.jgrapht.UndirectedGraph<V,E>	graph
protected org.jgrapht.util.FibonacciHeap<V>	heap

Constructor Summary

Constructors

Constructor and Description
CharikarDensestSubgraph(org.jgrapht.UndirectedGraph<V,E> graph) Compute the densest subgraph of a graph.

Method Summary

Modifier and Type	Method and Description
protected void	calculateDensestSubgraph()
static double	calculateDensity(org.jgrapht.Graph<?,?> g) Calculate the density of the graph as the number of edges divided by the number of vertices
org.jgrapht.graph.UndirectedSubgraph<V,E>	getDensestSubgraph()
protected V	getMinDegreeVertex(org.jgrapht.UndirectedGraph<V,E> graph)
protected V	getMinDegreeVertexBruteForce(org.jgrapht.UndirectedGraph<V,E> graph)

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected org.jgrapht.UndirectedGraph<V,E> graph

bestSubGraph

protected org.jgrapht.graph.UndirectedSubgraph<V,E> bestSubGraph

heap

protected org.jgrapht.util.FibonacciHeap<V> heap

Constructor Detail

CharikarDensestSubgraph

public CharikarDensestSubgraph(org.jgrapht.UndirectedGraph<V,E> graph)

Compute the densest subgraph of a graph.

Parameters:

graph - the graph.

Method Detail

getMinDegreeVertexBruteForce

protected V getMinDegreeVertexBruteForce(org.jgrapht.UndirectedGraph<V,E> graph)

getMinDegreeVertex

protected V getMinDegreeVertex(org.jgrapht.UndirectedGraph<V,E> graph)

calculateDensestSubgraph

protected void calculateDensestSubgraph()

calculateDensity

public static double calculateDensity(org.jgrapht.Graph<?,?> g)

Calculate the density of the graph as the number of edges divided by the number of vertices

Parameters:

g - the graph

Returns:

the density

getDensestSubgraph

public org.jgrapht.graph.UndirectedSubgraph<V,E> getDensestSubgraph()

Returns:

The densest subgraph