4

I'm searching for a certain pathfinding algorithm which considers a certain sort of branch in the network. However, I find it difficult to define my search term as I do not know how this certain kind of edge is named. Have a look at the image, the red circled branch.

How to name a branch of which one of the two nodes is only single connected, in other words, one node is integrated in the network by only one connection?

Usually, in a network, most nodes are more or less 'intersections', meaning they connect two edges. However, in the image, you see that one edge 'sticks out', like a street ending in nowhere.

How to name this sort of edge?

Sorry, if the answer to this question may be to some of you very natural, I'm very new to this topic. This question relates to my other question ('Yen's or Eppstein for path with intermediate destinations with 'dead ends'?').

enter image description here

  • 2
    dangling edges/nodes would be the term I guess. can't provide any proper reference, though, but it's frequently used in graph theory. – ThingumaBob May 13 '18 at 11:35
  • 1
    Dangling node is how it would be described in ArcGIS. – PolyGeo May 13 '18 at 11:52
  • 1
    Cul de sac and pipestem come to mind. The mathematics folks might have a formal name, but I suspect this is going to fall into an opinion-based discussion. – Vince May 13 '18 at 11:54
  • Numerically is a node with single neighbor. – FelixIP May 13 '18 at 21:43
  • 1
    I generate networks from skeletonized binary images frequently, and I call them spurs. – Jon May 14 '18 at 14:37
2

I think the term 'dangling edges/nodes' is what I was looking for in my case. However the answer to this question seems to depend on the field of interest. Within ArcGIS applications such branches are named dangling nodes/ or dangling edges (for example https://desktop.arcgis.com/de/arcmap/latest/extensions/data-reviewer/finding-dangles-on-line-features.htm). However, other terms are also used, for example 'hanging edges' or 'redundant edges' (e.g. see Ying et al 2011, https://www.fig.net/resources/proceedings/2011/2011_3dcadastre/3Dcad_2011_21.pdf). As such, for the above given example there are a variety of terms possible as there is no official standard term.

  • This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review – Simbamangu May 13 '18 at 16:25
  • This was the answer to my question, that is why I wrote it down. In which way did you mean that it did not provide an anwer? – mauegraus May 14 '18 at 11:44
  • Apologies, did not read carefully enough. However, one-line answers are not encouraged here, and as one other commenter points out the question itself seems like it will lead to 'opinion based' answers. Can you provide a reference and some explanation for this answer? – Simbamangu May 14 '18 at 12:12
  • In my personal opinion you're answer is not authorative nor complete enough to be marked as solved, I would suggest marking this topic/answer as Wiki as it is an interesting question. – RJJoling May 14 '18 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.