Java Universal Network/Graph Framework / Discussion / Open Discussion: Two DAGs side by side

Hi Tom & Joshua,

Thanks for your time. I carefully went through the MinimumSpanningTreeDemo and created a proof-of-concetp demo (which will be attached below). What I found out is that MinimumSpanningForest2 seems not to be able to handle DirectedSparseGraph, at least, the spanning tree output is not right. Note that my observation may be incorrect.

The source code is listed below. Your comments (suggestions) would be very helpful to me.

Vincent Y. Shen

/*
* Copyright (c) 2003, the JUNG Project and the Regents of the University of
* California All rights reserved.
*
* This software is open-source under the BSD license; see either "license.txt"
* or http://jung.sourceforge.net/license.txt for a description.
*
*/

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BorderFactory;
import javax.swing.JApplet;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;

import org.apache.commons.collections15.Transformer;
import org.apache.commons.collections15.functors.ConstantTransformer;

import edu.uci.ics.jung.algorithms.layout.KKLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.layout.StaticLayout;
import edu.uci.ics.jung.algorithms.layout.TreeLayout;
import edu.uci.ics.jung.algorithms.shortestpath.MinimumSpanningForest2;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Forest;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseForest;
import edu.uci.ics.jung.graph.SparseTree;
import edu.uci.ics.jung.visualization.DefaultVisualizationModel;
import edu.uci.ics.jung.visualization.GraphZoomScrollPane;
import edu.uci.ics.jung.visualization.VisualizationModel;
import edu.uci.ics.jung.visualization.VisualizationViewer;
import edu.uci.ics.jung.visualization.control.CrossoverScalingControl;
import edu.uci.ics.jung.visualization.control.DefaultModalGraphMouse;
import edu.uci.ics.jung.visualization.control.ScalingControl;
import edu.uci.ics.jung.visualization.decorators.EdgeShape;
import edu.uci.ics.jung.visualization.decorators.PickableEdgePaintTransformer;
import edu.uci.ics.jung.visualization.decorators.PickableVertexPaintTransformer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.picking.MultiPickedState;
import edu.uci.ics.jung.visualization.picking.PickedState;
import edu.uci.ics.jung.visualization.renderers.Renderer;
import edu.uci.ics.jung.visualization.transform.MutableTransformer;

/**
* Demonstrates a single graph with 3 layouts in 3 views.
* The first view is an undirected graph using KKLayout
* The second view show a TreeLayout view of a MinimumSpanningTree
* of the first graph. The third view shows the complete graph
* of the first view, using the layout positions of the
* MinimumSpanningTree tree view.
*
* @author Tom Nelson
*
*/
public class MinimumSpanningTreeDemo extends JApplet {

     /**
     * the graph
     */
    Graph<String,String> graph;
    Forest<String,String> tree;

    /**
     * the visual components and renderers for the graph
     */
    VisualizationViewer<String,String> vv0;
    VisualizationViewer<String,String> vv1;
    VisualizationViewer<String,String> vv2;
//    VisualizationViewer<String,Number> vv3;

    /**
     * the normal transformer
     */
    MutableTransformer layoutTransformer;

    Dimension preferredSize = new Dimension(300,300);
    Dimension preferredLayoutSize = new Dimension(400,400);
    Dimension preferredSizeRect = new Dimension(500,250);



     private void createGraph() {
                graph = new DirectedSparseGraph<String, String>();

                /*
                try {

                    File f = new File(System.getProperty("user.dir") + "/data/my.graph");
                    System.out.println(System.getProperty("user.dir") + "/data/my.graph");
                    BufferedReader in = new BufferedReader(new FileReader(f));
                    String str;
                    while ((str = in.readLine()) != null) {
                        String[] values = str.trim().split("\"");
                        if(values.length==2){
                            graph.addVertex(values[1]);
                            System.out.println("Create root: " + values[1]);
                        }else{
                            if(values.length==5){
                                graph.addEdge(values[1]+"-->"+values[3], values[1], values[3]);
                                //edge_weight.put(values[1]+"-->"+values[3], Double.parseDouble(values[4]));
                                System.out.println("Create edge: "+values[1]+"-->"+values[3]);
                            }
                        }
                    }
                    in.close();



                } catch (Exception e) {
                    e.printStackTrace();
                }
                */


                String root1 = "root1";
                graph.addVertex(root1);
                //edge_weight.put(root+"B",0.3);
                graph.addEdge(root1+"B", root1, "B");
                //edge_weight.put(root+"A",0.7);
                graph.addEdge(root1+"A", root1, "A");

                String root2 = "root2";
                graph.addVertex(root2);
                //edge_weight.put(root+"B",0.3);
                graph.addEdge(root2+"C", root2, "C");
                //edge_weight.put(root+"A",0.7);
                graph.addEdge(root2+"D", root2, "D");


            }


