Weighted undirected graph for mapping system in python

Question

I want to know how can i implement a weighted undirected graph in python for map. Map have cities and some road, which link between citiies and have respective weight.

A dedicated graph library could be a good choice here, such as discussed here: https://stackoverflow.com/questions/606516/python-graph-library. It also depends what you need to do with the graph afterwards. — Dr. V, Jun 07 '20 at 15:55
Does this answer your question? [Python Graph Library](https://stackoverflow.com/questions/606516/python-graph-library) — Amitai Irron, Jun 07 '20 at 16:24

score 1 · Accepted Answer · answered Jun 07 '20 at 16:26

If you don't want to just use one of the available graph libraries…

A standard way of representing graphs is an adjacency list. You can implement this as a dictionary where the keys are node names (or some other ID to lookup nodes) and the values are a list of edges. The edges can be some data structure that gives you the connecting node name and a weight — anything from a tuple to a NamedTuple to a full edge class. For example here is a minimal weighted graph:

places = {
    'A': set([('B', 10), ('C', 5)]),
    'B': set([('D', 3), ('A', 10)]),
    'C': set([('F', 20), ('G', 9), ('A', 5)]),
    'D': set([('B', 3)]),
    'F': set([('C', 20)]),
    'G': set([('C', 9)])
}

You can tell it's undirected because each edge appears twice — in the source and the destination node's list.

This format will support the primary graph algorithms like DFS, BFS, Dijkstra...

Here's a quick and dirty depth first search:

places = {
    'A': set([('B', 10), ('C', 5)]),
    'B': set([('D', 3), ('A', 10)]),
    'C': set([('F', 20), ('G', 9), ('A', 5)]),
    'D': set([('B', 3)]),
    'F': set([('C', 20)]),
    'G': set([('C', 9)])
}


def findARoute(start, end, places, visited = None):
    if visited is None:
        visited  = set()

    visited.add(start)

    try:
        edges = places[start]
    except KeyError:
        return # node not in graph

    for edge in edges:
        node, wieght = edge

        if node not in visited:
            print(f'Trying {start} -> {node}')
            if node == end:
                print(f'Found: {end}')
                return
            findARoute(node, end, places, visited)

findARoute('A', 'G', places)

Prints:

Trying A -> B
Trying B -> D
Trying A -> C
Trying C -> F
Trying C -> G
Found: G

Weighted undirected graph for mapping system in python

1 Answers1