Revision history [back]

It seems to be not fully implemented in Sage and would be hard in general.

The first thing to do is to compute the intersection matrix of your collection as in the following code (I named S the collection).

sage: S = [Set([0, 1, 3, 7]),
...        Set([0, 5, 4, 6]),
...        Set([0, 8, 4, 7]),
...        Set([0, 8, 5, 9]),
...        Set([8, 5, 4, 2]),
...        Set([2, 3, 5, 6]),
...        Set([3, 6, 7, 8])]
sage: n = len(S)
sage: m = matrix(n)
sage: for i in xrange(n):
...      for j in xrange(n):
...          m[i,j] = S[i].intersection(S[j]).cardinality()

Let consider the graph G associated to the matrix (see wikipedia graph theory) where I put labels on edges instead of multiedges.

sage: G = Graph(loops=True)
sage: for i in xrange(n):
...      for j in xrange(i+1):
...         G.add_edge(i,j,m[i,j])

Now, what you're looking for is a subgraph H (your intersection conditions) of your graph G. The question would be equivalent to a variation of the subgraph isomorphism problem and the induced subgraph isomorphism problem. The variation comes from the fact that your graphs G and H have some integer label on edges (or multiplicity of edges) and you are looking for a copy of H in G as labeled graphs... In any case, such a problem is NP-complete in general, meaning that a fast algorithm would be impossible to design. Depending on your intersection conditions (in your question H is just a cyclic graph) it may be better.

There is a brute force way to do subgraph search in Sage with subgraph_search but it does not handle your case. It is possible to modify slightly the code of subgraph_search in order to make it work in your case... (the only thing to do is to implement a new condition that checks for labels and set the attribute is_admissible of sage.graphs.generic_graph_pyx.SubgraphSearch to it). It would be nice to have it in Sage!

It seems to be not fully implemented in Sage and would be hard in general.

The first thing to do is to compute the intersection matrix of your collection as in the following code (I named S the collection).

sage: S = [Set([0, 1, 3, 7]),
...        Set([0, 5, 4, 6]),
...        Set([0, 8, 4, 7]),
...        Set([0, 8, 5, 9]),
...        Set([8, 5, 4, 2]),
...        Set([2, 3, 5, 6]),
...        Set([3, 6, 7, 8])]
sage: n = len(S)
sage: m = matrix(n)
sage: for i in xrange(n):
...      for j in xrange(n):
...          m[i,j] = S[i].intersection(S[j]).cardinality()

Let consider the graph G associated to the matrix (see wikipedia graph theory) where I put labels on edges instead of multiedges.

sage: G = Graph(loops=True)
Graph()
sage: for i in xrange(n):
...      for j in xrange(i+1):
xrange(i):
...         G.add_edge(i,j,m[i,j])

Now, what you're looking for is a subgraph H (your intersection conditions) of your graph G. The question would be equivalent to a variation of the subgraph isomorphism problem and the induced subgraph isomorphism problem. The variation comes from the fact that your graphs G and H have some integer label on edges (or multiplicity of edges) and you are looking for a copy of H in G as labeled graphs... In any case, such a problem is NP-complete in general, meaning that a fast algorithm would be impossible to design. Depending on your intersection conditions (in your question H is just a cyclic graph) it may be better.

There is a brute force way to do subgraph search in Sage with subgraph_search but it does not handle your case. It is possible to modify slightly the code of subgraph_search in order to make it work in your case... (the only thing to do is to implement a new condition I created a ticket for that checks for labels and set the attribute is_admissible of sage.graphs.generic_graph_pyx.SubgraphSearch to it). It would trac #13280 hoping it will be nice to have it in Sage!

sage: H = Graph()
sage: H.add_edge(1,2,2)
sage: H.add_edge(1,3,1)
sage: H.add_edge(2,3,2)
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch
sage: X = SubgraphSearch(G, H, edge_labels=True)
sage: for x in X: print x
[0, 2, 1]
[0, 2 ,3]
...
[6, 5, 4]

sage: S[0].intersection(S[2]).cardinality()
2
sage: S[0].intersection(S[1]).cardinality()
1
sage: S[2].intersection(S[1]).cardinality()
2

It seems to be not fully implemented in Sage and would be hard in general.

The first thing to do is to compute the intersection matrix of your collection as in the following code (I named S the collection).

sage: S = [Set([0, 1, 3, 7]),
...        Set([0, 5, 4, 6]),
...        Set([0, 8, 4, 7]),
...        Set([0, 8, 5, 9]),
...        Set([8, 5, 4, 2]),
...        Set([2, 3, 5, 6]),
...        Set([3, 6, 7, 8])]
sage: n = len(S)
sage: m = matrix(n)
sage: for i in xrange(n):
...      for j in xrange(n):
...          m[i,j] = S[i].intersection(S[j]).cardinality()

Let consider the graph G associated to the matrix (see wikipedia graph theory) where I put labels on edges instead of multiedges.

sage: G = Graph()
sage: for i in xrange(n):
...      for j in xrange(i):
...         G.add_edge(i,j,m[i,j])

Now, what you're looking for is a subgraph H (your intersection conditions) of your graph G. The question would be equivalent to a variation of the subgraph isomorphism problem and the induced subgraph isomorphism problem. The variation comes from the fact that your graphs G and H have some integer label on edges (or multiplicity of edges) and you are looking for a copy of H in G as labeled graphs... In any case, such a problem is NP-complete in general, meaning that a fast algorithm would be impossible to design. Depending on your intersection conditions (in your question H is just a cyclic graph) it may be better.

There is a brute force way to do subgraph search in Sage with subgraph_search but it does not handle your case. It is possible to modify slightly the code of subgraph_search in order to make it work in your case... I created a ticket for that trac #13280 hoping it will be available in the next release of Sage ;-)

With the patch applied, I get the following answer

sage: H = Graph()
sage: H.add_edge(1,2,2)
sage: H.add_edge(1,3,1)
sage: H.add_edge(2,3,2)
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch
sage: X = SubgraphSearch(G, H, edge_labels=True)
sage: for x in X: for s in G.search_subgraph_iterator(H, edge_labels=True):
....:     print x
s
[0, 2, 1]
[0, 2 ,3]
...
[6, 5, 4]

Then you can check that all those sub collections are answer to the question. As an example, I consider the first solution [0,2,1]

sage: S[0].intersection(S[2]).cardinality()
2
sage: S[0].intersection(S[1]).cardinality()
1
sage: S[2].intersection(S[1]).cardinality()
2