graph/product: add extended modular product function
diff --git a/graph/product/product.go b/graph/product/product.go
index 354b002..09f81ba 100644
--- a/graph/product/product.go
+++ b/graph/product/product.go
@@ -296,6 +296,60 @@
}
}
+// ModularExt constructs the Modular product of a and b in dst with
+// additional control over assessing edge agreement.
+//
+// In addition to the modular product conditions, agree(u₁v₁, u₂v₂) must
+// return true when (u₁~v₁ and u₂~v₂) for an edge to be added between
+// (u₁, u₂) and (v₁, v₂) in dst. If agree is nil, Modular is called.
+//
+// ModularExt is O(n^2) time where n is the order of the Cartesian product
+// of a and b.
+func ModularExt(dst graph.Builder, a, b graph.Graph, agree func(eA, eB graph.Edge) bool) {
+ if agree == nil {
+ Modular(dst, a, b)
+ return
+ }
+
+ _, _, product := cartesianNodes(a, b)
+ if len(product) == 0 {
+ return
+ }
+
+ for _, p := range product {
+ dst.AddNode(p)
+ }
+
+ _, aUndirected := a.(graph.Undirected)
+ _, bUndirected := b.(graph.Undirected)
+ _, dstUndirected := dst.(graph.Undirected)
+ undirected := aUndirected && bUndirected && dstUndirected
+
+ n := len(product)
+ if undirected {
+ n--
+ }
+ for i, u := range product[:n] {
+ var m int
+ if undirected {
+ m = i + 1
+ }
+ for _, v := range product[m:] {
+ if u.A.ID() == v.A.ID() || u.B.ID() == v.B.ID() {
+ // No self-loops.
+ continue
+ }
+ eA := a.Edge(u.A.ID(), v.A.ID())
+ eB := b.Edge(u.B.ID(), v.B.ID())
+ inA := eA != nil
+ inB := eB != nil
+ if (inA && inB && agree(eA, eB)) || (!inA && !inB) {
+ dst.SetEdge(dst.NewEdge(u, v))
+ }
+ }
+ }
+}
+
// cartesianNodes returns the Cartesian product of the nodes in a and b.
func cartesianNodes(a, b graph.Graph) (aNodes, bNodes []graph.Node, product []Node) {
aNodes = lexicalNodes(a)
diff --git a/graph/product/product_ext_example_test.go b/graph/product/product_ext_example_test.go
new file mode 100644
index 0000000..e868faa
--- /dev/null
+++ b/graph/product/product_ext_example_test.go
@@ -0,0 +1,131 @@
+// Copyright ©2019 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 product_test
+
+import (
+ "fmt"
+
+ "gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/iterator"
+ "gonum.org/v1/gonum/graph/product"
+ "gonum.org/v1/gonum/graph/simple"
+ "gonum.org/v1/gonum/graph/topo"
+)
+
+// person is a graph.Node representing a person.
+type person struct {
+ name string // name is the name of the person.
+ id int64
+}
+
+// ID satisfies the graph.Node interface.
+func (n person) ID() int64 { return n.id }
+
+func ExampleModularExt_subgraphIsomorphism() {
+ // Extended attributes of the graph can be used to refine
+ // subgraph isomorphism identification. By filtering edge
+ // agreement by weight we can identify social network
+ // motifs within a larger graph.
+ //
+ // This example extracts sources of conflict from the
+ // relationships of Julius Caesar, Mark Antony and
+ // Cleopatra.
+
+ // Make a graph describing people's relationships.
+ //
+ // Edge weight indicates love/animosity.
+ people := simple.NewDirectedGraph()
+ for _, relationship := range []simple.WeightedEdge{
+ {F: person{name: "Julius Caesar", id: 0}, T: person{name: "Cleopatra", id: 1}, W: 1},
+ {F: person{name: "Cleopatra", id: 1}, T: person{name: "Julius Caesar", id: 0}, W: 1},
+ {F: person{name: "Julius Caesar", id: 0}, T: person{name: "Cornelia", id: 3}, W: 1},
+ {F: person{name: "Cornelia", id: 3}, T: person{name: "Julius Caesar", id: 0}, W: 1},
+ {F: person{name: "Mark Antony", id: 2}, T: person{name: "Cleopatra", id: 1}, W: 1},
+ {F: person{name: "Cleopatra", id: 1}, T: person{name: "Mark Antony", id: 2}, W: 1},
+ {F: person{name: "Fulvia", id: 4}, T: person{name: "Mark Antony", id: 2}, W: 1},
+ {F: person{name: "Fulvia", id: 4}, T: person{name: "Cleopatra", id: 1}, W: -1},
+ {F: person{name: "Octavia", id: 5}, T: person{name: "Mark Antony", id: 2}, W: 1},
+ {F: person{name: "Octavia", id: 5}, T: person{name: "Cleopatra", id: 1}, W: -1},
+ } {
+ people.SetEdge(relationship)
+ }
+
+ // Make a graph for the query pattern: a love triangle.
+ pattern := simple.NewDirectedGraph()
+ for _, relationsip := range []simple.WeightedEdge{
+ {F: person{name: "A", id: -1}, T: person{name: "B", id: -2}, W: 1},
+ {F: person{name: "B", id: -2}, T: person{name: "A", id: -1}, W: 1},
+ {F: person{name: "C", id: -3}, T: person{name: "A", id: -1}, W: -1},
+ {F: person{name: "C", id: -3}, T: person{name: "B", id: -2}, W: 1},
+ } {
+ pattern.SetEdge(relationsip)
+ }
+
+ // Produce the modular product of the two graphs.
+ p := simple.NewDirectedGraph()
+ product.ModularExt(p, people, pattern, func(a, b graph.Edge) bool {
+ return a.(simple.WeightedEdge).Weight() == b.(simple.WeightedEdge).Weight()
+ })
+
+ // Find the maximal cliques in the undirected induction
+ // of the modular product.
+ mc := topo.BronKerbosch(undirected{p})
+
+ // Report the cliques that are identical in order to the pattern.
+ fmt.Println("Person — Relationship position:")
+ for _, c := range mc {
+ if len(c) != pattern.Nodes().Len() {
+ continue
+ }
+ for _, p := range c {
+ // Extract the mapping between the
+ // inputs from the product.
+ p := p.(product.Node)
+ people := p.A.(person)
+ pattern := p.B.(person)
+ fmt.Printf(" %s — %s\n", people.name, pattern.name)
+ }
+ fmt.Println()
+ }
+
+ // Unordered output:
+ // Person — Relationship position:
+ // Cleopatra — A
+ // Mark Antony — B
+ // Octavia — C
+ //
+ // Cleopatra — A
+ // Mark Antony — B
+ // Fulvia — C
+}
+
+// undirected converts a directed graph to an undirected graph
+// with edges between nodes only where directed edges exist in
+// both directions in the original graph.
+type undirected struct {
+ graph.Directed
+}
+
+func (g undirected) From(uid int64) graph.Nodes {
+ nodes := graph.NodesOf(g.Directed.From(uid))
+ for i := 0; i < len(nodes); {
+ if g.Directed.Edge(nodes[i].ID(), uid) != nil {
+ i++
+ } else {
+ nodes[i], nodes = nodes[len(nodes)-1], nodes[:len(nodes)-1]
+ }
+ }
+ return iterator.NewOrderedNodes(nodes)
+}
+func (g undirected) Edge(xid, yid int64) graph.Edge {
+ e := g.Directed.Edge(xid, yid)
+ if e != nil && g.Directed.Edge(yid, xid) != nil {
+ return e
+ }
+ return nil
+}
+func (g undirected) EdgeBetween(xid, yid int64) graph.Edge {
+ return g.Edge(xid, yid)
+}
diff --git a/graph/product/product_test.go b/graph/product/product_test.go
index 35490c9..bf24cd8 100644
--- a/graph/product/product_test.go
+++ b/graph/product/product_test.go
@@ -314,6 +314,22 @@
}
}
+func TestModularExt(t *testing.T) {
+ for _, test := range productTests {
+ got := simple.NewUndirectedGraph()
+ ModularExt(got, test.a, test.b, func(a, b graph.Edge) bool { return true })
+ gotBytes, _ := dot.Marshal(got, "", "", " ")
+
+ want := simple.NewUndirectedGraph()
+ naiveModular(want, test.a, test.b)
+ wantBytes, _ := dot.Marshal(want, "", "", " ")
+
+ if !bytes.Equal(gotBytes, wantBytes) {
+ t.Errorf("unexpected ModularExt product result for %s:\ngot:\n%s\nwant:\n%s", test.name, gotBytes, wantBytes)
+ }
+ }
+}
+
// (u₁~v₁ and u₂~v₂) or (u₁≁v₁ and u₂≁v₂).
func naiveModular(dst graph.Builder, a, b graph.Graph) {
_, _, product := cartesianNodes(a, b)
