001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm; 033 034import org.apache.commons.math3.linear.Array2DRowRealMatrix; 035import org.apache.commons.math3.linear.EigenDecomposition; 036import org.apache.commons.math3.linear.RealMatrix; 037import org.graphstream.algorithm.generator.BarabasiAlbertGenerator; 038import org.graphstream.graph.Edge; 039import org.graphstream.graph.Graph; 040import org.graphstream.graph.implementations.AdjacencyListGraph; 041 042public class Spectrum implements Algorithm { 043 044 public static enum EigenValuesAlgorithm { 045 POWER_ITERATION, INVERSE_ITERATION 046 } 047 048 protected EigenValuesAlgorithm mode; 049 protected Graph graph; 050 protected EigenDecomposition decomposition; 051 052 /* 053 * (non-Javadoc) 054 * 055 * @see 056 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 057 */ 058 public void init(Graph graph) { 059 if (graph == null) 060 throw new NullPointerException(); 061 062 this.graph = graph; 063 } 064 065 /* 066 * (non-Javadoc) 067 * 068 * @see org.graphstream.algorithm.Algorithm#compute() 069 */ 070 public void compute() { 071 if (graph == null) 072 throw new NotInitializedException(this); 073 074 int m = graph.getNodeCount(); 075 RealMatrix a = new Array2DRowRealMatrix(m, m); 076 Edge e; 077 078 for (int idx1 = 0; idx1 < m; idx1++) 079 for (int idx2 = 0; idx2 < m; idx2++) { 080 e = graph.getNode(idx1).getEdgeToward(idx2); 081 a.setEntry(idx1, idx2, e != null ? 1 : 0); 082 } 083 084 decomposition = new EigenDecomposition(a, 0); 085 } 086 087 public int getEigenvaluesCount() { 088 double[] values = decomposition.getRealEigenvalues(); 089 return values == null ? 0 : values.length; 090 } 091 092 public double getEigenvalue(int i) { 093 return decomposition.getRealEigenvalue(i); 094 } 095 096 public double[] getEigenvalues() { 097 return decomposition.getRealEigenvalues(); 098 } 099 100 public double[] getEigenvector(int i) { 101 return decomposition.getEigenvector(i).toArray(); 102 } 103 104 public double getLargestEigenvalue() { 105 double[] values = decomposition.getRealEigenvalues(); 106 double max = Double.MIN_VALUE; 107 108 if (values != null) 109 for (int i = 0; i < values.length; i++) 110 max = Math.max(max, values[i]); 111 112 return max; 113 } 114 115 public static void main(String... args) { 116 Graph g = new AdjacencyListGraph("g"); 117 118 BarabasiAlbertGenerator gen = new BarabasiAlbertGenerator(); 119 gen.addSink(g); 120 gen.begin(); 121 for (int i = 0; i < 200; i++) 122 gen.nextEvents(); 123 gen.end(); 124 125 Spectrum spectrum = new Spectrum(); 126 spectrum.init(g); 127 spectrum.compute(); 128 129 } 130}