data-structuresformatspanning-tree

Data format to represent spanning tree/graph theory network

So in the same way this hierarchy Hierarchical relationship chart

Can be represented by this XML

<plants>
    <flowers>
        <annuals />
        <perennials />
    </flowers>
    <trees>
        <conifers />
        <deciduous />
    </trees>
</plants>

Is there a data format (same category as XML, JSON, CSV, etc) that can represent a spanning tree (or a network of points with edges/bridges in graph theory) like this one: Spanning tree diagram So that programmatically it can be read, parsed, and manipulated (ultimately for the purposes of testing algorithms on them) just as XML and the others can be?

Solution

  • Graph data structure. Have a look at their adjacency matrix and adjacency list implementation.

    Adjacency matrix

    You create an N x N 2-dimensional array and assign graph[i][j] = 1 if there is an edge between ith and jth nodes otherwise graph[i][j] = 0. Also graph[i][j] = graph[j][i] if your graph is undirected.

    Adjacency list

    You create N lists, one for each node and append into them all the nodes (mostly their indices) that have an edge with the corresponding node

    In case of weighted graph, you should store the weight value directly in the adjacency matrix, in case of adjacency list, you can append a pair of two integers in the list