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}