Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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: en.wikipedia.org/wiki/Path_(graph_theory)). –  Qiaochu Yuan Jun 10 '12 at 0:16
    
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."). –  jwhitlock Jun 10 '12 at 1: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. –  jwhitlock Jun 10 '12 at 1:17
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
This page was also very useful to me: 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. –  jwhitlock Jun 10 '12 at 4:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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