Accessing vertex/edge indices

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Accessing vertex/edge indices

Helen Lampesis
Hello graphGang!

I have some relative simple (but also quiet practical) questions for you.

1. How can you access the indices of the nodes of an arbitrary graph?
        - You can not assume that they are equal to the "range(graph.num_vertices())”.  For instance, imagine that we are dealing with a filtered version of some graph.
        - Is there another way than invoking the iterator graph.vertices() ?

The application I have at hand is to sample pairs of nodes of a graph and apply a function like the shortest distance between them (and I would like to do that fast).

2. I think that when it comes to sampling/accessing of the indices of edges there is not a better way than invoking the iterator graph.edges() and work with its output. Correct?

Thanks a lot,
H.

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Accessing vertex/edge indices

Elliot

Why do you not want to use graph.vertices?

Elliot

On Aug 4, 2014 5:57 PM, "Helen Lampesis" <[hidden email]> wrote:
Hello graphGang!

I have some relative simple (but also quiet practical) questions for you.

1. How can you access the indices of the nodes of an arbitrary graph?
        - You can not assume that they are equal to the "range(graph.num_vertices())”.  For instance, imagine that we are dealing with a filtered version of some graph.
        - Is there another way than invoking the iterator graph.vertices() ?

The application I have at hand is to sample pairs of nodes of a graph and apply a function like the shortest distance between them (and I would like to do that fast).

2. I think that when it comes to sampling/accessing of the indices of edges there is not a better way than invoking the iterator graph.edges() and work with its output. Correct?

Thanks a lot,
H.

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Accessing vertex/edge indices

Elliot

With either vertices or edges, if you're going to call the iterator multiple times, I feel like it might be faster to use it once to build a list or array, and then work with indices to that.  With edges, I'd build one list of edge objects and another of tuples of source index, target index, index to the edge list, and whatever properties I need.  Graph tool is fast when it uses the c++ functions, but it's just python otherwise, and needs to be treated like python.

Be aware that numpy arrays can be super slow if misused. Masking is just a convenience,  not the fastest way for all situations.  Also,  arrays are immutable and "changing" them is very slow compared to lists.

I'm new to graphtool though, so I take my advice with a grain of salt.

On Aug 4, 2014 7:35 PM, "..." <[hidden email]> wrote:

Why do you not want to use graph.vertices?

Elliot

On Aug 4, 2014 5:57 PM, "Helen Lampesis" <[hidden email]> wrote:
Hello graphGang!

I have some relative simple (but also quiet practical) questions for you.

1. How can you access the indices of the nodes of an arbitrary graph?
        - You can not assume that they are equal to the "range(graph.num_vertices())”.  For instance, imagine that we are dealing with a filtered version of some graph.
        - Is there another way than invoking the iterator graph.vertices() ?

The application I have at hand is to sample pairs of nodes of a graph and apply a function like the shortest distance between them (and I would like to do that fast).

2. I think that when it comes to sampling/accessing of the indices of edges there is not a better way than invoking the iterator graph.edges() and work with its output. Correct?

Thanks a lot,
H.

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Accessing vertex/edge indices

Tiago Peixoto
Administrator
In reply to this post by Helen Lampesis
On 08/05/2014 12:55 AM, Helen Lampesis wrote:
 > Hello graphGang!
 >
 > I have some relative simple (but also quiet practical) questions for you.
 >
 > 1. How can you access the indices of the nodes of an arbitrary graph?
 > - You can not assume that they are equal to the "range(graph.num_vertices())”.  For instance, imagine that we are dealing with a filtered version of some graph.
 > - Is there another way than invoking the iterator graph.vertices() ?

If you are dealing with a filtered graph, the Graph.vertices iterator is
the best way.

Another option is the use the Graph.vertex(i, use_index=False), to
return the i-th vertex. However, if you use this with filtered graphs,
it takes time O(N) per call.

 > The application I have at hand is to sample pairs of nodes of a graph
 > and apply a function like the shortest distance between them (and I
 > would like to do that fast).

The simplest thing you can do is to build a list of vertices at the
beginning, and use that for the rest of the algorithm.

 > 2. I think that when it comes to sampling/accessing of the indices of
 > edges there is not a better way than invoking the iterator
 > graph.edges() and work with its output. Correct?

Yes. The edges are not stored in a single array, so they cannot be
addressed easily. But again, you can easily store the edge descriptors
in a list in the initialization of your algorithm, and address them
easily.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <tiago@skewed.de>