IsomorphicDoc < FST

---+ Isomorphic 

---++ Description

This operation determines if two transducers with a [[IsomorphicDoc#IsomorphicCaveats][certain required determinism]] have the same states, irrespective of numbering, and the same transitions with the same labels and weights, irrespective of ordering. In other words, =Isomorphic(A, B)=  is true if and only if the states of A can be renumbered and the transitions leaving each state reordered so that [[EqualDoc][Equal(A, B)]] is true.

---++ Usage

| <verbatim>
template <class Arc>
bool Isomorphic(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                double delta = kDelta);
</verbatim> | 
fstisomorphic a.fst b.fst
</verbatim> |

---++ Examples

| ==A== | ==B== | ==C==|
| %ATTACHURL%/iso1.png |  %ATTACHURL%/iso2.png |  %ATTACHURL%/iso3.png | 

<verbatim>
Isomorphic(A, B);  // returns true
Isomorphic(A, C);  // returns false

$ if fstisomorphic a.fst b.fst; then echo true; else echo false; fi
true
$ if fstisomorphic a.fst c.fst; then echo true; else echo false; fi
false
</verbatim>



---++ Complexity

=Isomorphic=
   * Time: O(_V<sub>1</sub>_ + _V<sub>2</sub>_ + _E<sub>1</sub> log D<sub>1</sub>_ + _E<sub>2</sub>  log D<sub>2</sub>_)
   * Space:  O(_V<sub>1</sub>_ + _V<sub>2</sub>_  + _D<sub>1</sub>_ + _D<sub>2</sub>_)
where  _V<sub>i</sub>_ = # of states, _E<sub>i</sub>_ = # of transitions,  _D<sub>i</sub>_ = maximum [[FstGlossary#OutDegreeDef][out-degree]]

#IsomorphicCaveats
---++ Caveats

The inputs should be deterministic in the sense that no state has two transitions with the same input label, output label and weight (e.g., deterministic after [[EncodeDecodeDoc][Encode]] is performed on the labels and weights). If non-determinism in this sense is encountered, an error is raised.
This requirement is imposed since the general solution is _graph isomorphism complete_, for which no known polynomial-time algorithm exists.

---++ See Also

[[EqualDoc][Equal]], [[EquivalentDoc][Equivalent]], [[RandEquivalentDoc][RandEquivalent]]


---++ References

Zemlyachenko, Viktor N., Nickolay M. Korneenko, and Regina I. Tyshkevich. "Graph isomorphism problem." Journal of Soviet Mathematics 29.4 (1985): 1426-1481.

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who
png	iso1.png	r1	manage	9.4 K	2014-04-23 - 00:26	MichaelRiley
png	iso2.png	r1	manage	9.5 K	2014-04-23 - 00:26	MichaelRiley
png	iso3.png	r1	manage	11.4 K	2014-04-23 - 00:26	MichaelRiley

This topic: FST > WebHome > FstQuickTour > IsomorphicDoc
Topic revision: r6 - 2018-04-27 - MichaelRiley