blob: b361d0e3fd35ee47248c2a262daa77216ec18638 [file] [log] [blame]
 // Copyright ©2015 The Gonum Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package graph // Undirect converts a directed graph to an undirected graph. type Undirect struct { G Directed } var _ Undirected = Undirect{} // Node returns the node with the given ID if it exists in the graph, // and nil otherwise. func (g Undirect) Node(id int64) Node { return g.G.Node(id) } // Nodes returns all the nodes in the graph. func (g Undirect) Nodes() Nodes { return g.G.Nodes() } // From returns all nodes in g that can be reached directly from u. func (g Undirect) From(uid int64) Nodes { if g.G.Node(uid) == nil { return Empty } return newNodeIteratorPair(g.G.From(uid), g.G.To(uid)) } // HasEdgeBetween returns whether an edge exists between nodes x and y. func (g Undirect) HasEdgeBetween(xid, yid int64) bool { return g.G.HasEdgeBetween(xid, yid) } // Edge returns the edge from u to v if such an edge exists and nil otherwise. // The node v must be directly reachable from u as defined by the From method. // If an edge exists, the Edge returned is an EdgePair. The weight of // the edge is determined by applying the Merge func to the weights of the // edges between u and v. func (g Undirect) Edge(uid, vid int64) Edge { return g.EdgeBetween(uid, vid) } // EdgeBetween returns the edge between nodes x and y. If an edge exists, the // Edge returned is an EdgePair. The weight of the edge is determined by // applying the Merge func to the weights of edges between x and y. func (g Undirect) EdgeBetween(xid, yid int64) Edge { fe := g.G.Edge(xid, yid) re := g.G.Edge(yid, xid) if fe == nil && re == nil { return nil } return EdgePair{fe, re} } // UndirectWeighted converts a directed weighted graph to an undirected weighted graph, // resolving edge weight conflicts. type UndirectWeighted struct { G WeightedDirected // Absent is the value used to // represent absent edge weights // passed to Merge if the reverse // edge is present. Absent float64 // Merge defines how discordant edge // weights in G are resolved. A merge // is performed if at least one edge // exists between the nodes being // considered. The edges corresponding // to the two weights are also passed, // in the same order. // The order of weight parameters // passed to Merge is not defined, so // the function should be commutative. // If Merge is nil, the arithmetic // mean is used to merge weights. Merge func(x, y float64, xe, ye Edge) float64 } var ( _ Undirected = UndirectWeighted{} _ WeightedUndirected = UndirectWeighted{} ) // Node returns the node with the given ID if it exists in the graph, // and nil otherwise. func (g UndirectWeighted) Node(id int64) Node { return g.G.Node(id) } // Nodes returns all the nodes in the graph. func (g UndirectWeighted) Nodes() Nodes { return g.G.Nodes() } // From returns all nodes in g that can be reached directly from u. func (g UndirectWeighted) From(uid int64) Nodes { if g.G.Node(uid) == nil { return Empty } return newNodeIteratorPair(g.G.From(uid), g.G.To(uid)) } // HasEdgeBetween returns whether an edge exists between nodes x and y. func (g UndirectWeighted) HasEdgeBetween(xid, yid int64) bool { return g.G.HasEdgeBetween(xid, yid) } // Edge returns the edge from u to v if such an edge exists and nil otherwise. // The node v must be directly reachable from u as defined by the From method. // If an edge exists, the Edge returned is an EdgePair. The weight of // the edge is determined by applying the Merge func to the weights of the // edges between u and v. func (g UndirectWeighted) Edge(uid, vid int64) Edge { return g.WeightedEdgeBetween(uid, vid) } // WeightedEdge returns the weighted edge from u to v if such an edge exists and nil otherwise. // The node v must be directly reachable from u as defined by the From method. // If an edge exists, the Edge returned is an EdgePair. The weight of // the edge is determined by applying the Merge func to the weights of the // edges between u and v. func (g UndirectWeighted) WeightedEdge(uid, vid int64) WeightedEdge { return g.WeightedEdgeBetween(uid, vid) } // EdgeBetween returns the edge between nodes x and y. If an edge exists, the // Edge returned is an EdgePair. The weight of the edge is determined by // applying the Merge func to the weights of edges between x and y. func (g UndirectWeighted) EdgeBetween(xid, yid int64) Edge { return g.WeightedEdgeBetween(xid, yid) } // WeightedEdgeBetween returns the weighted edge between nodes x and y. If an edge exists, the // Edge returned is an EdgePair. The weight of the edge is determined by // applying the Merge func to the weights of edges between x and y. func (g UndirectWeighted) WeightedEdgeBetween(xid, yid int64) WeightedEdge { fe := g.G.Edge(xid, yid) re := g.G.Edge(yid, xid) if fe == nil && re == nil { return nil } f, ok := g.G.Weight(xid, yid) if !ok { f = g.Absent } r, ok := g.G.Weight(yid, xid) if !ok { r = g.Absent } var w float64 if g.Merge == nil { w = (f + r) / 2 } else { w = g.Merge(f, r, fe, re) } return WeightedEdgePair{EdgePair: [2]Edge{fe, re}, W: w} } // Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge. // If x and y are the same node the internal node weight is returned. If there is no joining // edge between the two nodes the weight value returned is zero. Weight returns true if an edge // exists between x and y or if x and y have the same ID, false otherwise. func (g UndirectWeighted) Weight(xid, yid int64) (w float64, ok bool) { fe := g.G.Edge(xid, yid) re := g.G.Edge(yid, xid) f, fOk := g.G.Weight(xid, yid) if !fOk { f = g.Absent } r, rOK := g.G.Weight(yid, xid) if !rOK { r = g.Absent } ok = fOk || rOK if g.Merge == nil { return (f + r) / 2, ok } return g.Merge(f, r, fe, re), ok } // EdgePair is an opposed pair of directed edges. type EdgePair [2]Edge // From returns the from node of the first non-nil edge, or nil. func (e EdgePair) From() Node { if e[0] != nil { return e[0].From() } else if e[1] != nil { return e[1].From() } return nil } // To returns the to node of the first non-nil edge, or nil. func (e EdgePair) To() Node { if e[0] != nil { return e[0].To() } else if e[1] != nil { return e[1].To() } return nil } // ReversedEdge returns a new Edge with the end point of the // edges in the pair swapped. func (e EdgePair) ReversedEdge() Edge { if e[0] != nil { e[0] = e[0].ReversedEdge() } if e[1] != nil { e[1] = e[1].ReversedEdge() } return e } // WeightedEdgePair is an opposed pair of directed edges. type WeightedEdgePair struct { EdgePair W float64 } // ReversedEdge returns a new Edge with the end point of the // edges in the pair swapped. func (e WeightedEdgePair) ReversedEdge() Edge { e.EdgePair = e.EdgePair.ReversedEdge().(EdgePair) return e } // Weight returns the merged edge weights of the two edges. func (e WeightedEdgePair) Weight() float64 { return e.W } // nodeIteratorPair combines two Nodes to produce a single stream of // unique nodes. type nodeIteratorPair struct { a, b Nodes curr Node idx, cnt int // unique indicates the node in b with the key ID is unique. unique map[int64]bool } func newNodeIteratorPair(a, b Nodes) *nodeIteratorPair { n := nodeIteratorPair{a: a, b: b, unique: make(map[int64]bool)} for n.b.Next() { n.unique[n.b.Node().ID()] = true n.cnt++ } n.b.Reset() for n.a.Next() { if _, ok := n.unique[n.a.Node().ID()]; !ok { n.cnt++ } n.unique[n.a.Node().ID()] = false } n.a.Reset() return &n } func (n *nodeIteratorPair) Len() int { return n.cnt - n.idx } func (n *nodeIteratorPair) Next() bool { if n.a.Next() { n.idx++ n.curr = n.a.Node() return true } for n.b.Next() { if n.unique[n.b.Node().ID()] { n.idx++ n.curr = n.b.Node() return true } } n.curr = nil return false } func (n *nodeIteratorPair) Node() Node { return n.curr } func (n *nodeIteratorPair) Reset() { n.idx = 0 n.curr = nil n.a.Reset() n.b.Reset() }