Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Mixed Graphs

Kevin
2012-10-10
2013-05-29
  • Kevin
    Kevin
    2012-10-10

    I've figured out how to create and display mixed graphs (graphs with both directed and undirected edges) without modifying the prefuse library at all.  I did it by extending four classes.  Where should I put 'em? :D

     
  • Kevin
    Kevin
    2012-10-10

    'Kay, here it is.  Slightly improved since last night, now five classes.  This code is provided under the terms of the BSD license.

    MixedGraph.java:

    package krum.prefuse.data;
    import krum.prefuse.data.tuple.DirectableEdge;
    import prefuse.data.Graph;
    import prefuse.data.Node;
    import prefuse.data.Table;
    import prefuse.data.tuple.TupleManager;
    /**
     * A <tt>Graph</tt> that allows a mixture of directed and undirected edges.
     * The graph's directed property becomes a default that can be overridden for
     * each edge, and the directed property of edges can be changed after they are
     * created.
     */
    public class MixedGraph extends Graph {
    
        // TODO: study how m_links is used in Graph; may need to manipulate it in MixedGraph methods
    
        // have to hard-code this default because PrefuseConfig doesn't provide a default default
        /** The default column name for the directed property in the edge table */
        public static final String DEFAULT_DIRECTED_KEY = "directed";
        
        /** The column name for the directed property in the edge table */
        protected String m_dkey;
        
        public MixedGraph() {
            super();
            initMixed(DEFAULT_DIRECTED_KEY);
        }
        public MixedGraph(boolean directed) {
            super(directed);
            initMixed(DEFAULT_DIRECTED_KEY);
        }
        public MixedGraph(Table nodes, boolean directed) {
            super(nodes, directed);
            initMixed(DEFAULT_DIRECTED_KEY);
        }
        public MixedGraph(Table nodes, Table edges, boolean directed) {
            super(nodes, edges, directed);
            initMixed(DEFAULT_DIRECTED_KEY);
        }
    
        public MixedGraph(Table nodes, boolean directed, String nodeKey,
                String sourceKey, String targetKey, String directedKey) {
            super(nodes, directed, nodeKey, sourceKey, targetKey);
            initMixed(directedKey);
        }
        public MixedGraph(Table nodes, Table edges, boolean directed,
                String nodeKey, String sourceKey, String targetKey, String directedKey) {
            super(nodes, edges, directed, nodeKey, sourceKey, targetKey);
            initMixed(directedKey);
        }
        // this one's weird, but included for superclass compatibility
        public MixedGraph(Table nodes, Table edges, boolean directed,
                String sourceKey, String targetKey, String directedKey) {
            super(nodes, edges, directed, sourceKey, targetKey);
            initMixed(directedKey);
        }
    
        protected void initMixed(String directedKey) {
            m_dkey = directedKey;
            Table edges = getEdgeTable();
            edges.addColumn(m_dkey, boolean.class, m_directed);
            m_edgeTuples = new TupleManager(edges, this, DirectableEdge.class);
        }   
        public int addEdge(int s, int t, boolean directed) {
            int r = super.addEdge(s, t);
            Table edges = getEdgeTable();
            edges.setBoolean(r, m_dkey, directed);
            return r;
        }
    
        public DirectableEdge addEdge(Node s, Node t, boolean directed) {
            nodeCheck(s, true);
            nodeCheck(t, true);
            int e = addEdge(s.getRow(), t.getRow(), directed);
            return getEdge(e);
        }
    
        @Override
        public DirectableEdge addEdge(Node s, Node t) {
            return addEdge(s, t, m_directed);
        }
    
        @Override
        public DirectableEdge getEdge(int e) {
            return ( e < 0 ? null : (DirectableEdge)m_edgeTuples.getTuple(e) );
        }
        
        public boolean isDirected(DirectableEdge e) {
            edgeCheck(e, true);
            return getEdgeTable().getBoolean(e.getRow(), m_dkey);
        }
        
        public boolean isDirected(int e) {
            return getEdgeTable().getBoolean(e, m_dkey);
        }
        
        public void setDirected(DirectableEdge e, boolean directed) {
            edgeCheck(e, true);
            getEdgeTable().setBoolean(e.getRow(), m_dkey, directed);
        }
        
        public void setDirected(int e, boolean directed) {
            getEdgeTable().setBoolean(e, m_dkey, directed);
        }
        
        public String getDirectedField() {
            return m_dkey;
        }
    }
    

    MixedVisualGraph.java:

    package krum.prefuse.visual;
    import prefuse.visual.VisualGraph;
    import prefuse.visual.VisualTable;
    public class MixedVisualGraph extends VisualGraph {
    
        protected String m_dkey;
        public MixedVisualGraph(VisualTable nodes, VisualTable edges,
                boolean directed, String nodeKey, String sourceKey, String targetKey, String directedKey) {
            super(nodes, edges, directed, nodeKey, sourceKey, targetKey);
            m_dkey = directedKey;
        }
    
        public String getDirectedField() {
            return m_dkey;
        }
    }
    

    MixedVisualization.java:

    package krum.prefuse;
    import krum.prefuse.data.MixedGraph;
    import krum.prefuse.visual.MixedVisualGraph;
    import krum.prefuse.visual.tuple.DirectableEdgeItem;
    import prefuse.Visualization;
    import prefuse.data.Graph;
    import prefuse.data.Schema;
    import prefuse.data.expression.Predicate;
    import prefuse.data.tuple.TupleManager;
    import prefuse.util.PrefuseLib;
    import prefuse.visual.VisualItem;
    import prefuse.visual.VisualTable;
    import prefuse.visual.tuple.TableNodeItem;
    /**
     * A <tt>Visualization</tt> with support for mixed graphs.
     */
    public class MixedVisualization extends Visualization {
        public synchronized MixedVisualGraph addGraph(String group, MixedGraph graph) {
            return addGraph(group, graph, null);
        }
        public synchronized MixedVisualGraph addGraph(String group, MixedGraph graph, Predicate filter) {
            return addGraph(group, graph, filter, VisualItem.SCHEMA, VisualItem.SCHEMA);
        }
        public synchronized MixedVisualGraph addGraph(String group, MixedGraph graph,
                Predicate filter, Schema nodeSchema, Schema edgeSchema) {
            checkGroupExists(group); // check before adding sub-tables
            String ngroup = PrefuseLib.getGroupName(group, Graph.NODES); 
            String egroup = PrefuseLib.getGroupName(group, Graph.EDGES);
            VisualTable nt, et;
            nt = addTable(ngroup, graph.getNodeTable(), filter, nodeSchema);
            et = addTable(egroup, graph.getEdgeTable(), filter, edgeSchema);
            
            MixedVisualGraph vg = new MixedVisualGraph(nt, et, // <-- here's the magic
                    graph.isDirected(), graph.getNodeKeyField(),
                    graph.getEdgeSourceField(), graph.getEdgeTargetField(), graph.getDirectedField());
            vg.setVisualization(this);
            vg.setGroup(group);
         
            addDataGroup(group, vg, graph);
            
            TupleManager ntm = new TupleManager(nt, vg, TableNodeItem.class);
            TupleManager etm = new TupleManager(et, vg, DirectableEdgeItem.class); // <-- more magic
            nt.setTupleManager(ntm);
            et.setTupleManager(etm);
            vg.setTupleManagers(ntm, etm);
            
            return vg;
        }
    }
    

    DirectableEdge.java:

    package krum.prefuse.data.tuple;
    import krum.prefuse.data.MixedGraph;
    import prefuse.data.tuple.TableEdge;
    /**
     * A <tt>TableEdge</tt> that allows its directed property to be reassigned.
     */
    public class DirectableEdge extends TableEdge {
        @Override
        public boolean isDirected() {
            return ((MixedGraph)m_graph).isDirected(this);
        }
        
        public void setDirected(boolean directed) {
            ((MixedGraph)m_graph).setDirected(this, directed);
        }
        
        // TODO: method to swap s and t?
        
    }
    

    DirectableEdgeItem.java:

    package krum.prefuse.visual.tuple;
    import krum.prefuse.visual.MixedVisualGraph;
    import prefuse.visual.tuple.TableEdgeItem;
    /**
     * The visual representation of a <tt>DirectableEdge</tt>.
     */
    public class DirectableEdgeItem extends TableEdgeItem {
        @Override
        public boolean isDirected() {
            return m_table.getBoolean(m_row, ((MixedVisualGraph)m_graph).getDirectedField());
        }
    }
    
     
  • Kevin
    Kevin
    2012-10-11

    Upon further reflection, there's a completely different approach to this that might be better.  For most purposes, an undirected edge in a mixed graph is effectively equivalent to two directed edges.  My requirement is that those two edges be drawn as a single undirected edge; I don't care if they're actually represented that way in the Graph.  This might be more simply achievable by using a directed Graph and some custom ColorActions.

     
  • Kevin
    Kevin
    2012-10-11

    Success!  All it took was two custom Predicates.

    import prefuse.data.Edge;
    import prefuse.data.Tuple;
    import prefuse.data.expression.AbstractPredicate;
    /** Matches an edge (s, t) if an edge (t, s) exists */
    public class PairedEdgePredicate extends AbstractPredicate {
        @Override
        public boolean getBoolean(Tuple tuple) {
            if(!(tuple instanceof Edge)) return false; 
            Edge e = (Edge) tuple;
            return  e.getGraph().getEdge(e.getTargetNode(), e.getSourceNode()) != null;
        }
    }
    
    import prefuse.data.Edge;
    import prefuse.data.Tuple;
    import prefuse.data.expression.AbstractPredicate;
    /** Matches an edge (s, t) if s.getRow() < t.getRow() */
    public class AscendingEdgePredicate extends AbstractPredicate {
        @Override
        public boolean getBoolean(Tuple tuple) {
            if(!(tuple instanceof Edge)) return false; 
            Edge e = (Edge) tuple;
            return e.getSourceNode().getRow() < e.getTargetNode().getRow();
        }
    }
    
    import javax.swing.JFrame;
    import javax.swing.SwingUtilities;
    import prefuse.Constants;
    import prefuse.Display;
    import prefuse.Visualization;
    import prefuse.action.ActionList;
    import prefuse.action.RepaintAction;
    import prefuse.action.assignment.ColorAction;
    import prefuse.action.layout.graph.RadialTreeLayout;
    import prefuse.controls.DragControl;
    import prefuse.data.Graph;
    import prefuse.data.expression.AndPredicate;
    import prefuse.data.expression.NotPredicate;
    import prefuse.render.DefaultRendererFactory;
    import prefuse.render.EdgeRenderer;
    import prefuse.util.ColorLib;
    import prefuse.visual.VisualItem;
    public class FakeMixDemo {
    
        public FakeMixDemo() {
            // directed graph
            Graph graph = new Graph(true);
            for(int i = 0; i < 3; ++i) graph.addNode();
            graph.addEdge(0, 1);
            graph.addEdge(1, 0);
            graph.addEdge(0, 2);
    
            // visualization
            Visualization vis = new Visualization();
            vis.add("graph", graph);
    
            // generic renderer factory
            DefaultRendererFactory rf = new DefaultRendererFactory();
            // set up an edge renderer for paired edges that draws no arrowhead
            EdgeRenderer er = new EdgeRenderer();
            er.setArrowType(Constants.EDGE_ARROW_NONE);
            rf.add(new PairedEdgePredicate(), er);
            vis.setRendererFactory(rf);
    
            // item coloring
            ActionList colors = new ActionList();
            // make unpaired edges red and fill their arrowhead 
            colors.add(new ColorAction("graph.edges",
                    new NotPredicate(new PairedEdgePredicate()),
                    VisualItem.FILLCOLOR,
                    ColorLib.rgb(255, 0, 0)));
            colors.add(new ColorAction("graph.edges",
                    new NotPredicate(new PairedEdgePredicate()),
                    VisualItem.STROKECOLOR,
                    ColorLib.rgb(255, 0, 0)));
    
            // make paired ascending edges gray
            colors.add(new ColorAction("graph.edges",
                    new AndPredicate(new PairedEdgePredicate(),
                    new AscendingEdgePredicate()),
                    VisualItem.STROKECOLOR,
                    ColorLib.gray(127)));
    
            // paired descending edges remain transparent
    
            // boring nodes
            colors.add(new ColorAction("graph.nodes", VisualItem.STROKECOLOR, ColorLib.gray(127)));
            colors.add(new ColorAction("graph.nodes", VisualItem.FILLCOLOR, ColorLib.rgb(200,200,255)));
    
            vis.putAction("colors", colors);
    
            // layout
            ActionList layout = new ActionList(/*Activity.INFINITY*/);
            layout.add(new RadialTreeLayout("graph"));
            layout.add(new RepaintAction());
            vis.putAction("layout", layout);
    
            // display
            Display display = new Display(vis);
            display.setSize(500, 500);
    
            // controls
            display.addControlListener(new DragControl());
    
            // frame
            JFrame frame = new JFrame("Fake MixedGraph");
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.add(display);
            frame.pack();
            frame.setVisible(true);
    
            vis.run("colors");
            vis.run("layout");
        }
    
        public static void main(String[] args) {
            SwingUtilities.invokeLater(new Runnable() {
                @Override
                public void run() {
                    new FakeMixDemo();
                }
            });
        }
    }