    /**
     * create an instance of a simple graph in two views with controls to
     * demo the zoom features.
     *
     */

    public MinimumSpanningTreeDemo() {

        // create a simple graph for the demo
        // both models will share one graph
        createGraph();

        MinimumSpanningForest2<String,String> prim =
            new MinimumSpanningForest2<String,String>(graph,
                new SparseForest<String,String>(), SparseTree.<String,String>getFactory(),
                (Transformer<String,Double>)new ConstantTransformer(1.0));

        tree = prim.getForest();
        //tree.setRoot("allTopics");
        //tree.setRoot("allMessages");
        // create two layouts for the one graph, one layout for each model
        Layout<String,String> layout0 = new KKLayout<String,String>(graph);
        layout0.setSize(preferredLayoutSize);
        Layout<String,String> layout1 = new TreeLayout<String,String>(tree);

        Layout<String,String> layout2 = new StaticLayout<String,String>(graph, layout1);

        // create the two models, each with a different layout
        VisualizationModel<String,String> vm0 =
            new DefaultVisualizationModel<String,String>(layout0, preferredSize);
        VisualizationModel<String,String> vm1 =
            new DefaultVisualizationModel<String,String>(layout1, preferredSizeRect);
        VisualizationModel<String,String> vm2 =
            new DefaultVisualizationModel<String,String>(layout2, preferredSizeRect);

        // create the two views, one for each model
        // they share the same renderer
        vv0 = new VisualizationViewer<String,String>(vm0, preferredSize);
        vv1 = new VisualizationViewer<String,String>(vm1, preferredSizeRect);
        vv2 = new VisualizationViewer<String,String>(vm2, preferredSizeRect);

//        vv1.setRenderContext(vv2.getRenderContext());

        vv1.getRenderContext().setMultiLayerTransformer(vv0.getRenderContext().getMultiLayerTransformer());
        vv2.getRenderContext().setMultiLayerTransformer(vv0.getRenderContext().getMultiLayerTransformer());

        vv1.getRenderContext().setEdgeShapeTransformer(new EdgeShape.Orthogonal());

        vv0.addChangeListener(vv1);
        vv1.addChangeListener(vv2);

        vv0.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());
        vv2.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());

        Color back = Color.decode("0xffffbb");
        vv0.setBackground(back);
        vv1.setBackground(back);
        vv2.setBackground(back);

        vv0.getRenderer().getVertexLabelRenderer().setPosition(Renderer.VertexLabel.Position.CNTR);
        vv0.setForeground(Color.darkGray);
        vv1.getRenderer().getVertexLabelRenderer().setPosition(Renderer.VertexLabel.Position.CNTR);
        vv1.setForeground(Color.darkGray);
        vv2.getRenderer().getVertexLabelRenderer().setPosition(Renderer.VertexLabel.Position.CNTR);
        vv2.setForeground(Color.darkGray);

        // share one PickedState between the two views
        PickedState<String> ps = new MultiPickedState<String>();
        vv0.setPickedVertexState(ps);
        vv1.setPickedVertexState(ps);
        vv2.setPickedVertexState(ps);

        PickedState<String> pes = new MultiPickedState<String>();
        vv0.setPickedEdgeState(pes);
        vv1.setPickedEdgeState(pes);
        vv2.setPickedEdgeState(pes);

        // set an edge paint function that will show picking for edges
        vv0.getRenderContext().setEdgeDrawPaintTransformer(new PickableEdgePaintTransformer<String,String>(vv0.getPickedEdgeState(), Color.black, Color.red));
        vv0.getRenderContext().setVertexFillPaintTransformer(new PickableVertexPaintTransformer<String>(vv0.getPickedVertexState(),
                Color.red, Color.yellow));
        vv1.getRenderContext().setEdgeDrawPaintTransformer(new PickableEdgePaintTransformer<String,String>(vv1.getPickedEdgeState(), Color.black, Color.red));
        vv1.getRenderContext().setVertexFillPaintTransformer(new PickableVertexPaintTransformer<String>(vv1.getPickedVertexState(),
                Color.red, Color.yellow));

        // add default listeners for ToolTips
        vv0.setVertexToolTipTransformer(new ToStringLabeller());
        vv1.setVertexToolTipTransformer(new ToStringLabeller());
        vv2.setVertexToolTipTransformer(new ToStringLabeller());

        vv0.setLayout(new BorderLayout());
        vv1.setLayout(new BorderLayout());
        vv2.setLayout(new BorderLayout());

        Font font = vv0.getFont().deriveFont(Font.BOLD, 16);
        JLabel vv0Label = new JLabel("<html>Original Graph<p>using KKLayout");
        vv0Label.setFont(font);
        JLabel vv1Label = new JLabel("Minimum Spanning Trees");
        vv1Label.setFont(font);
        JLabel vv2Label = new JLabel("Original Graph using TreeLayout");
        vv2Label.setFont(font);
        JPanel flow0 = new JPanel();
        flow0.setOpaque(false);
        JPanel flow1 = new JPanel();
        flow1.setOpaque(false);
        JPanel flow2 = new JPanel();
        flow2.setOpaque(false);
        flow0.add(vv0Label);
        flow1.add(vv1Label);
        flow2.add(vv2Label);
        vv0.add(flow0, BorderLayout.NORTH);
        vv1.add(flow1, BorderLayout.NORTH);
        vv2.add(flow2, BorderLayout.NORTH);

