[feature] adding a mixed graph model

[kkdd]

Hello, I hope gonum would also support mixed (multi)graphs, which have the mixture of directed and undirected edges. I think it is mathematically universal, and it adapts OpenStreetMap data well, for example.

Is this feature absent from the current master?

Yes.

[kortschak]

A graph with directed and undirected edges can be represented using a directed graph. Is there are reason you cannot do this?

[kkdd]

Do you mean that each undirected edge can be converted to two directed ones with opposite directions? I would like to calculate the three quantities of inward, outward, and undirected degrees for each vertex based on a mixed graph model.

[kortschak]

Do you mean that each undirected edge can be converted to two directed ones with opposite directions?

Yes.

I would like to calculate the three quantities of inward, outward, and undirected degrees for each vertex based on a mixed graph model.

That is doable with the current implementation with a little extra work. Iterate over the results of g.From(u) and g.To(u), the result of the first is out, the result of the second is in, and the intersection of the two is inout.

[kkdd]

I'm afraid that conversion isn't invertible. Two edges with opposite directions residing in a directed graph, or (u, v) and (v, u), can't always revert to the status before conversion without additional information.

[kortschak]

If that's the case, tag the edge with a user graph.Edge type. What you want to do is implementable in client code. Adding a third type of graph for this would be a large amount of work for something that can already be achieved.

type bidirected struct {
    f, t     graph.Node
    reverse *bidirected
    // any other data you want to hold …
}

func (e *bidirected) From()         graph.Node { return e.f }
func (e *bidirected) To()           graph.Node { return e.t }
func (e *bidirected) ReversedEdge() graph.Edge { return e.reversed }

func addBidirectedTo(g graph.EdgeAdder, e graph.Edge) {
    bIn := bidirected{f: e.From(), t: e.To()}
    bOut := bidirected{t: e.From(), t: f.To()}
    bIn.reverse = &bOut
    bOut.reverse = &bIn
    g.Set(g, &bIn)
    g.Set(g, &bOut)
}

Obviously, this would be better if the bidirected was just given to the helper, but this adequately links the two directions.

[kkdd]

Thank you for your advice. I agree that adding the third type is not worth the effort.

I'm afraid this place is no more appropriate, but it isn't so easy to emulate undirected edges by representing as the twins of converted directed edges, as follows:

When considering the transformation of the undirected edges from the former status to the latter status, as described in smoothing of degree-2 vertices in wikipedia, such vertices aren't seem to be easily identified after above conversion.

[kortschak]

I can't see why not.

[kkdd]

Consider the mixed graph of [○ー○ー○↔︎○], which has four vertices, and would be smoothed to that of [○ー○↔︎○], which has three vertices.

If you would try to emulate the above by means of the conversion from undirected to directed edges, the both converted graphs, [○↔︎○↔︎○↔︎○] and [○↔︎○↔︎○], are no more homeomorphic, meaning the failure of emulation.

[kortschak]

If you use the edge type I have above (or something similar), you can distinguish between undirected edges and directed edges in the graph by virtue of the type (undirected are that type and directed are just a simple edge). We are not going to add a mixed graph.