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
    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