Problems using the dijktstra search

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

Problems using the dijktstra search

josubg
Hi all.

I'm trying to use the dijktstra search But I have a exception.The property that is used a int32_t and the GraphViews aren't empty. Any clue of  what is my error?

This is the code:

        referents_graph = GraphView(graph, vfilt= lambda v: graph.vertex_properties["type"][v]=="referent")
        navigable_graph = GraphView(graph, reversed=True)

        referents = referents_graph.vertices()
        weight = navigable_graph.edge_properties["weight"]

        for base_referent in referents:
            # Calculate the distance of all accessible referents
            distances, predecessors =  graph_tool.search.dijkstra_search(navigable_graph,base_referent,weight)

This is the trace:

  File "/data/workspace/stanford-corenlp-python/contextgenerator.py", line 218, in resolve_corefenrence
    distances, predecessors =  graph_tool.search.dijkstra_search(navigable_graph,base_referent,weight)
  File "/usr/local/lib/python2.7/dist-packages/graph_tool/decorators.pyc", line 2, in dijkstra_search
    Bq�Oc
  File "/usr/local/lib/python2.7/dist-packages/graph_tool/search/__init__.py", line 126, in wrap
    ret = func(*args, **kwargs)
  File "/usr/local/lib/python2.7/dist-packages/graph_tool/search/__init__.py", line 841, in dijkstra_search
    compare, combine, zero, infinity)
  TypeError: No registered converter was able to produce a C++ rvalue of type int from this Python object of type float


Thanks for the time.
Reply | Threaded
Open this post in threaded view
|

Re: Problems using the dijktstra search

Tiago Peixoto
Administrator
On 07/12/2012 01:14 PM, josubg wrote:

> Hi all.
>
> I'm trying to use the dijktstra search But I have a exception.The property
> that is used a int32_t and the GraphViews aren't empty. Any clue of  what is
> my error?
>
> This is the code:
>
>         referents_graph = GraphView(graph, vfilt= lambda v:
> graph.vertex_properties["type"][v]=="referent")
>         navigable_graph = GraphView(graph, reversed=True)
>
>         referents = referents_graph.vertices()
>         weight = navigable_graph.edge_properties["weight"]
>
>         for base_referent in referents:
>             # Calculate the distance of all accessible referents
>             distances, predecessors =
> graph_tool.search.dijkstra_search(navigable_graph,base_referent,weight)
This has been fixed now in git... As a workaround, you can also do the following:

     dijkstra_search(navigable_graph,base_referent,weight, infinity=1000000)

Where the infinity value is a suitably large number.

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>




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

signature.asc (566 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Problems using the dijktstra search

josubg
Thanks a lot!

I can get the correct distances normal nodes  but I'm getting distances for not reachable nodes. These distances are high compared with the others distances (cost 140 against a mean cost of 5) but nothing that can be programmatic filtered (like a constant inf value or negative value). If I put infinity=-1 all distances changes to -1 (also the reachable nodes). If is use a big infinity like 100000, the unreachable nodes get this distance.

Is this the expected result of the function? 

On Thu, Jul 12, 2012 at 6:52 PM, Tiago de Paula Peixoto <[hidden email]> wrote:
On 07/12/2012 01:14 PM, josubg wrote:
> Hi all.
>
> I'm trying to use the dijktstra search But I have a exception.The property
> that is used a int32_t and the GraphViews aren't empty. Any clue of  what is
> my error?
>
> This is the code:
>
>         referents_graph = GraphView(graph, vfilt= lambda v:
> graph.vertex_properties["type"][v]=="referent")
>         navigable_graph = GraphView(graph, reversed=True)
>
>         referents = referents_graph.vertices()
>         weight = navigable_graph.edge_properties["weight"]
>
>         for base_referent in referents:
>             # Calculate the distance of all accessible referents
>             distances, predecessors =
> graph_tool.search.dijkstra_search(navigable_graph,base_referent,weight)

This has been fixed now in git... As a workaround, you can also do the following:

     dijkstra_search(navigable_graph,base_referent,weight, infinity=1000000)

Where the infinity value is a suitably large number.

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>




_______________________________________________
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: Problems using the dijktstra search

Tiago Peixoto
Administrator
On 07/16/2012 12:39 PM, Nasgar wrote:
> Thanks a lot!
>
> I can get the correct distances normal nodes  but I'm getting distances for not reachable nodes. These distances are high compared with the others distances (cost 140 against a mean cost of 5) but nothing that can be programmatic filtered (like a constant inf value or negative value). If I put infinity=-1 all distances changes to -1 (also the reachable nodes). If is use a big infinity like 100000, the unreachable nodes get this distance.
>
> Is this the expected result of the function?

Yes, vertices which are unreached have a distance of "infinity". If this
is not given by the user, it is computed to be max(weight) * (N + 1),
since it is larger than any possible distance. If the user wants to
filter out these vertices, this value can be used, or the user himself
can specify the infinity value. If the user specifies the value, it
needs to be large enough, otherwise there will be problems, as you
noticed when setting it to -1.

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>




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

signature.asc (566 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Problems using the dijktstra search

josubg
Thanks.

On Mon, Jul 16, 2012 at 2:09 PM, Tiago de Paula Peixoto <[hidden email]> wrote:
On 07/16/2012 12:39 PM, Nasgar wrote:
> Thanks a lot!
>
> I can get the correct distances normal nodes  but I'm getting distances for not reachable nodes. These distances are high compared with the others distances (cost 140 against a mean cost of 5) but nothing that can be programmatic filtered (like a constant inf value or negative value). If I put infinity=-1 all distances changes to -1 (also the reachable nodes). If is use a big infinity like 100000, the unreachable nodes get this distance.
>
> Is this the expected result of the function?

Yes, vertices which are unreached have a distance of "infinity". If this
is not given by the user, it is computed to be max(weight) * (N + 1),
since it is larger than any possible distance. If the user wants to
filter out these vertices, this value can be used, or the user himself
can specify the infinity value. If the user specifies the value, it
needs to be large enough, otherwise there will be problems, as you
noticed when setting it to -1.

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>




_______________________________________________
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