Fancy Metro Maps Documentation

app.py

The core module of Fancy Metro Maps. Runs on a Flask Web Server and loads JSON files containing information about Metro Maps in Graph format. Forwards Metro Map information to the front-end and generates octilinear graph layouts for metro maps to also forward to the front-end. Communication with the front-end is done via the JSON file format. The algorithms implemented follow those explained in the paper.

class app.Edge(featureData)

The Edge class represents Line Connections loaded from JSON as Python objects. Note: Since one edge represents one connection of one train line between two stations, there may be multiple edges between two stations.

__init__(featureData)

Initializes a new edge object.

Parameters:

featureData – An object that contains IDs for station_from and station_to, as well as an array for the colors of lines running on that edge and and array for the labels of lines running

on that edge.

__str__()

ToString method for edges.

Returns:

IDs for station_from and station_to this edge connects.

line_color

Array of colors for the lines running on this edge.

line_count()

Returns the number of lines running on this edge.

Returns:

Number of lines on this edge in integer format.

line_label

Array of labels for the lines running on this edge

station_from

The station this edge starts at.

station_to

The station this edge ends at.

station_tuple()

Returns the tuple of stations this edge connects.

Returns:

Tuple of station IDs in string format.

class app.Encoder(*, skipkeys=False, ensure_ascii=True, check_circular=True, allow_nan=True, sort_keys=False, indent=None, separators=None, default=None)

The Encoder class is used to convert NX Graph data to JSON.

default(o)

Used to encode NX Graphs to JSON.

class app.Station(featureData)

The Station class represents Stations loaded from JSON as Python objects.

SWITCH_POINT_COUNTER = 0

Amount of switch points in the metro map

__init__(featureData)

Initializes a new Station Object.

Parameters:

featureData – An object that contains coordinates (lat, lng) and the ID (usually hex, but any format permissible) of the station. Note: If the ID in featureData is empty, it is a switch

point. Therefore we initialize it with label “Switch Point<X>”, with X being the switch point counter for identification.

__str__()

ToString function for station objects. Returns the station label.

Returns:

station_label in String format.

coord_x

The x-coordinate of the station.

coord_y

The y-coordinate of the station.

id

The ID of the station.

pos_tuple()

Returns a tuple for the coordinates of the station object . :return: tuple of coord_x and coord_y

app.aux_path_to_octi_path(aux_path)

Converts the given path in the auxiliary graph to a path in the octilinear graph.

Parameters:

aux_path – List of path edges in the auxiliary graph.

Returns:

Tuple: (list of path edges, list of path nodes).

app.auxiliary_graph(G: Graph)

Generates the auxiliary graph for an octilinear graph. For more information on the auxiliar graph, check out the paper.

Parameters:

G – The octilinear graph the auxiliary graph should be generated for as an NX Graph object.

Returns:

Auxiliary graph as an NX Graph object.

app.chebyshev_dist(n, m)

Calculates the Chebyshev distance between two nodes of the octilinear graph.

Parameters:

  • n – Node n.

  • m – Node m.

Returns:

The Chebyshev distance between node n and m.

app.close_bend_and_sink_edges_on_path(path_nodes, A)

Sets the edge costs of sink- and bend-edges belonging to nodes on the given path to infinity.

Parameters:

  • path_nodes – List of path nodes in the octilinear graph.

  • A – The auxiliary graph to modify.

Returns:

The modified auxiliary graph.

app.close_diagonals_through_path(auxiliary_path, A)

Sets the edge costs of diagonals to infinity if they cross the given path.

Parameters:

  • auxiliary_path – The path on graph A.

  • A – The auxiliary graph to modify.

Returns:

The modified auxiliary graph.

app.flip_edge(e)

Flips an edge’s orientation.

Parameters:

e – The edge to flip as an NX Edge object.

Returns:

The nodes of the edge in reversed order.

app.generate_metro_graph(city, grid_resolution)

Generates Metro Map in Octilinear graph format. Performs three attempts and saves the result in Shared_Graph_Success. If no layout is found, the result is stored in Shared_Graph and still forwarded to the Front-End.

