from topologic import Vertex, Edge, Wire, Face, Shell, Cell, CellComplex, Cluster, Topology, Graph, VertexUtility, FaceUtility, TopologyUtility
import cppyy

# Based on https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627

def vIndex(v, vList):
    for i in range(len(vList)):
            if VertexUtility.Distance(v, vList[i]) < 0.001:
                        return i+1
    return None

def main(maxVertices):
  global graph
  global cycles
  returnValue = []
  for edge in graph:
      for node in edge:
          findNewCycles([node], maxVertices)
  for cy in cycles:
      row = []
      for node in cy:
          row.append(node)
          returnValue.append(row)
  return returnValue

def findNewCycles(path, maxVertices):
    if len(path) > maxVertices:
        return
    start_node = path[0]
    next_node= None
    sub = []
    #visit each edge and each node of each edge
    for edge in graph:
        node1, node2 = edge
        if start_node in edge:
            if node1 == start_node:
                next_node = node2
            else:
                next_node = node1
            if not visited(next_node, path):
                # neighbor node not on path yet
                sub = [next_node]
                sub.extend(path)
                # explore extended path
                findNewCycles(sub, maxVertices)
            elif len(path) > 2  and next_node == path[-1]:
                # cycle found
                p = rotate_to_smallest(path)
                inv = invert(p)
                if isNew(p) and isNew(inv):
                    cycles.append(p)

def invert(path):
    return rotate_to_smallest(path[::-1])

#  rotate cycle path such that it begins with the smallest node
def rotate_to_smallest(path):
    n = path.index(min(path))
    return path[n:]+path[:n]

def isNew(path):
    return not path in cycles

def visited(node, path):
    return node in path

topologies = cppyy.gbl.std.list[Wire.Ptr]()
fcsel = FreeCADGui.Selection.getSelection()           
for fcs in fcsel:
  fce = fcs.Shape.Edges
  clus = Topology.ByString(fce[0].exportBrepToString())
  for e in fce:
    top = Topology.ByString(e.exportBrepToString())
    clus = Topology.Merge(clus, top)

wires = cppyy.gbl.std.list[Wire.Ptr]()
_ = clus.Wires(wires)

pyWires = list(wires)
maxVertices = 17
resultWires = cppyy.gbl.std.list[Wire.Ptr]()
for pyWire in pyWires:
  pyWire.__class__ = Wire
  
  tEdges = cppyy.gbl.std.list[Edge.Ptr]()
  _ = pyWire.Edges(tEdges)
  tVertices = cppyy.gbl.std.list[Vertex.Ptr]()
  _ = pyWire.Vertices(tVertices)
  graph = []
  for anEdge in tEdges:
      graph.append([vIndex(anEdge.StartVertex(), list(tVertices)), vIndex(anEdge.EndVertex(), list(tVertices))])

  cycles = []

  resultingCycles = main(maxVertices)
  result = []
  for aRow in resultingCycles:
      row = []
      for anIndex in aRow:
          row.append(list(tVertices)[anIndex-1])
      result.append(row)

  for i in range(len(result)):
      c = result[i]
      resultEdges = cppyy.gbl.std.list[Edge.Ptr]()
      for j in range(len(c)-1):
          v1 = c[j]
          v2 = c[j+1]
          e = Edge.ByStartVertexEndVertex(v1, v2)
          resultEdges.push_back(e)
      e = Edge.ByStartVertexEndVertex(c[len(c)-1], c[0])
      resultEdges.push_back(e)
      resultWire = Wire.ByEdges(resultEdges)
      resultWires.push_back(resultWire)

resultShell = Face.ByExternalBoundary(resultWires.front())
for aWire in resultWires:
  face = Face.ByExternalBoundary(aWire)
  resultShell = Topology.Merge(face, resultShell)

sh=Part.Shape()
sh.importBrepFromString(str(resultShell.String()))
Part.show(sh)

g = Graph.ByTopology(resultShell, True, False, False, False, False, False, 0.0001)
gtop = g.Topology()
sh = Part.Shape()
sh.importBrepFromString(str(gtop.String()))
Part.show(sh)