Proposed code changes to handle edge overlaps:

Jan 10, 2013 at 2:34 PM

Could someone working on the NodeXL code do a once over on these proposed changes.  I am hoping the approach suggested here is not too naïve.

I am wondering if there is a more optimal approach, since I pass through the edge date twice.

In IGraphs.cs

// MP! Added in support of overlapping edges.
public enum
GraphOverlapmode
{
    Overlapped = 0,
    BezierSplay = 1,
    OvalSplay = 2,
    SquareSplay = 3
}

    // MP! Added in support of overlapping edges.
    GraphOverlapmode
    Overlapmode
    {
        get;
    }

In Graph.cs (this introduces a non breaking change in the constructor):

    Graph
    (
        GraphDirectedness directedness,

        // MP! Added in support of overlapping edges.
        GraphOverlapmode overlapmode = GraphOverlapmode.None
    )
    :
    base( m_oIDGenerator.GetNextID() )
    {
        const String MethodName = "Constructor";

        this.ArgumentChecker.CheckArgumentIsDefined(
            MethodName, "directedness", directedness,
            typeof(GraphDirectedness) );

        m_eDirectedness = directedness;

        // MP! Added in support of overlapping edges.
        m_eOverlapmode = overlapmode;

        m_oVertexCollection = new VertexCollection(this);
        m_oEdgeCollection = new EdgeCollection(this);

        AssertValid();
    }

 

    // MP! Added in support of overlapping edges.
    public GraphOverlapmode
    Overlapmode
    {
        get
        {
            //AssertValid();

            return (m_eOverlapmode);
        }
    }

In GraphDrawer.cs:

// MP! Added in support of overlapping edges.
using System.Runtime.InteropServices;

