Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
Some code in GT assumes matchings are sets of edges, while other code assumes a matching is a graph regular of degree one. There are also 2 versions of is_matching
All code needs to be searched for what kind of input is_matching expects.
minimum_maximal_matching_size must be checked and provoded doctests
kept this version in properties.sage:
def is_matching(g):
"""
Returns True if this graph is the disjoint union of complete graphs of order 2.
This version in utilities.sage is now commented out:
"""
def is_matching(s): #this version works for SETS of edges. another version in GT tests if a GRAPH has only degree one edges
"""
True if set of edges s is a matching, i.e. no edges share a common vertex
Ignores edges labels; only compares indices 0 and 1 in edge tuples.
"""
vertex_list = []
for e in s:
vertex_list.append(e[0])
vertex_list.append(e[1])
if len(vertex_list) != len(set(vertex_list)):
return False
else:
return True
"""
fix
"""
THIS version requires potential matchings to be SETS or LISTS of edges (non-graphs);
code in GT sometimes requires a matching to be a GRAPH (regular of degree 1)
def minimum_maximal_matching_size(g):
"""
The minimum number of edges k s.t. there exists a matching of size k which is not extendable
"""
if(g.size() == 0):
return 0
matchings_old = []
matchings = [[e] for e in g.edges()]
while True:
matchings_old = matchings
matchings = []
for matching in matchings_old:
extendable = False
for e in (edge for edge in g.edges() if edge not in matching):
possible_matching = matching + [e]
if is_matching(possible_matching):
matchings.append(possible_matching)
extendable = True
if not extendable:
return len(matching)
Some code in GT assumes matchings are sets of edges, while other code assumes a matching is a graph regular of degree one. There are also 2 versions of is_matching
All code needs to be searched for what kind of input is_matching expects.
minimum_maximal_matching_size must be checked and provoded doctests
kept this version in properties.sage:
def is_matching(g): """ Returns True if this graph is the disjoint union of complete graphs of order 2.
This version in utilities.sage is now commented out: """ def is_matching(s): #this version works for SETS of edges. another version in GT tests if a GRAPH has only degree one edges """ True if set of edges s is a matching, i.e. no edges share a common vertex
Ignores edges labels; only compares indices 0 and 1 in edge tuples. """ vertex_list = [] for e in s: vertex_list.append(e[0]) vertex_list.append(e[1]) if len(vertex_list) != len(set(vertex_list)): return False else: return True """
fix """ THIS version requires potential matchings to be SETS or LISTS of edges (non-graphs); code in GT sometimes requires a matching to be a GRAPH (regular of degree 1)
def minimum_maximal_matching_size(g): """ The minimum number of edges k s.t. there exists a matching of size k which is not extendable """ if(g.size() == 0): return 0
add_to_lists(minimum_maximal_matching_size, intractable_invariants, all_invariants) """