[pgrouting-users] directed graphs?

[Stephen Woodbridge]

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