Parameters:

  • city – String for the city the graph should be built for.

  • grid_resolution – Resolution the octilinear grid should have.

app.get_angular_edge_ordering(metro_map, node)

Orders the edges incident to a given node based on their clockwise angle to the up-vector.

Parameters:

  • metro_map – The input graph.

  • node – A node of the input graph.

Returns:

An ordered list of the incident edges to the node.

app.get_aux_node_id(aux_node)

Returns a value in range [0,7] corresponding to the direction in which the octilinear graph edge points, where 0 is straight up. The numbers 1 through 7 are distributed from 0 in a clockwise fashion. :param aux_node: Node on the auxiliary graph to calculate the orientation for. :return: Orientation represented as an integer in range [0,7]

app.get_auxiliary_bend_angle(edge) → int

Returns the angle (in degrees) that an edge bend moving over the given edge would make. The returned angle is rounded to an integer.

Parameters:

edge – the auxiliary edge to find the bend angle of.

Returns:

the angle.

app.get_bend_edge_cost(edge)

Determines and returns the default cost of a given bend edge.

Parameters:

edge – the edge to get the cost of.

Returns:

the ascertained edge cost.

app.get_candidates_and_make_temp_aux_changes(edge, grid_node_dict, A, G, M)

Finds node candidates for the start/end node of the edge that needs to be routed. Also opens up previously closed edges on the auxiliary graph, that now need to be revisited. Since these changes to the auxiliary graph are temporary, all edits are logged in the dictionary a_change_dict, so they can be reversed after the edge has been routed.

Parameters:

  • edge –

  • grid_node_dict –

  • A – The auxiliary graph.

  • G – The octilinear graph.

  • M – The input graph.

Returns:

Tuple: (start node info, end node info, the modified auxiliary graph , the change dictionary for the auxiliary graph)

app.get_clockwise_dist(edge1, edge2, edge_ordering)

Determines the clockwise distance of two edges (edge1 and edge2) connecting to the same node, which is defined by the number of edges, that connect to the node in the clockwise angle spanned by the edges + 1.

Parameters:

  • edge1 – The first edge.

  • edge2 – The second edge.

  • edge_ordering – An edge list sorted in clockwise order.

Returns:

The clockwise distance between edge1 and edge2.

app.get_closest_node(octi_node, node_1, node_2)

returns the closest of two nodes (of the input graph) to a node of the octilinear graph.

Parameters:

  • octi_node – octilinear grid graph node.

  • node_1 – node 1 of the input graph.

  • node_2 – node 2 of the input graph.

Returns:

node_2 if node_2 is closer to octi_node than node_1; node_1 otherwise.

app.get_counter_clockwise_dist(edge1, edge2, edge_ordering)

Determines the counter-clockwise distance of two edges (edge1 and edge2) connecting to the same node, which is defined by the number of edges, that connect to the node in the counter-clockwise angle spanned by the edges + 1.

Parameters:

  • edge1 – The first edge.

  • edge2 – The second edge.

  • edge_ordering – An edge list sorted in clockwise order.

Returns:

The counter-clockwise distance between edge1 and edge2.

app.get_cw_angle(v1, v2)

Calculates the clockwise angle between vectors v1 and v2.

Parameters:

  • v1 – Vector v1.

  • v2 – Vector v2.

Returns:

Clockwise angle between v1 and v2 in radians.

app.get_data_graph(city, precalculated, grid_resolution=50)

Forwards the processed map for the required city in octilinear layout to the Front-End.

Parameters:

  • city – City to return in string format.

  • precalculated – Whether to use a precalculated layout or perform live calculation. String holding “true” or “false”.

  • grid_resolution – Resolution the octilinear grid should have.

Returns:

JSON file with graph data.

app.get_data_map(city)

Forwards the unprocessed graph for the required city to the Front-End.

Parameters:

city – City to return in string format.

Returns:

JSON file with graph data.

app.get_external_edge_cost(edge)

Returns the default cost of an external edge in the auxiliary graph.

Parameters:

edge – the edge.

Returns:

the default edge cost.

app.get_ldeg(G, v)

Computes the line degree (ldeg) of a station. For more information on the line degree, check out the paper.

