How to create a spanning tree

Question

I have a directed graph for all kinds of available address formats in Java, which includes cycles. I want to store user Address which is a span of this graph in addition to the above template. My graph is obtained from the XML below:

<address>
    <city start="true">
        <minicity />
        <street />
        <square />
    </city>
    <minicity>
        <street />
        <alley />
        <square />
    </minicity>
    <street>
        <street />
        <alley />
        <blibd />
    </street>
    <square>
        <street />
        <alley />
        <blibd />
    </square>
    <alley final="true">
        <alley />
        <blibd />
        <plaque />
    </alley>
    <blibd final="true">
        <alley />
        <blibd />
        <plaque />
    </blibd>
    <plaque final="true">
        <stage />
        <unit />
    </plaque>
    <stage final="true">
        <unit />
    </stage>
    <unit final="true">
    </unit>
</address>

As you can see the street node of the graph has a cycle above itself. A sample of the user address would look like this:

city:a street:b street:c street:d alley:f

My question is: What is the best way to store the user's address graph? I have the above template graph and want to know whether it would be better to save the user graph within this template or outside in a different structure.

Answer 1

An adjacency matrix is a standard way of representing a graph. In your case each element of the matrix could be supplemented with the node category (city, etc).

A user's address could be derived by storing a separate reference to the inner most node of a given address and tracing outwards to the city level to construct the address.

I personally would probably opt for a more structured approach than a generic graph though, creating business objects like City, Street, etc, and therefore enforcing the structure of the address; e.g.

public interface Residence {
  int getNumber();
  Street getStreet();
}

public interface Street {
  City getCity();
}

public interface City {
  Country getAddress();
}

To display an address given a Residence I simply walk the object graph; e.g.

Residence r = ...
System.err.println(String.format("%d %s %s %s", r.getNumber(), r.getStreet(), r.getStreet().getCity(), r.getStreet().getCity().getCountry()));