// MP! Added in support of overlapping edges.
[StructLayout(LayoutKind.Explicit)]
struct NodeComparer
{
    [FieldOffset(0)]
    public ulong vpair;
    [FieldOffset(0)]
    public int v1;
    [FieldOffset(4)]
    public int v2;
}

    public void
    DrawGraph
    (
        IGraph graph,
        GraphDrawingContext graphDrawingContext
    )
    {
        Debug.Assert(graph != null);
        Debug.Assert(graphDrawingContext != null);
        AssertValid();

        // MP! Added in support of overlapping edges.
        NodeComparer nodecomparer;

        Dictionary<ulong, List<IEdge>> EdgeOverlaps = null;

        if (graph.Overlapmode != GraphOverlapmode.None)
            EdgeOverlaps = new Dictionary<ulong, List<IEdge>>();

        // Implementation note:
        //
        // In a previous GDI+ implementation of this graph drawer, the edges
        // had to be drawn first to allow the vertices to cover the ends of the
        // edges.  That required a complex three-step drawing process: 1) allow
        // the vertex drawer to move each vertex if necessary to prevent the
        // vertex from falling outside the graph rectangle; 2) draw the edges
        // using the moved vertex locations; and 3) draw the vertices.
        //
        // This WPF implementation is simpler, for two reasons:
        //
        // 1. WPF uses retained-mode graphics, so covering the ends of the
        //    edges can be accomplished simply by adding
        //    m_oUnselectedEdgeDrawingVisuals to m_oVisualCollection before
        //    adding m_oAllVertexDrawingVisuals.  That means that the vertices
        //    can be drawn onto m_oAllVertexDrawingVisuals first, and the
        //    vertex drawer can move the vertices as necessary before drawing
        //    them.  A three-step process is no longer required.
        //
        // 2. The edges in this implementation don't actually need to be
        //    covered, because they terminate at the vertex boundaries instead
        //    of the vertex centers, as in the GDI+ implementation.

        m_oVisualCollection.Clear();

        DrawBackground(graph, graphDrawingContext);

        Visual oGroupVisual;

        if ( m_oGroupDrawer.TryDrawGroupRectangles(graph, graphDrawingContext,
            out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }

        if ( m_oGroupDrawer.TryDrawCombinedIntergroupEdges(
            graph, graphDrawingContext, out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }

        m_oAllVertexDrawingVisuals = new DrawingVisual();
        m_oUnselectedEdgeDrawingVisuals = new DrawingVisual();
        m_oSelectedEdgeDrawingVisuals = new DrawingVisual();

        // Draw the vertices after moving them if necessary.  Each vertex needs
        // to be individually hit-tested and possibly redrawn by
        // RedrawVertex(), so each vertex is put into its own DrawingVisual
        // that becomes a child of m_oAllVertexDrawingVisuals.
        //
        // Selected vertices should always be on top of unselected vertices, so
        // draw them first.  Note that this could also be accomplished by using
        // two DrawingVisual objects, m_oUnselectedVertexDrawingVisuals and
        // m_oSelectedVertexDrawingVisuals, in a manner similar to what is done
        // for edges.  However, vertices have to be hit-tested, and having two
        // DrawingVisual objects for two sets of vertices would complicate and
        // slow down hit-testing, so this solution is the simpler one.

        LinkedList<IVertex> oSelectedVertices = new LinkedList<IVertex>();

        foreach ( IVertex oVertex in GetVerticesToDraw(graph) )
        {
            if ( m_oVertexDrawer.GetDrawAsSelected(oVertex) )
            {
                oSelectedVertices.AddLast(oVertex);
            }
            else
            {
                DrawVertex(oVertex, graphDrawingContext);
            }
        }

        foreach (IVertex oVertex in oSelectedVertices)
        {
            DrawVertex(oVertex, graphDrawingContext);
        }

        // MP! Added in support of overlapping edges.
        if (graph.Overlapmode != GraphOverlapmode.None)
        {
            // MP! Determine edge overlaps here.
            foreach (IEdge oEdge in graph.Edges)
            {
                nodecomparer.vpair = 0;

                if (oEdge.Vertex1.ID > oEdge.Vertex2.ID)
                {
                    nodecomparer.v1 = oEdge.Vertex2.ID;
                    nodecomparer.v2 = oEdge.Vertex1.ID;
                }
                else
                {
                    nodecomparer.v1 = oEdge.Vertex1.ID;
                    nodecomparer.v2 = oEdge.Vertex2.ID;
                }

                if (!EdgeOverlaps.ContainsKey(nodecomparer.vpair))
                    EdgeOverlaps.Add(nodecomparer.vpair, new List<IEdge>() { oEdge });
                else
                    EdgeOverlaps[nodecomparer.vpair].Add(oEdge);
            }
        }

        oSelectedVertices = null;

        // Draw the edges.  The edges don't need to be hit-tested, but they
        // might need to be redrawn by RedrawEdge(), so each edge is put into
        // its own DrawingVisual that becomes a child of either
        // m_oUnselectedEdgeDrawingVisuals or m_oSelectedEdgeDrawingVisuals.

        foreach (IEdge oEdge in graph.Edges)
        {
            // MP! Added in support of overlapping edges.
            if (graph.Overlapmode != GraphOverlapmode.None)
            {
                nodecomparer.vpair = 0;

                if (oEdge.Vertex1.ID > oEdge.Vertex2.ID)
                {
                    nodecomparer.v1 = oEdge.Vertex2.ID;
                    nodecomparer.v2 = oEdge.Vertex1.ID;
                }
                else
                {
                    nodecomparer.v1 = oEdge.Vertex1.ID;
                    nodecomparer.v2 = oEdge.Vertex2.ID;
                }

                if (EdgeOverlaps.ContainsKey(nodecomparer.vpair))
                    continue;
                else
                    DrawEdge(oEdge, graphDrawingContext);
            }
            else
                DrawEdge(oEdge, graphDrawingContext);
        }

        // MP! Added in support of overlapping edges.
        if (graph.Overlapmode != GraphOverlapmode.None)
        {
            foreach (var EdgeElement in EdgeOverlaps)
            {
                // Splay common edges appart.
                foreach(IEdge oEdge in EdgeElement.Value)
                {
                    // ... Something like ...
      DrawSplayedEdge(oEdge, graphDrawingContext, EdgeElement.Value.Count, graph.Overlapmode);
                }
            }
        }

        // Selected edges need to be drawn on top of all the vertices
        // (including selected vertices) to guarantee that they will be
        // visible; hence the addition order seen here.

        m_oVisualCollection.Add(m_oUnselectedEdgeDrawingVisuals);
        m_oVisualCollection.Add(m_oAllVertexDrawingVisuals);
        m_oVisualCollection.Add(m_oSelectedEdgeDrawingVisuals);

        if ( m_oGroupDrawer.TryDrawGroupLabels(graph, graphDrawingContext,
            out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }
    }

 

Jan 10, 2013 at 3:38 PM

Helps to actually try out the code one write.  Sorry for the mistakes above.  Here's a working proof of concept:

Changed Enum to:

public enum
GraphOverlapmode
{
    Overlapped = 0,
    BezierSplay = 1,
    OvalSplay = 2,
    SquareSplay = 3,
    SkipOverlaps = 99
}

Changed DrawGraph to:

    public void
    DrawGraph
    (
        IGraph graph,
        GraphDrawingContext graphDrawingContext
    )
    {
        Debug.Assert(graph != null);
        Debug.Assert(graphDrawingContext != null);
        AssertValid();

        // MP! Added in support of overlapping edges.
        NodeComparer nodecomparer;

        Dictionary<ulong, List<IEdge>> EdgeOverlaps = null;

        if (graph.Overlapmode != GraphOverlapmode.Overlapped)
            EdgeOverlaps = new Dictionary<ulong, List<IEdge>>();

        // Implementation note:
        //
        // In a previous GDI+ implementation of this graph drawer, the edges
        // had to be drawn first to allow the vertices to cover the ends of the
        // edges.  That required a complex three-step drawing process: 1) allow
        // the vertex drawer to move each vertex if necessary to prevent the
        // vertex from falling outside the graph rectangle; 2) draw the edges
        // using the moved vertex locations; and 3) draw the vertices.
        //
        // This WPF implementation is simpler, for two reasons:
        //
        // 1. WPF uses retained-mode graphics, so covering the ends of the
        //    edges can be accomplished simply by adding
        //    m_oUnselectedEdgeDrawingVisuals to m_oVisualCollection before
        //    adding m_oAllVertexDrawingVisuals.  That means that the vertices
        //    can be drawn onto m_oAllVertexDrawingVisuals first, and the
        //    vertex drawer can move the vertices as necessary before drawing
        //    them.  A three-step process is no longer required.
        //
        // 2. The edges in this implementation don't actually need to be
        //    covered, because they terminate at the vertex boundaries instead
        //    of the vertex centers, as in the GDI+ implementation.

        m_oVisualCollection.Clear();

        DrawBackground(graph, graphDrawingContext);

        Visual oGroupVisual;

        if ( m_oGroupDrawer.TryDrawGroupRectangles(graph, graphDrawingContext,
            out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }

        if ( m_oGroupDrawer.TryDrawCombinedIntergroupEdges(
            graph, graphDrawingContext, out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }

        m_oAllVertexDrawingVisuals = new DrawingVisual();
        m_oUnselectedEdgeDrawingVisuals = new DrawingVisual();
        m_oSelectedEdgeDrawingVisuals = new DrawingVisual();

        // Draw the vertices after moving them if necessary.  Each vertex needs
        // to be individually hit-tested and possibly redrawn by
        // RedrawVertex(), so each vertex is put into its own DrawingVisual
        // that becomes a child of m_oAllVertexDrawingVisuals.
        //
        // Selected vertices should always be on top of unselected vertices, so
        // draw them first.  Note that this could also be accomplished by using
        // two DrawingVisual objects, m_oUnselectedVertexDrawingVisuals and
        // m_oSelectedVertexDrawingVisuals, in a manner similar to what is done
        // for edges.  However, vertices have to be hit-tested, and having two
        // DrawingVisual objects for two sets of vertices would complicate and
        // slow down hit-testing, so this solution is the simpler one.

        LinkedList<IVertex> oSelectedVertices = new LinkedList<IVertex>();

        foreach ( IVertex oVertex in GetVerticesToDraw(graph) )
        {
            if ( m_oVertexDrawer.GetDrawAsSelected(oVertex) )
            {
                oSelectedVertices.AddLast(oVertex);
            }
            else
            {
                DrawVertex(oVertex, graphDrawingContext);
            }
        }

        foreach (IVertex oVertex in oSelectedVertices)
        {
            DrawVertex(oVertex, graphDrawingContext);
        }

        // MP! Added in support of overlapping edges.
        if (graph.Overlapmode != GraphOverlapmode.Overlapped)
        {
            // MP! Determine edge overlaps here.
            foreach (IEdge oEdge in graph.Edges)
            {
                nodecomparer.vpair = 0;

                if (oEdge.Vertex1.ID > oEdge.Vertex2.ID)
                {
                    nodecomparer.v1 = oEdge.Vertex2.ID;
                    nodecomparer.v2 = oEdge.Vertex1.ID;
                }
                else
                {
                    nodecomparer.v1 = oEdge.Vertex1.ID;
                    nodecomparer.v2 = oEdge.Vertex2.ID;
                }

                if (!EdgeOverlaps.ContainsKey(nodecomparer.vpair))
                    EdgeOverlaps.Add(nodecomparer.vpair, new List<IEdge>() { oEdge });
                else
                    EdgeOverlaps[nodecomparer.vpair].Add(oEdge);
            }
        }

        oSelectedVertices = null;

        // Draw the edges.  The edges don't need to be hit-tested, but they
        // might need to be redrawn by RedrawEdge(), so each edge is put into
        // its own DrawingVisual that becomes a child of either
        // m_oUnselectedEdgeDrawingVisuals or m_oSelectedEdgeDrawingVisuals.

        if (graph.Overlapmode == GraphOverlapmode.Overlapped)
        {
            foreach (IEdge oEdge in graph.Edges)
            {
                DrawEdge(oEdge, graphDrawingContext);
            }
        }
        else
        {
            foreach (var EdgeElement in EdgeOverlaps)
            {
                // Draw single edge when only one is present or when overlapping edges are to be skipped.
                if (EdgeElement.Value.Count == 1 || graph.Overlapmode == GraphOverlapmode.SkipOverlaps)
                {
                    DrawEdge(EdgeElement.Value[0], graphDrawingContext);
                }
                else
                {
                    // Splay common edges appart.
                    foreach (IEdge oEdge in EdgeElement.Value)
                    {
                        // Need some other function here ... like SplayEdges ...
                        DrawEdge(oEdge, graphDrawingContext);
                    }
                }
            }
        }

        // Selected edges need to be drawn on top of all the vertices
        // (including selected vertices) to guarantee that they will be
        // visible; hence the addition order seen here.

        m_oVisualCollection.Add(m_oUnselectedEdgeDrawingVisuals);
        m_oVisualCollection.Add(m_oAllVertexDrawingVisuals);
        m_oVisualCollection.Add(m_oSelectedEdgeDrawingVisuals);

        if ( m_oGroupDrawer.TryDrawGroupLabels(graph, graphDrawingContext,
            out oGroupVisual) )
        {
            m_oVisualCollection.Add(oGroupVisual);
        }
    }

Jan 10, 2013 at 5:57 PM

If anyone is interested, I have a set of code changes that add support for overlapped edges based on the ideas presented above.  I have only implemented "BezierSplay" mode for disambiguating overlapped edges.  Hopefully someone on the dev side of NodeXL might choose to integrate and expand these changes.

Would be nice to have this formalized into NodeXL.

Coordinator
Jan 10, 2013 at 10:36 PM

Hello!

We really appreciate this effort.  We will certainly discuss ways to integrate your ideas soon.  Our delay is not based on our enthusiasm for edges++, we are just short on hours right now (civic obligations are being served)!

-
Marc

Coordinator
Jan 11, 2013 at 5:48 AM

Thanks for the suggestions, neomata.  We hope to fix the overlapping edge problem in some future release, although it's not on our immediate list of work items.

-- Tony

Jan 11, 2013 at 6:25 AM

No worries.  I fine tuned the solution some more and added a couple additional overlap modes as detailed by the enums.  It was surprisingly easy to do thanks to a well designed core.  All in all it took less than 3 hours to add the overlapping edge feature.  Works quite nicely now for what I need.  I don't have the editing mode working quite right (no overlap during edit), but the final layout/render is fine.

I'm using NodeXL to display a state machine diagram, by the way.  The WPF app allows you to dynamically change the layout style and also edit the layout thanks to your control.

Thanks a bunch!