[pgrouting-users] directed graphs?

[Anton Patrushev]

Hi Steve,

> OK, this explains it much better. So I have a network of streets that are
> mostly bi-directional. I use assign_vertex_id() to build the topology and I
> can treat this as totally bi-directional and use a cost value.

Yep.

> I can add a reverse_cost column to this table can populate it with the cost
> values, then fixup the one_way streets by making the wrong direction of the
> street a HIGH cost and then use this as a directed graph with reverse costs.

Yep. If you have any information about one way streets, you can
restore the directions by introducing reverse_cost.

> I do not have truely directed graph data unless I was to say modify
> assign_vertex_id() to be smarter about interpreting my data via its
> attributes and building a directed graph topology in say another table.

This is not quite clear for me. What are you going to do? Do you want
to split edges to make separate edge for each direction?
If not, you don't need to change the topology function, because node
ids have nothing to do with direction if you keep the original number
of edges.

> So, when I call any of the shortest path functions, IF I want to use the
> reverse cost, then I need to set the directed=true AND has_reverse_cost=true
> AND include the reverse_cost column. Is this true?

Exactly!

> Conversely, specifying has_reverse_cost=true AND directed=false does
> nothing?

Let's see. If graph is undirected, cost value is used for both
directions, which means that reverse_cost value makes no sense.

Anton.

On Mon, Aug 18, 2008 at 10:53 PM, Stephen Woodbridge
<woodbri at swoodbridge.com> wrote:
> Anton Patrushev wrote:
>>
>> It depends on your original data.
>>
>> Graphs can be undirected, directed or directed with reverse cost.
>> In undirected graph cost value is used for both directions (from
>> source to target and from target to source).
>> In directed graph cost value is used for one direction (from source to
>> target), reverse direction is prohibited.
>> In directed graph with reverse cost reverse_cost value is used for
>> reverse direction (from target to source) and cost value is used for
>> normal direction (from source to target).
>
> OK, this explains it much better. So I have a network of streets that are
> mostly bi-directional. I use assign_vertex_id() to build the topology and I
> can treat this as totally bi-directional and use a cost value.
>
> I can add a reverse_cost column to this table can populate it with the cost
> values, then fixup the one_way streets by making the wrong direction of the
> street a HIGH cost and then use this as a directed graph with reverse costs.
>
> I do not have truely directed graph data unless I was to say modify
> assign_vertex_id() to be smarter about interpreting my data via its
> attributes and building a directed graph topology in say another table.
>
> So, when I call any of the shortest path functions, IF I want to use the
> reverse cost, then I need to set the directed=true AND has_reverse_cost=true
> AND include the reverse_cost column. Is this true?
>
> Conversely, specifying has_reverse_cost=true AND directed=false does
> nothing?
>
> Thanks,
>  -Steve
>
>> assign_vertex_id() doesn't change the original data. It just builds a
>> topology - assigns unique ids to unique nodes.
>>
>> I don't know what kind of data you have. If it doesn't have any
>> reverse cost and it represents a road network there can be two
>> possibilities: it is undirected; or it is directed and has one
>> separate edges for both directions.
>>
>> Anton.
>>
>> On Mon, Aug 18, 2008 at 1:26 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com> wrote:
>>>
>>> How should the directed boolean be used?
>>>
>>> For example does function assign_vertex_id() build a directed or
>>> undirected graph?
>>>
>>> Does using a reverse_cost column imply a directed graph?
>>>
>>> I assume that if I use assign_vertex_id() to build my graphs, which
>>> appears to build undirected graphs, that I will set directed to false
>>> and that this option would only be used if I wrote my own function the
>>> specifically build directed graph.
>>>
>>> -Steve
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.postlbs.org
>>> http://lists.postlbs.org/mailman/listinfo/pgrouting-users
>>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.postlbs.org
>> http://lists.postlbs.org/mailman/listinfo/pgrouting-users
>
>