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.graphstream.graph.Graph; 035 036/** 037 * Algorithms are used to compute properties on graphs or graph elements. These 038 * properties could be a measure, color, spanning tree, etc... Algorithms are 039 * divided into two steps : 040 * 041 * <ol> 042 * <li>initialization, that initialize or reset the algorithm ;</li> 043 * <li>computation, that computes a property or updates a previous result.</li> 044 * </ol> 045 * <p> 046 * Algorithm interface aims to define algorithms that do no handle dynamics of 047 * the graph, whereas algorithms implementing the 048 * {@link org.graphstream.algorithm.DynamicAlgorithm} interface (an extended 049 * version of Algorithm) are able to handle this dynamics. 050 * </p> 051 * <p> 052 * This following is an example of an algorithm that computes max, min and 053 * average degrees of a graph: 054 * </p> 055 * <pre> 056 * public class DegreesAlgorithm implements Algorithm { 057 * Graph theGraph; 058 * int minDegree, maxDegree, avgDegree; 059 * 060 * public void init(Graph graph) { 061 * theGraph = graph; 062 * } 063 * 064 * public void compute() { 065 * avgDegree = 0; 066 * minDegree = Integer.MAX_VALUE; 067 * maxDegree = 0; 068 * 069 * for(Node n : theGraph.getEachNode() ) { 070 * int deg = n.getDegree(); 071 * 072 * minDegree = Math.min(minDegree, d); 073 * maxDegree = Math.max(maxDegree, d); 074 * avgDegree += d; 075 * } 076 * 077 * avgDegree /= theGraph.getNodeCount(); 078 * } 079 * 080 * public int getMaxDegree() { 081 * return maxDegree; 082 * } 083 * 084 * public int getMinDegree() { 085 * return minDegree; 086 * } 087 * 088 * public int getAverageDegree() { 089 * return avgDegree; 090 * } 091 * } 092 * </pre> 093 * <p> 094 * Complexity of algorithms can be specify in the documentation with the help of 095 * the "@complexity" tag. 096 * </p> 097 */ 098public interface Algorithm { 099 /** 100 * Initialization of the algorithm. This method has to be called before the 101 * {@link #compute()} method to initialize or reset the algorithm according 102 * to the new given graph. 103 * 104 * @param graph 105 * The graph this algorithm is using. 106 */ 107 void init(Graph graph); 108 109 /** 110 * Run the algorithm. The {@link #init(Graph)} method has to be called 111 * before computing. 112 * 113 * @see #init(Graph) 114 */ 115 void compute(); 116}