1
$\begingroup$

I have a dataset of pairs of map coordinates, and I suspect that they could be connected to make a path. However, I'm not sure what the end points are, or if the coordinates actually make a path. I'm using the python networkx library, but it assumes you know a bit of graph theory to know what functions to use.

If I have a non-directed graph that looks like a path (a-b, b-c, c-d, ... y-z), how does graph theory describe the graph? What does it call the 'endpoints' 'a' and 'z'?

  • 1
    This isn't a question about graph theory, it's a question about the networkx library (so I don't really think it's appropriate here). There's no guarantee that answers here will be relevant to the networkx library. Is there documentation you could refer to? (But anyway, in graph theory a path is called a path: http://en.wikipedia.org/wiki/Path_(graph_theory)).2012-06-10
  • 0
    I gave the full background of my problem because I know almost no graph theory, and I hoped a fuller explanation of my problem would help overcome any lack of vocabulary in the problem domain. networkx provides excellent documentation, but it is written as if you've studied graph theory ("The periphery is the set of nodes with eccentricity equal to the diameter.").2012-06-10
  • 1
    Knowing the proper terminology will be a huge help in finding the right part of the documentation. Your wikipedia link was very helpful. If you answer with "The path is called a foo path, the endpoints are nodes with attribute bar of value X", maybe with some links, then I'll call it the accepted answer.2012-06-10

1 Answers 1

1

I took a look at the documentation. networkx calls a path a path. It calls a the source and z the target of the path. See

http://networkx.lanl.gov/reference/algorithms.shortest_paths.html

or maybe just

http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.generic.has_path.html

depending on what exactly you want to do.

  • 0
    This page was also very useful to me: http://en.wikipedia.org/wiki/Glossary_of_graph_theory. The number of edges connecting a node is the degree, and the 'endpoint' nodes have a degree of 1 and are called leafs. A simple path visits each node just once, and a Hamiltonian is a path that visits each node on the graph.2012-06-10