//        vv2.getRenderContext().setEdgeDrawPaintTransformer(new Transformer<Number,Paint>() {
//
//            public Paint transform(Number e) {data
//                if(tree.getEdges().contains(e) == false) return Color.lightGray;
//                return Color.black;
//            }});

        Container content = getContentPane();
        JPanel grid = new JPanel(new GridLayout(0,1));
        JPanel panel = new JPanel(new BorderLayout());
        panel.add(new GraphZoomScrollPane(vv0), BorderLayout.WEST);
        grid.add(new GraphZoomScrollPane(vv1));
        grid.add(new GraphZoomScrollPane(vv2));
//        panel.add(new GraphZoomScrollPane(vv3), BorderLayout.EAST);
        panel.add(grid);

        content.add(panel);

        // create a GraphMouse for each view
        DefaultModalGraphMouse gm0 = new DefaultModalGraphMouse();
        DefaultModalGraphMouse gm1 = new DefaultModalGraphMouse();
        DefaultModalGraphMouse gm2 = new DefaultModalGraphMouse();
        DefaultModalGraphMouse gm3 = new DefaultModalGraphMouse();

        vv0.setGraphMouse(gm0);
        vv1.setGraphMouse(gm1);
        vv2.setGraphMouse(gm2);
//        vv3.setGraphMouse(gm3);

        // create zoom buttons for scaling the transformer that is
        // shared between the two models.
        final ScalingControl scaler = new CrossoverScalingControl();

        vv0.scaleToLayout(scaler);
        vv1.scaleToLayout(scaler);
        vv2.scaleToLayout(scaler);
