BarabasiAlbert.java

Go to the documentation of this file.

/*
    Synthia, a data structure generator
    Copyright (C) 2019-2020 Laboratoire d'informatique formelle
    Université du Québec à Chicoutimi, Canada
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.
 
    You should have received a copy of the GNU Lesser General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package examples.graphs;
 
import ca.uqac.lif.synthia.Picker;
import ca.uqac.lif.synthia.Reactive;
import ca.uqac.lif.synthia.random.RandomBoolean;
import ca.uqac.lif.synthia.random.RandomInteger;
import ca.uqac.lif.synthia.tree.GraphPicker;
import ca.uqac.lif.synthia.tree.GraphRenderer;
import ca.uqac.lif.synthia.tree.IntegerNodePicker;
import ca.uqac.lif.synthia.tree.Node;
import ca.uqac.lif.synthia.util.AsInt;
import ca.uqac.lif.synthia.util.Tick;
import static examples.util.Utilities.colorGradient;
 
/**
 * Generates a graph following the
 * <a href="https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model">Barabási–Albert
 * model</a>. Such a graph is generated by first picking a number of vertices.
 * For each new vertex <i>n</i>' added to the graph, an edge is added to
 * an existing node <i>n</i> with probability <i>d<sub>n</sub></i>/<i>D</i>,
 * where <i>d<sub>n</sub></i> is the current degree of <i>n</i> and <i>D</i> is
 * the sum of the degrees of all pre-existing vertices.
 * <p>
 * The resulting graph has the property of being <em>scale-free</em>: it
 * contains few vertices with high degree, and many vertices with low degree.
 * An example of a graph generated by this program is the following:
 * <p>
 * <img src="./doc-files/graphs/Graph.png" alt="Graph" />
 * <p>
 * In the source code, this graph is merely printed to the console in the DOT
 * format of the <a href="https://graphviz.org">Graphviz</a> graph rendering
 * tool. 
 * @author Sylvain Hallé
 * @ingroup Examples
 */
public class BarabasiAlbert<T> extends GraphPicker<T>
{
    public static void main(String[] args)
    {
        BarabasiAlbert<Integer> generator = new BarabasiAlbert<Integer>(
                new IntegerNodePicker(new AsInt(new Tick(0, 1))), new RandomInteger(15, 100), new RandomBoolean());
        Node<Integer> root = generator.pick();
        
        /* Draw. We cannot show the graph, but the following instructions render it as
           a Graphviz input file. We tweak the default settings for a better display. */
        GraphRenderer<Integer> gr = new GraphRenderer<Integer>(false) {
            public String getLabel(Node<Integer> n) { return ""; }
            public String getColor(Node<Integer> n) { return colorGradient((float) n.getChildren().size() / generator.getMaxDegree()); }
        }.setNodeString("[style=\"filled\",width=0.1,height=0.1,shape=\"circle\"]");
        gr.printToDot(System.out, root);
    }
    
    protected Reactive<Float,Boolean> m_coin;
    
    public BarabasiAlbert(Picker<Node<T>> node_picker, Picker<Integer> size, Reactive<Float,Boolean> coin)
    {
        super(node_picker, size);
        m_coin = coin;
    }
    
    @Override
    public Node<T> pick()
    {
        /* The graph starts with two connected nodes. */
        Node<T> start_node1 = m_nodePicker.pick();
        Node<T> start_node2 = m_nodePicker.pick();
        connect(start_node1, start_node2);
        m_nodes.add(start_node1);
        m_nodes.add(start_node2);
        
        /* Add nodes until the desired size is reached. */
        int sum_kj = 2, size = m_size.pick();
        while (m_nodes.size() < size)
        {
            Node<T> new_n = m_nodePicker.pick();
            m_nodes.add(new_n);
            int added = 0;
            for (Node<T> n : m_nodes)
            {
                int k_i = n.getChildren().size();
                m_coin.tell((float) k_i / (float) sum_kj);
                if (m_coin.pick())
                {
                    connect(new_n, n);
                    added++;
                }
            }
            sum_kj += 2 * added;
        }
        return start_node1;
    }
 
    @Override
    public Picker<Node<T>> duplicate(boolean with_state)
    {
        // Don't care for this example.
        return null;
    }
}