search

oss-bandb / GraphView

Android GraphView is used to display data in graph structures.
Apache License 2.0
1.04k stars 129 forks source link

IndexOutOfBoundsException when using SugiyamaAlgorithm for certain cases #62

Open renyuneyun opened 4 years ago

renyuneyun commented 4 years ago

As the title says, the graph may run into problem in certain cases, when trying to draw itself.

My initialization of the algorithm is:

val configurationBuilder = SugiyamaConfiguration.Builder().setLevelSeparation(300).setNodeSeparation(100)
val algorithm = SugiyamaAlgorithm(SugiyamaConfiguration(configurationBuilder))

The known simplest graph structure is with three nodes (reported in renyuneyun/Easer#310 ):

s1
s2 -> p1

I tried to dig into GraphView's code, but wasn't able to understand what type1Conflicts is meant for. Therefore, here is the stacktrace:

    java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
        at java.util.ArrayList.get(ArrayList.java:437)
        at de.blox.graphview.layered.SugiyamaAlgorithm.verticalAlignment(SugiyamaAlgorithm.java:586)
        at de.blox.graphview.layered.SugiyamaAlgorithm.assignX(SugiyamaAlgorithm.java:367)
        at de.blox.graphview.layered.SugiyamaAlgorithm.coordinateAssignment(SugiyamaAlgorithm.java:328)
        at de.blox.graphview.layered.SugiyamaAlgorithm.run(SugiyamaAlgorithm.java:53)
        at de.blox.graphview.BaseGraphAdapter.notifySizeChanged(BaseGraphAdapter.java:29)
        at de.blox.graphview.GraphNodeContainerView.onMeasure(GraphNodeContainerView.java:368)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChild(ViewGroup.java:6829)
        at android.view.ViewGroup.measureChildren(ViewGroup.java:6806)
        at com.otaliastudios.zoom.ZoomLayout.onMeasure(ZoomLayout.kt:129)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.FrameLayout.onMeasure(FrameLayout.java:194)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.FrameLayout.onMeasure(FrameLayout.java:194)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at androidx.coordinatorlayout.widget.CoordinatorLayout.onMeasureChild(CoordinatorLayout.java:733)
        at com.google.android.material.appbar.HeaderScrollingViewBehavior.onMeasureChild(HeaderScrollingViewBehavior.java:95)
        at com.google.android.material.appbar.AppBarLayout$ScrollingViewBehavior.onMeasureChild(AppBarLayout.java:1556)
        at androidx.coordinatorlayout.widget.CoordinatorLayout.onMeasure(CoordinatorLayout.java:803)
        at android.view.View.measure(View.java:24710)
        at androidx.drawerlayout.widget.DrawerLayout.onMeasure(DrawerLayout.java:1119)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.FrameLayout.onMeasure(FrameLayout.java:194)
        at androidx.appcompat.widget.ContentFrameLayout.onMeasure(ContentFrameLayout.java:143)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.LinearLayout.measureChildBeforeLayout(LinearLayout.java:1552)
        at android.widget.LinearLayout.measureVertical(LinearLayout.java:842)
        at android.widget.LinearLayout.onMeasure(LinearLayout.java:721)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.FrameLayout.onMeasure(FrameLayout.java:194)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.LinearLayout.measureChildBeforeLayout(LinearLayout.java:1552)
        at android.widget.LinearLayout.measureVertical(LinearLayout.java:842)
        at android.widget.LinearLayout.onMeasure(LinearLayout.java:721)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewGroup.measureChildWithMargins(ViewGroup.java:6858)
        at android.widget.FrameLayout.onMeasure(FrameLayout.java:194)
        at com.android.internal.policy.DecorView.onMeasure(DecorView.java:749)
        at android.view.View.measure(View.java:24710)
        at android.view.ViewRootImpl.performMeasure(ViewRootImpl.java:3259)
        at android.view.ViewRootImpl.measureHierarchy(ViewRootImpl.java:2042)
        at android.view.ViewRootImpl.performTraversals(ViewRootImpl.java:2337)
        at android.view.ViewRootImpl.doTraversal(ViewRootImpl.java:1930)
        at android.view.ViewRootImpl$TraversalRunnable.run(ViewRootImpl.java:7988)
        at android.view.Choreographer$CallbackRecord.run(Choreographer.java:1154)
        at android.view.Choreographer.doCallbacks(Choreographer.java:977)
        at android.view.Choreographer.doFrame(Choreographer.java:893)
2020-02-08 17:08:34.571 14743-14743/ryey.easer.beta E/AndroidRuntime:     at android.view.Choreographer$FrameDisplayEventReceiver.run(Choreographer.java:1139)
        at android.os.Handler.handleCallback(Handler.java:883)
        at android.os.Handler.dispatchMessage(Handler.java:100)
        at android.os.Looper.loop(Looper.java:214)
        at android.app.ActivityThread.main(ActivityThread.java:7682)
        at java.lang.reflect.Method.invoke(Native Method)
        at com.android.internal.os.RuntimeInit$MethodAndArgsCaller.run(RuntimeInit.java:516)
        at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:950)
DennisBlock commented 4 years ago

The problem is that s1 does not have a connection to the rest of your nodes. The only algorithm that supports single nodes without a connection is the FruchtermanReingoldAlgorithm.

Future versions will have some checks and better error messages to help unterstand what went wrong.

renyuneyun commented 4 years ago

Thanks for explaining that. I wasn't aware that SugiyamaAlgorithm only works for fully-connected graphs.

Do you think it (in principle) is better for the user-side (i.e. me) to fix this by adding a virtual "root" node in my application, or should it be an option for the GraphView library to have the ability to add a virtual (and invisible) root node?

GregorBlock commented 4 years ago

Sounds good to me. We'll think about it.