//        vv3.scaleToLayout(scaler);

        JButton plus = new JButton("+");
        plus.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                scaler.scale(vv1, 1.1f, vv1.getCenter());
            }
        });
        JButton minus = new JButton("-");
        minus.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                scaler.scale(vv1, 1/1.1f, vv1.getCenter());
            }
        });

        JPanel zoomPanel = new JPanel(new GridLayout(1,2));
        zoomPanel.setBorder(BorderFactory.createTitledBorder("Zoom"));

        JPanel modePanel = new JPanel();
        modePanel.setBorder(BorderFactory.createTitledBorder("Mouse Mode"));
        gm1.getModeComboBox().addItemListener(gm2.getModeListener());
        gm1.getModeComboBox().addItemListener(gm0.getModeListener());
        gm1.getModeComboBox().addItemListener(gm3.getModeListener());
        modePanel.add(gm1.getModeComboBox());

        JPanel controls = new JPanel();
        zoomPanel.add(plus);
        zoomPanel.add(minus);
        controls.add(zoomPanel);
        controls.add(modePanel);
        content.add(controls, BorderLayout.SOUTH);
    }

    /**
     * a driver for this demo
     */
    public static void main(String[] args) {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().add(new MinimumSpanningTreeDemo());
        f.pack();
        f.setVisible(true);
    }
}

Joshua & Tom,

Thanks for the suggestions from both you. I can confirm that there needs a way to 1.) pass a collection of root vertices (undirected graph and only if we know the correct association among roots and components) or 2.) find the correct root for each component. I attached a brief implementation of 2.) as MST3 below for your consideration.

public class MinimumSpanningForest3<V,E> {

    protected Graph<V,E> graph;
    protected Forest<V,E> forest;
    protected Transformer<E,Double> weights =
        (Transformer<E,Double>)new ConstantTransformer<Double>(1.0);

    /**
     * create a Forest from the supplied Graph and supplied Factory, which
     * is used to create a new, empty Forest. If non-null, the supplied root
     * will be used as the root of the tree/forest. If the supplied root is
     * null, or not present in the Graph, then an arbitary Graph vertex
     * will be selected as the root.
     * If the Minimum Spanning Tree does not include all vertices of the
     * Graph, then a leftover vertex is selected as a root, and another
     * tree is created
     * @param graph
     * @param factory
     * @param root
     * @param weights
     */
    public MinimumSpanningForest3(Graph<V, E> graph,
            Factory<Forest<V,E>> factory,
            Factory<Tree<V,E>> treeFactory,
            Transformer<E, Double> weights) {
        this(graph, factory.create(),
                treeFactory,
                weights);
    }

    /**
     * create a forest from the supplied graph, populating the
     * supplied Forest, which must be empty.
     * If the supplied root is null, or not present in the Graph,
     * then an arbitary Graph vertex will be selected as the root.
     * If the Minimum Spanning Tree does not include all vertices of the
     * Graph, then a leftover vertex is selected as a root, and another
     * tree is created
     * @param graph the Graph to find MST in
     * @param forest the Forest to populate. Must be empty
     * @param root first Tree root, may be null
     * @param weights edge weights, may be null
     */
    public MinimumSpanningForest3(Graph<V, E> graph,
            Forest<V,E> forest,
            Factory<Tree<V,E>> treeFactory,
            Transformer<E, Double> weights) {

        if(forest.getVertexCount() != 0) {
            throw new IllegalArgumentException("Supplied Forest must be empty");
        }
        this.graph = graph;
        this.forest = forest;
        if(weights != null) {
            this.weights = weights;
        }

        WeakComponentGraphClusterer<V,E> wcgc =
            new WeakComponentGraphClusterer<V,E>();
        Collection<Graph<V,E>> components = wcgc.transform(graph);

        for(Graph<V,E> component : components) {
                        Collection<V> nodes = component.getVertices();
                        V root = null;
                        Iterator<V> tracker = nodes.iterator();
                        while(tracker.hasNext()){
                            V vertex = tracker.next();
                            if(component.inDegree(vertex)==0){
                                root = vertex;
                                break;
                            }
                        }

                        PrimMinimumSpanningTree<V,E> mst = new PrimMinimumSpanningTree<V,E>(treeFactory, root, weights);
            forest.getTrees().add(mst.transform(component));
        }
    }

    public Forest<V,E> getForest() {
        return forest;
    }
}

Two DAGs side by side

Java graph/network library

Forums

Help

Two DAGs side by side

Two DAGs side by side

Java graph/network library

Forums

Help

Two DAGs side by side document.SUBSCRIPTION_OPTIONS = { "thing": "topic", "subscribed": false, "url": "subscribe", "icon": { "css": "fa fa-envelope-o" } };

Two DAGs side by side