Parameters:

  • G – Octilinear Graph in NX Graph format.

  • v – Node of G for which the ldeg should be computed.

Returns:

ldeg in integer format

app.get_map_edge_angle(edge_dir)

Calculates the clockwise angle of an edge of the input graph relative to the up-vector.

Parameters:

edge_dir – Vector pointing in the direction that the edge faces.

Returns:

The clockwise angle of the edge to the up-vector in radians.

app.get_map_extents(map_graph)

Calculates the bounds of the given graph and returns them.

Parameters:

map_graph – graph with geo-spatial node positions.

Returns:

nested array of length 2: [[y min, y max],[x min, x max]].

app.get_other_node(edge, node)

For any edge and node passed, returns the other node of that edge.

Parameters:

  • edge – The edge for which you want to get the other node as an NX Edge object.

  • node – The node you already have for this edge as an NX Node object.

Returns:

The other node of the edge passed as a parameter as an NX Node object.

app.get_shortest_astar_path_to_set(start_node, target_nodes, A, min_cheapest_path_cost)

Determines the cheapest path on auxiliary graph A between start_node and target_node. Discards paths that are more expensive than min_cheapest_path_cost. We use this function in a loop to find the shortest set-set distance. If another iteration has already found a cheaper path, we ignore it due to the parameter min_cheapest_path_cost.

Parameters:

  • start_node – Octilinear Graph node.

  • target_nodes – Set of octilinear Graph nodes.

  • A – The auxiliary Graph.

  • min_cheapest_path_cost – Paths more expensive than this will be ignored.

Returns:

Tuple: (list of octi graph path edges, list of octi graph path nodes, list of aux graph path edges, path cost).

app.get_sink_edge_cost(edge)

Returns the default cost of a sink edge.

Parameters:

edge – the edge.

Returns:

the default edge cost.

app.in_range(edge_apos, min_cw, min_ccw, cw_clearance, ccw_clearance)

Checks if the angular position of a sink edge is within the range of other fixed edges and outside the clearance of yet unfixed edges.

Parameters:

  • edge_apos – The angular position of the edge in question (integer in range [0,7], 0 correlates to directly up; the rest increases clockwise)

  • min_cw – Range minimum clockwise value.

  • min_ccw – Range minimum counter-clockwise value.

  • cw_clearance – Edge clearance in clockwise direction.

  • ccw_clearance – Edge clearance in counter-clockwise direction.

Returns:

app.index()

Index is called when you enter the landing page of the Flask server. It simply returns the index.html file located in /static/.

Returns:

Flask rendered Web Page for /static/index.html

app.is_closed(node, A)

Checks whether all sink edges are closed and returns the result.

Parameters:

  • node – The node for which to check the sink edge status.

  • A – The auxiliary graph to check the sink edge status on.

Returns:

True if all sink edges are closed, else False. Boolean value.

app.load_data(filename)

Loads a JSON file that specifies a city’s metro map from disk and converts it into an NX Graph of Station and Edge objects.

Parameters:

filename – The name of the file to be loaded without the filetype extension in string format.

Returns:

NX Graph for the required city.

app.make_permanent_aux_changes(A, path_info)

Makes permanent changes to the auxiliary graph after a new edge has been routed. Specifically, it closes bend- and sink-edges of the nodes of the new path; and it closes diagonals crossing the path.

Parameters:

  • A – The auxiliary graph which is to be modified.

  • path_info – Dictionary containing information about the routed path.

Returns:

The modified auxiliary graph.

app.modify_target_sink_edge_costs(A_, input_node, candidate_nodes, a_change_dict)

Adjusts the sink-edge cost of all given candidate_nodes based on their distance to the input_node. The greater the distance the higher the cost. Since these changes are temporary all edits are logged in the dictionary a_change_dict, so they can be reversed after the edge has been routed.

Parameters:

  • A – The auxiliary graph to be modified.

  • input_node – A node from the input graph.

  • candidate_nodes – A set of nodes from the octilinear graph.

  • a_change_dict – A dictionary of the changes made to graph A_.

Returns:

Tuple: (modified auxiliary graph, modified change dictionary).

