Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
def IsCyclic(self):
"""
IsCyclic() returns True if the graph is cyclic (and connected).
(An exception is raised on disconnected graphs.)
This function quits early as soon as a cycle is found.
"""
self.Reset()
if (type(self.g) is Ugraph):
is_cyclic = self._IsCyclicUgraph(0, Dgraph.NULL)
else:
is_cyclic = self._IsCyclic(0)
if ((self.sv != self.g.nv) and (not is_cyclic)):
raise(Disconnected(self.g, "Error(IsCyclic): "+
"The input graph is not connected."))
return is_cyclic
def FindEdge(self, istart, istop):
"""
A simple function looks up the edge id number
corresponding to an edge connecting vertex istart to istop.
If not present returns Dgraph.NULL.
"""
iv = istart
for je in self.neighbors[iv]:
jv = self.edges[je].stop
if jv == istop:
return je
return Dgraph.NULL
def IsCyclic(self):
"""
IsCyclic() returns True if the graph is cyclic (and connected).
(An exception is raised on disconnected graphs.)
This function quits early as soon as a cycle is found.
"""
self.Reset()
if (type(self.g) is Ugraph):
is_cyclic = self._IsCyclicUgraph(0, Dgraph.NULL)
else:
is_cyclic = self._IsCyclic(0)
if ((self.sv != self.g.nv) and (not is_cyclic)):
raise(Disconnected(self.g, "Error(IsCyclic): " +
"The input graph is not connected."))
return is_cyclic
def Reset(self):
self.sv = 0
self.se = 0
for iv in range(0, self.g.nv):
self.vvisited[iv] = False
self.vorder[iv] = Dgraph.NULL
for ie in range(0, self.g.ne):
self.evisited[ie] = False
self.eorder[ie] = Dgraph.NULL
def FindEdge(self, istart, istop):
"""
A simple function looks up the edge id number
corresponding to an edge connecting vertex istart to istop.
If not present returns Dgraph.NULL.
"""
iv = istart
for je in self.neighbors[iv]:
jv = self.edges[je].stop
if jv == istop:
return je
return Dgraph.NULL
# AND vertex Jv with jv
self.ie_to_Ie[self.se] = Je
self.se += 1
self.eoccupiedG[Je] = True
self.iv_to_Iv[self.sv] = Jv
self.sv += 1
self.voccupiedG[Jv] = True
# Then continue the recursion
for match in self.Match():
yield match
self.voccupiedG[Jv] = False
self.sv -= 1
self.iv_to_Iv[self.sv] = Dgraph.NULL
self.eoccupiedG[Je] = False
self.se -= 1
self.ie_to_Ie[self.se] = Dgraph.NULL
assert(not self.eoccupiedG[Je])
# Match both edge Je with je
# AND vertex Jv with jv
self.ie_to_Ie[self.se] = Je
self.se += 1
self.eoccupiedG[Je] = True
self.iv_to_Iv[self.sv] = Jv
self.sv += 1
self.voccupiedG[Jv] = True
# Then continue the recursion
for match in self.Match():
yield match
self.voccupiedG[Jv] = False
self.sv -= 1
self.iv_to_Iv[self.sv] = Dgraph.NULL
self.eoccupiedG[Je] = False
self.se -= 1
self.ie_to_Ie[self.se] = Dgraph.NULL
def Reset(self):
self.sv = 0
self.se = 0
for iv in range(0, self.g.nv):
self.vvisited[iv] = False
self.vorder[iv] = Dgraph.NULL
for ie in range(0, self.g.ne):
self.evisited[ie] = False
self.eorder[ie] = Dgraph.NULL