V - Type of verticesE - Type of edgespublic class GoldbergMaximumDensitySubgraphAlgorithmNodeWeights<V extends Pair<?,Double>,E> extends GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
This variant of the algorithm assumes the density of a positive real edge and vertex weighted
graph G=(V,E) to be defined as \[\frac{\sum\limits_{e \in E} w(e) + \sum\limits_{v \in V}
w(v)}{\left|{V}\right|}\] and sets the weights of the network from
GoldbergMaximumDensitySubgraphAlgorithmBase as proposed in the above paper. For this case
the weights of the network must be chosen to be: \[c_{ij}=w(ij)\,\forall \{i,j\}\in E\]
\[c_{it}=m'+2g-d_i-2w(i)\,\forall i \in V\] \[c_{si}=m'\,\forall i \in V\] where $m'$ is such
that all weights are positive and $d_i$ is the degree of vertex $i$ and $w(v)$ is the weight of
vertex $v$.
For details see GoldbergMaximumDensitySubgraphAlgorithmBase. All the math to prove the
correctness of these weights is the same.
Because the density is per definition guaranteed to be rational, the distance of 2 possible
solutions for the maximum density can't be smaller than $\frac{1}{W(W-1)}$. This means shrinking
the binary search interval to this size, the correct solution is found. The runtime can in this
case be given by $O(M(n,n+m)\log{W})$, where $M(n,m)$ is the runtime of the internally used
MinimumSTCutAlgorithm and $W$ is the sum all edge and vertex weights from $G$.
graph, guess| Constructor and Description |
|---|
GoldbergMaximumDensitySubgraphAlgorithmNodeWeights(Graph<V,E> graph,
V s,
V t,
double epsilon)
Convenience constructor that uses PushRelabel as default MinimumSTCutAlgorithm
|
GoldbergMaximumDensitySubgraphAlgorithmNodeWeights(Graph<V,E> graph,
V s,
V t,
double epsilon,
Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor
|
| Modifier and Type | Method and Description |
|---|---|
protected double |
computeDensityDenominator(Graph<V,E> g) |
protected double |
computeDensityNumerator(Graph<V,E> g) |
protected double |
getEdgeWeightFromSourceToVertex(V v)
Getter for network weights of edges su for u in V
|
protected double |
getEdgeWeightFromVertexToSink(V v)
Getter for network weights of edges ut for u in V
|
calculateDensest, getDensitypublic GoldbergMaximumDensitySubgraphAlgorithmNodeWeights(Graph<V,E> graph, V s, V t, double epsilon, Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
graph - input for computations - additional source vertext - additional target vertexepsilon - to use for internal computationalgFactory - function to construct the subalgorithmpublic GoldbergMaximumDensitySubgraphAlgorithmNodeWeights(Graph<V,E> graph, V s, V t, double epsilon)
graph - input for computations - additional source vertext - additional target vertexepsilon - to use for internal computationprotected double computeDensityNumerator(Graph<V,E> g)
computeDensityNumerator in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>g - the graph to compute the numerator density fromprotected double computeDensityDenominator(Graph<V,E> g)
computeDensityDenominator in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>g - the graph to compute the denominator density fromprotected double getEdgeWeightFromSourceToVertex(V v)
GoldbergMaximumDensitySubgraphAlgorithmBasegetEdgeWeightFromSourceToVertex in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>v - of Vprotected double getEdgeWeightFromVertexToSink(V v)
GoldbergMaximumDensitySubgraphAlgorithmBasegetEdgeWeightFromVertexToSink in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>v - of VCopyright © 2019. All rights reserved.