app.octi_node_in_mm_node_raidus(octi_node, mm_node)

Checks if the given node (in the octilinear graph) is within the given input nodes search radius.

Parameters:

  • octi_node – The node in the octilinear graph.

  • mm_node – The node in the input graph.

Returns:

True if the octi_node is contained in the search radius of mm_node.

app.octilinear_graph(x1, y1, x2, y2, node_dist)

Generates an octilinear NX Graph with the required settings.

Parameters:

  • x1 – X position where the graph starts.

  • y1 – Y position where the graph starts.

  • x2 – X position where the graph ends.

  • y2 – Y position where the graph ends.

  • node_dist – Distance between each two nodes in x- or y-direction on the octilinear graph.

Returns:

Octilinear graph as an NX Graph object.

app.open_sink_edges(A_, G, metro_map, octi_node, input_node, input_edge, a_change_dict)

Resets costs of sink edges connected to the given octi_node, if they have previously been set to infinity. This function is used on start/end nodes of line drawings if a new line needs to connect to the station. Therefore costs are only reset, if the sink-edge in question satisfies the angular edge ordering requirements. Also, a cumulative bend-score to all already existing is lines added to the cost. Since these changes to the auxiliary graph are temporary, all edits are logged in the dictionary a_change_dict, so they can be reversed after the edge has been routed.

Parameters:

  • A – The auxiliary graph.

  • G – The octilinear graph.

  • metro_map – The input graph.

  • octi_node – A node in the octilinear graph. The cost of it’s sink edges in the auxiliary graph will be adjusted.

  • input_node – The corresponding input graph node to the octi_node.

  • input_edge – The edge of the input graph, that is supposed to be added this edge routing iteration.

  • a_change_dict – A dictionary of the changes made to graph A_.

Returns:

Tuple: (modified auxiliary graph, modified change dictionary).

app.order_input_edges(G)

Performs the ordering of the input edges on the octilinear graph. Input edges are any edges that exist in the metro map of the city we want to compute this for. For more information on the algorithm used, check out the paper.

Parameters:

G – The octilinear graph for which you want to compute the edge ordering as an NX Graph object.

Returns:

List of edges in correct ordering. Edges are NX Edge objects.

app.read_angular_ordering(edge, edge_ordering)

Finds the id of a given edge within a given edge ordering.

Parameters:

  • edge – The given edge.

  • edge_ordering – The given edge ordering.

Returns:

The id of the edge within the edge ordering.

app.route_edge(n0, n1, A, G, M, grid_node_dict, edge)

Routes a single edge using the auxiliary graph A.

Parameters:

  • n0 – Information about the start node (from the input graph) and its candidates (from the octilinear graph).

  • n1 – Information about the end node (from the input graph) and its candidates (from the octilinear graph)

  • A – The auxiliary graph used to find the edge routing.

  • G – The octilinear graph to draw the found route onto.

  • M – The input graph.

  • grid_node_dict – A dictionary containing the positions of all fixed stations on the octilinear grid.

  • edge – The edge to be routed.

Returns:

Tuple: (operation successful: boolean , the modified octilinear graph, the modified grid_node_dict, information about the routed path)

app.route_edges(edges, G, M)

this function finds a valid grid drawing for a given input graph based on a given edge ordering

Parameters:

  • edges – ordered edge list from the input graph

  • G – the octilinear graph to be modified

  • M – the input graph with geo coordinates

Returns:

a modified version of G, the edges used for the drawing now have a ‘line’ property while the stations have a ‘stationInfo’ property and are marked with ‘isStation’ = true

app.squared_octi_node_to_mm_node_distance(octi_node, mm_node)

Calculates the squared distance between a node in the octilinear graph, and a node in the input graph.

Parameters:

  • octi_node – The node in the octilinear graph.

  • mm_node – The node in the input graph.

Returns:

Squared distance.

app.undo_temporary_aux_changes(A, a_change_dict)

Reverts previously made temporary changes to the auxiliary graph A.

Parameters:

  • A – The auxiliary graph to clean up.

  • a_change_dict – A dictionary containing all changes that need to be undone.

Returns:

The auxiliary graph with all temporary changes undone.

Indices and tables