straph.paths package

Submodules

straph.paths.path_object module

class straph.paths.path_object.Path(times=None, links=None)

Bases: object

add_link(l, t)

check_coherence(S)

duration()

length()

plot(S, color='#18036f', markersize=10, dag=False, fig=None)

Draw a path on the StreamGraph object S

Parameters

• S –

• color –

• markersize –

• dag –

• fig –

Returns

straph.paths.paths module

straph.paths.paths.FP(S, source, destination=None, start_time=None, E=None)

straph.paths.paths.FP_W_postprocess(W)

straph.paths.paths.FP_initialisation(S, source)

straph.paths.paths.FP_postprocess(R, source, destination=None, start_time=None)

straph.paths.paths.FP_source_initialisation(L, source, t0, t1)

straph.paths.paths.FP_update(L, R, t0, t1, u, v)

Lu is sorted by the value of su and we analyze temporal links in temporal order. :param R: :param L: :param t0: :param t1: :param u: :param v: :return:

straph.paths.paths.FSP(S, source, destination=None, start_time=None, E=None)

straph.paths.paths.FSP_W_postprocess(W)

straph.paths.paths.FSP_initialisation(S, source)

straph.paths.paths.FSP_postprocess(R, source, destination=None, start_time=None)

straph.paths.paths.FSP_source_initialisation(L, source, t0, t1)

straph.paths.paths.FSP_update(L, R, t0, t1, u, v)

straph.paths.paths.FoP(S, source, destination=None, start_time=None, E=None)

If destination is specified: Return the time to reach destination from source in S. Otherwise: Return the time to reach every reachable node in S from source. :param E: :param S: Stream graph :param source: temporal source node :param destination: optional :param start_time: optional, if not specified assume that the start time is source[0] :return:

straph.paths.paths.FoP_initialisation(S, source)

‘L’ initialisation for FoP

Parameters

• S –

• source –

Returns

straph.paths.paths.FoP_postprocess(R, source, destination=None, start_time=None)

Post process elements in ‘L’ to obtain time to reach ‘ttr’

Parameters

• start_time –

• R –

• source –

• destination – optional

Returns

straph.paths.paths.FoP_postprocess_pw(W)

straph.paths.paths.FoP_source_initialisation(L, source, t0, t1)

straph.paths.paths.FoP_update(L, R, t0, t1, u, v)

We update ‘L’ according to the link (t0,t1,u,v) and FoP properties.

Parameters

• R –

• L –

• t0 –

• t1 –

• u –

• v –

Returns

straph.paths.paths.L_Algorithm(S, source, initialisation_function, update_function, source_init_function, start_time=None, is_temporal_source=False, sfp_special_case=False, E=None)

An implementation of L-Algorithm (described in ~add ref): Single Source Algorithm to compute temporal paths in Stream Graph IMPORTANT : We suppose that we are in the WCC of ‘source’ otherwise it’s fucking expensive !

Parameters

• E –

• sfp_special_case –

• is_temporal_source –

• start_time –

• source_init_function –

• update_function –

• S – A Stream Graph

• source – A temporal source node

• initialisation_function – Functions according to the path’s type (supported: - foremost path - shortest foremost path - shortest path - fastest shortest path - fastest path - shortest fastest path)

Returns

R containing the best results

straph.paths.paths.SFP(S, source, destination=None, start_time=None, E=None)

straph.paths.paths.SFP_W_postprocess(W)

straph.paths.paths.SFP_initialisation(S, source)

straph.paths.paths.SFP_postprocess(R, source, destination=None, start_time=None)

straph.paths.paths.SFP_source_initialisation(L, source, t0, t1)

straph.paths.paths.SFP_update(L, R, t0, t1, u, v)

Update L and R according to the link (t0,t1,u,v) :param L: :param R: :param t0: :param t1: :param u: :param v: :return:

straph.paths.paths.SFP_update_old(L, R, t0, t1, u, v)

Update Lv from (t0,t1,u,v) according to SFP constraints. Dans L_u pour les SFP on a : soit un seul triplet et a_u > s_u either many triplets and a_u <= s_u, they are sorted by their departure time

Parameters

• R –

• L –

• t0 –

• t1 –

• u –

• v –

Returns

straph.paths.paths.SFoP(S, source, destination=None, start_time=None, E=None)

straph.paths.paths.SFoP_W_postprocess(W)

straph.paths.paths.SFoP_initialisation(S, source)

straph.paths.paths.SFoP_postprocess(R, source, destination=None, start_time=None)

Post Process elements in ‘L’ to obtain times to reach and lengths of shortest foremost path

Parameters

• R –

• source –

• destination –

• start_time –

Returns

straph.paths.paths.SFoP_source_initialisation(L, source, t0, t1)

straph.paths.paths.SFoP_update(L, R, t0, t1, u, v)

straph.paths.paths.SP(S, source, destination=None, start_time=None, E=None)

straph.paths.paths.SP_W_postprocess(W)

straph.paths.paths.SP_initialisation(S, source)

straph.paths.paths.SP_postprocess(R, source, destination=None, start_time=None)

straph.paths.paths.SP_source_initialisation(L, source, t0, t1)

straph.paths.paths.SP_update(L, R, t0, t1, u, v)

Update Lv with the best element of Lu ! :param R: :param L: :param t0: :param t1: :param u: :param v: :return:

straph.paths.paths.bfs_update(L, R, source, batch_links, temporal_adjacency_list, update_function, sfp_special_case=False)

Proceeds to browse every links present at instant :math:’t_0’ in order to propagate the update on current possible paths

Parameters

• sfp_special_case –

• R –

• L –

• source –

• batch_links –

• temporal_adjacency_list –

• update_function –

Returns

straph.paths.paths.get_temporal_sources(S, source)

Return the maximal segmented nodes (t0,t1,u) s.t u = source.

Parameters

• S – Stream Graph

• source – source node

Returns

straph.paths.paths.plot_adjacency_list(S, a_l)

Plot the current adjacency list adj_list.

Parameters

• S – A stream graph (we get its labels)

• a_l – an adjacency list

Returns

Plot of adjacency list

straph.paths.paths.plot_stream(S, t)

Plot the stream graph and a marker for the instant t.

Parameters

• S – A stream Graph

• t – An instant

Returns

Plot of the stream graph

Module contents